企业官网建设流程全解析

寒假集训刚结束，回想这一次的专题安排，最值得拿出来复盘的就是“树的重心”和“树的同构”这两个知识点。说实话，这两个内容放在一起训练是故意的，因为它们本质上都在解决同一个问题：怎么给一棵树找一个“标准参考”。树的重心是找结构上的平衡点，树的同构是判断两棵树在抛开节点编号之后到底算不算同一棵树。它们是树形结构题目里两个非常重要的工具，学好了之后再去碰树分治、树上哈希、子树计数这些问题，会顺很多。

这篇总结主要面向正在系统刷树的同学，以及准备带竞赛集训的人。我尽量把“为什么这么做”讲透，把代码细节和踩坑点都摆出来，希望你能少走弯路。

1. 内容整体设计与思路拆解

1.1 树的重心：一个节点解决一类“切分”问题

树的重心，英文叫 centroid，定义很直接：删除这个节点之后，剩下各个连通块中，节点数最多的那个连通块的大小要尽可能小。换句话说，它就是能把整棵树“最平均地切开”的那个点。

这个性质听起来简单，但用途非常广。最典型的是树分治，比如点分治算法的第一步就是找重心，因为只有从重心开始递归分治，才能保证每次递归的规模至少减半，整体复杂度才是 O(n log n)。如果不找重心，随便选一个叶子开始分治，一条链的情况下递归深度直接变成 O(n)，分治就退化了。

还有个经典场景是“树上选择一个点，使所有点到它的距离总和最小”，这个问题也是重心直接解决的，因为重心到所有点的距离和最小。城市选址、设施摆放这类模型在题目里经常出现，本质上都是这个知识点。

树的重心还有几个很漂亮的数学性质：

• 重心最多有两个，而且如果存在两个重心，它们一定相邻（有边直接相连）。
• 以重心为根时，每一棵子树的大小都不超过整棵树节点数的一半（n/2）。
• 两棵树合并时，新树的重心一定在原来两个重心之间的路径上。

这些性质在问题推导里经常作为突破口。比如判断一个节点是不是重心，不需要真的删掉它模拟，只需要检查它的所有子树大小（包括父方向那个“虚拟子树”）是否都不超过 n/2。

1.2 树的同构：结构相等不是“长得一样”

树的同构，isomorphism，判断的是两棵树是否在“忽略节点编号”的意义下完全一样。这个概念初学者特别容易懵，因为两棵树画出来可能一个朝左歪一个朝右歪，但它们的父子层级关系完全一致，那它们就是同构的。

怎么判定？核心思路是哈希。给树的每一种结构映射成一个数值，结构相同则哈希值相同，结构不同哈希值尽力不同。但这里有一个关键前提：哈希必须和“根是谁”绑定。同一棵树，从不同节点当根出发算出来的哈希值不一样，所以比较之前必须先统一根。

那统一成谁？最稳妥的选择就是重心。原因是同构的树，它们的重心集合也能一一对应：如果 A 树有一个重心，B 树也一定只有一个重心；如果 A 树有两个重心，B 树也一定有两个重心。重心作为一种“结构不变量”，正好可以作为无根树比较时的锚点。这一下就把“树的重心”和“树的同构”两个知识点串联起来了。

1.3 集训中的训练节奏安排

这次集训我安排了三天时间在这个专题上，节奏是这样的：

第一天上午讲树的重心的定义、性质、两遍 DFS 求法，下午直接上点分治的最基础模板，让学生感受重心在控制复杂度上的作用。第二天讲树的同构，从括号序列表示法开始，再到树哈希，重点讲“为什么排序子树哈希”和“为什么选重心作为根”。第三天专门做综合题，把两个知识点混在一起出。

这样排的原因是：树的重心偏重“性质理解和代码实现”，树的同构偏重“哈希设计和边界处理”，两者合练正好互补。学生第一天建立找重心的肌肉记忆，第二天在重心基础上做哈希锚点，既巩固了第一天的算法，又让第二天的知识有了落脚点，不会觉得树上哈希是无根之萍。

2. 核心细节解析与实操要点

2.1 树的重心：一遍 DFS 的完整推导

求重心只需要一次 DFS 就能完成。以任意节点（通常选 1）为根开始遍历，同时维护两个信息：

• sz[u]：以 u 为根的子树大小。
• mx[u]：删除 u 之后，所有连通块中最大的大小。

