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\)有了一定的了解，接下来就做点例题来小试牛刀
例题
- 洛谷 P1352 没有上司的舞会
题意：一棵\(n\)个节点的有向树，每个节点有权值\(r_i\),选出若干个节点，若选了当前节点，那就不能再选其儿子节点了，求出最大的权值之和。
思路：设\(f[i][j]\)表示以\(i\)为根节点的子树，当前节点状态为\(j\)，\(j=1\)表示选上当前节点，\(j=0\)表示不选该节点，所得到的最大权值。显然，状态转移方程如下
代码
#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;
}
- 洛谷 P1122 最大子树和
题意：一棵\(n\)个节点的树，每个节点有美丽指数\(b_i\)，通过剪掉任意多条边(也可以不剪)，使剩下的子树美丽指数之和最大，求出最大值。
思路：设\(f[i]\)表示以\(i\)为根的子树最大的美丽指数之和，很显然，状态转移方程如下
代码
#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;
}
- 洛谷 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;
}
- 洛谷 P2015 二叉苹果树
题意：一棵\(n\)个节点的树，每根树枝上有若干个苹果，现在要保留\(k\)个树枝，求出最多能留住多少苹果。
思路：显然，对于每条边，有两种选择，要么剪掉这条边，要么留下这条边，所以\(dp\)的其中一维是树枝的数量，设\(f[i][j]\)表示以\(i\)为节点，保留\(j\)根树枝可以得到的最大苹果数，则状态转移方程
代码
#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;
}
- CF1187E Tree Painting
题意：给定一棵\(n\)个点的树 初始全是白点
要求你做\(n\)步操作，每一次选定一个与一个黑点相隔一条边的白点，将它染成黑点，然后获得该白点被染色前所在的白色联通块大小的权值。
第一次操作可以任意选点。
求可获得的最大权值。
思路：这是一道经典的换根\(dp\)题，先用一次\(dfs\)求出以其中一个节点(例如1)为根，所得到的权值，该权值等于所有节点到该节点的距离之和+节点个数。得到以某节点为根的答案后，再进行状态转移，当前节点为根和其相邻节点为根有一个状态转移，(即换根的核心)，\(num[i]\)表示以\(i\)为根的子树其子节点深度之和，\(f[i]\)表示以\(i\)为根的权值，在第一次\(dfs\)后，我们已经求出了所有节点的\(num[i]\),对于第二次\(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<<ma+n<<endl;
return 0;
}
- 洛谷 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;
}
- 洛谷 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]\)转移，从而得到以每个节点为根时的不方便值，状态转移方程如下
代码
#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;
}
- 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;
}
- 牛客小白月赛45 E筑巢
题意：给定你一个n个节点的树，你需要在树上选取一个非空连通块，使其舒适度和最大。选择的边和点的舒适度都是舒适度。
思路：该题是一道树形\(dp\)，与此题比较类似的是\(dp\)中的[最大连续子段和]，可以设\(f[i]\)表示选了\(i\)节点的连通块的最大舒适度，我们来考虑状态的转移，设\(a[i]\)表示\(i\)节点自己的点权，则
另外还要考虑边界条件，若\(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;
}
其他例题
- 洛谷 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');
}
}
- 洛谷 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++)//遍历这组中所有的元素
- CF767C Garland
树形\(dp\)板子题，找三个权值和相同的子树，从下往上遍历更新即可。 - CF219D Choosing Capital for Treeland
换根\(dp\)练手的经典题，当从某点向相邻的节点转移时，只有该两点之间的边权不同，其他边权没有变化，当\(u\)向\(v\)的边权为\(0\)时，\(v\)向\(u\)的边权则一定为\(1\)，反之亦然，所以可以考虑换根\(dp\) - 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学习笔记的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！
您可能喜欢
-
Slicm 框架怎么进行用户认证？-icode9专业技术文章分享11-13
-
在查询时将 map_coord 列的值转换为字符串有哪些方法？-icode9专业技术文章分享11-13
-
如何将微信地区改成自定义文案？-icode9专业技术文章分享11-13
-
DNS 缓存存在问题有哪些症状和解决方法？-icode9专业技术文章分享11-13
-
HTTP 状态码（405）-Method Not Allowed是什么意思？-icode9专业技术文章分享11-13
-
HTTP 状态码（500）-Internal Server Error是什么意思？-icode9专业技术文章分享11-13
-
在 Element UI 中无法修改 $confirm 的取消按钮文字是什么原因？-icode9专业技术文章分享11-13
-
unity XR是什么？-icode9专业技术文章分享11-13
-
伴随矩阵是什么？-icode9专业技术文章分享11-13
-
怎么使用grep -E 来查找匹配最后 2 条数据？-icode9专业技术文章分享11-13
-
怎么实现登陆并管理指定的 Git 仓库？-icode9专业技术文章分享11-13
-
git 如何上传当前文件不带跟目录？-icode9专业技术文章分享11-13
-
VMware ESXi 6.7U3u macOS Unlocker & OEM BIOS 集成 Realtek 网卡驱动和 NVMe 驱动11-12
-
阿里云轻量应用服务器不限流程，轻量和ECS有啥区别？11-12
-
无法访问 GitHub有哪些原因？-icode9专业技术文章分享11-12
栏目导航
