企业官网建设流程全解析

A同学昨晚在群里发了一道题，编号是11981，题目名叫 Corrupted Friendship。他问我：“这题题面绕来绕去，到底要让我统计什么？”我一看就明白，这种题表面是讲“友谊破裂”的故事，实际内核就是经典的树上点对计数。你去枚举所有路径肯定完蛋，真正要做的只有两件事：一遍DFS算出子树大小，再套一个组合数补集公式。

如果你正在刷树形DP相关的题，或者卡在这种“路径经过某个节点多少次”的问题上，这篇笔记应该能帮你把思路彻底理清。全文会用我自己的理解把题意重新组织一遍，给出公式推导、完整C++代码以及几个我在实际提交中踩过的坑。题面本身并不复杂，复杂的是怎么把“腐化一个节点”翻译成“删掉一个点之后数连通块”。

1. 题面背后的关键信息：腐化节点究竟在统计什么

1.1 先把题意理顺：唯一路径上的节点就是“友谊见证者”

我没有拿到这题的官方英文题面，按我自己的理解重新整理一遍：一场朋友圈子，里面有N个人，朋友关系恰好构成一棵树，任意两个人之间都通过唯一的一条路径连通。题里把这条唯一路径看作一段友谊链，路径上经过的所有节点都是这段友谊的见证者。

题目里的“腐化”事件是这样的：某个节点变坏了，那么所有路径中包含该节点的友谊链都要断掉。最终要求的是，对树上的每一个节点w，分别回答“如果w腐化了，有多少对朋友的友谊会因此破裂”，然后把所有节点的答案加起来输出。

这里有一个非常关键的观察：腐化节点w，本质上就是把w从树上删除。w被删掉之后，剩下的N-1个节点如果还连通，说明他们之间的路径根本没有经过w；如果不连通，说明唯一路径上必然有w，友谊就断了。所以这个题根本不是在逐条路径上做判断，而是在数“删除w后，跨连通块的点对数”。

1.2 删点之后的朋友圈：连通块才是真正的计量单位

我习惯用一个生活场景来类比：把这棵树想象成由好几座桥连接的岛屿群，每个节点是一座岛，每条边是一座桥。w是其中一座很重要的枢纽岛，这座岛某天突然沉没了，整个群岛网络立刻分裂成若干块。原来住在同一块里的人还能互相走动，跨块的人就再也联系不上。

那么腐化带来的破坏，就是“原本能联系、现在联系不上的那些人”有多少对。这个数等于全树总点对数，减去仍然在同一块内部的点对数。

这个转换做完，题目难度已经从图论降到组合计数了。因为连通块的大小不需要逐个去数，只需要知道每个节点的子树大小，树的DFS天然就能提供这个信息。后文所有内容都在围绕这件事展开。

2. 公式怎么来：用补集数出“不经过w”的点对

2.1 暴力做法为什么必死

先看一下最容易想到的暴力方案：枚举所有的点对(u,v)，然后从u到v走一趟树，判断路径上是否包含w。点对数量已经有C(N,2)个，单次路径判断最轻也要O(logN)甚至O(N)，整体复杂度动辄O(N^2)往上，N稍微大一点就完全跑不动。

有人会想，那我预处理每个节点到根的路径，做树上差分行不行？这其实方向已经对了，但差分通常用来回答“某条路径上是否有标记”或者“经过某条边的次数”，对一个节点w去枚举所有经过它的路径，最后还是绕回点对级别的枚举。真正省时间的做法是反过来数：不经过w的点对有多少，然后用总数一减。

2.2 补集转换：数“还活着”的朋友比数“断联”的朋友简单

全部朋友对数是固定的，C(N,2)。删掉w之后，树会分裂成若干连通块。这时候有一个很干脆的事实：

两个节点u、v的路径不经过w，当且仅当u、v在同一个连通块里；路径经过w，当且仅当u、v不在同一个连通块里。

证明只需要用树的唯一路径性质。如果u和v在同一个块里，那么连接它们的唯一路径上的每一条边都在这个块内，自然不经过w。反过来，如果它们不在同一个块里，那么它们在删掉w之后没有任何一条边路径可以连通，唯一路径只能依赖w，所以路径一定经过w。

于是对于节点w，设删掉它之后各个连通块的大小为s1, s2, ..., sk，那么：

不经过w的点对数 = C(s1,2) + C(s2,2) + ... + C(sk,2) 经过w的点对数 = C(N,2) - Σ C(si,2)

这才是这道题唯一的“算法”，后面全是实现细节。我每次写这类题都会提醒自己：正面不好数的东西，先看看反面好不好数，往往一数就破。

2.3 三个边界小例子，验证公式不是算错了