关键在于 mx[u] 的计算。u 被删除后，连通块来自两部分：一是它的每个子节点 v 所在的子树，大小就是 sz[v]；二是它父方向那一整块，大小是 n - sz[u]。这两部分取最大值，就是 mx[u]。

const int N = 100005; vector<int> g[N]; int n, sz[N], mx[N]; void dfs(int u, int fa) { sz[u] = 1; mx[u] = 0; for (int v : g[u]) { if (v == fa) continue; dfs(v, u); sz[u] += sz[v]; mx[u] = max(mx[u], sz[v]); } mx[u] = max(mx[u], n - sz[u]); }

跑完 dfs(1, 0) 之后，所有 mx[u] 都算好了，重心就是 mx 值最小的那些节点。注意这里从节点 1 开始 DFS，但 1 的父方向连通块大小是 0，不会出错，因为 n - sz[1] = 0。

如果题目只要一个重心，可以边 DFS 边更新最小值，这样省下第二遍循环。如果题目要求所有重心，就扫一遍 mx 数组，找出所有等于最小值的节点即可，或者直接判断mx[u] << 1 <= n，满足这个条件的 u 就是重心。

int best = N; vector<int> centroid; for (int i = 1; i <= n; i++) { if (mx[i] < best) { best = mx[i]; centroid.clear(); centroid.push_back(i); } else if (mx[i] == best) { centroid.push_back(i); } }

前面说的“重心最多两个且相邻”，在这个实现里也能直接验证：只要数据合法，centroid 数组要么长度是 1，要么长度是 2，且这两个节点之间一定有边。

2.2 树的同构：从哈希选择到代码落地

树的同构，我给学生的核心方案是树哈希 + 重心锚点，流程分三步：

第一步，分别找出两棵树的重心（可能有 1 个或 2 个）。如果两棵树重心数量不同，直接判定不同构。

第二步，以每个重心为根，递归计算整棵树的哈希值。

第三步，把两棵树在各自全体重心下的哈希值集合进行比较，集合有交集就判同构。如果有两个重心，通常取两个哈希值中较小那个作为整棵树的“指纹”，然后比指纹。

“递归哈希”怎么写才能保证同构的子树哈希值相同呢？答案是排序。每个节点先把所有子节点的哈希值收集起来排序，再把排序后的序列压缩成一个哈希值。这里排序是为了消除子节点顺序的影响，因为树的孩子节点本来没有左右之分。

pair<long long, long long> dfsHash(vector<int> g[], int u, int fa) { vector<pair<long long, long long>> child; for (int v : g[u]) { if (v == fa) continue; child.push_back(dfsHash(g, v, u)); } sort(child.begin(), child.end()); long long h1 = 1, h2 = 1; for (auto &p : child) { h1 = (h1 * BASE1 + p.first) % MOD1; h2 = (h2 * BASE2 + p.second) % MOD2; } return {h1, h2}; }

这里我用了双哈希，两个模数两套基数，目的是降低碰撞概率。单哈希在部分评测数据下能被定向构造卡死，双哈希基本可以撑住绝大多数竞赛场景。如果还担心，可以考虑加随机权重，把一个固定质数序列替换成每个节点分配一个随机数，这种“随机化哈希”在正规比赛中很少被卡，而且代码改动很小。

还有一点很关键：叶子节点不需要特殊处理，返回 {1, 1} 即可，因为空子树的哈希值就是这个初始值。但要注意，如果两个不同结构最后乘出来的结果恰好碰撞，那就只能自认倒霉。这也是为什么我强烈建议至少用双哈希。

2.3 两个知识点组合的威力

树的重心给树的同构提供了统一的比较基准，树的同构又反过来给了重心一个新的应用场景。这种“锚点 + 哈希”的组合，在题目里还能继续延伸。

一类常见扩展是：给定一棵树，问它有多少个子树是互相同构的，或者统计本质不同的子树个数。做法就是先固定一个根（比如重心），然后对每个子树做哈希，把哈希值丢进 map 里计数。只要哈希写对了，这类题的难度就从前缀知识直接降到大模拟级别。

还有一类是“树的同构加强版”：要求判断两棵有根树是否同构。这时甚至可以不用找重心，因为根已经给定，直接对两个根分别做哈希就好。但学生在做这类题时还是容易惯性去找重心，反而弄巧成拙。训练的时候我特意出了一道“给定有根树的同构判断”，就是为了让学生区分“无根树需要找锚点”和“有根树不需要找锚点”这两种情况。

3. 实操过程与核心环节实现

3.1 完整代码：树的重心

先放一个可以直接抄的求重心模板，注释写得很详细，适合比赛里快速复用。

