题目链接

题意

给定一棵 $n$ 个点的有边权有根树，和一个长为 $n$ 的序列 $a$。接着有 $m$ 个操作：

1. 给定 $l,~r$，将区间 $[l,~r]$ 中的每一个元素变为它在树上的上一级结点编号。
2. 给定 $l,~r$，问区间内 $[l,~r]$ 内与根节点距离最近的结点到根节点的距离。

$n,~m \le 2 \times 10^5$，边权为非负整数

分析

考虑以 $\sqrt n$ 大小分块，对每一块维护块内答案。

容易发现当只有整块操作时，如果在某一时刻某个块内元素 $A$ 到达了块内另一元素 $B$ 在该时刻前已到达过的位置，在接下来的操作中 $A$ 将不再会对该块块内答案产生贡献，因为接下来的每一时刻 $B$ 都一定为 $A$ 的祖先，其到根节点距离一定小于 $A$ 到根节点距离。因此我们可以考虑在遇到这样的情况时将 $A$ 从块中删除，不再在之后的操作中更新 $A$，显然不会对答案产生影响，这样的话块内所有节点在树上对应最多只会覆盖整棵树 $O(n)$ 个结点，即块内时间复杂度为 $O(n)$，总时间复杂度为 $O(n \sqrt n)$。

在修改区间的边缘所在块时，我们可以考虑直接暴力重算修改部分。虽然这可能导致部分已删除的点被重新加入块内，但是并不影响块内总体时间复杂度。需要暴力将块内结点向上跳时可以使用重链剖分维护，在同一重链中跳跃的时间复杂度为 $O(1)$，每个点经过轻边的次数不超过 $O(\log n)$，因此全局花在暴力上移结点的总时间复杂度为 $O(n \log n)$。

总时间复杂度 $O((n+m) \sqrt n)$，比较考验卡常水平，可以参考代码中的卡常方法。

代码

View On Github