CF1805E.There Should Be a Lot of Maximums

You are given a tree (a connected graph without cycles). Each vertex of the tree contains an integer. Let's define the $\mathrm{MAD}$ (maximum double) parameter of the tree as the maximum integer that occurs in the vertices of the tree at least $2$ times. If no number occurs in the tree more than once, then we assume $\mathrm{MAD}=0$.

Note that if you remove an edge from the tree, it splits into two trees. Let's compute the $\mathrm{MAD}$ parameters of the two trees and take the maximum of the two values. Let the result be the value of the deleted edge.

For each edge, find its value. Note that we don't actually delete any edges from the tree, the values are to be found independently.

给你一棵树（即一个无环的连通图）。树的每个顶点上有一个整数。我们定义该树的 $\mathrm{MAD}$（最大重复值）参数为：在树的所有顶点中至少出现两次的最大整数。若树中所有整数均至多出现一次，则定义 $\mathrm{MAD} = 0$。

注意：若从树中删除一条边，树将分裂成两棵子树。我们分别计算这两棵子树的 $\mathrm{MAD}$ 参数，并取二者中的较大值。该较大值即为被删边的“值”。

对树中的每一条边，求出其对应的“值”。注意：我们并不实际从树中删除任何边，所有边的值均需独立计算。

The first line contains one integer $n$ ($2 \le n \le 10^5$) — the number of vertices in the tree.

Each of the next $n - 1$ lines contains two integers $u$ and $v$ ($1 \le u, v \le n$) — the ends of an edge of the tree. It's guaranteed that the given edges form a valid tree.

The last line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le 10^9$) — the numbers in the vertices.

第一行包含一个整数 $n$（$2 \le n \le 10^5$）—— 树中顶点的数量。

接下来的 $n - 1$ 行每行包含两个整数 $u$ 和 $v$（$1 \le u, v \le n$）—— 树的一条边的两个端点。保证所给的边构成一棵合法的树。

最后一行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \le a_i \le 10^9$）—— 各顶点上的数值。

For each edge in the input order, print one number — the maximum of the $\mathrm{MAD}$ parameters of the two trees obtained after removing the given edge from the initial tree.

对于输入中每条边，输出一个数字——即从初始树中移除该边后所得的两棵树各自的 $\mathrm{MAD}$ 参数的最大值。

In the first example, after removing edge $(1, 2)$ no number repeats $2$ times in any of the resulting subtrees, so the answer is $\max(0, 0)=0$.

After removing edge $(2, 3)$, in the bigger subtree, $1$ is repeated twice, and $2$ is repeated twice, so the $\mathrm{MAD}$ of this tree is $2$.

After removing edge $(2, 4)$, in the bigger subtree, only the number $1$ is repeated, and in the second subtree, only one number appears, so the answer is $1$.

In the second example, if edge $1 \leftrightarrow 4$ is not removed, then one of the subtrees will have two $1$, so the answer — $1$. And if edge $1 \leftrightarrow 4$ is deleted, both subtrees have no repeating values, so the answer is $0$.

在第一个样例中，删除边 $(1, 2)$ 后，任意一个生成的子树中均无数字出现恰好 $2$ 次，因此答案为 $\max(0, 0)=0$。

删除边 $(2, 3)$ 后，在较大的子树中，数字 $1$ 出现了两次，数字 $2$ 也出现了两次，因此该子树的 $\mathrm{MAD}$ 为 $2$。

删除边 $(2, 4)$ 后，在较大的子树中仅有数字 $1$ 出现重复；而在另一个子树中，仅有一个数字出现，因此答案为 $1$。

在第二个样例中，若不删除边 $1 \leftrightarrow 4$，则其中一个子树将包含两个 $1$，因此答案为 $1$；而若删除边 $1 \leftrightarrow 4$，则两个子树中均无重复数值，因此答案为 $0$。