3654. 管理孩子

单点时限: 2.0 sec

内存限制: 512 MB

只有小孩子知道自己在找什么。
他们把时间花费在布洋娃娃身上。
因此对他们而言,
洋娃娃就变得很重要。

一旦有人将娃娃拿走,他们就会号啕大哭。

管理小孩子真是一件费力费神的事情。

现在你要管理的 $n$ 个小孩子们分别在 $n$ 个不同的地方,他们之间有 $n-1$ 条路径连接而形成一个联通块,即 $n$ 个小孩子们所在的点构成了一棵树结构。

但是洋娃娃是有限的。你只在其中的某几个位置放了洋娃娃。

这么多小孩子的管理,你一个人已经完全不足以应付了。所以你打算请好多的管理员来帮助你管理小孩子们。显然,为了方便管理员,每一个管理员管理的一定是一些互相连通位置上的孩子。

为了提高管理的效果,你希望每一个管理员管理尽量少的孩子,准确地说,你希望管理最多孩子的管理员管理的孩子数量最少。

而小孩子们都是离不开洋娃娃的,所以每一个管理员管理的那些位置上,应该至少有一个洋娃娃,不然小孩子们会哭会闹会……

输入格式

第一行两个正整数 $n,k$ ($2 \le n \le 2 \cdot 10^5, 1 \le k \le 2 \cdot 10^5$),分别表示孩子的数量和洋娃娃的数量。

接下来 $n-1$ 行每行两个数表示一条边 $u_i, v_i$ ($1 \le u_i, v_i \le n$)。

接下来一行 $k$ 个各不相同的整数 $b_1, b_2, \ldots, b_k$ ($1 \le b_i \le n$),表示每个洋娃娃所在的位置。

输出格式

一行一个正整数表示答案,即管理最多孩子的管理员管理的孩子数量最少是多少。

样例

Input
5 2
1 2
2 3
3 4
4 5
1 5
Output
3

提示

样例所给的树正好是一条链: $1-2-3-4-5$ ,在位置 $1$ 和 $5$ 各有一个洋娃娃。

有两种最优的割法,在 $2-3$ 之间断开或者在 $3-4$ 之间断开。

这两种方案的两个联通块大小都是 $2$ 和 $3$ ,所以最优方案就是最大联通块最小是 $3$。

22 人解决,28 人已尝试。

26 份提交通过,共有 73 份提交。

4.6 EMB 奖励。

创建: 1 年,11 月前.

修改: 1 年,10 月前.

最后提交: 1 年,6 月前.

来源: EOJ Monthly 2018.12

题目标签