直径端点颜色

题目描述

给定一棵有 $N$ 个顶点的树 $T$，顶点编号为 $1,2,\ldots,N$。对于 $i=1,2,\ldots,N-1$，第 $i$ 条边连接顶点 $u_i$ 和 $v_i$。

每个顶点都被染了一种颜色，顶点 $v$ 的颜色为 $C_v$。

请求出满足以下两个条件的整数对 $(u,v)$（$1 \le u < v \le N$）的数量：

• 顶点 $u$ 和顶点 $v$ 颜色相同；
• 连接 $u$ 和 $v$ 的简单路径长度等于树 $T$ 的直径。

这里，路径的长度指路径上的边数，树的直径指树中最长简单路径的长度。

输入格式

输入第一行为一个整数 $N$。

接下来 $N-1$ 行，第 $i$ 行为两个整数 $u_i,v_i$。

最后一行为 $N$ 个整数 $C_1,C_2,\ldots,C_N$，相邻两个数之间用一个空格隔开。

输出格式

输出一行一个整数，表示答案。

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

1

样例 1 解释

只有一对整数满足条件：$(1,5)$。

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,6)$ 和 $(4,7)$。

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

2

样例 3 解释

有两对整数满足条件：$(4,5)$ 和 $(5,9)$。

数据范围

对于所有测试数据，保证：

• $2 \le N \le 2 \times 10^5$；
• $1 \le u_i,v_i \le N$；
• 给定的图是一棵树；
• $1 \le C_i \le N$；
• 所有输入值均为整数。

子任务

本题共 20 个测试点，按测试点计分：

每个测试点单独评分，全部测试点的得分之和即为本题得分。