AT_abc163_f [ABC163F] path pass i

题目描述

给定一棵 $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$ 的答案。

输入输出样例 #1

输入 #1

3
1 2 1
1 2
2 3

输出 #1

5
4
0

输入输出样例 #2

输入 #2

1
1

输出 #2

1

输入输出样例 #3

输入 #3

2
1 2
1 2

输出 #3

2
2

输入输出样例 #4

输入 #4

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

输出 #4

5
8
10
5
5

输入输出样例 #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

输出 #5

18
15
0
14
23
0
23
0

说明/提示

数据范围

• $1 \le n \le 2 \times 10^5$
• $1 \le c_i \le n$
• $1 \le u_i, v_i \le n$