W1024理论的推演

W1024理论的推演

Description

艾尔海森最近在教令院中抓捕犯下累累罪行的大贤者，大贤者能够在教令院手握大权，最重要的原因是教令院中内鬼很多！

作为一个普通的「文弱书生」，他决定在武力清除这些余党前做一些计算。首先他将教令院关系网络列出，由于艾尔海森智力超群，他只研究这张关系网络的最小生成树。
在这棵树上，标注了若干红色的点，表示教令院中的内鬼。整个教令院内鬼间的团结程度定义为：所有红色点之间的距离之和。

由于艾尔海森还要去找卡维♂玩游戏，他现在要求你，教令院的学者，求出这棵教令院内鬼关系网络的最小生成树的内鬼之间的团结程度。聪明的你，一定能轻松解决这个问题。

Input

$\boxed{{\displaystyle \begin{array}{rlr}& n& m\\ & r_1& r_2& & \dots & & r_m\\ & u_1& v_1\\ & u_2& v_2\\ & ⋮& n-1\text{ lines}\\ & u_{n-1}& v_{n-1}\end{array}}}$

输入包含 $n+1$ 行

• 第一行包含两个整数 $n,m$ 分别表示树的点数，红色点的个数
• 第二行包含 $m$ 个数，表示红色点的编号
• 第 $3$ 到第 $n+1$ 行，每行包含两个整数 $u,v$，表示 $(u,v)$ 之间有一条边。
  数据范围：
• $1\le n\le {10}^5$
• $1\le m\le n$
• $0\le u,v\le n-1$

Output

一个数，表示答案。

Sample Input

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

Sample Output

10

Hint

如图所示，红色点之间的距离分别为 $5,4,1$，和为 $10$。

Solution

两个红点相会，会经过某条边 $x\times y$ 次，其中 $x,y$ 分别为这条边左右的红点数量。
显然所有边的贡献之和即为所求，一次 dfs 即可解决

Code

$/\ast \dots TODO\ast /$