企业官网建设流程全解析

1. 这个技巧到底在解决什么问题

如果让我选一个十分容易上手、又经常能在竞赛里救场的小众算法，我大概率会投 DSU on tree 一票。它的全称是树上启发式合并，英文名 dsu on tree，说白了就是用轻重儿子剖分的思想，在 (O(n \log n)) 时间内批量回答每个子树的统计类问题。最近我在整理一份自己的 dsu on tree 题集，正好把模板代码和几个经典题型的 AC 代码一起沉淀成一篇博客，给正在学树上算法、或者比赛前想回顾模板的选手做参考。

先抛一个最典型的场景：给你一棵 n 个节点的树，每个节点有一种颜色，需要对于每一个节点输出它的子树里有多少种不同的颜色。如果 n 只有两三百，直接在每个点暴力跑一遍子树就行，递归完一个子树统计完立刻清空，时间上是所有子树大小的总和，链状树直接变成 (n^2)。可竞赛里 n 往往给到 (10^5) 甚至 (2 \times 10^5)，这时候必须找一个接近线性的办法。

朴素思路的痛处在哪：全局开一个桶，DFS 一个节点时把整个子树塞进桶里，得到答案后直接把桶清空，再 DFS 下一个节点。看似挺常规，但问题就是重复扫描。重链上每个点都会被反复加入、清除，链越长浪费越明显。有些选手会选择对每个子树开一个独立桶，然后用某种合并策略把子树桶并上去。这种思路的本质是“按子树合并”，如果每次把小的桶合并到大桶里，也就是启发式合并的想法，理论上也可以做到 (O(n \log n))，但实现上要处理桶的交换、挂载，稍微麻烦。

DSU on tree 是另一种实现路线，它不显式合并桶，而是利用 DFS 的顺序复用统计信息。它把“每个子树统计完整一遍”的问题转换成“有选择地复用重儿子的统计结果，只暴力加轻儿子”。这个思路和标准并查集的路径压缩优化关系不大，之所以叫 DSU，是因为很多资料里把它归到和启发式合并同一大类里，实际代码里根本没有并查集。名字容易让人走偏，理解上就是“树上离线启发式统计”。

适合读这篇的人：已经会树的 DFS、vector 存图、递归，想系统学习树上统计题的选手；或者比赛前需要快速回顾模板的选手。它不要求你有多难的数学基础，核心就是一组 DFS 流程和一个 add 函数。后面我会直接给出一套可运行的题集代码，你换个题目改的就是 add 函数里的那几行。

2. 核心原理：为什么复杂度能做到 O(n log n)

要理解 DSU on tree，先要接受两个概念：重儿子和轻儿子。重儿子是所有儿子中子树 size 最大的那一个，其余儿子统称轻儿子。这个划分就是树链剖分里的轻重划分，只是我们在 DSU 里不用链的编号，只用重儿子这一个信息。

算法整体只有三个步骤：

1. 第一次 DFS，预处理每个节点的 size 和重儿子。
2. 第二次 DFS 自顶向下处理，对每个节点先递归所有轻儿子，并且轻儿子处理完后要清掉自己的统计影响；再递归重儿子，这次保留统计影响。
3. 当前节点的重儿子统计保留后，再暴力把当前节点自己以及所有轻儿子子树加入全局桶，此时桶里正好是当前整棵子树的信息，记录答案。如果当前节点是作为轻链上的节点被处理，最后再把整个当前子树从桶里清空。

为什么先轻后重？这是整个技巧最关键的设计。重儿子子树是所有孩子里最大的，如果最后处理它并保留，它的统计结果可以直接给当前节点用，这样当前节点在记录答案时，只需要把轻儿子和节点自己补进来，不用重新扫重儿子。如果反过来先处理重儿子并把桶清掉，那就白白损失了重儿子的复用价值。

复杂度证明网上很多说法，我用自己的话讲一遍。分析某个节点 u 最终会在 dfsAdd 这个遍历里被加入几次。从根到 u 的路径上，每经过一条轻边，子树大小至少减半。因为孩子里重儿子最大，那么任意一个轻儿子的 size 不会超过父亲子树大小的一半。所以整条路径上轻边数不超过 (\log_2 n) 量级。u 只有在某条轻链上的祖先需要“重新补扫轻儿子”时，或者本身处于一条重链上被顺带保留时，才会被加入。前者出现的次数就是到根路径上轻边数，后者每个节点只贡献常数次。合起来每个节点最多被加入 (O(\log n)) 次，加入和清除又是成对出现，所以总复杂度 (O(n \log n))。注意这已经是相当紧的界，实际常数不大，10 万级别数据非常轻松。

