103596: [Atcoder]ABC359 G - Sum of Tree Distance

Problem Statement

You are given a tree with $N$ vertices. The $i$-th edge connects vertices $u_i$ and $v_i$ bidirectionally.

Additionally, you are given an integer sequence $A=(A_1,\ldots,A_N)$.

Here, define $f(i,j)$ as follows:

• If $A_i = A_j$, then $f(i,j)$ is the minimum number of edges you need to traverse to move from vertex $i$ to vertex $j$. If $A_i \neq A_j$, then $f(i,j) = 0$.

Calculate the value of the following expression:

Constraints

• $2 \leq N \leq 2 \times 10^5$
• $1 \leq u_i, v_i \leq N$
• $1 \leq A_i \leq N$
• The input graph is a tree.
• All input values are integers.

Input

The input is given from Standard Input in the following format:

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

Output

Print the answer.

Sample Input 1

4
3 4
4 2
1 2
2 1 1 2

Sample Output 1

4

$f(1,4)=2, f(2,3)=2$. For all other $i, j\ (1 \leq i < j \leq N)$, we have $f(i,j)=0$, so the answer is $2+2=4$.

Sample Input 2

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

Sample Output 2

19

问题描述

你被给定一棵有 $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$。

计算以下表达式的结果：

限制条件

• $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