W1024理论的推演

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

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

由于艾尔海森还要去找卡维♂玩游戏，他现在要求你，教令院的学者，求出这棵教令院内鬼关系网络的最小生成树的内鬼之间的团结程度。聪明的你，一定能轻松解决这个问题。 ## Input \(\boxed{\begin{align}&n&m\\&r_{1}&r_{2}&&\dots&&r_{m}\\&u_{1}&v_{1}\\&u_{2}&v_{2}\\&\vdots &n-1\text{ lines}\\&u_{n-1}&v_{n-1}\end{align}}\)

输入包含 \(n+1\) 行 - 第一行包含两个整数 \(n, m\) 分别表示树的点数，红色点的个数 - 第二行包含 \(m\) 个数，表示红色点的编号 - 第 \(3\) 到第 \(n+1\) 行，每行包含两个整数 \(u, v\)，表示 \((u, v)\) 之间有一条边。 数据范围： - \(1\leq n\leq 10^5\) - \(1\leq m\leq n\) - \(0\leq u,v\leq 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

\(\Huge{/*\dots TODO*/}\)