有个很自然的疑问：既然每个子树最终都要统计，为什么不能直接用一次 DFS 把答案记下来？因为不同子树之间统计信息相互干扰，一个桶不可能同时表示两个子树。DSU 的思路是让桶始终处于“某个特定子树完整状态”，并且尽量复用重儿子的计算，把每次重构的开销均摊到轻链上。你可以把它理解成你写作业时，先花大力气把一张大卷子完整做完，之后的几张小卷子里，凡是和大卷子重叠的题直接抄答案，只有新增的小题单独做。

3. 模板代码：三步走框架

先给出一个最通用的模板，这个模板适合“需要统计每个子树某类属性”的题目。后续题集里所有代码都是它的变种。

第一段是预处理 DFS。存图用 vector，root 取 1，fa 传 0：

void dfs1(int u, int fa) { sz[u] = 1; for (int v : g[u]) { if (v == fa) continue; dfs1(v, u); sz[u] += sz[v]; if (sz[v] > sz[son[u]]) son[u] = v; } }

这段代码的作用很简单：计算出每个节点的子树大小，并记录 size 最大的儿子作为重儿子。有个小细节，son 数组初始化是 0，对于叶子节点 son[u] 就是 0，后续判断if (son[u])时能安全跳过。

第二段是 add 函数。它的作用是把一棵子树整体加入全局桶，或者整体从全局桶里移除。加入和移除通过 val 的 1 / -1 来控制。注意它要跳过 skipNode：

