洛谷 CF600E · 难度 省选/NOI−

题目描述

给你一棵以结点 $1$ 为根的有根树，每个节点最开始都被涂上了颜色。

如果颜色 $c$ 在以结点 $v$ 为根的子树中出现次数最多，则称其在以结点 $v$ 为根的子树中占重要地位。一棵树中可以有很多颜色同时占重要地位。

以 $v$ 为根的子树指结点 $v$ 及其他到根结点的路径包含 $v$ 的结点。

请输出对于每一个结点 $v$，在其子树中占重要地位的颜色编号之和。

输入格式

第一行包含一个整数 $n$，表示树的结点个数。

第二行包含 $n$ 个整数 $c_i$，表示每个结点的颜色。

接下来 $n-1$ 行，每行包含两个整数 $x_j$ 和 $y_j$，表示每条边。结点 $1$ 是树的根。

输出格式

输出一行 $n$ 个整数，表示对于每个节点，在以其为根的子树中占重要地位的颜色编号之和。

说明/提示

数据范围

对于所有数据，$1\le n\le {10}^5$，$1\le c_i\le 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