给你一棵树(没有循环的连通图)。树的每个顶点都包含一个整数。我们将树的 $$$\mathrm{MAD}$$$ (最大双精度)参数定义为树的顶点中至少出现 $$$2$$$ 次的最大整数。如果树中没有数字出现超过一次,则我们假设 $$$\mathrm{MAD}=0$$$。
请注意,如果从树中删除一条边,它会分裂成两棵树。让我们计算两棵树的 $$$\mathrm{MAD}$$$ 参数并取两个值中的最大值。令结果为删除边的值。
对于每条边,找到其值。请注意,我们实际上并没有从树中删除任何边,这些值是独立找到的。
输入
第一行包含一个整数 $$$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$$$) — 顶点中的数字。
输出
对于输入顺序中的每条边,打印一个数字 - 从初始树中删除给定边后获得的两棵树的 $$$\mathrm{MAD}$$$ 参数的最大值。
示例
输入 #1
5 1 2 2 3 2 4 1 5 2 1 3 2 1
输出 #1
0 2 1 2
输入 #2
6 1 2 1 3 1 4 4 5 4 6 1 2 3 1 4 5
输出 #2
1 1 0 1 1
注意
在第一个示例中,删除边 $$$(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$$$。