# 动态树方案

Codex（GPT-6）：应用标准 Link-Cut Tree，维护每块垫子到出口的有根路径。该方案不依赖操作分批保证，但在当前完整数据上超过参考时限，见[主解的比较](solution.zh.md)。

## 有根树建模

增加出口节点，把垫子 $i$ 的父节点设为 $i+K_i$ ，越界时设为出口。父节点编号总是更大，因而没有环，每个点最终到达出口。查询答案就是该点到出口的边数。

用 Link-Cut Tree 维护这棵有根树。辅助伸展树的中序表示一条从祖先到后代的首选路径；每个辅助节点记录这条路径中的节点数，不包含虚子树大小。`Access(u)` 把出口到 $u$ 的路径暴露在同一棵辅助树中，再把 $u$ 伸展到根。此时辅助树大小减一就是路径边数。

修改父节点时，先 `Access(u)` .其左辅助子树包含全部祖先，断开这条辅助连接就切断了 $u$ 到其原父节点的逻辑边，祖先之间的边仍然保留。然后将 $u$ 的路径父指针设为新目标。新目标编号更大，不可能在 $u$ 的后代中，因此不会产生环。

## 正确性与复杂度

初始化的父边恰好等于弹跳转移。切边与连边只替换本次修改的那条转移；其余父边保持不变。因此动态树始终表示当前弹跳规则。暴露路径后的节点数准确计算从起点到出口的边数，也就是弹跳次数。

由于根始终是出口，本题不需要换根或路径反转。标准伸展树访问的摊还分析给出每次操作 $O(\log n)$ ，整体为 $O(n+q\log(n+1))$ ，空间为 $O(n)$ ；单次操作不保证最坏对数时间。初始化直接设置路径父指针，辅助树初始均为单点，耗时线性。

[实现](alternative.cpp)与标准程序使用相同的两种输出模式和越界起点规则。当前实测说明一般性需要常数开销，不能据渐进界声称它在这些分批数据上更快。