如果你刷树上的题刷到一定量大概率早就听过dsu on tree这个名字。它还有一个更直白的叫法树上启发式合并。我第一次看到这个名字的时候以为是某种并查集技巧真正学完才发现它和并查集没有任何关系它解决的是“对每个节点询问它子树内部的某种统计信息”这一类问题。暴力做法是每个节点都去遍历一次子树复杂度 O(n²)而 dsu on tree 可以稳定压到 O(n log n)实现思路非常固定轻重儿子划分、保留重儿子贡献、暴力加回轻儿子贡献。这篇文章就是我沉淀下来的 dsu on tree 题集整理包含题目分层方式、可复用的 AC 代码以及刷题时最容易踩的坑。现在直接把核心内容和代码记录在这里给同样在整理树上问题题集的人做个参考。1. dsu on tree 是什么为什么值得建一个题集1.1 一句话版本dsu on tree 是一个离线处理子树统计问题的算法。它先把树按照子树大小分出重儿子和轻儿子然后对每个节点按固定顺序递归先递归处理所有轻儿子每次处理完都把贡献清空再递归处理重儿子处理完之后保留贡献把各个轻儿子子树里的点暴力加回全局统计把当前节点自己也加进去此时全局统计正好是当前节点的完整子树信息如果需要记录答案如果当前节点是被当作轻儿子递归进来的就清空整棵子树的贡献。这个过程看起来就是“一个节点被反复暴力加入很多次”但轻重儿子划分保证了每个点被暴力加入的次数只有 O(log n)所以总复杂度是 O(n log n)。很多人容易误解的是 DSU 这个名字。DSU 通常是并查集但这里根本没有并查集操作。树上启发式合并里真正借用的是“启发式”三个字每次都保留信息最丰富的那个分支牺牲掉其他分支让暴力次数可控。理解了这点题目不管怎么变核心都是维护addOne和removeOne这两个单点状态转移函数。1.2 复杂度为什么是 O(n log n)先说结论每个节点被“暴力加入”的次数等于它到根路径上轻边数量的 O(1) 倍而任意节点到根的轻边数量不超过 O(log n)。原因是轻儿子的子树大小最多只有父节点子树大小的一半。如果某个非重儿子的大小超过了半棵子树那它就会成为重儿子。所以每次经过一条轻边节点所在的子树大小至少翻倍而节点总数只有 n所以轻边数量自然被 log n 限制住。实际递归中一个点什么时候会被“暴力加入”只有当它属于某个轻儿子的子树、而祖先需要把该轻儿子的贡献加到全局统计时它才会被重新遍历。重儿子这条链上的贡献是可以直接继承的不需要重复统计。于是每个点被加入的次数就是它头顶的轻边数量加一次自身加入整体 O(n log n)。空间上只需要 O(n) 的统计数组不需要额外套数据结构这也是它在赛场上非常好用的原因。1.3 什么样的题该收进题集我建题集时给自己定了一个标准凡是“无修改、离线、子树区间统计”的题优先放进 dsu on tree 题集。具体来说常见适合的类型有统计每个子树内出现次数最多的颜色或者多个众数的编号之和统计每个子树内深度等于某个值的节点个数统计每个子树内不同颜色数量统计每个子树内满足某种路径长度限制的点对数量统计子树内按位异或相关的结果比如路径异或值出现次数把某个节点的重儿子信息保留后合并其他轻儿子信息本质是给树形 DP 做优化。不适合的类型也很明显如果操作本身支持在线修改或者需要频繁删除非整棵子树的信息dsu on tree 就很难处理。数据范围如果大到 n10^6也要谨慎虽然复杂度是 O(n log n)常数并不小。2. 我的题集是怎么分层的2.1 分层标准从模板到变种一开始我刷 dsu on tree 的时候把所有题塞在一起结果很混乱。后来整理成三层A 层、B 层、C 层。A 层是纯模板题只要会背板子就能过。主要价值是把手感和代码顺序练熟。这类题通常只要求统计子树内的颜色、深度这类一维信息。B 层是在模板之上加一层转化。比如把路径距离问题转化成深度差问题把异或问题转化成前缀异或问题。这层最值得收集因为它能真正体现 dsu on tree 的“统计量怎么设计”比“代码怎么写”更重要。C 层是综合题可能还要配合树形 DP、容斥、可撤销哈希、线段树合并等知识。这类题不一定非要用 dsu on tree也可能存在更优做法但在 dsu on tree 题集里放几道可以明确它的能力边界。2.2 题集一览表我大概按这个结构维护题目清单层级题目类型统计量核心代码复用点A1子树众数出现次数最多的颜色编号之和cnt freq sumAtFreqA2子树深度计数子树内 dep d 的节点数cnt[dep]A3子树不同颜色数有多少种不同颜色首次加入时判断 cnt0B1子树内距离为 k 的节点数与当前点距离为 k 的点数cnt[dep] dep 偏移B2子树内路径异或值计数路径异或值等于 x 的路径数前缀异或 cntB3全局距离为 k 的点对数所有无序点对以 u 为 LCA 的分支合并C1子树内按位统计类二进制位上的奇偶性cnt bit 逐位维护C2子树内颜色最小值类出现次数最小的颜色平衡树或堆辅助这张表里每一行对应一个独立的题目场景实际训练时根据数据范围和题目细节调统计量即可。2.3 每道题只记一句话备注题集不是越多越好。我现在的习惯是每道题只保留一句话备注写在模板代码的注释里。比如 A2 的备注是“查询多个 d 时用 vector 离线挂在节点上”B2 的备注是“路径异或转化为根到点异或再通过 cnt 统计”。这样考前扫一眼就能把所有变种串起来而不是每次重新读一整道题。另外所有 AC 代码统一维护成两个文件一个是纯板子文件另一个是带例题的完整代码文件。板子文件里只保留dfs1、dfs2、addOne、removeOne这四件事其他乱七八糟的优化都不放。这样碰到新题时复制板子再改addOne和removeOne就行。3. 三类代表题与可复用的 AC 代码3.1 A 层基础板子子树众数编号和先给出一道最经典的板子给一棵 n 个节点的树每个节点有一个颜色对于每个节点 u求 u 的子树中出现次数最多的颜色的编号之和。注意如果多个颜色出现次数同时最大需要把这些颜色的编号全部加起来。这道题用 dsu on tree 的完整 AC 代码可以写成下面这样#include bits/stdc.h using namespace std; const int N 100000 5; int n; vectorint g[N]; int colorOfNode[N]; // 每个节点的原始颜色 int idOfColor[N]; // 离散化后的颜色编号 - 原始颜色 int h[N]; // 每个节点的颜色编号 int sz[N], son[N], dep[N]; int cnt[N]; // cnt[c]颜色 c 当前出现次数 int freqCnt[N]; // freqCnt[t]出现次数为 t 的颜色有多少种 long long sumAtFreq[N]; // sumAtFreq[t]出现次数为 t 的颜色编号和 int mxCnt; long long ans[N]; void dfs1(int u, int p) { sz[u] 1; for (int v : g[u]) { if (v p) continue; dep[v] dep[u] 1; dfs1(v, u); sz[u] sz[v]; if (sz[son[u]] sz[v]) son[u] v; } } void addNode(int u) { int c h[u]; int old cnt[c]; if (old) { freqCnt[old]--; sumAtFreq[old] - idOfColor[c]; } int nw old 1; cnt[c] nw; freqCnt[nw]; sumAtFreq[nw] idOfColor[c]; if (nw mxCnt) mxCnt nw; } void removeNode(int u) { int c h[u]; int old cnt[c]; freqCnt[old]--; sumAtFreq[old] - idOfColor[c]; int nw old - 1; cnt[c] nw; if (nw) { freqCnt[nw]; sumAtFreq[nw] idOfColor[c]; } } void applySubtree(int u, int p, bool add) { if (add) addNode(u); else removeNode(u); for (int v : g[u]) { if (v p) continue; applySubtree(v, u, add); } } void dfs2(int u, int p, bool keep) { // 先处理轻儿子处理完就清空 for (int v : g[u]) { if (v p || v son[u]) continue; dfs2(v, u, false); } // 再处理重儿子保留贡献 if (son[u]) dfs2(son[u], u, true); // 把轻儿子子树暴力加回来 for (int v : g[u]) { if (v p || v son[u]) continue; applySubtree(v, u, true); } // 加上当前节点自己 addNode(u); // 此时全局统计正好是 u 的整个子树 ans[u] sumAtFreq[mxCnt]; // 如果当前节点是作为轻儿子被递归进来的清空整棵子树 if (!keep) { applySubtree(u, p, false); mxCnt 0; } } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin n; vectorint allColors; allColors.reserve(n); for (int i 1; i n; i) { cin colorOfNode[i]; allColors.push_back(colorOfNode[i]); } sort(allColors.begin(), allColors.end()); allColors.erase(unique(allColors.begin(), allColors.end()), allColors.end()); for (int i 1; i n; i) { h[i] lower_bound(allColors.begin(), allColors.end(), colorOfNode[i]) - allColors.begin() 1; idOfColor[h[i]] colorOfNode[i]; } for (int i 1; i n; i) { int u, v; cin u v; g[u].push_back(v); g[v].push_back(u); } dfs1(1, 0); dfs2(1, 0, true); for (int i 1; i n; i) { cout ans[i] \n; } return 0; }这个版本比很多人写的模板复杂一点因为它处理了“多个众数编号和”的情况。大部分 dsu on tree 只需要维护出现次数最大值不需要维护编号和。如果题目只问众数是谁就可以把sumAtFreq数组整个删掉freqCnt也可以简化成检查cnt[c] mxCnt。我之所以保留这个完整版本是因为它能处理好几个常见的众数变体题。注意removeNode里没有去实时维护mxCnt因为删除只会发生在整棵子树清空时清空完直接把mxCnt 0即可不需要做复杂的最大值回退。3.2 A 层变体子树深度计数另一类很常见的板子是对于每个节点 u回答多个询问“u 的子树内深度为 d 的节点有多少个”。思路很简单全局维护一个cnt[dep]表示当前统计集合内某个深度的节点数量。加到节点 x 时执行cnt[dep[x]]删除时执行cnt[dep[x]]--。查询时直接把答案记成cnt[d]。核心代码就是去掉颜色相关的所有部分void addNode(int u) { cnt[dep[u]]; } void removeNode(int u) { cnt[dep[u]]--; } void applySubtree(int u, int p, int delta) { if (delta 1) addNode(u); else removeNode(u); for (int v : g[u]) { if (v ! p) applySubtree(v, u, delta); } } void dfs2(int u, int p, bool keep) { for (int v : g[u]) { if (v ! p v ! son[u]) dfs2(v, u, false); } if (son[u]) dfs2(son[u], u, true); for (int v : g[u]) { if (v ! p v ! son[u]) applySubtree(v, u, 1); } addNode(u); for (auto q : queries[u]) { ans[q.id] cnt[q.dep]; } if (!keep) { applySubtree(u, p, -1); } }这里唯一容易错的是queries[u]的处理。如果每个节点只问一个深度直接查完就完事。如果问多个深度必须把询问完整挂在对应的节点上等递归到该节点时一次性处理。我第一次写的时候就犯了这个错在递归过程中又去遍历所有询问导致复杂度多了一个 O(q) 的乘法直接超时。3.3 B 层进阶统计距离为 k 的点对再看一个更有价值的变种题给一棵树和一个整数 k统计有多少无序点对 (u, v) 满足树上路径长度等于 k。这里的 k 固定。这个题目看起来像点分治但用 dsu on tree 也能做实现思路是枚举每个点作为路径的 LCA然后合并子树信息。先预处理出每个节点的深度把当前统计集合中的节点按深度计数。当递归到节点 u 时需要保证全局cnt集合里已经包含 u 本身、重儿子子树的全部贡献以及已经处理过的轻儿子子树贡献。然后对于当前要处理的轻儿子子树 v先遍历 v 子树里的每个点 x用公式targetDep dep[u] * 2 k - dep[x]也就是和 x 组成合法路径、且 LCA 是 u 的那个点它的深度应该是 targetDep。用cnt[targetDep]加到总答案里。统计完整个 v 子树后再把 v 子树全部加入cnt。核心代码long long total 0; void collect(int u, int p, vectorint nodes) { nodes.push_back(u); for (int v : g[u]) { if (v ! p) collect(v, u, nodes); } } void dfs2(int u, int p, bool keep) { for (int v : g[u]) { if (v ! p v ! son[u]) dfs2(v, u, false); } if (son[u]) dfs2(son[u], u, true); addNode(u); // cnt[dep[u]] // u 与已合并集合中的点组成距离 k 的点对 total cnt[dep[u] k]; for (int v : g[u]) { if (v p || v son[u]) continue; vectorint nodes; collect(v, u, nodes); for (int x : nodes) { int targetDep dep[u] * 2 k - dep[x]; if (targetDep 0 targetDep n) { total cnt[targetDep]; } } for (int x : nodes) { addNode(x); } } if (!keep) { applySubtree(u, p, -1); } }这里total cnt[dep[u] k]统计的是 u 到已合并集合里深度为 dep[u]k 的点的距离。注意如果 k0这个统计会把 u 和它自己算进去所以 k0 时要单独处理不要直接套这个式子。这个例子最值得放到题集里的原因是它展示了 dsu on tree 不只是“统计子树内部信息”还可以用来做路径合并统计。核心思想依然是单点加入和按深度统计但把点对的合并顺序安排好了就能在不重复统计的情况下覆盖所有 LCA 情况。3.4 C 层的思路与边界C 层我一般不放太多因为很多综合题其实有更优解法。比如有些题可以用线段树合并做复杂度同样是 O(n log n)但支持更多维护操作有些路径统计题点分治写起来更顺有些带修改的子树题需要用树上莫队。C 层题集的意义在于提醒自己dsu on tree 适合“把多个儿子的信息合并到重儿子”的场景如果添加、删除单点信息的代价很大它就不是好选择。维护单点信息的代价如果超过 O(1)总复杂度就会变大。比如要维护子树中位数用 dsu on tree 加平衡树复杂度会到 O(n log² n)虽然能跑但未必比线段树合并更好。所以 C 层题集更像是“对比题”用来帮助建立算法选择的直觉。我会在每一道 C 层题旁边标注一句为什么这道题用 dsu on tree 而不是线段树合并或点分治以及在哪种数据范围下需要换做法。4. 刷题集时最容易踩的 6 个坑4.1 add 和 remove 的顺序不能乱dsu on tree 的固定顺序是先轻儿子递归并清空再重儿子递归并保留然后加轻儿子子树然后加当前节点查答案最后按需清空。这个顺序少一步都不对。比如先加重儿子再处理轻儿子重儿子的贡献会被轻儿子的清空误伤如果查询放在清空之后统计到的就是空集合如果轻儿子和重儿子都递归后才加当前节点某些题目也可以但逻辑上不够统一。我建议把所有顺序写成注释放在板子开头每次抄模板时照着执行不要靠记忆。4.2 查询时机必须在清空之前答案要在当前节点的完整子树信息加入全局统计后、清空之前记录。很多新手在dfs2一开始就查询或者等keepfalse清空后才查询结果得到的一定是错误答案。这一点尤其在处理多个询问时容易犯必须把询问挂在节点上在查询时机统一处理不能在递归中途随意插入查询。4.3 重儿子选错复杂度直接退化重儿子必须是子树大小最大的儿子。如果不加这个划分只是随便选一个儿子保留那每个节点被暴力加入的次数就不受 O(log n) 约束整体可能退化成 O(n²)。还有一个隐藏问题当多个儿子大小相同时任选一个作为重儿子即可但不能不选。为了保险我一般用if (sz[son[u]] sz[v]) son[u] v;这种严格不等式初始化son[u]0sz[0]0。4.4 只清 cnt 不清辅助状态像众数那道题里维护了mxCnt、sumAtFreq等额外状态清空整棵子树时如果只把cnt减掉而mxCnt还停留在旧值下一次addNode判断if (nw mxCnt)就会出问题。清空完整棵子树的贡献之后cnt全为 0这个时候可以直接把mxCnt 0。但要注意如果当前节点 keeptrue是不能清空的所以这个重置只能写在if (!keep)分支里。4.5 把整个子树逻辑塞进 addOne这是我自己踩过最多次的坑。addOne和removeOne应该只负责单个节点的状态更新子树批量加入交给applySubtree或循环遍历去做。如果图省事把一个子树的全部逻辑写进addOne后面题目一变整个函数就得重写。维护这个边界很重要单点函数保持纯净批量操作和遍历逻辑放在外层这样代码才是真正可复用的。4.6 数据范围大时注意递归栈和离散化n10^5 级别的链式树上普通 dfs 递归很容易爆栈。可以在训练环境里把栈大小调大但很多评测环境并不能精确控制。比较稳妥的方式是先用 BFS 把树的深度顺序求出来再用非递归处理父链关系或者直接把递归深度控制住数据偏小时再递归。还有一个实际问题颜色值可能很大离散化要提前做。如果颜色值和节点数量不是一个数量级直接拿颜色当数组下标会数组越界或内存浪费。下面整理成一张速查表适合复习时快速看现象常见原因处理方式答案少算了某个子树查询时轻儿子还没全部加入检查 dfs2 顺序答案多算了一部分查询后没有清空又重复统计keepfalse 时清空整棵子树复杂度变成 O(n²)重儿子划分错误或没有划分严格按最大子树选 sonmxCnt 越走越大清空后没重置辅助状态在 !keep 分支重置 mxCnt数据大时栈溢出链式树递归太深换 BFS 或迭代解决数组越界颜色值未离散化统一做坐标压缩5. 如何让题集长期可维护5.1 维护一颗“单点操作”的心我写 dsu on tree 题集最大的感受是这个算法真正需要设计的部分只有两个函数addOne和removeOne。只要能回答清楚两个问题加入一个节点时统计量怎么变删除一个节点时统计量怎么变。剩下的事情全部是模板。所以题集里的每道题我都会先写清楚这两个函数再想其他部分。这听起来很简单但能帮你跳出“套板子套错”的困境。5.2 用对拍验证板子刷题集时我会给每个 AC 代码配一个很小的随机数据生成器和暴力程序。暴力做法是每个节点重新遍历一遍子树n 取 10 左右。每次改动板子都先对拍几百组数据确保addOne、removeOne和批量遍历没有不对称问题。对拍这件事不能省。表面上看 dsu on tree 代码很短但一点小错误就非常难查尤其是那些“结果恰好错一点点但是整体答案看起来很正常”的 bug。5.3 与莫队、点分治的对比表题集维护到后期我加了一个对比维度用来快速判断一个题到底该用什么算法场景推荐算法原因无修改统计每个子树信息dsu on tree实现简单O(n log n)无修改统计路径全局信息点分治路径数量统计更直接有修改子树查询树上莫队或树剖数据结构需要增量修改需要合并复杂信息线段树合并合并函数更灵活这个表不是绝对的但它能防止我无脑把所有树上题都套 dsu on tree。5.4 题集扩展方向如果想把 dsu on tree 题集继续做厚可以关注几个方向第一个方向是“dsu on tree 可撤销数据结构”。有些统计量删除单点不好维护但可以做到撤销这时候可以把不可删除的信息改成可撤销版本。第二个方向是“按位拆分”。很多异或、奇偶性问题把每一位单独统计再用addOne维护位上的计数可以绕过复杂数据结构。第三个方向是“子树内动态询问”。原本 dfs2 是按树的结构离线处理的如果题目强制要求在某些时间点查询可能需要配合树的括号序和离线排序把树上问题转成序列上的启发式合并。最后一个方向是“和树形 DP 结合”。有些 DP 转移本来就是“父节点合并各个儿子”启发式合并可以大大降低合并多个小状态的开销这类题比纯模板题更值得收集。最后分享一个个人习惯我的 dsu on tree 板子文件开头永远写着四个函数的调用顺序dfs1 - 轻儿子 - 重儿子 - 加轻儿子 - 加当前节点 - 查询 - 清空。每次刷出新题我只改addOne和removeOne改完先对拍再提交。这个习惯帮我少踩了非常多的坑也让我在整理题集的时候能快速分清到底是模板问题还是题目本身的统计量设计问题。