CF750F

DJRzjl · 2021-09-13 15:03:32 · 题解

CF750F New Year and Finding Roots

首先分析，如果询问某个点 x​ ，其

1. 邻居数为 1 ，则 x 为叶子节点，并且我们可以知道它的父亲；
2. 邻居数为 2 ，则 x 为根节点，那么我们已经得到答案，直接结束；
3. 除次之外，邻居数一定为 3 ，则 x 为树中某个普通点。

假设我们现在在点 u​​​​ ，并且我们知道它的某个儿子，考虑如何让 u​​​ 一步步确定自己的父亲，一直走到根：

当 u​ 只有 2​ 个邻居没有确定父子关系，我们可以向这两个方向 bfs 地询问，一边会先找到一个叶子，于是另一边就是 u​ 的父亲，我们再令父亲点为点 u​​​ ，重复上述过程即可。

我们先随机取一个点询问，设为 s 。

如果开始时 s​ 是叶子，我们令 u​ 为 s 的父亲，向上跳即可；

如果开始时 s​​​ 有三个邻居，那么我们先向三个方向 bfs ，会有两边同时遇到叶子，另一边就是 s​ 的父亲，向那个方向跳，又回到先前的步骤；

这样我们就能成功找到根了，不过只有这些询问次数会超过 16 次，于是需要优化。

• 对于已经询问过的点，记下信息，以后不再询问它；

• 向几个方向 bfs 时，优先沿着之前询问过的邻居遍历（当然不可以是前驱点），这样能使以前向上方向 bfs 的信息充分利用；

根下第二层 bfs 第一次就能找到根，计算可以知道，最坏情况会询问 1+2+3+4+5+1+2=18​ 次

于是还需要优化：

• 当深度为 3 时，不需要再做 bfs 到叶子，根就在距离它为 2​ 的四个点之一，于是询问其中三个即可，这里有个小细节，对于四个点中某个没询问过的点，不询问它而是询问其他三个，否则可能出现询问为 17​ 次。

最后画个图理解下过程：（ 7 层，点顺序编号）

这里假设 s 初始为叶子，其他情况读者可以自己画图，不难得到其正确性。