There Should Be a Lot of Maximums

Description:

Input:

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.

Output:

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.

Sample Input:

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

Sample Output:

0
2
1
2

Sample Input:

6
1 2
1 3
1 4
4 5
4 6
1 2 3 1 4 5

Sample Output:

1
1
0
1
1

Note:

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$$$.