← 返回题目列表

Codeforces · 1805/E

E. 应该有很多最大值

中文机器翻译题面 查看原题

给你一棵树(没有循环的连通图)。树的每个顶点都包含一个整数。我们将树的 $$$\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$$$。