NOI D1T2

Register_int · 2026-07-22 14:04:01 · 题解

简单题。

我们的策略应当是这样的：选择 y_i 所在的一个连通块全部往 y_i 走，其余点随机跳。这个策略与 x_i 所在的位置是几乎无关的，因为 x_i 要么直接走过去，要么随机跳一次变成一般情况。所以只要对于所有 y_i 预处理答案即可。

设当前连通块内每个点到根的距离为 d_i，点数为 k。那么期望步数为 T=(n+\sum d_i)/k。拓展连通块的过程显然可以贪心 bfs，我们只需要判断什么时候应该停止。推一推式子可以发现，拓展是优的，当且仅当 T>kd。这说明我们取得一定是所有与 y_i 距离 \le d 的点，并且显然可二分判定。上点分树维护即可，查询距离用 \mathcal{O}(n\log n)-\mathcal{O}(1) LCA 即可，时间复杂度 \mathcal{O}(n\log^2n+m)。事实上你写得好直接就过了。

继续发掘性质。观察可得：树上任意两个相邻的点，他们取得距离差 \le 1，于是先二分一个点再拓展即可，时间复杂度 \mathcal{O}(n\log n + q)。

据说还能长剖做 \mathcal{O}(n+q)。但我不会。