前后缀分解这个技巧我一开始总觉得它是个“数组题专用”的招数直到有一次现场赛被一道树题卡死才意识到这玩意儿和DFS结合起来才是真正的完全体。那次题目是让统计删掉每个节点后剩余连通块的最大大小我第一反应是“每个点跑一遍DFSO(n^2)”——当然被数据教做人了。赛后看题解只有两遍DFS空间O(n)我当时就在想这不就是树上的前后缀分解吗后来我刷了不少题发现“DFS 前后缀分解”这对组合出现的频率远比想象中高尤其是树形DP、换根、路径统计这些场景。它解决的核心问题就一句话在不重复遍历的前提下拿到每一个枚举点的“左边信息”和“右边信息”。数组里左边是pre[i]右边是suf[i]树上左边是父侧信息右边是子树信息。而这个“左边”信息恰恰是DFS一路递归下来时天然携带的东西。这篇文章想把我踩过的坑、整理过的套路、写熟了的模板都掰开揉碎讲一遍适合那些已经会用DFS但总感觉“差点意思”的朋友。1. 前后缀分解到底在解决什么问题1.1 先用一道最经典的题感知它力扣238题“除自身以外数组的乘积”我愿称之为“前后缀分解的Hello World”。题目意思很简单给你一个数组nums要求返回一个新数组ans其中ans[i]等于nums数组中除了nums[i]以外的所有数的乘积。很多人的第一反应是用除法先算全数组乘积total然后ans[i] total / nums[i]。但一旦nums里有0这个方法立刻崩盘——两个0的情况下分母连0都是错的。而且很多人一开始没想过“不能使用除法”这个限制。这时候前后缀分解的思路就非常自然了pre[i]表示nums[0]到nums[i-1]的乘积即i左侧所有元素乘积不包含nums[i]suf[i]表示nums[i1]到nums[n-1]的乘积即i右侧所有元素乘积不包含nums[i]最终ans[i] pre[i] * suf[i]pre数组从左往右扫一遍就能得到suf数组从右往左扫一遍也能得到两组O(n)的循环中间没有任何除法兼容0的case。这就是前后缀分解最核心的骨架。1.2 为什么DFS会和前后缀分解组合出现数组的pre/suf是静态的、一次算完的但树上的信息不是“静态区间”这么简单。树上我们有父子关系、有递归结构一个节点既可能是某些点的“祖先”前缀来源又可能是另一些点的“后代”后缀来源。我举个例子你就明白了。数组里一个元素i它的“左边”就是下标比它小的所有元素区间固定但树上节点u的“左边”是谁是跟u同一次DFS遍历中从根到u这条路径上的所有节点。这个“左边”是动态的——它跟着DFS的递归深度走。也就是说DFS搜索过程中自然维护的“从根到当前节点的状态”就是树上前缀分解里所说的“前缀”而DFS递归返回时带上来的“子树状态”就是“后缀”。当你想要枚举树上的每一个点并且快速知道这个点“往上”的某信息 和 “往下”的某信息时DFS 前后缀就是最优解。如果不这么干你只能枚举一个点然后重跑一遍全树复杂度直接升到O(n^2)。2. 线性场景数组版前后缀分解的完整建法2.1 前后缀数组的定义与开闭区间约定在动手前我想先说一个最重要也最容易被忽视的细节pre和suf数组的定义必须统一“含不含当前下标”。我见过太多人写着写着把自己绕进去就是因为一会儿是“包含i的前缀积”一会儿是“不包含i的前缀积”下标又越界又错位。我习惯的约定是用“左闭右开”pre[i] 区间[0, i)的聚合结果显然pre[0]是空区间对应乘法单位元1suf[i] 区间(i, n)的聚合结果即[i1, n)显然suf[n-1]也是空区间对应1在这种定义下ans[i] pre[i] * suf[i]所有边界都不会越界。写代码时最好在注释里写清楚这个约定不然隔个两天回来看代码又是一头雾水。2.2 一个完整可运行的实现力扣238我用C写了一个完整版本代码量不长但很值得逐行琢磨vectorint productExceptSelf(vectorint nums) { int n nums.size(); vectorint ans(n, 1); // 左侧前缀ans[i] 先存 [0, i) 的乘积 for (int i 1; i n; i) { ans[i] ans[i - 1] * nums[i - 1]; } // 右侧后缀用变量 right 从右往左累乘 [i1, n) 的乘积 int right 1; for (int i n - 2; i 0; i--) { right * nums[i 1]; ans[i] * right; } return ans; }这个写法只用了一个结果数组没有真的开pre和suf两个数组空间复杂度O(1)不把输出数组算进去。第一遍循环从左往右把前缀乘积直接放进答案数组第二遍循环从右往左用一个滚动变量维护后缀乘积乘到ans上。2.3 进阶变形多个规则叠加、维护最值乘积只是聚合操作的一种前后缀分解同样适用于取最大值、最小值、按位与、异或等等。因为这套思路的本质是“把可分离的区间合并操作预处理成O(1)查询”。举个例子有一类题是“对于每个下标i计算左边最大值和右边最小值的差值”解法就是预处理preMax[i]和sufMin[i]然后一遍循环取答案。核心代码模板是pre[0] 0; // 或 -INF for (int i 1; i n; i) pre[i] max(pre[i-1], a[i-1]); suf[n-1] 0; // 或 INF for (int i n-2; i 0; i--) suf[i] min(suf[i1], a[i1]); for (int i 0; i n; i) ans max(ans, pre[i] - suf[i]);这套模板我在后面讲树的时候会反复用到只是把“下标区间”换成“子树路径”把“for循环遍历”换成“DFS遍历”。3. 树上的前后缀一次DFS解决“删除节点后的分裂问题”3.1 子树大小就是天然的后缀信息进入正题。树上的前后缀分解最典型的一个代表问题就是开头说的统计删掉每个节点后剩余连通块的最大大小。这题暴力做法是每删一个点跑一遍DFS看剩下的连通块多大O(n^2)直接超时。但用前后缀的思维重新想一遍删除节点u之后树会分裂成若干连通块。这些连通块分成两类第一类是u的每个“子树”在DFS树中以u的每个孩子为根的子树第二类是“u的父侧”也就是从u的父节点往上的那一大块大小等于n - siz[u]这里SIZ[u]表示以u为根的子树大小。你会发现siz[u]本身就是DFS从底向上返回的信息这就是“后缀”而n - siz[u]是父侧信息可以理解为“前缀”。所以答案就是对于每个节点u maxComp[u] max(所有孩子v的siz[v], n - siz[u])这个信息只需要一遍DFS求siz再一遍遍历统计即可复杂度O(n)。3.2 父侧信息作为递归参数传递换根法的本质如果题目只要求“删除每个点后最大连通块”那上面的两遍遍历就够了。但很多题会在这个基础上叠加别的条件比如“求所有点中maxComp[u]最小的点”也就是求树的重心或者“对每个点求删除后距离不超过K的节点数”之类。这时候你就需要一种更灵活的写法——在DFS递归过程中同时携带父侧信息往下传。这就是换根法的本质了。核心思路是向下递归时你天然有当前路径上累积的“前缀信息”比如从根走到当前节点的累计值从子树返回时你积攒了所有孩子的“后缀信息”比如整棵子树的大小、子树里满足条件的节点数把这两边信息在u处合并就是u的全部答案用代码写就是void dfs(int u, int parent, int parentSideSize) { // parentSideSize 是当前节点u的父侧连通块大小前缀信息 int totalMax parentSideSize; // 先假设父侧最大 for (int v : g[u]) { if (v parent) continue; // 递归前传给孩子v的父侧大小 n - siz[v] // 注意这里siz已经先算好了 dfs(v, u, n - siz[v]); // 从孩子返回后把子树大小作为候选 totalMax max(totalMax, siz[v]); } ans[u] totalMax; }这里有个细节值得琢磨dfs(v, u, n - siz[v])中为什么传下去的是n - siz[v]而不是n - siz[u]因为当你站在孩子v的角度看它的父侧连通块是整个树刨掉以v为根的子树大小就是n - siz[v]。至于u的父侧信息已经在v的父侧计算中被自动包含了——这正是“递归携带前缀”的精妙之处。3.3 完整代码统计删掉每个点后的最大连通块我把完整的C代码贴出来包含两遍DFS第一遍求siz第二遍计算答案。#include bits/stdc.h using namespace std; const int MAXN 100005; vectorint g[MAXN]; int siz[MAXN]; int ans[MAXN]; int n; void dfs_siz(int u, int parent) { siz[u] 1; for (int v : g[u]) { if (v parent) continue; dfs_siz(v, u); siz[u] siz[v]; } } void dfs_answer(int u, int parent, int parentSideSize) { ans[u] parentSideSize; for (int v : g[u]) { if (v parent) continue; ans[u] max(ans[u], siz[v]); dfs_answer(v, u, n - siz[v]); } } int main() { cin n; for (int i 1; i n; i) { int a, b; cin a b; g[a].push_back(b); g[b].push_back(a); } dfs_siz(1, 0); dfs_answer(1, 0, 0); // 根节点没有父侧传0即可 for (int i 1; i n; i) { cout i - ans[i] endl; } return 0; }你可以把这段代码丢到本地调一调跑一棵链状树、跑一棵星形树对比一下结果很快就会对“父侧大小”这个概念有感觉。3.4 为什么这套写法比暴力快复杂度推导暴力做法是枚举每个点删除删除后重新DFS一遍所有剩下来的连通块每个点最坏情况下要参与O(n)次DFS重跑总复杂度O(n^2)。用前后缀分解优化后第一遍DFS求siz每个点访问一次第二遍DFS每个点访问一次总复杂度O(n)额外空间只有几个数组。这个复杂度差距写下来好像没什么但在n10^5级别的树上O(n^2)是10^10次运算直接跑死人O(n)则是秒过。算法竞赛里这就是天壤之别。4. DFS搜索中的前缀维护路径统计与回溯撤销4.1 从根到当前节点的路径状态DFS天然维护序列前缀如果说第3节讲的是“自底向上的后缀信息”那这一节讲的是“自顶向下的前缀信息”。有一类问题是统计树上有多少条路径满足某个性质比如路径和等于K路径异或和等于K路径上出现某种颜色的次数等。这种题你如果对每条路径单独枚举路径数量是O(n^2)级别的复杂度直接爆炸。但DFS给了我们一个非常巧妙的工具当DFS走到当前节点u时从根到u的这条路径上的所有状态都是已知且连续的。这本质上就是一个“动态的前缀序列”。举个例子给定一棵带权树问有多少条路径的异或和等于K。这类题比如Codeforces上出现过的经典题的经典做法就是DFS 哈希表维护一个从根到当前节点u的路径异或值curXor对于当前路径上的任意起点x到终点u的路径异或值就等于rootToU ^ rootToParent(x)换句话说我们需要在历史中查询多少个“前缀异或值”等于curXor ^ KDFS走到u时把cnt[根到u的前缀异或值]加1离开u时减1这一步加一、离开时减一就是DFS的“回溯撤销”。它保证了哈希表里随时存活的都是“当前路径上的祖先前缀”不会混入兄弟子树里的信息。4.2 用哈希表匹配前后缀路径异或和题目我把核心代码写出来。这个代码虽然短但里面每一行的顺序都值得抠几遍#include bits/stdc.h using namespace std; const int MAXN 100005; vectorpairint, int g[MAXN]; // (to, weight) int val[MAXN]; // 点权或者是边权 unordered_mapint, int prefixCnt; long long ans 0; int K; void dfs(int u, int parent, int curXor) { // 先查之前路径上有多少个前缀异或值使得 xor K ans prefixCnt[curXor ^ K]; // 再把当前前缀加入记录要在递归子树之前加 prefixCnt[curXor]; for (auto [v, w] : g[u]) { if (v parent) continue; dfs(v, u, curXor ^ w); } // 回溯撤销当前节点及其子树搜完它对其他子树已经不可见 prefixCnt[curXor]--; } int main() { int n; cin n K; for (int i 1; i n; i) { int a, b, w; cin a b w; g[a].push_back({b, w}); g[b].push_back({a, w}); } prefixCnt[0] 1; // 空前缀保证根节点也能匹配 dfs(1, 0, 0); cout ans endl; return 0; }这里要注意查哈希表应该在把当前节点加入哈希表之前做然后更新哈希表。顺序错了答案会差出“u到u自身的路径”这种非法情况。很多新人第一次写都会在这个顺序上翻车。4.3 回溯撤销的细节子树之间互不干扰的原理这里我多说一句回溯撤销为什么必须做。树的DFS过程是先走到第一条子树把子树挖完再回到u再走向第二条子树。如果你在第一条子树里把某些值加进了哈希表而不撤销那么第二条子树在查询的时候就会看到“经过兄弟子树的前缀”但这一类前缀根本不在它的路径上统计出的答案就会偏大。所以正确思路是子树是一个封闭的上下文进入前状态是A子树搜完回到父节点时状态必须还原为A。这就是“DFS维护动态前缀”的核心纪律加了什么离开前必须减掉什么。很多高级树题比如边分治前的前置信息维护、树上启发式合并DSU on Tree其实都建立在这个“进入时增量、离开时撤销”的机制之上把这一节吃透后面那些题会顺畅很多。5. 实战翻车记录边界、数组语义、递归恢复5.1 pre和suf数组定义含糊导致的越界我见过很多次这样的错误pre[i]定义为包含i的前缀积然后用ans[i] pre[i] / nums[i]——接着遇到除数为0直接崩盘。或者把suf[i]定义成从i到n-1的后缀积却用ans[i] pre[i-1] * suf[i1]结果i0和in-1处逻辑混乱。真实竞赛里一旦下标越界调起来非常痛苦因为不是所有越界都会立即崩溃有时候只是答案全错但不报错。我的建议很简单统一用“不含当前下标”的定义并且在代码开头注释写明区间边界。比如// pre[i] [0, i) 的乘积 // suf[i] (i, n) 的乘积这个约定一旦固定下来ans[i]直接等于pre[i]*suf[i]根本不需要对边界特判。5.2 递归里改了全局状态忘记恢复这个坑在路径统计题里太常踩了。我举个很常见的例子void dfs(int u, int parent) { cnt[color[u]]; // 进入时增量 for (int v : g[u]) { if (v parent) continue; dfs(v, u); } // 这里忘了 cnt[color[u]]--; - 忘记恢复 }如果漏掉最后一行恢复整个子树的状态会污染后续查询。调试这个问题时你看到的现象往往是“答案总是偏大而且越深的节点偏得越离谱”。要避免这种问题我总结了一个土办法写递归函数时把“进入时改动的东西”列成一个清单在return前逐一恢复。如果你用的是C可以专门写一个大的作用域块或者干脆把状态封装成结构体借助RAII机制自动恢复。比赛里我就用前者简单不容易出错。5.3 根节点和叶子节点的特判场景前后缀分解的边界问题在数组场景容易看出在树场景容易被忽略根节点没有“父侧”信息所以parentSideSize初始化为0或者根据题目语义初始化为负无穷、0个节点等叶子节点没有任何子树所以maxComp[u]就只取决于父侧大小如果题目要求“删除节点后形成的每个连通块都满足某个条件”你还要注意总节点数是1的情况此时删掉唯一节点后没有任何连通块答案应该是0而不该是n-siz[u]0然后被max吃掉很多题目WA了半天最后发现就是特殊输入没处理n1, n2, 或者树退化成一条链。建议写完之后专门跑这类边界数据。5.4 在不破坏递归状态前提下的“原地修改”技巧第3节的树案例中我们用了两遍DFS一遍求siz一遍求答案。有没有可能把两遍合并成一遍可以但前提是你在递归时能同时拿到“父侧大小”。合并的思路是在第一次DFS求siz的过程中如果你还同时想算每个节点的maxComp[u]那父侧大小必须在递归到孩子节点前就算好并传下去。这时候需要注意siz[v]还没求出来你就不能直接n - siz[v]。所以常见的做法还是两遍DFS。第一遍稳定求siz第二遍再传父侧信息。不要为了“少一遍DFS”强行合并代码可读性会大打折扣调试时间反而更长。不过有一种情况可以合并如果你只是找重心在DFS过程中不断更新min(maxComp))你可以一遍DFS求完siz后直接在返回过程中检查每个点——因为此时每个点的siz都算好了父侧大小n - siz[u]也很好求。这种写法本质上还是利用了“siz都算好了”的事实。6. 哪些题型适合“DFS 前后缀分解”组合拳6.1 能套用的特征模板不是我硬要把所有树题都归类到“前后缀分解”但实战中确实有几个明显的信号出现任何一个你都可以往这个方向想一想问题涉及“删掉某个点/某条边之后剩余部分的某种统计”——这类题几乎必用父侧信息和子树信息的组合问题需要对每个点求“以该点为根时”的某种值——这就是换根法树上前后缀的标准形态问题需要统计路径、且路径的两个端点分布在某个分割点的两侧——DFS维护前缀 哈希表匹配后缀问题看似需要“枚举所有分割点每次重新计算两侧”——这就是前后缀分解的目标场景如果符合以上任意一条先别急着写暴力。停下来画一棵树想一想如果DFS到某个节点u我能从子树返回得到什么后缀信息如果DFS递归参数里携带什么我能从父侧得到什么前缀信息两边信息在u合并能不能算出u的答案这个“三步法”我用了很久实战里非常好用基本能把80%的“树统计类”题目都套进去。6.2 两道高频变形题的思考方向变形1给定树求以每个节点为根时整棵树的最大子树大小。这不是单纯求重心而是对所有点都要求。做法就是我们第3节的dfs_answer第一遍求siz第二遍对每个点算max(最大子树siz, n-siz[u])。这就是换根法模板题几乎能解决一大票以重心为核心的衍生题。变形2求树上所有路径中权值为K的路径数量。这就是第4节的哈希表做法。关键点在于“进入节点前查询、进入节点后更新、离开节点前撤销”的顺序。如果路径定义里有“边权”和“点权”的差别只需要把权值放在哪个环节处理好即可。6.3 我的建议先画图再写代码很多人学DFS相关技巧时喜欢直接看代码、抄模板我觉得这是最大的误区。前后缀分解本身逻辑不复杂但它和树的递归结构耦合后容易让人丢掉“数据流”的直觉。我自己的习惯是拿到一道树题先在草稿纸上画一棵7个节点的树然后把“删掉某个点”这个过程可视化自己走一遍DFS把pre和suf的值标在每个节点旁。这个方法花不了五分钟但能让我写码时不出边界错误、不掉递归恢复。如果你也觉得图画起来麻烦退一步至少要在代码里用printf或者debugger跟踪一下siz[u]和parentSideSize的变化。看到一个节点递归进子树的传参过程比盯着代码空想一百遍都有效。前后缀分解是一个“越用越顺手”的工具。数组题里它是两遍循环树题里它变成两遍DFS加一个递归传参。本质上都是“预处理两侧信息 枚举分割点”。一旦你在实战里自己动手推出过一遍换根、自己调通过一次路径统计的哈希表bug这套思想就算真正长在你脑子里了。下次再看到“删掉每个节点求XXX”的题你至少不会再犹豫要不要直接暴力。
