每个叶子结点都是出入口。
没指定根的情况下讨论叶子结点令人误解,根据英文题面应是
每个度为 1 的结点都是出入口。
并且翻译没说贝茜走到出口就逃走了,令人误解,至少我没模样例前云里雾里。另外其他地方稍作修改。
所以申请修正:
贝茜在一棵有 n 个节点的树上,每个度为 1 的结点是出入口。开始时,每个出入口都可以放一个农民。每个时刻,贝茜和农民都可以移动到相邻的一个结点。如果在她到达一个出口前,农民与贝茜相遇了(在边上或点上均算),则贝茜将被抓住。抓捕过程中,农民们与贝茜均知道对方在哪个结点。
请问:对于每个结点 i,如果开始时贝茜在该结点,最少有多少农民,她才会被抓住。
贝茜在一棵有 $n$ 个节点的树上,每个度为 $1$ 的结点是出入口。开始时,每个出入口都可能有一个农民。每个时刻,贝茜和农民都可以移动到相邻的一个结点。如果在她到达一个出口前,农民与贝茜相遇了(在边上或点上均算),则贝茜将被抓住。过程中,农民们与贝茜均知道对方在哪个结点。
请问:对于每个结点 $i$,如果开始时贝茜在该结点,最少有多少农民,她才会被抓住。