企业官网建设流程全解析

树形DP（很多地方也写成树状dp）在我眼里是算法里少有的"一旦开窍就再也不会忘"的东西。它的内核其实只用一句话就能概括：在树上做自底向上的状态合并。但真到了写题的时候，卡住大多数人的从来不是转移方程本身，而是前面那几步——状态怎么定义、复杂度为什么是那个数、答案不在根上的时候怎么办、递归爆栈了怎么改。这几年我带过不少人啃树形dp，发现同一个人把"最大独立集"写熟之后，遇到换根DP还是会翻车，遇到树上背包还是会写成 O(n³)。所以这篇不打算再复述一遍教材上的定义，而是按我自己的理解顺序，把树形dp拆成几件真正需要动手的事来讲，从状态设计一路讲到调试排查，代码都用 C++ 写，能直接抄去改。

1. 树上问题为什么天然适合"自底向上"

1.1 从一个具体的小问题入手

先别急着谈"状态""转移"这些词。拿一个最朴素的题感受一下：给一棵 n 个点的树，每个点有个权值，要求选出若干个点，选出的点之间不能有边相连，问最大权值和是多少。这个问题叫树上最大权独立集，是树形dp最经典的入门形态。

你可能会想：暴力枚举所有点选或不选，2ⁿ 种情况，n 稍微大一点就废了。但树这个东西有个很好的性质——它没有环，任意一条边断开都会把树分成两半，而这两半之间唯一的联系就是这条边本身。也就是说，如果我从叶子往上考虑，每个点只需要关心"我的子节点选没选"这一件事，完全不用管远处的点怎么选。这就是自底向上能成立的物理直觉。

把这个直觉翻译成代码，就是两个数组：dp[u][0] 表示以 u 为根的子树里、不选 u 的情况下的最大权值和；dp[u][1] 表示选了 u 的情况下的最大权值和。转移逻辑不说自明：如果我选了 u，那所有儿子都不能选，只能取 dp[v][0]；如果我不选 u，每个儿子选或不选都合法，取两者的较大值。

#include <bits/stdc++.h> using namespace std; const int N = 1e5 + 5; vector<int> g[N]; int val[N]; long long dp[N][2]; void dfs(int u, int fa) { dp[u][1] = val[u]; dp[u][0] = 0; for (int v : g[u]) { if (v == fa) continue; dfs(v, u); dp[u][1] += dp[v][0]; dp[u][0] += max(dp[v][0], dp[v][1]); } } int main() { // 建图、读权值略 dfs(1, 0); printf("%lld\n", max(dp[1][0], dp[1][1])); return 0; }

这段代码短得有点不像话，但它已经把树形dp的全部骨架都摆出来了：递归下去把子问题算完，回到当前点时把子问题的答案按规则合并。真正需要动脑的地方，从来都在"按什么规则合并"上。

1.2 递归序本身就是执行顺序

有一个点很多人没意识到：树形dp的求解顺序和普通的线性dp不一样。数组dp不是按下标从小到大填的，而是按后序遍历的顺序填的。dfs 函数在进入 u 之后先对所有子节点递归，等每个子节点都返回了，才开始算 dp[u]。这意味着在写 dp[u] 那两行的时候，所有儿子的 dp 值一定是最终值，绝对不会出现"用到还没算完的状态"这种事。

这一点决定了手写树形dp时的一个硬规则：合并儿子的循环必须写在递归调用之后，不能提前。我见过有人为了"先统计一下子树大小"把循环拆开，结果顺序一乱整个dp就崩了。

顺便说一个常见误会。很多教材把树形dp写成"从叶子节点开始递推"，给人一种"要先把叶子挑出来排序"的印象。实际上你不需要显式地排序，递归调用栈自动帮你做了这件事。真到了递归爆栈要改成迭代的时候，才需要手工去构造这个后序顺序，那是后话。

1.3 它和线性dp的分水岭

线性dp的状态转移是"从前往后"或者"从小范围往大范围"，状态之间存在一个天然的偏序。树形dp的状态之间存在的偏序是父子关系：儿子的状态必须先于父亲算完。这就是全部区别。

所以判断一个问题能不能用树形dp，看两件事就够了：第一，问题的结构是不是树（或者可以转化成树，比如基环树的环上拆边）；第二，一个点的答案能不能只靠它子树的信息拼出来。第二条比第一条更容易踩雷，因为有很多树上问题，光靠子树信息是不够的——这时候要么加状态维度，要么上换根DP，要么干脆换算法（点分治、树上莫队之类）。

提示：如果一个树上问题的答案需要"跨过某个点往上走再拐下来"，别急着往树形dp里硬塞状态，先想想是不是换根DP或者路径统计的活。

2. 状态设计：落笔之前先想清楚"我要记住什么"

