题目描述

$1$ から $N$ までの番号がつけられた $N$ 個の頂点を持つ木があります。この木の $i$ 番目の辺は頂点 $a_i$ と $b_i$ を結んでいます。 また、各頂点には色が塗られており、 頂点 $i$ に塗られている色は $c_i$ です。ここで、各頂点に塗られている色は $1$ 以上 $N$ 以下の整数で表されており、同じ整数は同じ色に、異なる整数は異なる色に対応します。

$k=1,2,...,N$ に対して、以下の問題を解いてください。

• 色 $k$ が塗られている頂点を一度以上通るような単純パスの数を求めよ

補足: 頂点 $u$ から頂点 $v$ へ向かう単純パスと、頂点 $v$ から頂点 $u$ へ向かう単純パスは区別しません。

输入格式

入力は以下の形式で標準入力から与えられる。

$N$ $c_1$ $c_2$ $...$ $c_N$ $a_1$ $b_1$ $:$ $a_{N-1}$ $b_{N-1}$

输出格式

$k=1,2,...,N$ に対する問題の答えを、順番に改行区切りで出力せよ。

题目大意

题目描述

给定一棵 $n$ 个点的树，给第 $i$ 个点染上颜色 $c_i$，其中，$c_i$ 为 $[1,n]$ 的一个整数。

现在，对于每一种颜色 $k$，你要求出有多少条简单路径满足路径上至少有一个点的颜色为 $k$。

输入格式

第一行一个整数 $n$。

接下来一行 $n$ 个整数，表示 $c_i$。

接下来第 $3$ 到第 $n+1$ 行，每行两个整数 $u_i,v_i$，描述一条树边。

输出格式

输出 $n$ 行，一行一个整数，分别表示对于颜色 $1,2,...,n$ 的答案。

3
1 2 1
1 2
2 3

5
4
0

1
1

1

2
1 2
1 2

2
2

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

5
8
10
5
5

8
2 7 2 5 4 1 7 5
3 1
1 2
2 7
4 5
5 6
6 8
7 8

18
15
0
14
23
0
23
0

提示

制約

• $1\ \leq\ N\ \leq\ 2\ \times\ 10^5$
• $1\ \leq\ c_i\ \leq\ N$
• $1\ \leq\ a_i,b_i\ \leq\ N$
• 与えられるグラフは木である。
• 入力はすべて整数である。

Sample Explanation 1

頂点 $i$ と頂点 $j$ を結ぶ単純パスを、$P_{i,j}$ と表します。 色 $1$ が塗られている頂点を一度以上通る単純パスは、 $P_{1,1}\,,\,$ $P_{1,2}\,,\,$ $P_{1,3}\,,\,$ $P_{2,3}\,,\,$ $P_{3,3}$ の $5$ つあります。 色 $2$ が塗られている頂点を一度以上通る単純パスは、 $P_{1,2}\,,\,$ $P_{1,3}\,,\,$ $P_{2,2}\,,\,$ $P_{2,3}$ の $4$ つあります。 色 $3$ が塗られている頂点を一度以上通る単純パスはありません。