题目详情题解（0）讨论（0）提交记录（0）

AT_abc163_f.[ABC163F] path pass i

省选/NOI-

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

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

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

输入格式

第一行一个整数 nn。

接下来一行 nn 个整数，表示 cic_i。

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

输出格式

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

输入输出样例

  • 输入#1

    3
1 2 1
1 2
2 3

    输出#1

    5
4
0

  • 输入#2

    1
1

    输出#2

    1

  • 输入#3

    2
1 2
1 2

    输出#3

    2
2

  • 输入#4

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

    输出#4

    5
8
10
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≤n≤2×1051 \le n \le 2 \times 10^5
  • 1≤ci≤n1 \le c_i \le n
  • 1≤ui,vi≤n1 \le u_i, v_i \le n

输入解题思路，AI测评打分。不知道怎么写?

首页