Corrupted Friendship题解：DFS子树大小与组合数补集统计

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后每个叶子都变成孤立块大小全是1C(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; vectorvectorint g; vectorll 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(N1, {})会把旧数据清掉sz和ans也一起重置这样每一组数据都是干干净净从零开始的。这个动作看起来不起眼却是多组输入题最容易翻车的地方。4.3 链状数据会直接爆掉递归栈树形DFS最大的隐患是毒瘤链。十万个节点串成一条链时递归版dfs会一层层压栈递归深度直接到十万。很多平台的默认栈空间根本扛不住运行到一半就段错误。这种情况在旧评测环境里尤其常见。解决方式很粗暴把系统递归栈换成自己的显式栈。逻辑几乎完全一样只是把“调用dfs(v)”换成了“把v压进栈”把“后序更新sz”换成了“逆序遍历先序序列”。void dfsIter(int root) { vectorint parent(N 1, 0), order; vectorint 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)。我们把这几个结论放进同一个表里统计对象删除后分出的连通块不经过该对象的点对数经过该对象的点对数删除节点w每个儿子子树块 上方块Σ C2(块大小)C2(N) - Σ C2(块大小)删除边e边两侧的两个子树块C2(sz) C2(N - sz)sz × (N - sz)这个表不需要背真正有价值的是底层的思考方式凡是遇到“唯一路径是否经过某个点或边”的计数几乎都能靠“这个点或边把树分成了哪些块”来回答。5.2 继续延伸点对距离和、割点判定、相交路径计数再往外走一步这个思想能覆盖的题目类型比想象中多。比如求所有点对距离和常见的做法就是把距离拆到每条边上一条边的贡献正好是它两侧点对数也就是sz×(N-sz)。又比如判断一个点是不是割点本质也是看它被删掉之后连通块数量是否大于1只需要统计儿子子树个数以及上方块是否存在。再比如一些“路径相交计数”的题会先给一堆树上的路径然后问某条路径经过另一条路径多少次。这类题经常也要先算清楚“某个点/边把树切成哪几块”然后再配合树上差分统计。这些问题看着千差万别公共内核都是同一个树是唯一的路径结构删除一个元素后连通块的划分就是一切计数的出发点。刷题如果只记这一题的AC代码过两周就忘如果记住“删点看块块内不算总数减块内”这个思考方式以后再看到“腐化”“破坏”“断联”这类词几乎可以条件反射地联想到连通块和补集计数。最后分享一个我调试这类树题的小习惯对拍时固定用链、星形、单点三种极简结构。链能暴露上方块和子树块大小的公式问题星形能验证中心节点的答案是不是C(N,2)单点能逼你检查N1时C2(0)和C2(1)的边界。这三种数据跑一遍核心公式基本就能确认没写错再出问题就只剩容器重置和long long那些事了。