题解 P8119 「Wdoi-1.5」幻想乡游览计划

Lynkcat · 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 。

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