← 返回题目列表

AtCoder · abc359_g

G. 树距离总和

中文机器翻译题面 查看原题

分数: 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