103683: [Atcoder]ABC368 D - Minimum Steiner Tree

Problem Statement

You are given a tree with $N$ vertices numbered $1$ to $N$. The $i$-th edge connects vertices $A_i$ and $B_i$.

Consider a tree that can be obtained by removing some (possibly zero) edges and vertices from this graph. Find the minimum number of vertices in such a tree that includes all of $K$ specified vertices $V_1,\ldots,V_K$.

Constraints

• $1 \leq K \leq N \leq 2\times 10^5$
• $1 \leq A_i,B_i \leq N$
• $1 \leq V_1 < V_2 < \ldots < V_K \leq N$
• The given graph is a tree.
• All input values are integers.

Input

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

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

Output

Print the answer.

Sample Input 1

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

Sample Output 1

4

The given tree is shown on the left in the figure below. The tree with the minimum number of vertices that includes all of vertices $1,3,5$ is shown on the right.

Sample Input 2

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

Sample Output 2

4

Sample Input 3

5 1
1 4
2 3
5 2
1 2
1

Sample Output 3

1

问题陈述

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

考虑通过从该图中删除一些（可能为零）边和顶点可以获得的一棵树。找到包含所有K个指定顶点V_1,…,V_K的最小顶点数的树。

约束条件

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

输入

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

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

输出

打印答案。

样本输入1

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

样本输出1

4

如下图所示，给定的树在左侧。包含所有顶点1,3,5的最小顶点数的树显示在右侧。

样本输入2

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

样本输出2

4

样本输入3

5 1
1 4
2 3
5 2
1 2
1

样本输出3

1