← 返回题目列表

AtCoder · abc368_d

G. 最小斯坦纳树

中文机器翻译题面 查看原题

分数: 425 点

问题陈述

你有一棵树 N 顶点编号 1 to N。的 i第一条边连接顶点 A_i 和 B_i.

考虑一棵可以通过从此图中删除一些(可能为零)边和顶点来获得的树。找到这样一棵树中包含所有节点的最小顶点数 K 指定顶点 V_1,\ldots,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 显示在右侧。

Figure


示例输入 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