思路与证明

对每个结点 $u$ 维护两个量：

$down[u]$ ：从 $u$ 向下走，到达其子树内某个红点的最大距离；若子树内不存在红点，设为负无穷（实现时用常数 $-\text{INF}$ 代表，例如 $-10^9$ ）。
$ans[u]$ ：以 $u$ 为根的子树内红点直径的答案。

P3748.第3题-红点直径

1000ms

Difficulty: 6

所属公司 : 科大讯飞

算法与标签>树

给定一棵以节点 $1$ 为根的树，树上共有 $n$ 个节点，其中某些节点被标记为“红点”。

定义某点 $u$ 的红点直径为：在 $u$ 的子树中，任取两个红点之间的最大距离（路径上经过的边数）。

如果子树中的红点数 $<2$ ，则红点直径为 $0$ 。

请计算每个节点的红点直径。

第一行输入整数 $n(1≤n≤2×10^5)$ ，表示树的节点数。

第二行输入 $n$ 个整数，其中 $c_1,c_2,...c_n$ ，其中 $c_i∈0,1$ 表示红点， $0$ 表示非红点。

接下来 $n-1$ 行，每行输入两个整数 $u,v$ ，表示树上的一条无向边。

输出一行 $n$ 个整数，第 $i$ 个数表示以节点 $i$ 为根的子树的红点直径。

输入

输出

3 0 0 1 0

输入

预期输出（选填）