公式推出来之后一定要拿小数据手算一下，不然边界错都不知道。第一个例子是一条5个节点的链：1-2-3-4-5，以1为根。看节点3，删掉3后，左边块{1,2}，右边块{4,5}，大小都是2。C(5,2)=10，内部点对是C(2,2)+C(2,2)=2，所以经过3的点对数等于8。手数一下，5个点里只有{1,2}和{4,5}这两对的路径不经过3，其余8对全部经过，完全吻合。

第二个例子是星形图，中心点1作为根，周围挂着很多叶子。删掉中心1后，每个叶子都变成孤立块，大小全是1，C(1,2)=0，所以答案就是C(N,2)。这也符合直觉：任意两个叶子之间的唯一路径都要穿过中心，中心一坏，所有叶子之间全断。

第三个例子看叶子节点leaf。删掉leaf后，剩下一个大小为N-1的连通块，所以经过leaf的点对数是C(N,2)-C(N-1,2)=N-1。这也很直观，只有以leaf为一个端点的那些路径才会经过它。

三个例子全对上，公式基本可信。

3. 代码实现：一遍DFS同时拿子树大小和上方块大小

3.1 为什么随便定根都行

这里有一个容易被忽略的性质：答案完全不依赖“谁是根”。因为“删掉w后形成哪些连通块”是树本身的结构属性，和DFS从哪个节点开始没有任何关系。所以代码里可以放心固定1号节点当根。

但理解这一点很重要，否则写公式时容易把“以1为根得到的子树”和“真实删点后的上方块”搞混。上方块指的是：删掉w后，w的父方向那一坨节点，它们不在w的子树里。这个块的大小正好是N-sz[w]，其中sz[w]是以当前根计算出的子树节点数。如果w本身就是根，那N-sz[w]=0，这一项自然消失。

3.2 子树大小和块大小的精确关系

对根为1的树做一遍DFS，每个节点u的sz[u]表示以u为根的子树包含多少节点。当删除u时，连通块的构成非常规律：

• u的每一个直接儿子v，对应一个连通块，大小等于sz[v]。
• 不在u子树里的所有节点，凑成另一个连通块，大小等于N-sz[u]。
• 如果u是根节点，最后一个块大小为0，不影响计算。

这些块覆盖了除u外的全部N-1个节点，而且互不重叠。这个结论可以顺手验证一下：把所有儿子子树的大小和上方块大小相加，得到的是Σsz[v] + (N-sz[u])，由于sz[u]=1+Σsz[v]，所以结果正好是N-1。

于是每个节点u的答案就变成一个非常短的式子：

ans[u] = C2(N) - (Σ C2(sz[v]) + C2(N - sz[u]))

这里C2(x)表示x*(x-1)/2。

3.3 可以直接抄的C++代码（递归版）

我给出一个完整的递归实现，直接在本地跑就能看到结果。代码很短，但类型选择很关键，所有和组合数相关的量一律用long long，原因下一章详细说。

#include <bits/stdc++.h> using namespace std; using ll = long long; vector<vector<int>> g; vector<ll> sz, ans; int N; ll C2(ll x) { return x * (x - 1) / 2; } void dfs(int u, int p) { sz[u] = 1; ll inner = 0; for (int v : g[u]) { if (v == p) continue; dfs(v, u); sz[u] += sz[v]; inner += C2(sz[v]); } ll up = N - sz[u]; inner += C2(up); ans[u] = C2(N) - inner; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int T; cin >> T; while (T--) { cin >> N; g.assign(N + 1, {}); sz.assign(N + 1, 0); ans.assign(N + 1, 0); for (int i = 0; i < N - 1; i++) { int u, v; cin >> u >> v; g[u].push_back(v); g[v].push_back(u); } dfs(1, 0); ll total = 0; for (int i = 1; i <= N; i++) total += ans[i]; cout << total << "\n"; } return 0; }

代码里g存的是无向边，dfs一次把所有sz和ans都算完，最后main里把每个节点的答案累加，就是题目要的那个总和。整体时间复杂度和空间复杂度都是O(N)，对N到十万级别完全够用。

额外说明一下：我这里按多组输入写了，实际提交时如果题目给的是单一测试数据，去掉T循环、保留最里面的while结构即可。老式评测系统里两种输入格式都很常见，直接改成 while (cin >> N) 也一样能跑。

4. 我踩过的坑：long long、容器重置、递归爆栈

4.1 第一步就翻车：int根本装不下组合数

树上计数题最经典的坑就是整数溢出，我自己第一次写的时候也在这一步吃过亏。N取100000的时候，C(N,2) = 100000 × 99999 / 2，大约是50亿，已经超过int的上限21亿。如果你写一个int类型的C2函数，算到乘法阶段就已经溢出，得出的结果完全不可信。

