【动态规划】树形DP入门

Little_Cake_qwq · 2026-02-09 20:48:38 · 算法·理论

前言

作者太弱了，如果发现文章问题欢迎在评论区评论或私信我。
本文部分内容转自 oiwiki。

正文

树形 DP，即在树上进行的 DP。由于树固有的递归性质，树形 DP 一般都是递归进行的。 -oiwiki

树形 dp 听上去很难，其实和线性 dp 差不了多少。

I.普通树形 dp

这类树形 dp 比较简单，一般只需要进行一次 dp。
嘴上说不清楚，还是看看例题吧：

例题1：P1122 最大子树和

题意：给定一棵树和每个点的点权，求其最大子树和。

这像一个在树上的最大子段和。由于题上没给根，所以我们以 1 节点为根，很明显这不影响答案。设 dp_u 为 u 的子树在选了 u 的情况下的最大子树和。

贪心考虑对于 u 的每一个子节点 v 选或不选 v 的最优大树和：显然，当 dp_v 大于 0 时，我们选它一定会加大和，所以是优的；而 dp_v 小于 0 时，明显选了会拉低和，所以是不优的。
因此，转移方程为：

代码如下：

const int N=2e5+8;
int n,ans=-INF;
int a[N],dp[N];
vector<int> edge[N];
void dfs(int u,int fa)//记录父亲防止重复递归
{
    dp[u]=a[u];
    for(auto v:edge[u])
    {
        if(v==fa) continue;
        dfs(v,u);
        dp[u]+=max(dp[v],0ll);
    }
    ans=max(ans,dp[u]);
}
signed main()
{
    n=read();
    for(int i=1;i<=n;i++) a[i]=read();
    for(int i=1;i<n;i++)
    {
        int u,v;u=read(),v=read();
        edge[u].pb(v);
        edge[v].pb(u);
    }
    dfs(1,0);
    cout<<ans;
    return 0;
}

总结：这类树形 dp 比较好想和好写，适合入门练习。

II.树上背包

既然可以在树上搞最大子树和，那是不是也可以在树上搞背包呢？

例题：P2014 [CTSC1997] 选课

题意：有 n 个课程，每个课程可能会有“先修课”，给定每个课程的学分和最大听课数量，求最大学分。

考虑将“先修课”变成父亲，0 看作是一门所有没有“先修课”的课程的先修课，然后以 0 为根开始 dp。
设 dp_{u,j} 表示 u 节点的子树中选 j 个节点的最大学分。对于每一个儿子 v，考虑枚举在 v 中选的节点数量。设这个量为 k，则其会在其他子树中选 j-k 个节点，转移方程为：

注意转移时的 j 需要倒着枚举。代码如下：

const int N=300+8;
int n,m;
int a[N],dp[N][N];
vector<int> edge[N];
void dfs(int u)
{
    dp[u][1]=a[u];
    for(auto v:edge[u])
    {
        dfs(v);
        for(int i=m+1;i>=1;i--)//倒着枚举！！！
            for(int j=0;j<i;j++)
                dp[u][i]=max(dp[u][i],dp[v][j]+dp[u][i-j]);
    }
}
signed main()
{
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    n=read();m=read();
    for(int i=1;i<=n;i++)
    {
        int u,v;u=read(),v=read();
        edge[u].pb(v);
    }
    dfs(0);
    cout<<dp[0][m+1];
    return 0;
}

总结：树上背包还是挺水的，理解了就可以了。

III.换根dp

树形 DP 中的换根 DP 问题又被称为二次扫描，通常不会指定根结点，并且根结点的变化会对一些值，例如子结点深度和、点权和等产生影响。 -oiwiki

换根 dp 一般都会有两次 dfs，第一次一般为以 1 为根的 dp，第二次为换根 dp。

例题：P2986 [USACO10MAR] Great Cow Gathering G

题意：给定一棵树，每个点有点权。请你确定一个点 u，使得以 u 为根时每个点的深度乘这个点的权值之和（以下简称为 u 的值）最小，请你求出这个最小值。

首先，假设 1 为根，求出它的值。用 dp 转移维护此时每个点 u 的子树权值和 sz_u 与此时 u 子树上的节点到 u 节点的深度和 dp_i。