# 大圣诞树 — 补充题解

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

## 重心分解与局部可达集合

该方案保留出题人的重心分解维护直径思想，并补齐路径删边接口。对每个重心 $c$ ，考虑当时分解组件内的树，以 $c$ 为根建立局部 Euler 序。每个点记录距离、所在第一条分支及局部子树区间。只在这个组件内考察仍能通过亮边到达 $c$ 的点。

每个分支用有序集合保存活跃点的 `(距离,编号)` ，另一集合维护每个非空分支的最大距离。加入代表重心自身的零距离候选，从不同分支中取最大的两个距离，相加就是经过 $c$ 的最长亮边路径。全局有序集合维护各重心候选。

## 删除一条边

只考虑该边两端共同拥有的重心祖先。相对于每个这样的重心，较深端点的局部子树就是因删边而失去连通性的部分。用局部活跃 Euler 下标集合的 `lower_bound` 找区间内的点，逐个删除，同时更新分支最大值、重心候选及全局候选。若该子树早已与重心断开，区间内没有活跃点，无需再做工作。

每个点在每个重心层级最多删除一次。首次删除之后无需恢复。初始暗边通过同样接口删除；每次路径操作使用父亲、LCA 与跳跃并查集，只把尚亮的边送入该接口。实现用显式栈构造重心分解和 Euler 区间，不对原树深度递归。

## 正确性

删边在每个相关局部树里恰好切断较深端点的整棵子树，所以活跃集合始终准确。来自不同分支且活跃的两个点，其唯一路径经过重心且全部亮，候选都合法。

反过来，对任意亮边路径的两端，取重心分解中首次把它们分到不同分支的重心；若一端就是重心也允许。该重心位于两端路径上，两端在其组件中均活跃，因此该路径长度不超过此处维护的候选。于是全局最大候选恰为森林直径。

## 复杂度与取舍

共有 $O(N\log N)$ 条点与重心记录，各记录的集合插入、删除花费 $O(\log N)$ .路径的首次删边定位另需 $O(M\log N)$ ，总时间为 $O(N\log^2N+M\log N)$ ，空间 $O(N\log N)$ .全局集合取最大只需常数时间。

它可按输入顺序立即作答，但有序集合占用更多时间和内存。本题保留 1024 MiB 内存，并按实测为在线方案留出时间；默认推荐更简单且更快的[离线方案](solution.zh.md)。Codex（GPT-6）完成局部区间删除实现、迭代遍历、输入适配与验证；程序见 [alternative.cpp](alternative.cpp)。

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