分数: 600 点
问题陈述
你有一棵树 N 顶点。的 i第一条边连接顶点 u_i 和 v_i 双向。
此外,还给你一个整数序列 A=(A_1,\ldots,A_N).
在这里,定义 f(i,j) 如下:
- If A_i = A_j,然后 f(i,j) 是从顶点移动所需遍历的最小边数 i 到顶点 j。如果 A_i \neq A_j,然后 f(i,j) = 0.
计算以下表达式的值:
\displaystyle \sum_{i=1}^{N-1}\sum_{j=i+1}^N f(i,j).
约束
- 2 \leq N \leq 2 \times 10^5
- 1 \leq u_i, v_i \leq N
- 1 \leq A_i \leq N
- 输入图是一棵树。
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N
u_1 v_1
\vdots
u_{N-1} v_{N-1}
A_1 A_2 \ldots A_N
输出
打印答案。
示例输入 1
4 3 4 4 2 1 2 2 1 1 2
示例输出 1
4
f(1,4)=2, f(2,3)=2。对于所有其他 i, j\ (1 \leq i < j \leq N),我们有 f(i,j)=0,所以答案是 2+2=4.
示例输入 2
8 8 6 3 8 1 4 7 8 4 5 3 4 8 2 1 2 2 2 3 1 1 3
示例输出 2
19