CF600E Lomsat gelral

题目描述

给定一棵以 $1$ 号顶点为根的树，每个顶点最开始都被涂上了一种颜色。

对于某个顶点 $v$，考虑以 $v$ 为根的子树。若一种颜色在这个子树中出现的次数达到最大值，则称这种颜色在该子树中占重要地位。一个子树中可能有多种颜色同时占重要地位。

对于每个顶点 $v$，请计算在以 $v$ 为根的子树中，所有占重要地位的颜色编号之和。

输入格式

第一行一个整数 $n$，表示顶点数。

第二行 $n$ 个整数 $c_1,c_2,\ldots,c_n$，表示每个顶点的颜色。

接下来 $n-1$ 行，每行两个整数 $x,y$，表示树中的一条无向边。树以 $1$ 为根。

输出格式

输出一行 $n$ 个整数，第 $i$ 个整数表示顶点 $i$ 的答案。

样例

样例输入

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

样例输出

5 3 2 3 3

数据范围与约定

$1\le n\le 10^5$，$1\le c_i\le 10^5$。