AT_abc482_e.Diameter Endpoint Colors

提高+/省选-

通过率:0%

时间限制:2.00s

内存限制:1024MB

AC君温馨提醒

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

题目描述

You are given a tree TT with NN vertices numbered 1,2,…,N1,2,\dots,N. For i=1,2,…,N−1i=1,2,\dots,N-1, the ii-th edge connects vertices uiu_i and viv_i.

Each vertex is painted in a color; vertex vv is painted in color CvC_v.

Find the number of integer pairs (u,v)(u,v) with 1≤u<v≤N1 \leq u < v \leq N that satisfy all of the following conditions.

  • Vertices uu and vv are painted in the same color.
  • The length of the simple path connecting vertices uu and vv equals the diameter of the tree TT.

Here, the length of a path is the number of edges in it, and the diameter of a tree is the maximum length of a simple path in the tree.

给你一棵有 NN 个顶点的树 TT,顶点编号为 1,2,…,N1,2,\dots,N。对于 i=1,2,…,N−1i=1,2,\dots,N-1,第 ii 条边连接顶点 uiu_i 和 viv_i。

每个顶点被染成某种颜色;顶点 vv 的颜色为 CvC_v。

求满足以下所有条件的整数对 (u,v)(u,v)(其中 1≤u<v≤N1 \leq u < v \leq N)的个数:

  • 顶点 uu 和 vv 被染成相同的颜色;
  • 连接顶点 uu 和 vv 的简单路径的长度等于树 TT 的直径。

其中,路径的长度定义为该路径所含边的数量,而树的直径定义为树中所有简单路径的最大长度。

输入格式

The input is given from Standard Input in the following format:

NN
u1u_1 v1v_1
u2u_2 v2v_2
⋮\vdots
uN−1u_{N-1} vN−1v_{N-1}
C1C_1 C2C_2 …\dots CNC_N

输入从标准输入中按以下格式给出:

NN
u1u_1 v1v_1
u2u_2 v2v_2
⋮\vdots
uN−1u_{N-1} vN−1v_{N-1}
C1C_1 C2C_2 …\dots CNC_N

输出格式

Print the answer.

输出答案。

输入输出样例

  • 输入#1

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

    输出#1

    1
  • 输入#2

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

    输出#2

    2
  • 输入#3

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

    输出#3

    2

说明/提示

Sample 1 Explanation:
There is 11 integer pair that satisfies the conditions: (1,5)(1,5).

Sample 2 Explanation:
There are 22 integer pairs that satisfy the conditions: (3,6)(3,6) and (4,7)(4,7).

Sample 3 Explanation:
There are 22 integer pairs that satisfy the conditions: (4,5)(4,5) and (5,9)(5,9).

Constraints

  • 2≤N≤2×1052 \leq N \leq 2 \times 10^5
  • 1≤ui,vi≤N1 \leq u_i, v_i \leq N
  • The given graph is a tree.
  • 1≤Ci≤N1 \leq C_i \leq N
  • All input values are integers.

样例 1 解释:
满足条件的整数对有 11 个:(1,5)(1,5)。

样例 2 解释:
满足条件的整数对有 22 个:(3,6)(3,6) 和 (4,7)(4,7)。

样例 3 解释:
满足条件的整数对有 22 个:(4,5)(4,5) 和 (5,9)(5,9)。

约束条件

  • 2≤N≤2×1052 \leq N \leq 2 \times 10^5
  • 1≤ui,vi≤N1 \leq u_i, v_i \leq N
  • 给定的图是一棵树。
  • 1≤Ci≤N1 \leq C_i \leq N
  • 所有输入值均为整数。

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

首页