树上距离之和

题目描述

给定一棵有 $N$ 个顶点的树。第 $i$ 条边双向连接顶点 $u_i$ 和 $v_i$。

此外,给定整数序列 $A=(A_1,\ldots,A_N)$。

这里,定义 $f(i,j)$ 如下:

如果 $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)$$

输入格式

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

$N$
$u_1$ $v_1$
$\vdots$
$u_{N-1}$ $v_{N-1}$
$A_1$ $A_2$ $\ldots$ $A_N$

输出格式

输出答案。

样例

4
3 4
4 2
1 2
2 1 1 2

4

$f(1,4)=2,\ f(2,3)=2$。对所有其他的 $i,j\ (1\le i\lt j\le N)$,都有 $f(i,j)=0$,所以答案为 $2+2=4$。

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

19

数据范围

• $2 \le N \le 2\times10^5$
• $1 \le u_i,v_i \le N$
• $1 \le A_i \le N$
• 输入的图是一棵树。
• 输入均为整数。