AT_abc482_e.Diameter Endpoint Colors
提高+/省选-
通过率:0%
时间限制:2.00s
内存限制:1024MB
AC君温馨提醒
该题目为【atcoder】题库的题目,您提交的代码将被提交至atcoder进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
You are given a tree T with N vertices numbered 1,2,…,N. For i=1,2,…,N−1, the i-th edge connects vertices ui and vi.
Each vertex is painted in a color; vertex v is painted in color Cv.
Find the number of integer pairs (u,v) with 1≤u<v≤N that satisfy all of the following conditions.
- Vertices u and v are painted in the same color.
- The length of the simple path connecting vertices u and v equals the diameter of the tree T.
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.
给你一棵有 N 个顶点的树 T,顶点编号为 1,2,…,N。对于 i=1,2,…,N−1,第 i 条边连接顶点 ui 和 vi。
每个顶点被染成某种颜色;顶点 v 的颜色为 Cv。
求满足以下所有条件的整数对 (u,v)(其中 1≤u<v≤N)的个数:
- 顶点 u 和 v 被染成相同的颜色;
- 连接顶点 u 和 v 的简单路径的长度等于树 T 的直径。
其中,路径的长度定义为该路径所含边的数量,而树的直径定义为树中所有简单路径的最大长度。
输入格式
The input is given from Standard Input in the following format:
N
u1 v1
u2 v2
⋮
uN−1 vN−1
C1 C2 … CN
输入从标准输入中按以下格式给出:
N
u1 v1
u2 v2
⋮
uN−1 vN−1
C1 C2 … CN
输出格式
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 1 integer pair that satisfies the conditions: (1,5).
Sample 2 Explanation:
There are 2 integer pairs that satisfy the conditions: (3,6) and (4,7).
Sample 3 Explanation:
There are 2 integer pairs that satisfy the conditions: (4,5) and (5,9).
Constraints
- 2≤N≤2×105
- 1≤ui,vi≤N
- The given graph is a tree.
- 1≤Ci≤N
- All input values are integers.
样例 1 解释:
满足条件的整数对有 1 个:(1,5)。
样例 2 解释:
满足条件的整数对有 2 个:(3,6) 和 (4,7)。
样例 3 解释:
满足条件的整数对有 2 个:(4,5) 和 (5,9)。
约束条件
- 2≤N≤2×105
- 1≤ui,vi≤N
- 给定的图是一棵树。
- 1≤Ci≤N
- 所有输入值均为整数。
输入解题思路,AI测评打分。不知道怎么写?