大圣诞树 — 题解¶
出题人解法：重心分解维护删边直径。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。出题人的重心分解删边维护直径思想另行保留为在线补充方案；两者均按当前输入规格重新实现并验证。