边分治比点分治更适合高阶树的核心优势是“不爆栈”和“分裂更均衡”；因删边总可得两连通块大小≤⌊n/2⌋，而点分治在星形树中递归深度退化为o(n)。
边分治为什么比点分治更适合高阶树
边分治的核心优势不是“更快”，而是“不爆栈”和“分裂更均衡”。点分治依赖找重心，但当某个节点度数极大（比如 10⁵ 级别的星形树），它的子树大小极不均衡：一个子树含 n−1 个节点，其余全是单点。递归深度退化为 O(n)，且每次分割后仍有巨型子树，导致时间复杂度失控。边分治绕开节点，直接切边——只要删掉一条边，就能把树拆成两个连通块，而最优切割边总能让两块大小都 ≤ ⌊n/2⌋。这在理论和实践中都更鲁棒。
如何识别并预处理高度数节点引发的边分治陷阱
直接对原始邻接表跑边分治会出问题：度数过大的节点（如 u 的 adj[u].size() > 1000）会导致枚举其所有邻边时，候选切割边集合膨胀，且很多边切了之后根本不能平衡子树。必须预处理：
- 先用一次 DFS 统计每个节点度数，标记所有
deg[u] > sqrt(n)的“重节点” - 对每个重节点
u，将其所有邻接边(u, v)拆成“轻-重边”：若v是重节点，这条边保留；否则将v及其整个子树打包成一个虚拟节点，再连向u - 最终得到一棵“压缩树”，节点数 ≤ 2√n，边数也受控，此时再跑标准边分治才安全
边分治中 dfs_size 和 find_centroid_edge 的关键修改点
标准边分治的 dfs_size 函数假设树是稀疏的，但高阶树下它可能反复遍历同一个重节点的大量邻边，造成 O(n²) 时间。必须改：
C++ Code Review Master
下载
组合式C++代码评审方案，融合静态分析、AI推理、多轮迭代评审和C++专项检查，适用于PR审查、增量代码审查、全项目评审和代码质量评分，触发词包括review cpp、cpp代码评审、C++review、代码审查。
-
dfs_size(u, parent)中，跳过所有已压缩的虚拟子树，只对真实轻边递归 -
find_centroid_edge不再暴力枚举所有边，而是对每条边(u, v)，只计算min(size[v], n - size[v])，且一旦发现该值 ≥ n/2 就立即返回——因为边分治只要求“存在一条边使两块 ≤ n/2”，不需要找最优边 - 注意：
size[v]必须是压缩后子树的实际节点数，不是虚拟节点的编号数，否则平衡性失效
合并信息时避免重复统计重节点贡献
边分治的“跨边路径”处理（如路径权值和、LCA 查询）最容易在这里翻车。高阶树中，大量路径经过同一个重节点 u，如果对每条经过 u 的边都独立统计，u 的贡献会被放大 deg(u) 次。正确做法是：
- 在每层分治中，只考虑被切割边
(a, b)分隔的两部分，所有合法路径必横跨a和b所在连通块 - 对
a块内所有节点，预处理到a的距离；对b块同理；然后双指针或桶统计满足条件的点对 - 绝对不要以重节点为中心做“点式聚合”，那本质上又退化回点分治的坏性质
真正难的不是写对第一次分治，而是确保每一层递归都维持压缩结构和大小约束——漏掉一次 size 更新或误用原始度数，整棵树就垮在第三层递归里。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