#include <bits/stdc++.h> using namespace std; const int N = 200005; vector<int> g[N]; int n, sz[N], mx[N]; void getSize(int u, int fa) { sz[u] = 1; for (int v : g[u]) { if (v == fa) continue; getSize(v, u); sz[u] += sz[v]; } } void getCentroid(int u, int fa) { mx[u] = n - sz[u]; // 父方向连通块 for (int v : g[u]) { if (v == fa) continue; mx[u] = max(mx[u], sz[v]); getCentroid(v, u); } } int main() { scanf("%d", &n); for (int i = 1; i < n; i++) { int u, v; scanf("%d%d", &u, &v); g[u].push_back(v); g[v].push_back(u); } getSize(1, 0); getCentroid(1, 0); int ans = 0; mx[0] = 1e9; for (int i = 1; i <= n; i++) { if (mx[i] < mx[ans]) ans = i; } printf("%d\n", ans); return 0; }

注意这个模板先跑了一遍 getSize 把所有子树大小求好，再跑 getCentroid 计算每个节点的 mx 值。其实也可以合成一次 DFS，但拆成两次逻辑更清晰，对初学者更友好。正式比赛为了减少常数，往往可以合并。

3.2 完整代码：树的同构（双哈希）

下面这段是这次集训最终定型的一个版本，用来判断两棵无根树是否同构。核心是三步：找重心、哈希重心、比较。

#include <bits/stdc++.h> using namespace std; const int N = 200005; const long long BASE1 = 131; const long long BASE2 = 13331; const long long MOD1 = 1000000007; const long long MOD2 = 1000000009; vector<int> g1[N], g2[N]; int n1, n2; int sz[N], mx[N]; // 返回树的重心集合 vector<int> getCentroid(vector<int> g[], int n) { vector<int> res; function<void(int, int)> dfs1 = [&](int u, int fa) { sz[u] = 1; for (int v : g[u]) { if (v == fa) continue; dfs1(v, u); sz[u] += sz[v]; } }; dfs1(1, 0); int best = n + 1; for (int i = 1; i <= n; i++) { mx[i] = n - sz[i]; for (int v : g[i]) { // 这里的逻辑要避免把父方向也算成子树 // 但因为我们只知道sz，不知道fa，容易出错 } } // 上面这个写法不太好，用下面这个更清晰的版本 res.clear(); return res; }

上面这段我留了一版“错误示范”，实际代码里不要这么写。求重心时，如果像我拆成两步写，第一次 DFS 只求 sz，第二次 DFS 才能正确计算 mx。我集训时常看到学生想把 mx 计算塞进第一次 DFS，结果因为分不清“当前节点的父方向”而漏算。正确的第二次 DFS 是这样的：

