题目描述

给定一棵 $n$ 个点的树，点编号 $1\sim n$，规定 $1$ 号点为根。每个点被涂上了一种颜色，第 $i$ 个点的颜色是 $c_i$。

对于每个点 $u$，请求出以 $u$ 为根的子树中出现了多少种不同的颜色。

输入格式

第一行一个整数 $n$。

第二行 $n$ 个整数 $c_1,c_2,\dots,c_n$，相邻两个整数之间用一个空格隔开。

接下来 $n-1$ 行，每行两个整数 $u$ 和 $v$，表示树上的一条边。

输出格式

一行 $n$ 个整数，第 $u$ 个数表示以 $u$ 为根的子树中不同颜色的种数，相邻两个整数之间用一个空格隔开。

输入输出样例 #1

输入 #1

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

输出 #1

2 2 1 2 1

说明

数据规模：$1\le n\le 2\times 10^5$，$1\le c_i\le n$。