2.1 状态里挂"当前点选没选"

最简单的一类状态就是"当前点是否被选中"，最大独立集就是典型。它的本质是把约束拆成"局部可见"的形式：题目说"相邻两点不能同时选"，我只要在合并儿子的时候检查这条边就够了，不需要记住整条路径。

顺着这个思路还能延伸出不少变体，比如相邻两点不能同时不选（最小支配集的弱化版）、相邻两点颜色不同（树的二染色）、每个点有 k 种颜色且相邻不能同色。这些问题的共同点是：约束只涉及一条边上的两个端点，所以状态里只需要挂当前点的选择即可。

但一旦约束跨过两条边、三条边，比如"距离为 2 的点不能同色"，状态就不能只记自己了，还得记住父亲的染色情况。这就是状态维度膨胀的起点。

2.2 状态里挂"容量"：树上背包

第二种常见形态是把一个数值型的量挂进状态。典型的就是树上背包：给一棵树，每个点有重量 w 和价值 v，选一个点必须先选它的父亲，问容量为 m 时能拿到的最大价值。

这里的 dp[u][j] 表示在 u 的子树里选 j 个点（且选了 u）的最大价值。转移就是在合并儿子的时候做一次卷积式的枚举：

int sz[N]; long long dp[N][M]; // 注意 M 不要开太大，下面会讲 void dfs(int u, int fa) { sz[u] = 1; for (int j = 0; j <= m; ++j) dp[u][j] = -INF; dp[u][1] = val[u]; for (int v : g[u]) { if (v == fa) continue; dfs(v, u); int up = min(sz[u], m); for (int j = up; j >= 1; --j) { if (dp[u][j] == -INF) continue; int lim = min(sz[v], m - j); for (int k = 1; k <= lim; ++k) { if (dp[v][k] == -INF) continue; dp[u][j + k] = max(dp[u][j + k], dp[u][j] + dp[v][k]); } } sz[u] += sz[v]; } }

这段代码里藏了两个细节，都是踩过坑才记住的。第一，j必须从大到小枚举，因为 dp[u][j+k] 会覆盖到比 j 大的位置，从小到大枚举会导致同一个儿子被重复选。第二，k的上界要卡成min(sz[v], m - j)，不能无脑写成 m，否则复杂度会白白多一个量级。

2.3 状态里挂"正在走的这条链"

第三种形态是路径类问题。求树的直径是最典型的例子：dp[u] 表示从 u 往下走的最长路，合并儿子的时候顺手更新一下全局答案。

