# 大圣诞树 — 题解

出题人解法：重心分解维护删边直径。Codex（GPT-6）：离线逆序方案，以及在线方案的局部 Euler 区间、路径接口和迭代实现。

## 把删边倒过来做

每条亮边最多第一次熄灭时有作用。以结点 1 为根，预处理父亲、深度及倍增 LCA。边用它的较深端点表示。另设跳跃并查集：`Find(u)` 返回向根走时尚未被跳过的最高连续已删除段的上端，初始暗边提前跳过。

对查询 $u,v$ 求 $w=\operatorname{LCA}(u,v)$ .分别从两端调用 `Find` ，只要当前深度大于 $w$ ，就记录该父边首次在本查询被删除，再令其跳向父亲的 `Find` .每条边只被记录一次。深度条件必须检查跳跃后的结点，因为它可能已经越过 $w$ .

建立全部操作完成后的亮边森林。每个连通分量维护大小、直径长度及一对直径端点。倒序处理查询：**先保存当前全局直径作为该次操作后的答案**，再恢复这次首次删除的边。

## 合并直径

若两个分量的端点分别为 $(a,b)$ 和 $(c,d)$ ，合并后只需比较旧直径以及四个跨分量距离：$d(a,c),d(a,d),d(b,c),d(b,d)$ .距离由深度和 LCA 在 $O(\log N)$ 内得到。虽然使用完整树上的距离，两个分量刚通过边相连后，该唯一树路径也全部属于新分量。

所用引理：在树中，给定任一直径端点 $a,b$ ，任一点 $z$ 的最远距离由 $a,b$ 之一取得。证明可将点投影到直径路径：若长度为 $D$ ，点 $x$ 的投影位置为 $s$ ，离路径高度为 $h$ ，直径的最大性给出 $h\le\min(s,D-s)$ .将 $z$ 投影为 $t$ 、高度为 $h_z$ ，则 $d(z,x)\le h_z+|t-s|+h\le h_z+\max(t,D-t)$ ，后者就是到两个端点距离的最大值。对连接边两侧分别应用引理，得到四个跨端点候选的充分性。

## 正确性

跳跃只越过已暗边，所以每次恰好记录路径上新变暗的边。最终森林因此准确。倒序开始时森林是全部查询后的状态；恢复查询 $i$ 首次删除的边后，恰好回到查询 $i-1$ 后的状态，初始暗边从不恢复。直径合并引理保证每个分量记录准确。逆序只增边，全局最大值只需取新旧最大，无需删除旧候选。归纳可知保存的全部答案正确。

## 复杂度与贡献

预处理、至多 $N-1$ 次合并和 $M$ 次 LCA，总计 $O((N+M)\log N)$ 时间，$O(N\log N+M)$ 空间。跳跃采用路径压缩，树遍历使用显式序列，避免深链递归。

Codex（GPT-6）提出并实现此离线逆序方案，见 [std.cpp](std.cpp)。出题人的重心分解删边维护直径思想另行保留为[在线补充方案](solution-alternative.zh.md)；两者均按当前输入规格重新实现并验证。

[题面](statement.zh.md) · [正式数据计划](tests/plan.json) · [生成器](tests/generate.py) · [测量记录](../../../docs/benchmark-R32.json)