84405 - LUK-Triumphal arch

讨论

统计

通过次数

提交次数

旧版界面

时间限制 : 2 秒

内存限制 : 128 MB

给一颗 $n$ 个节点的树，初始时 $1$ 号节点被染黑，其余是白的。两个人轮流操作，一开始 B 在 $1$ 号节点。每一轮，A 选择 $k$ 个点染黑，然后 B 走到一个相邻节点，如果 B 当前处于白点则 B 胜，否则当 A 将所有点染为黑点时 A 胜。求能让 A 获胜的最小的 $k$ 。

第一行读入一个整数 $n$ ，表示树的节点数

接下来 $n-1$ 行，每行读入两个用空格分隔的整数 $u,v$ ，表示 $u$ 、 $v$ 之间有一条边。

输出仅有一行，表示让 A 获胜的最小的 $k$ 。

$n \le 3 \times 10^5$ 。

POI