AT_abc368_d [ABC368D] Minimum Steiner Tree

题目描述

给定一棵有 $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$

输出格式

请输出答案。

输入输出样例 #1

输入 #1

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

输出 #1

4

输入输出样例 #2

输入 #2

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

输出 #2

4

输入输出样例 #3

输入 #3

5 1
1 4
2 3
5 2
1 2
1

输出 #3

1

说明/提示

限制条件

• $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$
• 给定的图是一棵树
• 输入均为整数

样例说明 1

给定的树如左图所示，从中删除若干边和顶点后，包含顶点 $1,3,5$ 的最小顶点数的树如右图所示。

由 ChatGPT 4.1 翻译