CF1805E.There Should Be a Lot of Maximums
普及/提高-
通过率:0%
AC君温馨提醒
该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
You are given a tree (a connected graph without cycles). Each vertex of the tree contains an integer. Let's define the 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 MAD=0 .
Note that if you remove an edge from the tree, it splits into two trees. Let's compute the 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.
输入格式
The first line contains one integer n ( 2≤n≤105 ) — the number of vertices in the tree.
Each of the next n−1 lines contains two integers u and v ( 1≤u,v≤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 a1,a2,…,an ( 1≤ai≤109 ) — the numbers in the vertices.
输出格式
For each edge in the input order, print one number — the maximum of the MAD parameters of the two trees obtained after removing the given edge from the initial tree.
输入输出样例
输入#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
说明/提示
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 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↔4 is not removed, then one of the subtrees will have two 1 , so the answer — 1 . And if edge 1↔4 is deleted, both subtrees have no repeating values, so the answer is 0 .