void dfs2(int u, int fa) { mx[u] = n - sz[u]; // 父方向那一块 for (int v : g[u]) { if (v == fa) continue; mx[u] = max(mx[u], sz[v]); dfs2(v, u); } }

完整判同构代码如下：

pair<long long, long long> dfsHash(vector<int> g[], int u, int fa) { vector<pair<long long, long long>> vec; for (int v : g[u]) { if (v == fa) continue; vec.push_back(dfsHash(g, v, u)); } sort(vec.begin(), vec.end()); long long h1 = 1, h2 = 1; for (auto &p : vec) { h1 = (h1 * BASE1 + p.first) % MOD1; h2 = (h2 * BASE2 + p.second) % MOD2; } return {h1, h2}; } bool sameTree() { vector<int> c1 = getCentroid(g1, n1); vector<int> c2 = getCentroid(g2, n2); if (c1.size() != c2.size()) return false; vector<pair<long long, long long>> v1, v2; for (int root : c1) v1.push_back(dfsHash(g1, root, 0)); for (int root : c2) v2.push_back(dfsHash(g2, root, 0)); sort(v1.begin(), v1.end()); sort(v2.begin(), v2.end()); return v1 == v2; }

v1 和 v2 相等，说明两棵树在所有重心下的哈希指纹集合一致。因为同构树的重心数量和对应关系是一一匹配的，所以这个判断是充分必要条件。如果只有单重心，集合里只有一个元素，比较退化成一次哈希值比较。

另外，如果对确定性有极高要求，不想承担哈希碰撞的风险，可以改用 AHU 算法的括号序列：每个节点递归得到所有子树的括号序列，排序后拼接，最外层再包上一层括号。两棵树同构当且仅当括号序列完全相等。

string dfsEncode(vector<int> g[], int u, int fa) { vector<string> vec; for (int v : g[u]) { if (v == fa) continue; vec.push_back(dfsEncode(g, v, u)); } sort(vec.begin(), vec.end()); string res = "("; for (auto &s : vec) res += s; res += ")"; return res; }

这个方法理论上是绝对安全的，缺点是字符串拼接和比较开销大，在 n 较大或需要多次比较时不划算。我的建议是：平时练习用括号序列帮助理解，比赛用双哈希拿效率和稳定性。

3.3 典型题目复盘：从空白到 AC

集训里有一道题正好卡在了双重心上。题目是洛谷 P5043 【模板】树同构（[BJOI2015]树的同构），需要判断多棵树之间哪些是同构的。

学生的第一版代码单重心都能跑对，一遇到双重心就 WA。排查下来，问题是只取了第一个重心做哈希，没有考虑第二个重心也可能产生不同的哈希指纹。对于双重心树，两个重心各自为根得到的哈希值很可能不同，但两棵同构的双重心树，重心哈希值集合必须一致。修正后的做法就是上面代码里的vector<pair<long long, long long>>比较集合。

另一个高频错误是递归层数过深导致爆栈。树的节点数一旦到了 2e5 量级，而且构造成一条链，递归 DFS 很容易爆系统栈。比赛时要么在本地编译器加栈空间参数，要么直接用栈模拟 DFS。更稳妥的做法在 Windows 下用 Code Runner 调大栈限制，在 Linux 下用ulimit -s unlimited，但比赛评测环境的栈通常都开得比较大，一般 2e5 递归没问题，只有那种 n 到 1e6 的极端题才需要考虑。

4. 常见问题与排查技巧实录

4.1 树的重心常见问题速查

如果发现自己求出的重心有三个，十有八九是代码逻辑问题。注意 “mx[u] <= n / 2” 这个条件是“充分必要条件”，而不是“收集条件”，一定不会超过两个节点满足。

4.2 树的同构常见问题速查

有一个细节值得单独强调：排序子树哈希值的时机。如果每个节点的子树哈希已经是一个 pair（双哈希），排序要用 pair 的字典序，不要只按第一维排。我之前有个学生只按第一维排，结果两棵子树第一维碰撞但第二维不同，排序后顺序固定错了，整棵树哈希跟着错。

4.3 集训中发现的三个“隐藏坑”

第一个坑是“重心的父方向”在初始化时写成n - sz[1]。根节点的父方向应该是 0，n - sz[1] 也恰好是 0，所以根节点没问题；但是换到非根节点时，如果用同样的式子没问题，但很多人把逻辑想岔了，在根上做特判时把mx[1]设成了一个奇怪的值，导致根节点永远成为最小值。正确做法是统一用n - sz[u]，不要去特判。

第二个坑是哈希初始值的设置。叶子节点我设成 1，有的写法设成 0，两种都可以，但必须保持一致。如果对某棵树从两个不同重心做哈希，初始值不一致，hash 值就完全没可比性。

第三个坑是拼接子节点哈希时的“顺序”虽然排序了，但排序后仍然要防止重复子树造成的影响。比如某个节点下面有两个同构子树，排序后序列可能是 {h, h}，拼接时先乘后加会得到某个值。如果把子树顺序手动调换，排序后还是 {h, h}，拼接值还是同一个，所以这种写法天然稳定。

5. 最后再分享一点我的个人体会

经过这次寒假集训，我最大的感受是：树的重心和树的同构绝对不能只看模板，一定要亲手去推一遍性质。比如重心为什么最多两个？为什么它们相邻？这些性质如果只是背下来，遇到变形题很容易束手无策。我建议每个初学者都手动画一棵 7 个或 8 个节点的树，找出它的重心，再用刚才说的mx[u] <= n / 2验证一遍，多画几棵就真的理解了。

另外，树的同构这块，哈希函数的选择是玄学中的玄学。我自己的准则是：能用双哈希就不用单哈希，能加随机权重就加，代码多写两行，心理踏实得多。还有一个好习惯是把哈希的模数和基数都定义成常量，比赛时如果需要微调，改一处就行。

这次集训还有个小细节，最后一天我让学生把树的重心模板和树的同构模板放在同一个代码文件里，练了十几道题之后，大部分人已经能做到看到题马上判断出该用哪个。如果下次还有人问我树的同构怎么入门，我的回答始终是：先去把树的重心彻底搞懂，再回来学哈希，你会发现整个思路一下子就串起来了。