自动搬运

查看原文

来自洛谷，原作者为

	Little09 「按照我们原来的期待 去证明我们的未来」

搬运于2025-08-24 22:29:55，当前版本为作者最后更新于2021-03-26 22:51:57，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

迟到了的出题人题解。

部分分如下：

• Subtask 2：枚举一下加哪条边，然后按照有向图博弈去做。
• Subtask 4：在一个自己能到达的必败点，连一条边到后面的另一个必败点。可以后缀 min 处理。
• Subtask 5：先手则 0，后手则 -1。

考虑必胜点和必败点的思想。当一个点指向的所有点都是必胜点，这个点是必败点。否则是必胜点。叶子节点是必败点。

先不考虑加边，处理出每个点是必胜点还是必败点。接着处理出每个点的改变会不会影响到根的改变。

先考虑加边形成环的情况，是不会使得必败变成必胜的。只会使局面变成平局或不变。证明。

不形成环的情况，就是 $v$ 不在 $u$ 到根的路径上。考虑一个 $u$ 改变会影响根。对于这个点是必胜点，肯定是无法改变的。对于这个点是必败点，只要把它连到一个必败点上去，它就能改变。要计算出最小的不在这个点到根路径上的必败点。

接下来的问题是要计算出最小的不在这个点到根路径上的必败点。

• Subtask 3：每次暴力扫一遍。
• Subtask 6：发现要维护单点插入、删除和整体 min，用 multiset 等数据结构维护。
• Subtask 7：在树上跑两遍 dfs，一遍从左往右，一遍从右往左。每次便遍历顺序是先儿子再父亲。会发现在第一次遍历 $x$ 节点前的所有点是树上在 $x$ 左边的点和 $x$ 子树的点，第二次遍历 $x$ 节点前的所有点是树上在 $x$ 右边的点和 $x$ 子树的点。两次的并就是不在 $x$ 到根路径上的点。做个前缀 min 即可。
• 也还有其他很多的线性做法。

正解复杂度线性。貌似被堆的 log 过去了，但是我不想卡了。

代码细节比较多，但是思路算是清晰的。写得比较丑，就不给代码了。