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

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

Score : $600$ points

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:

$\displaystyle \sum_{i=1}^{N-1}\sum_{j=i+1}^N f(i,j)$.


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

Output

得分:$600$ 分 ---

问题描述

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


限制条件

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

加入题单

上一题 下一题 算法标签: