J9 习题-7 树上数颜色2

题目描述

有一棵 $n$ 个结点的以 $1$ 号结点为根的有根树。每个结点都有一个颜色，颜色是以编号表示的， $i$ 号结点的颜色编号为 $c_i$。

如果一种颜色在以 $x$ 为根的子树内出现次数最多，称其在以 $x$ 为根的子树中占主导地位。显然，同一子树中可能有多种颜色占主导地位。

你的任务是对于每一个 $i\in[1,n]$，求出以 $i$ 为根的子树中，占主导地位的颜色的编号和。

输入格式

第一行一个整数 $n$，表示树的结点数；

接下来一行 $n$ 个数，表示每个结点的颜色 $c[i]$；

接下来 $n-1$ 行，每行一条边；

输出格式

一行 $n$ 个数，以 $i$ 为根的子树中，占主导地位的颜色的编号和。

样例输入

4
1 2 3 4
1 2
2 3
2 4

样例输出

10 9 3 4

样例分析

如上所述。

数据范围

对于 $100\%$ 的数据：$1\leq m,c[i]\leq n\leq 10000$。