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

题目背景

在古老的修仙界，存在一株通天彻地的“太古灵树”。这棵树由 $N$ 个汇聚天地元气的“灵穴”组成，灵穴之间通过 $N-1$ 条“灵脉”相互连接，形成了一个巨大的树形结构。

每一个灵穴都蕴含着一种特定的“五行元力”（如金、木、水、火、土等，但种类远不止五种）。为了修炼，修仙者需要在灵树上通过灵脉进行“周天运转”。一次周天运转是指在灵树上选择两个灵穴 $u$ 和 $v$（$u$ 可以等于 $v$），并让真气沿着 $u$ 到 $v$ 的唯一简单路径流动。

若某次周天运转的路径中，至少经过了一个蕴含“元力 $k$”的灵穴，则称这次运转与“元力 $k$”发生了共鸣。

掌管灵树的宗门长老希望你计算出，对于每一种元力，究竟有多少种不同的周天运转路径能够与其产生共鸣。

题目描述

给定一棵包含 $N$ 个节点的树（即太古灵树），节点编号为 $1$ 到 $N$。

树上的第 $i$ 条边连接节点 $a_i$ 和 $b_i$。

每个节点 $i$ 都有一个属性值 $c_i$（$1 \le c_i \le N$），表示该灵穴蕴含的元力种类。

简单来说我们需要对于 $k = 1, 2, \dots, N$，分别解决以下问题：

求出有多少条简单路径，满足路径上至少有一个节点的属性值为 $k$。

输入格式

输入数据的第一行包含一个整数 $N$，表示灵穴的数量。

第二行包含 $N$ 个整数 $c_1, c_2, \dots, c_N$，其中 $c_i$ 表示第 $i$ 个灵穴的元力属性。

接下来 $N-1$ 行，每行包含两个整数 $a_i, b_i$，表示第 $i$ 条灵脉连接的两个灵穴编号。

输出格式

输出共 $N$ 行。

第 $k$ 行输出一个整数，表示与“元力 $k$”发生共鸣的路径数量。

样例

3
1 2 1
1 2
2 3

5
4
0

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

5
8
10
5
5

提示

样例解释

样例1

• 灵穴 1 (属性1) —— 灵穴 2 (属性2) —— 灵穴 3 (属性1)
• 元力 1：
  • 路径 (1,1)：经过灵穴1（属性1），符合。
  • 路径 (1,2)：经过灵穴1，符合。
  • 路径 (1,3)：经过灵穴1和3，符合。
  • 路径 (2,3)：经过灵穴3，符合。
  • 路径 (3,3)：经过灵穴3，符合。
  • 共 5 条。
• 元力 2：
  • 路径 (1,2), (2,2), (2,3) 经过灵穴2（属性2）。
  • 路径 (1,3) 经过灵穴2。
  • 共 4 条。
• 元力 3：
  • 树中没有属性为 3 的灵穴，故共鸣路径数为 0。

数据范围

对于所有测试数据，满足：

• $1 \le N \le 2 \times 10^5$
• $1 \le c_i \le N$
• $1 \le a_i, b_i \le N$
• 给定的图保证是一棵树。
• 输入均为整数。

为了全面测试算法的正确性与效率，本题共设置 20 个测试点，具体分布如下：

测试点编号	$N$ 的规模	特殊性质
1 ~ 5	$N \le 100$	无
6 ~ 10	$N \le 3,000$
11 ~ 15	$N \le 50,000$	树退化为一条链
16 ~ 20	$N \le 200,000$	无