Luogu6779 [Ynoi2009] rla1rmdq

题意：给定一棵 个点的树，边有边权。

维护长为 的序列 ，支持下列操作 ：

• 对于 ，令 变为 。（特殊地，定义 ）

• 查询

允许离线，，时限 ，空限 。

---

分块。

对于每个块，记 为整块一起上跳的次数。

对于修改或查询中的散块，暴力计算并将 置为 。

这需要支持快速求树上 级祖先，可以使用重剖。每个节点只会向上走，只会付出 的额外代价，除此之外每次询问可以看做 。

接下来只需考虑全局修改和询问的子问题，用于处理整块。

• 观察 ：若某个关键点 的祖先存在其他关键点，可以忽略 的贡献。

于是，在树上记录该点是否被经过，若某个关键点的父亲被经过，则可以将其删除。每个点只会被经过一次，这样只会移动 次。

注意，在重构块时，原先被删除的点可能再次跻身候选点之列。

对于删除的点，要打上时间戳，这样在暴力重构时就可以知道要跳多少步。

逐块处理以节省空间。时间复杂度 ，空间复杂度 。

明天也要开心哦~