前后缀分解这个技巧，我一开始总觉得它是个“数组题专用”的招数，直到有一次现场赛被一道树题卡死，才意识到这玩意儿和DFS结合起来，才是真正的完全体。那次题目是让统计删掉每个节点后剩余连通块的最大大小，我第一反应是“每个点跑一遍DFS，O(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[i+1]到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)的聚合结果，即[i+1, n)，显然suf[n-1]也是空区间，对应1
在这种定义下，ans[i] = pre[i] * suf[i]，所有边界都不会越界。写代码时最好在注释里写清楚这个约定，不然隔个两天回来看代码，又是一头雾水。
2.2 一个完整可运行的实现（力扣238）
我用C++写了一个完整版本，代码量不长但很值得逐行琢磨：
vector<int> productExceptSelf(vector<int>& nums) { int n = nums.size(); vector<int> ans(n, 1); // 左侧前缀：ans[i] 先存 [0, i) 的乘积 for (int i = 1; i < n; i++) { ans[i] = ans[i - 1] * nums[i - 1]; } // 右侧后缀：用变量 right 从右往左累乘 [i+1, 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[i+1], a[i+1]); 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; vector<int> 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)，额外空间只有几个数组。
这个复杂度差距写下来好像没什么，但在n=10^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 ^ K - DFS走到u时，把
cnt[根到u的前缀异或值]加1；离开u时，减1
这一步加一、离开时减一，就是DFS的“回溯撤销”。它保证了哈希表里随时存活的都是“当前路径上的祖先前缀”，不会混入兄弟子树里的信息。
4.2 用哈希表匹配前后缀：路径异或和题目
我把核心代码写出来。这个代码虽然短，但里面每一行的顺序都值得抠几遍：
#include <bits/stdc++.h> using namespace std; const int MAXN = 100005; vector<pair<int, int>> g[MAXN]; // (to, weight) int val[MAXN]; // 点权，或者是边权 unordered_map<int, 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[i+1]，结果i=0和i=n-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了半天，最后发现就是特殊输入没处理：n=1, n=2, 或者树退化成一条链。建议写完之后专门跑这类边界数据。
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”的题，你至少不会再犹豫要不要直接暴力。
