交互题暂时无法评测

幽云蓝 · 2023-05-11 17:51:43 · 题解

假设所有边方向都未知。首先，如果是个菊花图怎么办。答案很简单，在所有叶子上放物品，然后看哪些叶子上的物品消失了。

排除了菊花图的情况，我们会发现树的深度至少为 3。我们把所有结点按其深度模 3 分类，选择最多的那一类，记这些点为 S。我们在点集 S 的所有点上放置物品，然后对于每个点会有三种情况：

1. 物品没动，那与它相连的所有边的方向都找到了，确定了至少一条新边的方向；
2. 物品移动到儿子上了，确定了一条新边的方向；
3. 物品没有移动到儿子上也没有留在原地，那么一定是去父亲了，也确定了一条新边的方向。

总而言之，这一次操作会让总共的未知边数削减至原来的 \frac{2}{3}。接下来，产生的新问题就是有的边现在变为已知了，我们希望不重复计算到这些边。可以发现，即使有些边变成已知边这个操作还是能不断进行下去。

考虑把邻边中存在未知边的点的点权置为 1，其他点点权置为 0。这次依旧把所有结点按其深度模 3 分类，但改为选择权值和最大的那一类。对于已知边，如果它和放置了物品的点相连，记得将其方向改为指向放置物品的点。

一次操作会使未知边数乘 \frac{2}{3}，分析一下可以发现 30 次足够找出所有的边了。