C/C++教程

carnation13的树形dp学习笔记

本文主要是介绍carnation13的树形dp学习笔记,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

大一时,我们在某次集训队训练时,\(zjn\)学长就笑着调侃道:“树形dp在我们当年只是一道铁牌题,连树形dp都不会还打什么ACM”。于是乎,抱着一种好奇心,也为了能够在比赛时做出树形\(dp\)的题目,我便开始了树形\(dp\)的学习。

树形 dp

概念

树形\(dp\),顾名思义,就是在树上\(dp\),又由于树固有的递归性质,树形\(dp\)一般都是递归进行的。

实现

既然使用递归去实现,那么我们自然需要用到\(dfs\)函数去搜索整棵树,而对于\(dp\)数组的参数选择,一般选择当前枚举到的节点\(u\),并通过它的儿子节点\(v\)来更新,其他维记录其他信息。
而对于树形\(dp\)的基本形式,已经有大佬总结出了较为模板的做法,设\(dp[i][j][0/1]\),其中\(i\)是以\(i\)为根的子树,\(j\)表示在以\(i\)为根的树中选\(j\)个子节点,\(0\)表示当前节点不选,\(1\)表示选上当前节点,有时候可以压掉\(j\)或者0/1这维。有关基础的\(dp\)方程模板

选择节点类

