以下是一些树形 DP 题目，为本蒟蒻在上网课时所整理。
顾名思义，树形 DP 是发生在树上的，状态转移发生在父结点和子结点之间。
状态转移的方向：一般叶子结点向根结点转移，也有相反的时候。
树的结构是递归的，我们常在树上进行 dfs 控制转移发生的次序。
由叶子结点向根结点的转移是发生在递归返回过程中，因此，DP 方程常出现在递归调用之后。由根向叶子结点转移的 DP 与之相反。
P1352 没有上司的舞会
题意
一个树上最大独立集问题。一棵树有一些节点（），点有权（），选择一个点集，点集中任意两点不可相邻，使得这个点集权之和最大。
点击查看题解
题解
设value[x] 是 节点点权，son 是 root 的后继，f[root][status] 为以 root 为根的子树，根节点的状态是 status（入选 或者不入选 ）时的最大独立集。则答案就是取 root 入选和不入选两者的最大值。状态转移方程：
f[root][1] = value[root] + ∑f[son][0];
f[root][0] = ∑max{f[son][1],f[son][0]};
代码
#include<bits/stdc++.h>
using namespace std;
namespace _yz
{
const int N=6000+10;
int n,root,r[N],head[N],cnt=0,m,f[N][2],in[N];
struct edge{int nxt,to;}e[N];
void add(int x,int y){e[++cnt]=(edge){head[x],y};head[x]=cnt;}
void dfs(int now)
{
f[now][1]=r[now];
for(int i=head[now];i;i=e[i].nxt)
{
int to=e[i].to;
dfs(to);
f[now][0]+=max(f[to][1],f[to][0]);//没去
f[now][1]+=f[to][0];//去了
}
}
void yzmain()
{
int t1,t2;
scanf("%d",&n);m=n-1;
for(int i=1;i<=n;i++) scanf("%d",r+i);
for(int i=1;i<=m;i++)
{
scanf("%d%d",&t1,&t2);
add(t2,t1);
in[t1]++;
}
for(int i=1;i<=n;i++) if(in[i]==0) root=i;
dfs(root);
printf("%d\n",max(f[root][0],f[root][1]));
return;
}
}
int main()
{
//freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
_yz::yzmain();
return 0;
}
P2014 [CTSC1997]选课
题意
一个树上背包问题。一个森林， 个点，点有权，选择一个数量为 的点集，使点集权值和最大，除各树的根节点外，每个点的父节点必在点集内。。
点击查看题解
题解
设f[u][j]是以 为根的子树入选 个点的最大值，其中 是 的子节点；设value[x] 是 节点点权。加一个虚拟的根，把森林变成树。根权值为 ，容量为 。问题转化为，一棵树， 个点，选择一个数量为 的点集，…
显而易见地：
代码
#include<bits/stdc++.h>
using namespace std;
namespace _yz
{
const int N=300+10;
int n,m,s[N],head[N],cnt=0,f[N][N];
struct edge{int nxt,to;}e[N];
void add(int x,int y){e[++cnt]=(edge){head[x],y};head[x]=cnt;}
void dfs(int root)
{
f[root][1]=s[root];
for(int i=head[root];i;i=e[i].nxt)//相当于分组背包的枚举组
{
int son=e[i].to;
dfs(son);
for(int j=m+1;j>=1;j--)//枚举“体积”
for(int k=1;k<j;k++)//相当于枚举“组”内物品 要为 root 腾出 1 来
f[root][j]=max(f[root][j],f[root][j-k]+f[son][k]);
}
}
void yzmain()
{
int tmp;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
{
scanf("%d%d",&tmp,s+i);
add(tmp,i);
}
dfs(0);
printf("%d\n",f[0][m+1]);
return;
}
}
int main()
{
//freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
_yz::yzmain();
return 0;
}
P2015 二叉苹果树
题意
一个树上背包问题。一棵树， 条边，边有边权（），选择一个数量为 的边集，使边集权值和最大，每条边的“父边”必在边集内。。
点击查看题解
题解
我们要把这个问题转化为“选课“问题。注意到，每条边只会有一个后继。于是，将边的权值转化为后继节点的权值；保留 条边，可转化为保留 个点。
其余的做法就和”选课“问题类似了。
代码
#include<bits/stdc++.h>
using namespace std;
namespace _yz
{
const int N=100+10;
int n,m,head[N],cnt=0,f[N][N];
struct edge{int nxt,to,len;}e[N*2];
void add(int x,int y,int len){e[++cnt]=(edge){head[x],y,len};head[x]=cnt;}
void dfs(int root,int dad)
{
for(int i=head[root];i;i=e[i].nxt)
{
int son=e[i].to;
if(son==dad) continue;
f[son][1]=e[i].len;
dfs(son,root);
for(int j=m;j>=1;j--)
for(int k=1;k<j;k++)
f[root][j]=max(f[root][j],f[root][j-k]+f[son][k]);
}
}
void yzmain()
{
int t1,t2,t3;
scanf("%d%d",&n,&m);m++;
for(int i=1;i<=n-1;i++)
{
scanf("%d%d%d",&t1,&t2,&t3);
add(t1,t2,t3),add(t2,t1,t3);
}
dfs(1,1);
printf("%d\n",f[1][m]);
return;
}
}
int main()
{
//freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
_yz::yzmain();
return 0;
}
P1131 [ZJOI2007] 时态同步
题意
给一棵树的一些边增加边权，使得每个叶子节点到根节点的距离最小且相等。求要增加的最小边权。节点数 ，边权 。
点击查看题解
题解
将边权转化为点权仍按照上题所述。显然，我们调整靠近根节点的节点，其下叶子节点距离根节点的距离都会增加，所以，调整越靠根节点的节点调整的代价越少。
据此结论，我们从叶子节点开始调起。在一个子树中，我们只需要使同一层的叶子节点权值相同，即都使权值增加为这些叶子节点的最大值。之后，用这个值更新它们的父节点权值（加上这个值）。
更新后，将叶子节点”砍“掉。父节点成了”叶子节点“。再按照类似的方法更新即可。
示例：
1 1 8 8
/ \ / \ : :
2 3 --> 7 5 --> 7 7 --> ans=6
/ \ \ : : :
5 1 2 5 5 2
更新途中，我们可以计算答案。对于每次更新，所作贡献是 叶子节点最大值 叶子节点数量 叶子节点权值和。记得用 long long。
代码
#include<bits/stdc++.h>
using namespace std;
namespace _yz
{
const long long N=500000+10,Val=1,Max=2,Num=3,Sum=4;
long long n,root,ans=0,head[N],cnt=0,f[N][10];
struct edge{long long nxt,to,len;}e[N*2];
void add(long long x,long long y,long long len){e[++cnt]=(edge){head[x],y,len};head[x]=cnt;}
void dfs(long long root,long long dad)
{
for(long long i=head[root];i;i=e[i].nxt)
{
long long son=e[i].to;
if(son==dad) continue;
f[son][Val]=e[i].len;
dfs(son,root);
f[root][Num]++;
f[root][Max]=max(f[root][Max],f[son][Max]);
f[root][Sum]+=f[son][Max];
}
ans+=f[root][Max]*f[root][Num]-f[root][Sum];
f[root][Max]+=f[root][Val];
}
void yzmain()
{
long long t1,t2,t3;
scanf("%lld%lld",&n,&root);
for(long long i=1;i<=n-1;i++)
{
scanf("%lld%lld%lld",&t1,&t2,&t3);
add(t1,t2,t3),add(t2,t1,t3);
}
dfs(root,root);
printf("%lld\n",ans);
return;
}
}
int main()
{
//freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
_yz::yzmain();
return 0;
}
X1578【例 4】战略游戏
题意
在一棵树的节点上放置最少数目的士兵，使得这些士兵能够瞭望到所有的边。某个士兵在一个节点上时，与该节点相连的所有边都将能被瞭望到。，其中 是节点数。
点击查看题解
题解
无后效性分析：一个节点放士兵与否，均不会对其他节点造成影响。
状态设计：设 f[i][0/1] 为对于以 为根节点的子树， 节点放与不放士兵时的最少士兵数。
状态转移方程：
边界：f[i][1] 初始化为 ，f[i][0] 初始化为 。
代码
#include<bits/stdc++.h>
using namespace std;
namespace _yz
{
const int N=1500+10;
struct edge{int nxt,to;}e[N*2];
int n,head[N],cnt=0,f[N][2];
void add(int a,int b)
{
e[++cnt]=(edge){head[a],b};
head[a]=cnt;
}
void dfs(int root,int dad)
{
f[root][1]=1;
for(int i=head[root];i;i=e[i].nxt)
{
int son=e[i].to;
if(son==dad) continue;
dfs(son,root);
f[root][0]+=f[son][1];
f[root][1]+=min(f[son][1],f[son][0]);
}
}
void yzmain()
{
int ta,tb,tc;
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d%d",&ta,&tb);
for(int j=1;j<=tb;j++)
{
scanf("%d",&tc);
add(ta,tc),add(tc,ta);
}
}
dfs(1,1);
printf("%d\n",min(f[1][1],f[1][0]));
return;
}
}
int main()
{
//freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
_yz::yzmain();
return 0;
}
附注
以下是 Yurchiu 的题解写作模板。
单题解
# 题意
<details><summary>点击查看题解</summary>
# 题解
# 代码
```cpp
```
</details>
多题解
#
## 题意
<details><summary>点击查看题解</summary>
## 题解
## 代码
```cpp
```
</details>
本文作者：Yurchiu
本文链接：https://yz-hs.github.io/8a876f7ed9d8/
版权声明：本博客中所有原创文章除特别声明外，均允许规范转载，转载请注明出处。所有非原创文章，按照原作者要求转载。