int down[N], diam = 0; void dfs(int u, int fa) { down[u] = 0; for (int v : g[u]) { if (v == fa) continue; dfs(v, u); // 先算跨过 u 的两条链拼接，再更新 down[u] diam = max(diam, down[u] + down[v] + 1); down[u] = max(down[u], down[v] + 1); } }

注意这两行的顺序不能反。先更新 diam 时用的是"之前已经处理过的兄弟子树里的最长链"，再加上当前子树的最长链，拼成一条穿过 u 的路径；如果先把 down[u] 更新了，就会变成同一条链自己和自己拼接，答案直接虚高。

这类"边遍历子节点边更新全局最优"的写法在路径统计里非常常见，本质上是把"经过 u 的所有路径"按"由哪个儿子提供另一端点"分了类，不多不少正好枚举一遍。

2.4 状态维度失控前的三个预警

状态设计最容易犯的错误是维度越加越多，最后写出一个 dp[u][i][j][k] 然后自己都理不清转移。我一般用三个信号来判断是不是跑偏了：

• 状态里出现了依赖子树外信息的量，比如"整棵树里选了几个"，那说明该用换根或者该用别的算法；
• 两个维度之间存在明显的冗余，比如 j 恒等于 sz[u]，那就不该单独立一维；
• 转移时需要回退某个已合并的贡献，比如"去掉某个儿子之后重新算"，这通常意味着要从树形dp换成换根DP或者按边贡献单独统计。

我个人经验：如果一个树形dp的状态超过两维，先把题目重新读一遍，八成是漏掉了某个能让你"只记子树信息"的性质。

3. 复杂度账本：为什么有人写出来是 O(n²)，有人是 O(n³)

3.1 合并两个子树到底枚举了多少次

树上背包那段代码，外层两层循环看起来非常吓人，很多人第一反应是 O(n³) 甚至更高。但实际分析下来并不是这样。

关键在于：每一对点 (a, b)，只在它们的 LCA 处被枚举一次。合并儿子 v 到 u 的时候，我们枚举的是"从 u 的已处理子树里选 j 个"和"从 v 的子树里选 k 个"的所有组合，这些组合的实质就是"一端在已处理子树、一端在 v 子树里的点对"。每个点对只会被它所在的那对子树枚举一次，而这两个子树的根恰好在同一层合并，也就是它们的 LCA 处。所以总的枚举次数是 O(n²)，而不是 O(n³)（在第二维不限容量的情况下）。

如果第二维被限制在 m 以内，那么每个点对至多贡献 m 次状态，整体复杂度是 O(n·m)。这个结论在树上背包类题目里非常实用，因为它告诉你可以放心地把容量开到几万，只要 n·m 在可接受范围内。

3.2 卡上界带来的实际差距

上面的分析是"理论值"，实际跑起来还有一层：你有没有真的把上下界卡紧。如果外层 j 从 m 开始枚举、内层 k 也老老实实从 1 枚举到 m，那么即使逻辑正确，常数也会大得离谱。正确的姿势是外层 j 上界取 min(sz[u], m)，内层 k 上界取 min(sz[v], m - j)，同时下界也可以优化，比如 j 至少为 1。

再进一步，如果你确定某棵子树的点数少于 m，那么在处理它的时候完全可以只枚举到 sz[v]，避免大量无效的 -INF 状态运算。我做过对比测试，同样一份逻辑，卡不卡上界在小数据上差别不明显，但 n 到 5000、m 到 5000 的时候，差距能到 3 倍以上。

3.3 那些不算进复杂度但拖慢程序的东西

复杂度对了不代表跑得快。树形dp常踩的几个"常数坑"：

特别是第三行。dp[N][M] 这种开法在 n = m = 5000 的时候就是 2500 万个 long long，两百兆内存直接起飞。常见的处理办法是给每个点动态分配一个大小为 sz[u]+1 的 vector，或者用树上背包经典的"儿子向父亲复用空间"的写法。

4. 换根DP：当答案不在根上

4.1 两次DFS的分工

有一类问题，问的是每个点作为起点（或者作为根）时的某个答案，比如"每个点到其它所有点的距离之和""每个点作为根时的最小深度和"。这类问题如果对每个点都单独跑一遍DFS，复杂度直接 O(n²)。换根DP的思路是用两次线性DFS把它压到 O(n)。

第一次DFS以任意点（通常取1）为根，求出每个点的子树信息，比如子树大小 sz[u]、子树内所有点到 u 的距离和 down[u]。第二次DFS从上往下走，利用"父亲已经算好的全局答案"推出儿子的答案。

4.2 完整走一遍：每个点到所有点的距离和

先看第一次DFS。down[u] 表示 u 的子树内所有点到 u 的距离之和：

long long sz[N], down[N], f[N]; int n; void dfs1(int u, int fa) { sz[u] = 1; down[u] = 0; for (int v : g[u]) { if (v == fa) continue; dfs1(v, u); sz[u] += sz[v]; down[u] += down[v] + sz[v]; // v 子树每个点到 u 都要多走一步 } }

down[v] + sz[v]这一项的含义是：v 子树内的每个点到 u 的距离，等于它到 v 的距离再加 1，所以总共多出 sz[v]。

第二次DFS要解决的问题是：已知 f[u]（所有点到 u 的距离和），怎么求 f[v]。把整棵树按"v 的子树"和"其余部分"切开，从 u 走到 v 时，v 子树里的 sz[v] 个点各自少走一步，其余 n - sz[v] 个点各自多走一步，所以：

f[1] = down[1]; void dfs2(int u, int fa) { for (int v : g[u]) { if (v == fa) continue; f[v] = f[u] - sz[v] + (n - sz[v]); dfs2(v, u); } }

化简一下就是f[v] = f[u] + n - 2 * sz[v]。这个式子非常漂亮，也很好记：每往下一个点，整体距离和的变化等于 n - 2·sz[v]。当 sz[v] 超过 n/2 时这个变化是负的，也就意味着重心方向的答案更小，这其实顺手也就把树的重心求出来了。

4.3 换根时最容易出错的两个地方

第一个坑是忘了方向。dfs2 里递推 f[v] 用到的 sz[v] 是"v 作为子节点时的子树大小"，这个值在第一次DFS里是以1为根算的，方向是对的。但如果你把换根逻辑套在别的量上，比如"子树内最大深度"，那就要小心了：从 u 推到 v 的时候，v 这一侧的信息变了，你得重新算一遍"u 去掉 v 这棵子树之后的最深链"，这往往需要维护最大值和次大值。我见过太多人在这里直接拿 max 一减，结果减掉的是别的儿子的贡献。

第二个坑是根节点的初值。f[1] 必须先用第一次DFS的结果填上，也就是 down[1]，不能想当然地写 0。这个错误在小样例上很容易被掩盖，因为 n 小的时候结果看起来差不多。

我自己的习惯是：换根DP写完先手算 n = 3 的一条链，看看三个点的答案是不是 3、2、3。这个例子能同时验证初值、方向、递推式三件事。

5. 把递归改写成迭代：深度上万之后的必修课

5.1 手工栈构造后序序列

树退化成链的时候，n 到十万级递归基本必爆。改迭代的第一步是构造一个父亲已知、且能倒序处理的节点序列：

int fa[N], order[N], cnt = 0; void build_order(int root) { stack<int> st; st.push(root); fa[root] = 0; while (!st.empty()) { int u = st.top(); st.pop(); order[++cnt] = u; for (int v : g[u]) { if (v == fa[u]) continue; fa[v] = u; st.push(v); } } } // 主逻辑：倒序遍历，保证儿子先于父亲 void solve() { for (int i = cnt; i >= 1; --i) { int u = order[i]; // 此处 dp[u] 的初始值 for (int v : g[u]) { if (v == fa[u]) continue; // 合并 dp[v] 到 dp[u] } } }

这个写法的原理是：栈式遍历保证了任何一个点在 order 中的位置一定晚于它的父亲（因为父亲先入 order 才轮到儿子）。所以把 order 倒过来，就是标准的后序——儿子永远在父亲前面被处理。逻辑和递归版本一模一样，只是把"调用栈"换成了"显式数组"。

5.2 什么时候可以偷懒用BFS序

如果你的转移只依赖"儿子已经算完"这一个条件，而且每个点的状态只需要被父亲读一次，那么其实用普通的 BFS 顺序加倒序遍历就足够了，上面的写法完全可以胜任。但如果你需要在处理 u 的时候同时访问"所有已经处理完的儿子以某个顺序排列"，那就得额外维护儿子列表，简单点说就是别用 vector 存临时结果，直接原地合并。

5.3 空间上的自适应

迭代写法的另一个好处是方便做内存控制。递归版本里，每一层栈帧都持有局部变量，深树上内存占用会明显上升。改成迭代之后，你可以按需分配：dp[u] 用 vector 按 sz[u]+1 开，处理完之后如果确定不再需要（比如只算一次答案），可以直接释放。树上背包用这种方式能把峰值内存压下来不少。

代价是代码会变长、可读性下降。所以我的取舍原则是：n 在 2×10⁴ 以内、且比赛环境允许开大栈，就用递归；超过这个量级或者题目明确给了深链数据，直接上迭代，别纠结。

6. 写挂了怎么查：一份可复用的排查链路

6.1 先把"树"本身验证掉

树形dp出问题，有相当一部分根本不是dp写错了，而是树建错了。最常见的三种：加了双向边但没判父亲导致死循环；节点编号从 0 开始却把 0 当成了"没有父亲"的哨兵；多组数据没有清空邻接表。

验证方法很土但很有效：加一段代码统计cnt（从根出发能访问到的点数），如果它不等于 n，直接说明建图或者遍历出了问题，不用往下查dp了。

// 调试用：确认遍历覆盖了所有点 assert(cnt == n); // 调试用：输出每个点的 sz 与深度 for (int i = 1; i <= n; ++i) printf("%d: sz=%d dep=%d\n", i, sz[i], dep[i]);

6.2 对拍是最省时间的办法

树形dp的状态转移逻辑很容易出边界错误，靠盯着看是看不出来的。写一个 O(2ⁿ) 的暴力（n ≤ 18 时把点集全部枚举一遍），随机生成小树对拍，通常几分钟就能抓到反例。我一般会固定几个特殊形状去测：纯链、纯菊花（一个中心连着所有点）、随机树、两个点。这四种形状几乎覆盖了所有"根节点特殊""深度极端""儿子数量极端"的边界情况。

对拍脚本不需要写得多精致，能跑就行：

for i in $(seq 1 500); do python3 gen.py > in.txt ./bf < in.txt > out1.txt ./sol < in.txt > out2.txt if ! diff -q out1.txt out2.txt > /dev/null; then echo "WA on case $i"; break fi done

6.3 常见错误对照表

最后一行那个"加计数器"的技巧我特别推荐。在双重循环里放一个++cnt_inner，跑一组大数据看看实际枚举了多少次。如果它远超 n²，那说明上界卡错了；如果它只有几千，但你却超时了，那瓶颈一定在别处。这比凭感觉猜要靠谱得多。

写到这里，我还想补一个自己踩过的坑。有一次做一道树上依赖背包，容量 m 开到了 30000，n 有 2000，理论上 n·m 是六千万，感觉能过。结果一直 TLE，查了半天发现是 dp 数组用了long long dp[N][M]的静态开法，一千万个 long long 光清零就花了不少时间，而且缓存局部性极差。后来改成按子树大小动态分配、并且用 int 存价值（确实没超 int 范围），时间直接掉到原来的四分之一。所以树形dp这东西，转移方程写对只算及格，把常数和内存一起管住，才算真的写完了。