树形DP教程：从递归视角彻底搞懂树上DP

ZhangChuan1350 · 2026-04-23 21:25:47 · 算法·理论

前言

在阅读本文前，你只需要：

• 了解树的各项概念和定义。
• 会用邻接表存一棵树。
• 会写 DFS 遍历树（知道怎么避免走回父节点）。

由于本文主要面向初学者，本文代码均使用 vector 存图。

由于树形 DP 题目变化多端，本文采用一点一例的方式——一个核心思想，配一道经典题。

自定义的符号和简写：

• 子树 u：以节点 u 为根节点的子树。

  基础树形 DP

  例题说明：采用 洛谷 P1352 没有上司的舞会、洛谷 P2016 战略游戏 和 洛谷 P1122 最大子树和 作为经典例题讲解。

本文默认你已经了解题意。

洛谷 P1352 没有上司的舞会

题目可以抽象为：
有一棵树，共有节点 n 个，编号为 i\in[1,n]，快乐指数为 r_i，要求选择若干个节点，使得：

• 任意一对父节点和子节点最多选一个。
• 最大化快乐指数。

思路： 可以发现，每个结点有且只有 2 种情况——选或不选，只需记录此状态即可。因为树形结构决定了通过递归必须从根向下传递信息，所以一般题目给出或自己选择选一个根。

:::info[我是如何思考状态的？]{open}

Step 1：分析限制条件

题目说父节点和子节点不能同时选。这意味着：

• 若父节点选了，任意子节点均不能选。
• 若父节点没选，任意子节点均可选可不选。

这是两种不同的状态，需要分别讨论和包含。
常用做法是用 0/1 表示，0 表示不选，1 表示选。

Step 2：判断子问题独立性

在树中，最小问题规模是每个子问题，而每个子问题均是独立的，但子问题的解依赖于父节点是否被选这个外部条件。
在子树中，根节点可以看做这棵子树的父节点，所以子树的解依赖这个根节点选没选——这就是为什么状态里必须记录根节点的选择状态。
因此状态必须记录下根节点是否选择这一重要信息。

Step 3：设计状态

综合 Step 1 与 Step 2，可以得到状态必须包含的两个信息：

• 当前处理的子树根节点，假设为 u。
• 当前子树的根节点是否选择，这个可以用 0/1 表示。

故 可得到 f_{u,0/1} 这一状态。 ::: 定义状态 f_{u,0/1}，表示以编号为 u 的节点为根节点，是否选择节点 u 的最大快乐指数。

综上，状态转移方程为

注意 n 的数据范围：1\leqslant n\leqslant10^6。int 会溢出，部分变量需要 long long。

根据状态转移方程直接翻译得出：

#include <bits/stdc++.h>
using namespace std;
constexpr int N=1e6+5;
vector<int>g[N];
int n,sz[N],root=1;
long long f[N],ans;
void build(int u,int dad,int dep){
    sz[u]=1; f[1]+=dep; //初始化
    for (const int &v:g[u]) {
        if (v==dad) continue;
        build(v,u,dep+1);
        sz[u]+=sz[v];
    }
}
void dp(int u,int dad){ //换根
    for (const int &v:g[u]){
        if (v==dad) continue;
        f[v]=f[u]+n-2*sz[v];
        dp(v,u);
    }
}
int main()
{
    scanf("%d",&n);
    for (int i=1;i<n;++i){
        int u,v;
        scanf("%d%d",&u,&v);
        g[u].push_back(v);
        g[v].push_back(u);
    }
    build(1,0,0); //根节点的深度为 0
    dp(1,0);
    for (int i=1;i<=n;++i) if (f[i]>ans) {ans=f[i];root=i;}
    printf("%d",root); 
    return 0;
}

时间复杂度：两个 O(n) 的 DFS，加上最后处理结果 O(n)，总时间复杂度为 O(n)。

洛谷 P2986 Great Cow Gathering G

:::epigraph[例题对比] 和 P3478 相比，这里的深度换成了距离，节点数换成了奶牛数——但核心思想完全一样。
我们将复用 P3478 的子树内外思想，推导出带权的换根公式。 ::: 题目可以抽象为：
有一棵 N 个节点的无根树，节点编号为 i\in[1,N]，节点 i 有 c_i 头奶牛。
树有 (N-1) 条无向边，记 w_{u,v} 为边 (u,v) 的边权。

定义状态 f_X，表示以 X 为集会地点的不方便程度为

其中 \operatorname{dist}(i,X) 是节点 i 到 X 的树上唯一路径的距离（边权和）。

这里依旧是题目要什么，状态定义什么。

要求：找出一个节点 X，使得 f_X 最小。

在换根 DP 的视角下，我们把集会地点 X 视作整棵树的临时根——所有奶牛到它的距离，就是它们在以 X 为根的树中的带权深度。