更阴险的是，ans[u]本身可能没有单个超过21亿，但题目最后要把所有节点的ans[u]加起来。N是十万规模时，总和会到几十万亿，只有long long扛得住。所以代码里sz、inner、ans、C2函数的参数和返回值，我全部写成ll，一点侥幸空间都不留。

4.2 多组输入之间，邻接表和数组没清干净的后果

这类老题非常喜欢多组数据。每次循环开头如果只读了N就忘记重置容器，上一组残留的邻接表还会待在那里。下一组的N如果更大，还可以硬着头皮跑；如果更小，访问到旧索引直接越界，轻则答案错，重则运行时错误。

正确做法是每轮都用assign重新分配一次。g.assign(N+1, {})会把旧数据清掉，sz和ans也一起重置，这样每一组数据都是干干净净从零开始的。这个动作看起来不起眼，却是多组输入题最容易翻车的地方。

4.3 链状数据会直接爆掉递归栈

树形DFS最大的隐患是毒瘤链。十万个节点串成一条链时，递归版dfs会一层层压栈，递归深度直接到十万。很多平台的默认栈空间根本扛不住，运行到一半就段错误。这种情况在旧评测环境里尤其常见。

解决方式很粗暴：把系统递归栈换成自己的显式栈。逻辑几乎完全一样，只是把“调用dfs(v)”换成了“把v压进栈”，把“后序更新sz”换成了“逆序遍历先序序列”。

void dfsIter(int root) { vector<int> parent(N + 1, 0), order; vector<int> st; st.push_back(root); parent[root] = -1; while (!st.empty()) { int u = st.back(); st.pop_back(); order.push_back(u); for (int v : g[u]) { if (v == parent[u]) continue; parent[v] = u; st.push_back(v); } } for (int i = N - 1; i >= 0; i--) { int u = order[i]; sz[u] = 1; ll inner = 0; for (int v : g[u]) { if (v == parent[u]) continue; sz[u] += sz[v]; inner += C2(sz[v]); } ll up = N - sz[u]; inner += C2(up); ans[u] = C2(N) - inner; } }

这个迭代版的原理是：order保存的是先序遍历顺序，父节点一定比所有子节点先进入order，所以逆序处理order时，处理到某个u，它的所有孩子的sz一定已经算完。栈深从系统栈的十万层，变成自己管理的一个数组，完全不用担心爆栈。我后来写树形DP默认就从迭代版起手，省得换着平台还要考虑栈大小。

5. 从这题能带出来的通用套路：节点删除与边删除其实是一家人

5.1 同一招换个对象：删点计数和删边计数对照

这道题刷完，再看其他树上计数题，会自然形成一个框架：统计“删掉某个结构后，还剩多少对点仍然连通”，本质都是“总数减块内数”。删节点看连通块，删边也一样。

删掉一条边e，树直接分成两块，大小分别是sz和N-sz，其中sz是边某一侧子树的节点数。那么不经过这条边的点对数就是C2(sz)+C2(N-sz)，经过这条边的点对数就是sz×(N-sz)。我们把这几个结论放进同一个表里：

这个表不需要背，真正有价值的是底层的思考方式：凡是遇到“唯一路径是否经过某个点或边”的计数，几乎都能靠“这个点或边把树分成了哪些块”来回答。

5.2 继续延伸：点对距离和、割点判定、相交路径计数

再往外走一步，这个思想能覆盖的题目类型比想象中多。比如求所有点对距离和，常见的做法就是把距离拆到每条边上，一条边的贡献正好是它两侧点对数，也就是sz×(N-sz)。又比如判断一个点是不是割点，本质也是看它被删掉之后连通块数量是否大于1，只需要统计儿子子树个数以及上方块是否存在。

再比如一些“路径相交计数”的题，会先给一堆树上的路径，然后问某条路径经过另一条路径多少次。这类题经常也要先算清楚“某个点/边把树切成哪几块”，然后再配合树上差分统计。这些问题看着千差万别，公共内核都是同一个：树是唯一的路径结构，删除一个元素后，连通块的划分就是一切计数的出发点。

刷题如果只记这一题的AC代码，过两周就忘；如果记住“删点看块，块内不算，总数减块内”这个思考方式，以后再看到“腐化”“破坏”“断联”这类词，几乎可以条件反射地联想到连通块和补集计数。

最后分享一个我调试这类树题的小习惯：对拍时固定用链、星形、单点三种极简结构。链能暴露上方块和子树块大小的公式问题，星形能验证中心节点的答案是不是C(N,2)，单点能逼你检查N=1时C2(0)和C2(1)的边界。这三种数据跑一遍，核心公式基本就能确认没写错；再出问题，就只剩容器重置和long long那些事了。