对于一颗大小为 , 根为 的有根树上的每个非叶子结点, 输出其子树中最多颜色的节点的编号的和
You are given a rooted tree with root in vertex . Each vertex is coloured in some colour.
Let's call colour dominating in the subtree of vertex if there are no other colours that appear in the subtree of vertex more times than colour . So it's possible that two or more colours will be dominating in the subtree of some vertex.
The subtree of vertex is the vertex and all other vertices that contains vertex in each path to the root.
For each vertex find the sum of all dominating colours in the subtree of vertex .
The first line contains integer — the number of vertices in the tree.
The second line contains integers , — the colour of the -th vertex.
Each of the next lines contains two integers — the edge of the tree. The first vertex is the root of the tree.
Print n integers — the sums of dominating colours for each vertex.
10 9 3 4
6 5 4 3 2 3 3 1 1 3 2 2 1 2 3
DSU on tree (树上启发式合并)板子题, 当然也可以使用线段树合并的方法
首先进行树链剖分, 先统计轻节点的答案, 再统计重节点的答案, 合并即可, 这里要注意消除影响