题目描述

给你一棵节点个数为 n，根节点为 1 的有根树，每个点有一种颜色用一个整数 \(c_i\) 表示，问你以 u (1 \(\leq\) u \(\leq\) n) 节点为根的子树中出现颜色最多的颜色的和，如果有多种颜色数相同，一起加入统计。

输入格式

第一行一个整数 n，表示节点个数。
第二行 n 个整数 \(c_i\)，表示第 i 个节点的颜色 \(c_i\)。
接下来 n - 1 行两个整数 \(x_i\), \(y_i\)，表示 \(x_i\) 到 \(y_i\) 有边。

输出格式

输出 n 个整数，从以 1 到 n 为根节点的子树中，颜色出现最多的颜色的和。

样例1

输入

4
1 2 3 4
1 2
2 3
2 4

输出

10 9 3 4

样例2

输入

15
1 2 3 1 2 3 3 1 1 3 2 2 1 2 3
1 2
1 3
1 4
1 14
1 15
2 5
2 6
2 7
3 8
3 9
3 10
4 11
4 12
4 13

输出

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

数据范围

对于 30%的数据， 1 \(\leq\) n \(\leq\) 100，1 \(\leq\) \(c_i\) \(\leq\) n；
对于 100%的数据， 1 \(\leq\) n \(\leq\) \(10^5\) ，1 \(\leq\) \(c_i\) \(\leq\) n， 1 \(\leq\) \(x_j\), \(y_j\) \(\leq\) n

限制

2s

来源

Codeforces600E
CWOI新高二专题测试十⑨