\[\left\{ \begin{array}{**lr**} dp[i][0]=dp[j][1] & \\ dp[i][1]=max/min(dp[j][0],dp[j][1]) & \end{array} \right. \]

树形背包类

\[\left\{ \begin{array}{**lr**} dp[v][k]=dp[u][k]+val & \\ dp[u][k]=max(dp[u][k],dp[v][k-1]) & \end{array} \right. \]

换根 dp

树形\(dp\)中的换根\(dp\)问题又被称为二次扫描,通常不会指定根结点,并且根结点的变化会对一些值,例如子结点深度和、点权和等产生影响。
通常需要两次\(DFS\),第一次\(DFS\)预处理诸如深度,点权和之类的信息,在第二次\(DFS\)开始运行换根动态规划。


通过以上的学习,我们对于树形\(dp\)有了一定的了解,接下来就做点例题来小试牛刀

例题

  1. 洛谷 P1352 没有上司的舞会
    题意:一棵\(n\)个节点的有向树,每个节点有权值\(r_i\),选出若干个节点,若选了当前节点,那就不能再选其儿子节点了,求出最大的权值之和。
    思路:设\(f[i][j]\)表示以\(i\)为根节点的子树,当前节点状态为\(j\),\(j=1\)表示选上当前节点,\(j=0\)表示不选该节点,所得到的最大权值。显然,状态转移方程如下

\[\left\{ \begin{array}{**lr**} f[x][0]+=max(f[v][0],f[v][1]) & \\ f[x][1]+=f[v][0] & \end{array} \right. \]

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,a[6006],t=0,head[6006],f[6006][2],in[6006]={0},w;
struct node
{
    ll v,next;
}e[6006];
void add(ll u,ll v)
{
    e[++t].v=v;
    e[t].next=head[u];
    head[u]=t;
}
void dp(ll x)
{
    f[x][0]=0;
    f[x][1]=a[x];
    for(ll i=head[x];i;i=e[i].next)
    {
        ll v=e[i].v;
        dp(v);
        f[x][0]+=max(f[v][0],f[v][1]);
        f[x][1]+=f[v][0];
    }
}
signed main()
{
    ios::sync_with_stdio(false);
    cin>>n;
    for(ll i=1;i<=n;++i)cin>>a[i];
    for(ll i=1;i<n;++i)
    {
        ll u,v;
        cin>>u>>v;
        add(v,u);
        in[u]++;
    }
    for(ll i=1;i<=n;++i)if(in[i]==0)w=i;
    dp(w);
    cout<<max(f[w][0],f[w][1]);
    return 0;
}
  1. 洛谷 P1122 最大子树和
    题意:一棵\(n\)个节点的树,每个节点有美丽指数\(b_i\),通过剪掉任意多条边(也可以不剪),使剩下的子树美丽指数之和最大,求出最大值。
    思路:设\(f[i]\)表示以\(i\)为根的子树最大的美丽指数之和,很显然,状态转移方程如下

\[\begin{aligned} f[u]+=f[v]\qquad(f[v]>0) \end{aligned} \]

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,a[20000],head[20000],t=0,f[20000],ans=-0x7fffffff;
struct node
{
    ll v,next;
}e[40000];
void add(ll u,ll v)
{
    e[++t].v=v;
    e[t].next=head[u];
    head[u]=t;
}
void dfs(ll u,ll fa)
{
    f[u]=a[u];
    for(ll i=head[u];i;i=e[i].next)
    {
        ll v=e[i].v;
        if(v!=fa)
        {
            dfs(v,u);
            if(f[v]>0)
            f[u]+=f[v];
        }
    }
}
signed main()
{
    ios::sync_with_stdio(false);
    cin>>n;
    for(ll i=1;i<=n;++i)cin>>a[i];
    for(ll i=1;i<n;++i)
    {
        ll u,v;
        cin>>u>>v;
        add(u,v);
        add(v,u);
    }
    dfs(1,0);
    for(ll i=1;i<=n;++i)ans=max(f[i],ans);
    cout<<ans;
    return 0;
}
  1. 洛谷 P2014 [CTSC1997] 选课
    题意:现在有\(N\)门功课,每门课有个学分,每门课有一门或没有直接先修课(若课程\(a\)是课程\(b\)的先修课即只有学完了课程\(a\),才能学习课程\(b\))。一个学生要从这些课程里选择\(M\)门课程学习,问他能获得的最大学分是多少?
    思路:该题是经典的树形背包题,设\(f[i][j]\)表示选择以\(i\)为根的子树中\(j\)个节点。\(u\)代表当前根节点,\(sum\)代表其选择的节点的总额。
    代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,m,head[306],t=0,a[306],f[306][306];
struct node
{
    ll v,next;
}e[306];
void add(ll u,ll v)
{
    e[++t].v=v;
    e[t].next=head[u];
    head[u]=t;
}
void dfs(ll u,ll sum)
{
    if(sum==0)return;
    for(ll i=head[u];i;i=e[i].next)
    {
        ll v=e[i].v;
        for(ll k=0;k<sum;++k)f[v][k]=f[u][k]+a[v];
        dfs(v,sum-1);
        for(ll k=1;k<=sum;++k)f[u][k]=max(f[u][k],f[v][k-1]);
    }
}
signed main()
{
    ios::sync_with_stdio(false);
    cin>>n>>m;
    for(ll i=1;i<=n;++i)
    {
        ll u;
        cin>>u>>a[i];
        add(u,i);
    }
    dfs(0,m);
    cout<<f[0][m];
    return 0;
}
  1. 洛谷 P2015 二叉苹果树
    题意:一棵\(n\)个节点的树,每根树枝上有若干个苹果,现在要保留\(k\)个树枝,求出最多能留住多少苹果。
    思路:显然,对于每条边,有两种选择,要么剪掉这条边,要么留下这条边,所以\(dp\)的其中一维是树枝的数量,设\(f[i][j]\)表示以\(i\)为节点,保留\(j\)根树枝可以得到的最大苹果数,则状态转移方程

\[\begin{aligned} f[i][j]=max(f[i][j],f[left][j]+e[left].apple+f[right][k-j]+e[right].apple) \end{aligned} \]

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,q,head[205],t=0,f[105][105];
struct node
{
    ll v,next,w;
}e[205];
void add(ll u,ll v,ll w)
{
    e[++t].v=v;
    e[t].w=w;
    e[t].next=head[u];
    head[u]=t;
}
void dfs(ll u,ll fa,ll w)
{
    ll son[3]={0},cnt=0;
    bool p=0;
    for(ll i=head[u];i;i=e[i].next)
    {
        ll v=e[i].v;
        if(v!=fa)
        {
            p=1;
            son[++cnt]=i;
            dfs(v,u,e[i].w);
        }
    }
    if(p==0)return;
    for(ll i=1;i<=q;++i)
    {
        for(ll j=0;j<=i;++j)
        {
            ll w=0;
            if(j-1>=0)w+=e[son[1]].w;
            if(i-j-1>=0)w+=e[son[2]].w;
            if(j)f[u][i]=max(f[u][i],f[e[son[1]].v][j-1]+f[e[son[2]].v][i-j-1]+w);
            else f[u][i]=max(f[u][i],f[e[son[2]].v][i-j-1]+w);
        }
    }
}
signed main()
{
    ios::sync_with_stdio(false);
    cin>>n>>q;
    for(ll i=1;i<=n-1;++i)
    {
        ll u,v,w;
        cin>>u>>v>>w;
        add(u,v,w);
        add(v,u,w);
    }
    dfs(1,0,0);
    cout<<f[1][q];
    return 0;
}
  1. CF1187E Tree Painting
    题意:给定一棵\(n\)个点的树 初始全是白点
    要求你做\(n\)步操作,每一次选定一个与一个黑点相隔一条边的白点,将它染成黑点,然后获得该白点被染色前所在的白色联通块大小的权值。
    第一次操作可以任意选点。
    求可获得的最大权值。
    思路:这是一道经典的换根\(dp\)题,先用一次\(dfs\)求出以其中一个节点(例如1)为根,所得到的权值,该权值等于所有节点到该节点的距离之和+节点个数。得到以某节点为根的答案后,再进行状态转移,当前节点为根和其相邻节点为根有一个状态转移,(即换根的核心),\(num[i]\)表示以\(i\)为根的子树其子节点深度之和,\(f[i]\)表示以\(i\)为根的权值,在第一次\(dfs\)后,我们已经求出了所有节点的\(num[i]\),对于第二次\(dfs\),不难得出如下的状态转移方程

\[\begin{aligned} f[v]=f[u]-num[v]+n-num[v] \end{aligned} \]

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,head[2000005],t=0,f[1000005],num[1000005],sum=0;
struct node
{
    ll v,next;
}e[2000005];
void add(ll u,ll v)
{
    e[++t].v=v;
    e[t].next=head[u];
    head[u]=t;
}
void dfs(ll u,ll fa,ll deep)
{
    for(ll i=head[u];i;i=e[i].next)
    {
        ll v=e[i].v;
        if(v==fa)continue;
        sum+=deep;
        dfs(v,u,deep+1);
        num[u]+=num[v];
    }
}
void dfs2(ll u,ll fa)
{
    for(ll i=head[u];i;i=e[i].next)
    {
        ll v=e[i].v;
        if(v==fa)continue;
        f[v]=f[u]-num[v]+n-num[v];
        dfs2(v,u);
    }
}
signed main()
{
    ios::sync_with_stdio(false);
    cin>>n;
    for(ll i=1;i<=n;++i)num[i]=1;
    for(ll i=1;i<=n-1;++i)
    {
        ll u,v;
        cin>>u>>v;
        add(u,v);
        add(v,u);
    }
    dfs(1,0,1);
    f[1]=sum;
    dfs2(1,0);
    ll ma=-1,ans;
    for(ll i=1;i<=n;++i)
    {
        if(f[i]>ma)
        {
            ans=i;
            ma=f[i];
        }
    }
    cout<<ma+n<<endl;
    return 0;
}
  1. 洛谷 P3478 [POI2008] STA-Station
    题意:给定一个 nn 个点的树,请求出一个结点,使得以这个结点为根时,所有结点的深度之和最大。
    一个结点的深度之定义为该节点到根的简单路径上边的数量。
    思路:这道题是上题的双倍经验,也是换根\(dp\)的经典题目,两题代码97%相同,除了输出不同,也不知道为啥难度会差一个档次,思路和上题一样,两次\(dfs\),第一次求出以某点为根的深度之和,第二次状态转移到以其他点位根的深度之和,最后输出最大的节点即可。
    代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,head[2000005],t=0,f[1000005],num[1000005],sum=0;
struct node
{
    ll v,next;
}e[2000005];
void add(ll u,ll v)
{
    e[++t].v=v;
    e[t].next=head[u];
    head[u]=t;
}
void dfs(ll u,ll fa,ll deep)
{
    for(ll i=head[u];i;i=e[i].next)
    {
        ll v=e[i].v;
        if(v==fa)continue;
        sum+=deep;
        dfs(v,u,deep+1);
        num[u]+=num[v];
    }
}
void dfs2(ll u,ll fa)
{
    for(ll i=head[u];i;i=e[i].next)
    {
        ll v=e[i].v;
        if(v==fa)continue;
        f[v]=f[u]-num[v]+n-num[v];
        dfs2(v,u);
    }
}
signed main()
{
    ios::sync_with_stdio(false);
    cin>>n;
    for(ll i=1;i<=n;++i)num[i]=1;
    for(ll i=1;i<=n-1;++i)
    {
        ll u,v;
        cin>>u>>v;
        add(u,v);
        add(v,u);
    }
    dfs(1,0,1);
    f[1]=sum;
    dfs2(1,0);
    ll ma=-1,ans;
    for(ll i=1;i<=n;++i)
    {
        if(f[i]>ma)
        {
            ans=i;
            ma=f[i];
        }
    }
    cout<<ans;
    return 0;
}
  1. 洛谷 P2986 [USACO10MAR] Great Cow Gathering G
    题意:给定一棵\(n\)个点的树,每个点有\(C_i\)只奶牛,每条边的距离长度为\(L_i\),选择一个节点为集会地点,定义不方便程度为其它牛棚中每只奶牛去参加集会所走的路程之和,求出最小的不方便值。
    思路:这题是上两题的三倍经验,同样是一道基础的换根\(dp\)题,设\(sum[i]\)表示以\(i\)为根节点的羊数量总和,\(f[i]\)表示以\(i\)为根节点的不方便值,\(sheep\)表示羊的总数量,在第一次\(dfs\)时,可以求出每个节点的\(sum[i]\)值,以及以1为根的不方便值,第二次\(dfs\)时,将\(f[i]\)转移,从而得到以每个节点为根时的不方便值,状态转移方程如下

\[\begin{aligned} f[v]=f[u]+(sheep-sum[v]-sum[v])*w \end{aligned} \]

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,a[100005],sum[100005],deep[100005]={0},head[200005],t=0,sheep=0,f[100005];
struct node
{
    ll v,next,w;
}e[200005];
void add(ll u,ll v,ll w)
{
    e[++t].v=v;
    e[t].w=w;
    e[t].next=head[u];
    head[u]=t;
}
void dfs(ll u,ll fa)
{
    for(ll i=head[u];i;i=e[i].next)
    {
        ll v=e[i].v,w=e[i].w;
        if(v==fa)continue;
        deep[v]=deep[u]+w;
        dfs(v,u);
        sum[u]+=sum[v];
    }
}
void dfs2(ll u,ll fa)
{
    for(ll i=head[u];i;i=e[i].next)
    {
        ll v=e[i].v,w=e[i].w;
        if(v==fa)continue;
        f[v]=f[u]+(sheep-sum[v]-sum[v])*w;
        dfs2(v,u);
    }
}
signed main()
{
    ios::sync_with_stdio(false);
    cin>>n;
    for(ll i=1;i<=n;++i){cin>>a[i];sum[i]=a[i];sheep+=a[i];}
    for(ll i=1;i<=n-1;++i)
    {
        ll u,v,w;
        cin>>u>>v>>w;
        add(u,v,w);
        add(v,u,w);
    }
    dfs(1,0);
    for(ll i=1;i<=n;++i)f[1]+=a[i]*deep[i];
    dfs2(1,0);
    ll ans=0x7fffffffffffffff;
    for(ll i=1;i<=n;++i)ans=min(ans,f[i]);
    cout<<ans<<endl;
    return 0;
}
  1. CF708C Centroids
    题意:给定一颗树,你有一次将树改造的机会,改造的意思是删去一条边,再加入一条边,保证改造后还是一棵树。
    请问有多少点可以通过改造,成为这颗树的重心?(如果以某个点为根,每个子树的大小都不大于\(\dfrac{n}{2}\)
    ,则称某个点为重心)
    思路:换根\(dp\)经典题,相比前面3题,此题难度上了一个档次,状态转移情况比较多,这里直接上代码,细节有空再补(十有八九鸽了)
    代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,head[800005],t=0,f[400004],sec[400004],mas[400004],ma[400004],siz[400004],g[400004];
struct node
{
    ll v,next;
}e[800005];
void add(ll u,ll v)
{
    e[++t].v=v;
    e[t].next=head[u];
    head[u]=t;
}
void dfs(ll u,ll fa)
{
    ma[u]=0;
    for(ll i=head[u];i;i=e[i].next)
    {
        ll v=e[i].v;
        if(v==fa)continue;
        dfs(v,u);
        siz[u]+=siz[v];
        if(siz[v]>siz[ma[u]])ma[u]=v;
        if(siz[v]>n/2)
        {
            if(f[v]>f[u])
            {
                sec[u]=f[u];
                f[u]=f[v];
                mas[u]=v;
            }
            else if(f[v]>sec[u])sec[u]=f[v];
        }
        else
        {
            if(siz[v]>f[u])
            {
                sec[u]=f[u];
                f[u]=siz[v];
                mas[u]=v;
            }
            else if(siz[v]>sec[u])sec[u]=siz[v];
        }
    }
}
void dfs2(ll u,ll fa)
{
    for(ll i=head[u];i;i=e[i].next)
    {
        ll v=e[i].v;
        if(v==fa)continue;
        g[v]=max(g[v],g[u]);
        if(n-siz[v]<=n/2)g[v]=max(g[v],n-siz[v]);
        if(v==mas[u])g[v]=max(g[v],sec[u]);
        else g[v]=max(g[v],f[u]);
        dfs2(v,u);
    }
}
signed main()
{
    ios::sync_with_stdio(false);
    cin>>n;
    for(ll i=1;i<=n-1;++i)
    {
        ll u,v;
        cin>>u>>v;
        add(u,v);
        add(v,u);
    }
    for(ll i=1;i<=n;++i)siz[i]=1;
    dfs(1ll,0ll);
    g[1]=0;
    dfs2(1ll,0ll);
    for(ll i=1;i<=n;++i)
    {
        if(siz[ma[i]]>n/2&&siz[ma[i]]-f[ma[i]]>n/2)cout<<0<<" ";
        else if(n-siz[i]>n/2&&n-siz[i]-g[i]>n/2)cout<<0<<" ";
        else cout<<1<<" ";
    }
    return 0;
}
  1. 牛客小白月赛45 E筑巢
    题意:给定你一个n个节点的树,你需要在树上选取一个非空连通块,使其舒适度和最大。选择的边和点的舒适度都是舒适度。
    思路:该题是一道树形\(dp\),与此题比较类似的是\(dp\)中的[最大连续子段和],可以设\(f[i]\)表示选了\(i\)节点的连通块的最大舒适度,我们来考虑状态的转移,设\(a[i]\)表示\(i\)节点自己的点权,则

\[\begin{aligned} f[i]=a[i]+\sum_{j}max(0,w_{ij}+f[j]) \end{aligned} \]

另外还要考虑边界条件,若\(i\)为叶子,则\(f[i]=a[i]\)
代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,a[200005],f[200005],ans=-0x7fffffffffffffff;
vector<pair<ll,ll>>p[200005];
void dfs(ll u,ll fa)
{
    for(auto y:p[u])
    {
        if(y.first==fa)continue;
        dfs(y.first,u);
        if(f[y.first]+y.second>0)f[u]+=f[y.first]+y.second;
    }
    ans=max(ans,f[u]);
}
signed main()
{
    ios::sync_with_stdio(false);
    cin>>n;
    ll now=n;
    for(ll i=1;i<=n;++i)cin>>a[i];
    for(ll i=1;i<=n-1;++i)
    {
        ll u,v,w;
        cin>>u>>v>>w;
        p[u].push_back({v,w});
        p[v].push_back({u,w});
    }
    for(ll i=1;i<=now;++i)f[i]=a[i];
    dfs(1,0);
    cout<<ans;
    return 0;
}

其他例题

  1. 洛谷 P2585 [ZJOI2006]三色二叉树
    树形\(dp\)简单题,\(dp\)部分不难,如何建树成为难题,代码实现较为简单,以下是邻接表建树的关键部分
void build(ll u,ll x)
{
    son[u]=x;
    for(ll i=1;i<=x;++i)
    {
        ++now;
        cin>>c;
        add(u,now);
        build(now,c-'0');
    }
}
  1. 洛谷 P1273 有线电视网
    该题是树形\(dp\)与分组背包的结合体,转移方程\(dp[i][j]=max(dp[i][j],dp[i][j-k]+dp[v][k]-\)这条边的花费\() i,j\)不解释了,\(v\)表示枚举到这一组(即\(i\)的儿子),\(k\)表示枚举到这组中的元素:选\(k\)个用户
    以下是分组背包伪代码
for(int k=1;k<=总共的组数;k++)//遍历所有的组k
	for(int j=v;j>=1;j--)//跟01背包类似,倒序枚举背包容量
    	for(int i=1;i<=组中的元素个数;i++)//遍历这组中所有的元素
  1. CF767C Garland
    树形\(dp\)板子题,找三个权值和相同的子树,从下往上遍历更新即可。
  2. CF219D Choosing Capital for Treeland
    换根\(dp\)练手的经典题,当从某点向相邻的节点转移时,只有该两点之间的边权不同,其他边权没有变化,当\(u\)向\(v\)的边权为\(0\)时,\(v\)向\(u\)的边权则一定为\(1\),反之亦然,所以可以考虑换根\(dp\)
  3. CF161D Distance in Tree
    该题做法有许多,比如树上启发式合并、长链剖分、点分治(板子题)、树形\(dp\)等等,这里只介绍树形\(dp\)的做法,因为其他做法我都不会,其中关键的\(dfs\)部分的代码如下
void dfs(int now,int p)
{
    dp[now][0]=1;
    for (int i=0;i<v[now].size();i++)
    {
        int to=v[now][i];
        if (to!=p)
        {
            dfs(to,now);
            for (int j=0;j<k;j++) ans+=(dp[now][j]*dp[to][k-j-1]);
            for (int j=0;j<k;j++) dp[now][j+1]+=dp[to][j];
        }
    }
}

启示

树形\(dp\)大多数对根和儿子进行转移,对于树上背包问题,前提要对简单的背包问题足够了解,也要注意枚举时的顺序,而换根\(dp\)无非就是对根进行转移,运用两次\(dfs\),第一次预处理,第二次转移。
完结撒花qwq

这篇关于carnation13的树形dp学习笔记的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!