int skipNode; void dfsAdd(int u, int fa, int val) { // 更新当前节点的统计，不同题目改这里 addNode(u, val); for (int v : g[u]) { if (v == fa || v == skipNode) continue; dfsAdd(v, u, val); } }

为什么需要 skipNode 而不是直接遍历整个子树？因为在 dfs2 里，重儿子的统计结果已经被保留在桶里了，如果 add 的时候又把重儿子加一遍，会重复计算。skipNode 只是单纯表示“当前哪个重儿子已经被保留了，别重复扫”。

第三段是主流程 dfs2：

int ans[MAXN]; void dfs2(int u, int fa, bool keep) { for (int v : g[u]) { if (v == fa || v == son[u]) continue; dfs2(v, u, false); } if (son[u]) dfs2(son[u], u, true); skipNode = son[u]; dfsAdd(u, fa, 1); ans[u] = getAnswer(); // 此时全局桶表示 u 的整个子树 skipNode = 0; if (!keep) { dfsAdd(u, fa, -1); } }

这段代码的逻辑顺序非常关键。先处理轻儿子并全部清除；再处理重儿子并保留；然后把当前节点和所有轻儿子加入；记录答案；如果当前节点不是重链上需要保留的节点，就把整个子树的统计清除，保证桶回到处理该轻儿子之前的状态。

模板的优点是结构固定，换题只改 dfsAdd 里的更新逻辑和 getAnswer 的返回逻辑。这也是 DSU on tree 容易上手的原因。下面进入正题，我用四道题组成一份小型的 DSU 题集，每一道都会给出可以直接提交的 AC 代码，以及为什么这么维护的说明。

4. 题集实战：四道经典题型与 AC 代码

4.1 题型一：子树内不同颜色种类数

题目描述比较经典：给一棵 n 个节点的树，根为 1，每个节点有一种颜色，求每个节点的子树里有多少种不同的颜色。数据范围一般是 n、颜色编号在 1 到 n 的整数内。

这个题是最标准的模板题，适合作为第一个 AC 的 DSU 练手。全局维护 cnt[color]，diffCnt 表示当前桶里不同颜色数。add 一个节点时，如果这个颜色从 0 变 1，diffCnt 加一；移除节点时，如果颜色从 1 变 0，diffCnt 减一。getAnswer 直接返回 diffCnt。

完整 AC 代码如下：

#include <bits/stdc++.h> using namespace std; const int MAXN = 200005; int n; vector<int> g[MAXN]; int color[MAXN]; int sz[MAXN], son[MAXN]; int cnt[MAXN]; int diffCnt; int skipNode; int ans[MAXN]; void dfs1(int u, int fa) { sz[u] = 1; for (int v : g[u]) { if (v == fa) continue; dfs1(v, u); sz[u] += sz[v]; if (sz[v] > sz[son[u]]) son[u] = v; } } void dfsAdd(int u, int fa, int val) { if (val == 1) { if (cnt[color[u]] == 0) diffCnt++; cnt[color[u]]++; } else { cnt[color[u]]--; if (cnt[color[u]] == 0) diffCnt--; } for (int v : g[u]) { if (v == fa || v == skipNode) continue; dfsAdd(v, u, val); } } void dfs2(int u, int fa, bool keep) { for (int v : g[u]) { if (v == fa || v == son[u]) continue; dfs2(v, u, false); } if (son[u]) dfs2(son[u], u, true); skipNode = son[u]; dfsAdd(u, fa, 1); ans[u] = diffCnt; skipNode = 0; if (!keep) { dfsAdd(u, fa, -1); } } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin >> n; for (int i = 1; i <= n; i++) cin >> color[i]; for (int i = 1; i < n; i++) { int x, y; cin >> x >> y; g[x].push_back(y); g[y].push_back(x); } dfs1(1, 0); dfs2(1, 0, true); for (int i = 1; i <= n; i++) cout << ans[i] << '\n'; return 0; }

这份代码可以直接作为你题集里的第一道模板题。实际测试中我会额外检查两类边界：一是颜色值可能很大，比如到 (10^9)，这时 cnt 数组下标不能直接用，先把颜色离散化到 1..n；二是整棵树是链状结构，递归深度可能到 10 万，极端情况需要处理栈空间问题，我在后面第五节专门讲。我辅导过的 A 同学第一次写这个题时，总是忘记在 dfs2 里对轻儿子传 keep=false，导致轻儿子子树统计结果互相污染，排查了很久才发现是 keep 参数传错了。

4.2 题型二：子树中出现次数最多的颜色编号之和

这里我们把统计目标变复杂一点：求每个节点子树里，出现次数最多的颜色的编号之和。如果有多种颜色并列最多，需要把它们的编号全部加起来。这个问题能让 DFS 过程稍微复杂，因为它需要维护的不是单个答案，而是一个动态的“出现次数桶的桶”。

我用一个例子说明维护方式。假设当前某节点子树里颜色 1 出现 5 次，颜色 2 出现 3 次，颜色 3 出现 5 次，答案就是 1 + 3 = 4。要支持动态增删一个节点的颜色，只靠 cnt[color] 是不够的，还需要知道“出现次数为 k 的所有颜色编号和”，以及当前最大的出现次数 maxOcc。于是开两个数组：

• cnt[color]：当前每个颜色的出现次数。
• sumOfCnt[k]：当前所有出现次数恰好为 k 的颜色编号之和。
• maxOcc：当前所有颜色里的最大出现次数。

新增一个颜色为 c 的节点时，旧次数 old 变成 old+1。操作顺序是先把 c 从 sumOfCnt[old] 里去掉，再加到 sumOfCnt[old+1]，同时更新 cnt[c]，最后如果 old+1 比 maxOcc 大，就把 maxOcc 更新为 old+1。删除节点时反向操作，并且如果 sumOfCnt[maxOcc] 变成 0，要不断把 maxOcc 往下降，直到重新存在某个次数层非空。注意 sumOfCnt[0] 不参与维护，避免颜色全部删除后桶里为 0 的脏数据干扰。

完整 AC 代码如下：

#include <bits/stdc++.h> using namespace std; typedef long long ll; const int MAXN = 200005; int n; vector<int> g[MAXN]; int color[MAXN]; int sz[MAXN], son[MAXN]; int cnt[MAXN]; ll sumOfCnt[MAXN]; int maxOcc; int skipNode; ll ans[MAXN]; void dfs1(int u, int fa) { sz[u] = 1; for (int v : g[u]) { if (v == fa) continue; dfs1(v, u); sz[u] += sz[v]; if (sz[v] > sz[son[u]]) son[u] = v; } } void dfsAdd(int u, int fa, int val) { int c = color[u]; int old = cnt[c]; int now = old + val; cnt[c] = now; if (old > 0) sumOfCnt[old] -= c; if (now > 0) sumOfCnt[now] += c; if (val == 1) { maxOcc = max(maxOcc, now); } else { while (maxOcc > 0 && sumOfCnt[maxOcc] == 0) maxOcc--; } for (int v : g[u]) { if (v == fa || v == skipNode) continue; dfsAdd(v, u, val); } } void dfs2(int u, int fa, bool keep) { for (int v : g[u]) { if (v == fa || v == son[u]) continue; dfs2(v, u, false); } if (son[u]) dfs2(son[u], u, true); skipNode = son[u]; dfsAdd(u, fa, 1); ans[u] = sumOfCnt[maxOcc]; skipNode = 0; if (!keep) { dfsAdd(u, fa, -1); maxOcc = 0; } } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin >> n; for (int i = 1; i <= n; i++) cin >> color[i]; for (int i = 1; i < n; i++) { int x, y; cin >> x >> y; g[x].push_back(y); g[y].push_back(x); } dfs1(1, 0); dfs2(1, 0, true); for (int i = 1; i <= n; i++) cout << ans[i] << '\n'; return 0; }

这里我把 ans 设成 long long，因为颜色编号如果极限叠加，比如 n 个节点不同颜色的编号都是 n，总和可能超过 int 范围。sumOfCnt 也一样用 long long，这是比赛里一个很常见的坑。另一个细节是每次递归返回一个轻儿子时，maxOcc 可能在删除过程中降到 0，然后下一个兄弟节点 add 时会从 1 开始增长，所以每轮 if (!keep) 后面把 maxOcc 置 0 是为了避免残留的旧值影响下一次 add 时的比较。实测这套代码对单组数据没问题，但如果是多组数据，记得把 sumOfCnt、cnt、maxOcc 全部清空。

4.3 题型三：子树内严格大于当前节点的权值个数

这道题换了一个思路：统计的东西不再是简简单单的颜色出现次数，而是一个偏序条件。给定一棵树，每个点有权值，求每个节点的子树里，权值严格大于当前节点权值的节点数。这个题如果直接对每个子树排序后二分，复杂度很高。用 DSU on tree 配合树状数组，可以在 (O(n\log^2 n)) 内解决，n 到 10 万时也比较稳定。

思路是先把权值离散化到 1..M，用 BIT 维护当前子树里各权值的出现次数。每次 dfsAdd 把一个节点加入或移除，对应 BIT 单点加减。当 dfs2 处理到 u 且整个子树的节点都已加入 BIT 时，查询整棵树所有节点数减去小于等于当前权值的节点数，也就是 BIT 后缀区间[w[u]+1, M]的总数，得到的就是子树内大于 w[u] 的节点个数。

完整 AC 代码如下：

#include <bits/stdc++.h> using namespace std; const int MAXN = 100005; int n; vector<int> g[MAXN]; int w[MAXN]; vector<int> vals; int sz[MAXN], son[MAXN]; int bit[MAXN]; int skipNode; int ans[MAXN]; void addBit(int pos, int val) { for (int i = pos; i <= n; i += i & -i) bit[i] += val; } int sumBit(int pos) { int res = 0; for (int i = pos; i > 0; i -= i & -i) res += bit[i]; return res; } void dfs1(int u, int fa) { sz[u] = 1; for (int v : g[u]) { if (v == fa) continue; dfs1(v, u); sz[u] += sz[v]; if (sz[v] > sz[son[u]]) son[u] = v; } } void dfsAdd(int u, int fa, int val) { addBit(w[u], val); for (int v : g[u]) { if (v == fa || v == skipNode) continue; dfsAdd(v, u, val); } } void dfs2(int u, int fa, bool keep) { for (int v : g[u]) { if (v == fa || v == son[u]) continue; dfs2(v, u, false); } if (son[u]) dfs2(son[u], u, true); skipNode = son[u]; dfsAdd(u, fa, 1); ans[u] = sumBit(n) - sumBit(w[u]); skipNode = 0; if (!keep) { dfsAdd(u, fa, -1); } } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin >> n; for (int i = 1; i <= n; i++) { cin >> w[i]; vals.push_back(w[i]); } sort(vals.begin(), vals.end()); vals.erase(unique(vals.begin(), vals.end()), vals.end()); for (int i = 1; i <= n; i++) { w[i] = lower_bound(vals.begin(), vals.end(), w[i]) - vals.begin() + 1; } for (int i = 1; i < n; i++) { int x, y; cin >> x >> y; g[x].push_back(y); g[y].push_back(x); } dfs1(1, 0); dfs2(1, 0, true); for (int i = 1; i <= n; i++) cout << ans[i] << '\n'; return 0; }

这个题的代码相比前两个只多了一个 BIT，理解起来也不难。需要注意的是 BIT 的 add 和 dfsAdd 是两个函数，前者是树状数组的更新操作，后者是 DSU 的子树遍历操作，别混成一个。离散化之后 w[u] 的范围是 1 到不同权值个数，BIT 数组开到 n+5 就足够。我实际跑过 n 等于 10 万、权值范围开满的随机数据和链状数据，时间都能过。如果你遇到时限很紧的题，也可以考虑不用 BIT，而是把所有点数放到一个有序数组里维护，但需要另外处理动态增删，反而复杂，BIT 是最稳的实现。

4.4 题型四：离线询问子树内指定深度的节点数

最后一个题型讲离线询问。给一棵树，给定 m 个询问，每次询问一个点 u，要求输出 u 的子树内深度恰好等于 d 的节点数量。深度可以约定根节点深度为 1。如果每个询问都暴力遍历子树，复杂度是不可接受的。利用 DSU on tree，我们可以把所有询问挂在对应节点上，在 dfs2 计算到该子树时，一次性回答挂在该节点的所有询问。

这里的关键是理解时序：当 dfs2 来到 u 节点，并执行完 dfsAdd(u, fa, 1) 之后，全局桶恰好就是 u 整棵子树的状态。所以此时直接查询深度统计数组 depCnt[d]，就能得到答案。这样每个询问的复杂度是 O(1)，总复杂度只比 DSU 模板多一个 m 的常数。

完整 AC 代码如下：

#include <bits/stdc++.h> using namespace std; const int MAXN = 100005; int n, m; vector<int> g[MAXN]; int sz[MAXN], son[MAXN]; int dep[MAXN]; int depCnt[MAXN]; int skipNode; vector<pair<int, int>> query[MAXN]; int queryAns[MAXN]; void dfs1(int u, int fa) { sz[u] = 1; dep[u] = dep[fa] + 1; for (int v : g[u]) { if (v == fa) continue; dfs1(v, u); sz[u] += sz[v]; if (sz[v] > sz[son[u]]) son[u] = v; } } void dfsAdd(int u, int fa, int val) { depCnt[dep[u]] += val; for (int v : g[u]) { if (v == fa || v == skipNode) continue; dfsAdd(v, u, val); } } void dfs2(int u, int fa, bool keep) { for (int v : g[u]) { if (v == fa || v == son[u]) continue; dfs2(v, u, false); } if (son[u]) dfs2(son[u], u, true); skipNode = son[u]; dfsAdd(u, fa, 1); for (auto p : query[u]) { queryAns[p.second] = depCnt[p.first]; } skipNode = 0; if (!keep) { dfsAdd(u, fa, -1); } } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin >> n; for (int i = 1; i < n; i++) { int x, y; cin >> x >> y; g[x].push_back(y); g[y].push_back(x); } cin >> m; for (int i = 1; i <= m; i++) { int u, d; cin >> u >> d; query[u].push_back({d, i}); } dfs1(1, 0); dfs2(1, 0, true); for (int i = 1; i <= m; i++) cout << queryAns[i] << '\n'; return 0; }

注意这个解法要求所有询问预先读入，因为我们要在 DFS 过程中回答，无法事后单独处理。这就是“离线”的含义。如果题目要求强制在线，就不能用 DSU 这一版，需要用可持久化线段树等结构，那属于另一个知识块了。实际训练里，我建议把离线询问答题这个套路单独练熟，它在很多树上统计题里都能复用，比如子树里权值落在某个区间的数量、子树里出现次数满足某个条件的颜色数等，换汤不换药。

5. 常见问题与调试技巧实录

5.1 递归爆栈问题

DSU on tree 的 dfs1 和 dfs2 都是递归写法，遇到链状树时递归深度可能达到 n。在本地编译器运行时，默认栈空间往往不够，程序直接崩掉。这类问题有几种处理方式。一是比赛环境允许的话，在本地执行命令调整栈大小后再运行程序；但提交到 OJ 时一般不用管，OJ 的进程栈通常比较大。二是在代码里改写成显式栈迭代，但这会让模板变复杂，不建议入门阶段这么做。三是如果本地调试遇到崩溃，先确认是不是递归深度的问题，可以临时把 n 改小测试，或者给 dfs1 后面加一个深度计数看看。我遇到过最冤枉的情况是某在线平台能跑，本地一跑就崩，最后发现是本地编辑器带了一个特殊编译器参数导致栈受限，和代码本身无关。

5.2 skipNode 设置遗漏或作用域出错

skipNode 这个全局变量是整个模板里最容易写错的地方。它必须在 dfsAdd 执行前被赋值为 son[u]，并且 dfsAdd 函数里去判断v == skipNode。最典型的错误是把 skipNode 写成 add 函数里的一个参数，每次递归传下去，这样重儿子子树的去重会在多层递归中失效。另一个常见问题是进入 dfsAdd 后，函数内部递归遍历到重儿子时又调了 dfsAdd，而 skipNode 还是 son[u]，所以整棵重儿子子树被正确跳过。如果你把 skipNode 在处理轻儿子时误赋成 0，重儿子就会被重复统计，答案偏大。调试技巧是在 dfsAdd 开头打印节点编号和 skipNode，然后对比预期值。

5.3 多组数据和数组清空

竞赛里有些题目有多组测试数据。这时如果只在 main 里读一次 n，所有全局数组都要在每组数据开始时清一下。很多人只清 cnt，忘记清 son 和 skipNode，结果第二次 dfs1 里重儿子判断错乱。最稳妥的做法是在每组数据处理开头，把涉及到的 vector 全部 clear，son 和 cnt 数组对应范围赋值 0，再重新读图。对于 n 很大的情况，逐组清空数组本身也要耗时间，不过相比单次 DSU 的复杂度，这部分可以接受。

5.4 add 函数里的 val 反向操作

dfsAdd 用同一个函数完成加入和清除，靠 val 是 1 还是 -1 区分。写反向操作时最容易漏的是：统计数组的恢复要严格按照加入的逆顺序。比如题型二里，删除一个节点时，必须先改 cnt，再更新 sumOfCnt[old] 和 sumOfCnt[now]，如果顺序反了，old 已经被覆盖，sumOfCnt 就维护错了。另一个办法是把加入逻辑封装成一个独立函数，比如加一个点就调用addPoint(c, 1)，删除点调用addPoint(c, -1)，这样逻辑清晰很多。我的建议是不要在 dfsAdd 里写一大串分支，而是把单个节点的更新抽出来，这样后面换题改起来更快。

5.5 答案数组与统计数组类型

有些 DSU 题答案会很大，比如统计编号之和、子树总权值，答案数组要开 long long。统计颜色的 cnt 数组一般开 int 没问题，但 sumOfCnt 这种累加编号的必须 long long。掉了这个细节，小数据可能看不出来，大数据对拍就直接 WA。建议初始化阶段就把 ans 开成 long long，宁可浪费一点空间，不要冒溢出风险。

6. 写在最后：练习建议与扩展方向

DSU on tree 看起来模板固定，但真正想熟练，还是要自己动手推几个数据。我的建议是找一个 n=7 或 n=8 的小树，手动模拟一遍 dfs2：记录每个节点完成后桶的状态，看看为什么重儿子子树不会被重复加入，为什么轻儿子子树会被重新扫一遍。这个过程跑通了，模板基本就吃透了。

这个算法能扩展的方向也不少：可以配合线段树维护区间信息，可以处理带权值的各类偏序统计，也可以结合离线回答子树内若干种约束的计数问题。不过它也有明确边界，主要擅长子树内部统计，不适合路径统计，路径统计通常要点分治或树上差分。如果做某个路径问题，别硬拿 DSU 套。

最后再分享一个小技巧：我在刷题集的时候习惯把模板拆成三块维护，dfs1 和 dfs2 基本不动，只改 add 函数和 getAnswer。这样一来，遇到新题第一反应就是看清楚子树状态是什么、需要维护几个数组，然后再动代码。很多同学觉得 DSU 难，其实难点根本不在算法，而在“什么时候该维护什么”的判断。多练几道，这个判断会越来越快。