E. 管理孩子 - EOJ Monthly 2018.12

仪表盘所有提交榜单题解

单点时限: 2.0 sec

内存限制: 512 MB

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

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

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

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

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

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

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

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

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

接下来 $n - 1$ 行每行两个数表示一条边 $u_{i}, v_{i}$ ( $1 \leq u_{i}, v_{i} \leq n$ )。

接下来一行 $k$ 个各不相同的整数 $b_{1}, b_{2}, \dots, b_{k}$ ( $1 \leq b_{i} \leq n$ )，表示每个洋娃娃所在的位置。

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

Input

Output

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

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

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

NaN

比赛状态发生变化，点 OK 刷新。

OK

EOJ Monthly 2018.12