思路与证明

1）核心定义

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

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

2）子问题合并

题目内容

给定一棵以节点$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$ 为根的子树的红点直径。

样例1

输入

5
0 1 0 1 1
1 2
1 3
1 4
4 5

输出

3 0 0 1 0