3654. 管理孩子

单测试点时限: 2.0 秒

内存限制: 512 MB

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

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

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

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

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

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

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

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

输入

第一行两个正整数 (),分别表示孩子的数量和洋娃娃的数量。

接下来 行每行两个数表示一条边 ()。

接下来一行 个各不相同的整数 (),表示每个洋娃娃所在的位置。

输出

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

样例

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

提示

样例所给的树正好是一条链: ,在位置 各有一个洋娃娃。

有两种最优的割法,在 之间断开或者在 之间断开。

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

21 人解决,27 已尝试。

25 份提交通过,共有 72 份提交。

8.3 EMB 奖励。

创建: 3 月,1 周前.

修改: 2 月,2 周前.

最后提交: 1 月,1 周前.

来源: EOJ Monthly 2018.12

标签