自动搬运

查看原文

来自洛谷，原作者为

	cyc001 给岁月以文明，而不是给文明以岁月

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

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

以下是正文

spj 的输出信息真的很有参考价值 /bx

Solution

考虑 subtask2 怎么做。

我们显然可以钦定度数为 $2$ 的点为根，则 mark 时可以标记目标节点到根的所有点。

然后我们现在的问题是如何在询问的时候沿着被染色的点走并尽量少地访问未染色节点。

首先我们可以直接往根走，直到遇到第一个染色节点，不难发现这一步的额外步数是 $0$。

现在我们需要将当前节点沿着染色的路径往子树里走，不难想到重链剖分的轻重边切换次数是 $O(\log n)$ 次，则直接每次优先访问重儿子即可保证询问次数。

现在讨论 subtask3，我们假设这棵树的性质足够好，则可以把根节点设置为树的重心。

那么如果有两个重心怎么办，可以通过复杂的分类讨论区保证正确性并且让询问次数多出好几次过不去，其实只要在染色时钦定离目标更近的点为根，然后在询问的时候任选一个重心为根，如果跳到根都没被染色就去另外一个重心。

然后可能需要稍微卡一下询问次数 /kk

Code

QOJ Link