粉碎者 题解¶
解法与取舍¶
出题人解法：限制度数、边分治与单调队列。 边分治方案保证 \(O(n\log(n+1))\) 时间，作为标程。点分治与线段树的通用上界为 \(O(n\log^2(n+1))\) ，但在测量数据上更快且使用更少内存。两者并列介绍：前者的通用最坏界更好，后者在这些输入上的实际开销更小，原因见下文。
程序与署名： std.cpp 实现出题人解法；Codex（GPT-6）负责实现整理、边界处理与证明说明。Codex（GPT-6）采用的点分治与线段树见 alternative.cpp 和并列方案题解。
把点权放到边上¶
为原边 \((u,v)\) 设置权值 \(v_u+v_v\) ，长度为一。任意非空边路径的边权和加上两个端点的点权，恰好是原路径点权和的两倍：内部点被相邻两条边各计一次，端点由额外项补齐。因此后面只维护倍增收益，最终除以二。
用虚点将最大度数限制为三¶
任选原根。若 \(u\) 的孩子依次为 \(v_1,\ldots,v_k\) ，建立虚点链 \(u,z_1,\ldots,z_k\) ，链边长度和权值均为零；再用长度为一、权值为 \(v_u+v_{v_i}\) 的边连接 \(z_i\) 与 \(v_i\) .原点之间路径的长度和收益都不变，但只能选择原点作为端点。
共有 \(2n-1\) 个点，最大度数至多三。每条长度为一的边仍记录对应的原边；虚边仅用于连接，不输出答案。
平衡边与深度配对¶
在当前连通块中选择使删除后较大部分最小的边 \(e\) .度数至多三的树存在两侧大小均至多约 \(2s/3\) 的边：取点重心，其最大相邻分量大小至少 \((s-1)/3\) 且至多 \(s/2\) ，对应边满足此界。因此分治层数为 \(O(\log(n+1))\) .
设切边长度为 \(\ell_e\in\{0,1\}\) 、权值为 \(w_e\) .从两侧端点分别收集各点的深度 \(d_x\) 和边权和 \(s_x\) .对原点端点 \(x,y\) ，合法条件及倍增收益为
另一侧按深度保存 \(s_y+v_y\) 的最大值；虚点不能成为候选端点。由于存在零长度边，普通遍历顺序未必按深度排列，程序用深度桶进行线性排序，再用单调队列处理两端单调递减的查询窗口。每个深度只入队、出队一次，两侧各查询一遍。
更新所有经过的原边¶
每个端点得到最佳完整路径收益后，逆遍历向本侧切边端点传播最大值，沿途更新经过的原边；若切边本身是原边，也更新它。一个候选只传播到该候选一定经过的边，故不会误报。任何跨切边路径经过的边都有一侧端点的记录向它传播，故不会漏掉。
删去切边后继续处理两侧，每条有边路径恰在首次被切断时进入上述配对。最后，一个原点的答案是其所有相邻原边答案的最大值除以二；任何包含它的非单点路径都会经过其中一条边。若 \(L=0\) ，还需用该点自己的点权更新答案。
复杂度与边界¶
每层各连通块总规模为 \(O(n)\) ，各块寻找切边、深度桶、窗口和传播均为线性时间，故总时间 \(O(n\log(n+1))\) ，空间 \(O(n)\) .大小至多八的块直接枚举原端点对。原树和分治都用显式遍历；路径和使用 64 位整数。
单点树、允许零条边、全负权以及找不到合法长度均单独覆盖。无解时输出 -1061109568 ，不把无解标记参与除法或加法。
理论复杂度与实际耗时¶
测量中，三十万节点随机树上，边分治版约为 0.959 秒，点分治＋线段树版约为 0.407 秒；一百万节点随机树上分别约为 4.106 和 1.978 秒。这里不仅是“差距拉不开”，而是通用最坏界较高的程序实际更快。主要原因可从它们处理的树和具体操作看出。
边分治方案扩大了参与分治的树¶
边分治方案将 \(n\) 个原点展开为 \(2n-1\) 个点，把 \(n-1\) 条原边改成 \(2n-2\) 条边。分治寻找切边、收集两侧记录时，虚点和零长度边也要访问。只有原点能作端点，但虚点仍参与连接与答案传播。
它还需分别整理两侧深度桶、做两次单调窗口查询、传播到原边，最后再由边答案恢复点答案。当前实现的访问记录为 32 字节，点分治方案为 24 字节。基础测量中的峰值工作集分别约为 63.75 和 38.27 MiB；这支持存储开销确有差别，但不是缓存性能的直接测量。
同一输入对两种分治的难度可能不同¶
最明显的是星形树。点分治删掉中心后，剩下的全是单点；最上层深度只有一，线段树查询也是常数工作量。因此点分治算法在这族星形输入上的实际算法工作为 \(O(n)\) ，并未达到它的通用 \(O(n\log^2(n+1))\) 界。
边分治为了消除中心的高度数，将星形展开成一条带叶子的虚点链，仍要做多层平衡边分治。“原来是浅树”并不代表展开后仍只用一次分治就能拆完。这是输入形状和分解方式的区别，不能只用两个最坏复杂度式子的大小关系判断。
| 三十万节点用例 | 边分治方案分治块大小之和 | 点分治方案分治块大小之和 | 点分治方案最大收集深度 | 备用查询循环总轮数 |
|---|---|---|---|---|
| 星形 | 10,578,542 | 599,999 | 1 | 299,999 |
| 平衡二叉树 | 10,586,647 | 4,906,621 | 18 | 10,773,528 |
| 随机树 | 10,686,040 | 2,917,867 | 26 | 11,405,052 |
“分治块大小之和”统计每次寻找分治中心或切边时处理的整个连通块；同一点在不同轮次会重复计数。两版均计入其小块终止处理之前的遍历，所以这能直接比较遍历规模，但它既不是总指令数，也不包含配对阶段的全部开销。随机树中边分治方案这个计数约为点分治方案的 3.66 倍；星形中约为 17.63 倍。
本表的随机树由随题生成器逐点连接已有父节点并重新编号得到，不能由这份输入的浅度推断所有随机树都具有同样的表现。
点分治方案的额外对数也经常较小¶
线段树按当前收集深度 \(D_c\) 建立，查询取决于 \(\log(D_c+2)\) ，并会受长度上限、空窗口和小分治块影响。随机树统计中平均每个端点查询约 3.91 轮，而不是每次都走整棵树对应的最大对数层数。深链、宽窗口确实能增加这些轮数，但仍要与边分治方案扩树及多次线性扫描的成本比较。
因此，边分治方案给出更好的通用最坏界，点分治方案在这些树形上处理更小的状态、较浅的深度范围，并少做部分转换。它们是有实际取舍的并列解法。计数记录核实了上述工作量差异；没有分阶段计时或缓存采样，所以不为每个原因分配未经测量的时间占比。扩大规模几倍只缓慢增大额外对数，未必抵消这些差异；现有结果也不排除别的树形、窗口或平台改变先后顺序。
深链与特殊树形能否改变先后顺序¶
定向构造覆盖梳形树、长短臂树、细分二叉树、双扫帚树、递归梳形树，以及宽窗口、二次幂附近窗口和随机重编号长链。它们分别放大深度范围、分治层数、有效查询数或改变访问顺序。在已测输入中，点分治与线段树仍更快。
例如，长链的边数范围取 \([1,\lfloor(n-1)/3\rfloor-5]\)，三十万、六十万和一百二十万节点时，点分治与线段树耗时分别约为边分治的 0.58、0.56 和 0.55 倍。即使随机重编号使两份程序都明显变慢，一百二十万节点长链上仍为 8.143168 秒对 4.452477 秒，线段树方案更快。后两种规模均只用于性能实验。
因此，现有构造没有让额外对数抵消扩树、遍历和配对方式的常数差异，也没有形成通过缩短时限排除线段树方案的依据。这个结论针对已测实现、范围和输入族，不是所有树形或平台上的速度保证。压力数据由 Codex（GPT-6）提供，复现与详细记录见树形构造与性能。
验证与性能¶
各方案的重复计时与峰值内存记录见评测环境与性能。