最小斯坦纳树

题目描述

给定一棵有 $N$ 个顶点的树，顶点编号为 $1$ 到 $N$。第 $i$ 条边连接顶点 $A_i$ 和 $B_i$。

考虑从该图中删除若干（可以为 0 条）边和顶点得到的树。求包含全部 $K$ 个指定顶点 $V_1,\ldots,V_K$ 的这样的树的最小顶点数。

输入格式

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

$N$ $K$
$A_1$ $B_1$
$\vdots$
$A_{N-1}$ $B_{N-1}$
$V_1$ $\ldots$ $V_K$

输出格式

输出答案。

样例

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

4

下图左侧为给定的树。包含顶点 $1,3,5$ 全部顶点、顶点数最少的树如右侧所示。

4 4
3 1
1 4
2 1
1 2 3 4

4

5 1
1 4
2 3
5 2
1 2
1

1

数据范围

• $1 \le K \le N \le 2\times 10^5$
• $1 \le A_i,B_i \le N$
• $1 \le V_1 \lt V_2 \lt \ldots \lt V_K \le N$
• 给定的图是一棵树。
• 所有输入值均为整数。