思路： 回想 P3478 的 \mathrm{size}_u，原来表示节点总数，但在本题中，实际表示这棵树以 1 为总根时，以节点 u 为根的子树的奶牛数量，只不过 P3478 的每个节点的“奶牛数量”是 1 而已。

参考 P3478，联系它们的关系，可以得到如下定义：

• 定义参数 \mathrm{cnt}，表示整棵树的奶牛数量，也就是

  \mathrm{cnt}=\sum_{i=1}^Nc_i

  这里的 \mathrm{cnt} 和 P3478 中的 “n” 功能相同，只不过从节点数量变成奶牛数量。

• 定义参数 \mathrm{size}_u，在以 1 为总根的情况下，以 u 为根的子树的奶牛数量。
  同理，其初始化为 \mathrm{size}_u\gets c_u，因为 u 是子树的根节点。
  其转移方程同样是

  \forall~v\in\operatorname{son}(u),~\mathrm{size}_u\gets\mathrm{size}_u+\mathrm{size}_v

  这里的 \mathrm{size}_u 和 P3478 的功能相同，只不过从子树内节点数量变成子树内奶牛数量。

由于根节点从 1 开始。由题目抽象部分容易得到 f_1 的初始化为

先来看看样例给的数据，这是通过样例生成的一棵树，节点上的数字代表其编号： :::align{center} ::: 发现：当根节点从 1 换到其子节点 3 时，原树中以 3 为根的子树中的所有节点均与 3 的距离减少了 w_{1,3}，同时其子树中的奶牛数量 \mathrm{size}_3，因此不方便程度减少了 \mathrm{size}_3\cdot w_{1,3}。
同时，原树中不在以 3 为根的子树中的节点增加了距离 w_{1,3}，且奶牛数量为总奶牛数量 \mathrm{cnt} 减去子树内的奶牛数量 \mathrm{size}_3，即不方便程度增加了 (\mathrm{cnt}-\mathrm{size}_3)\cdot w_{1,3}

因此，f_3 的值应为 f_1-\mathrm{size}_3\cdot w_{1,3}+(\mathrm{cnt}-\mathrm{size}_3)\cdot w_{1,3}，即

归纳： 令该树的原根为 u，新根为 v 且 v\in\operatorname{son}(u)，则状态 f 的转移方程为

最后，状态 f_i 存储以 i 为集会地点的不方便程度，题目要求最小化不方便程度，因此答案为

注：题目数据可能会超过 int，部分变量和数组需要开 long long。

理解了这个，代码不就是手到擒来吗？
洛谷 P2986 Great Cow Gathering G 的完整代码如下：

#include <bits/stdc++.h>
using namespace std;
constexpr int N=1e5+5;
struct Edge {int to,w;};
vector<Edge>g[N];
int n,c[N];
long long f[N],sz[N],cnt,ans=9e18;
void build(int u,int dad,long long dist){
    sz[u]=c[u];f[1]+=c[u]*dist;
    for (const Edge &e:g[u]){
        int v=e.to,w=e.w;
        if (v==dad) continue;
        build(v,u,dist+w);
        sz[u]+=sz[v];
    }
}
void dp(int u,int dad){
    for (const Edge &e:g[u]){
        int v=e.to,w=e.w;
        if (v==dad) continue;
        f[v]=f[u]+(cnt-2*sz[v])*w;
        dp(v,u);
    }
}
int main()
{
    scanf("%d",&n);
    for (int i=1;i<=n;++i) {scanf("%d",&c[i]);cnt+=c[i];}
    for (int i=1;i<n;++i){
        int a,b,l;
        scanf("%d%d%d",&a,&b,&l);
        g[a].push_back({b,l});
        g[b].push_back({a,l});
    }
    build(1,0,0);
    dp(1,0);
    for (int i=1;i<=n;++i) ans=min(ans,f[i]);
    printf("%lld",ans);
    return 0;
}

版权声明

:::epigraph[生成式人工智能使用说明] 本文的核心思想、推导过程、代码实现均由本人独立完成。保证本人的贡献远大于 DeepSeek 的贡献。
在撰写过程中，使用了 DeepSeek 对全文的语句通顺度进行润色。
::: 本文采用 知识共享 署名-非商业性使用-相同方式共享 4.0 国际 许可协议 进行许可。

您需遵守下列条件：

• 署名：您必须给出适当的署名，提供指向本许可协议的链接，并标明是否对原始作品作了修改。您可以用任何合理的方式来署名，但不得以任何方式暗示许可人为您或您的使用背书。
• 非商业性使用：您不得将本作品用于商业目的。
• 相同方式共享：如果您再混合、转换或者基于本作品进行创作，您必须基于与原先相同的许可协议分发您贡献的作品。

最后，欢迎各位读者引用本文（需注明文章来源和署名），祝您树形 DP 之路一帆风顺！