自动搬运

查看原文

来自洛谷，原作者为

	幽云蓝 a

搬运于2025-08-24 22:47:25，当前版本为作者最后更新于2023-05-11 17:51:43，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

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

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

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

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

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

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