自动搬运

查看原文

来自洛谷，原作者为

	Lynkcat Reset.

搬运于2025-08-24 22:36:11，当前版本为作者最后更新于2022-02-09 18:18:38，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

第一次做出月赛1C，写个题解纪念一下，虽然这个1C可能相比较于别的1C简单了不少。

首先 $20$ 分做法非常好想，只要模拟两遍普通树上 dfs 的过程即可，这样子做复杂度是 $O(4n)$ 的。

我们发现了问题，因为在这个做法中实际上根本没用交换操作。不难想到一种做法，在 dfs 的时候，一个走，一个留在根，每走一个不是回溯的步，就交换一下，复杂度 $O(3n)$ 。可以拿到 $40$ 分。

进一步思考我们又发现，这个做法的缺点是，交换操作带来的价值太小，如果两个人在不同的两个点 $x,y$ 并且在 $x$ 处的人没到过 $y$，在 $y$ 处的人没到过 $x$，交换操作实际上会带来 $2$ 的收益，上面这个做法带来的收益只有 $1$。

进一步思考，我们发现两个人可以分开走各自的，然后每走到一个新点，就交换一下。

这样子做复杂度是 $O(2n+\max($第一个人走的点数$,$第二个人走的点数$))$。设第一个人走的点数为 $x$，另一个人为 $y$。容易发现我们把重心作为根的话可以做到让 $\min(x,y)\times 2\leq \max(x,y)$。所以最终复杂度最坏达到 $\frac{8}{3}n$ 。

代码写的很怪，就只贴个链接了。