该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

有一棵 $n$ 个结点的以 $1$ 号结点为根的有根树。

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

你的任务是对于每一个 $i\in[1,n]$，求出以 $i$ 为根的子树中，不同颜色数目。

输入格式

第一行一个整数 $n$ $(1 \le n \le 2 \times 10^{5} )$ 。

下来 $n$ 个整数 $c_{i}$ $( 1 \le c_{i} \le n )$, $c_{i}$ 表示每个节点的颜色。

下来 $n-1$ 行，每行两个整数 $x , y$ $( 1 \le x,y \le n ,x \ne y )$，表示一条无向边。

输出格式

输出 $n$ 个整数，输出以 $i$ $(i\in[1,n])$ 为根的子树中，不同颜色数目。

输入输出样例

输入 #1

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

输出 #1

3 2 1 1 1