Minimum Steiner Tree

题目描述

给你一个由 $1$ 到 $N$ 编号的 $N$ 个顶点组成的树。第 $i$ 条边连接顶点 $A_i$ 和 $B_i$。 考虑可以通过从该图中删除若干（可能为零）条边和顶点得到的树。求包含给定的 $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

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 \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,3,5$ 并且顶点数最少的树如右侧所示。

标签: AtCoder|abc368D

来源

AtCoder|abc368D