【learning】树形dp题目汇总

69 阅读 0 评论 46 点赞

我是靠谱客的博主瘦瘦河马，最近开发中收集的这篇文章主要介绍【learning】树形dp题目汇总，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

树形dp，就是在树上dp。
解决这类问题的一般步骤
1、确定状态的意思
2、确定状态转移方程
3、确定细节，就是边界和+1-1之类的东西。
这里主要是我树形dp的练习记录。
T1 oiclass1453 二叉苹果树
思路：在dfs的过程中dp。让f[i][j]表示在以i为根的子树内，保留j根树枝，最多保留的苹果树。
状态转移方程： f[i][j]=max(f[i][j−k−1]+f[son][k]+这条上的苹果数) f [ i ] [ j ] = m a x ( f [ i ] [ j − k − 1 ] + f [ s o n ] [ k ] + 这条上的苹果数 ) ，边界 f[i][0]=0 f [ i ] [ 0 ] = 0 。
代表：在之前的子树内取 j−k−1 j − k − 1 条树枝，在当前子树内取k条树枝，再取连接父子的树枝的最大值。
最后答案就是 f[1][m] f [ 1 ] [ m ] 。
代码：

#include<cstdio>
#include<algorithm>
using namespace std;
const int N=105;
int n,m,u,v,d,cnt,head[N],to[N*2],nxt[N*2],dd[N*2],f[N][N];
void adde(int u,int v,int d){
to[++cnt]=v;
nxt[cnt]=head[u];
dd[cnt]=d;
head[u]=cnt;
}
void dfs(int pre,int u,int t){
int v;
for(int i=head[u];i;i=nxt[i]){
v=to[i];
if(v!=pre){
dfs(u,v,t-1);
for(int j=t;j>0;j--){
for(int k=0;k<j;k++){
f[u][j]=max(f[u][j],f[u][j-k-1]+f[v][k]+dd[i]);
}
}
}
}
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<n;i++){
scanf("%d%d%d",&u,&v,&d);
adde(u,v,d);
adde(v,u,d);
}
dfs(0,1,m);
printf("%dn",f[1][m]);
return 0;
}

T2 oiclass1454 选课
思路：在dfs的过程中dp。其实题目中已经给了一个现成的根—0。让f[i][j]表示在I为根的子树内选j门课的最大学分。
状态转移方程：f[i][j]=max(f[i][j-k]+f[son][k-1]+选son的学分)，边界f[i][0]=0。
代表：在之前的子树内选j-k门课，在当前子树选k-1门课，再选当前的儿子这门课的最大值。
最后答案就是f[0][m]。
代码：

#include<cstdio>
#include<algorithm>
using namespace std;
int n,m,pre,d,cnt,head[305],to[305],nxt[305],dd[305],f[305][205];
void adde(int u,int v,int d){
to[++cnt]=v;
nxt[cnt]=head[u];
dd[cnt]=d;
head[u]=cnt;
}
void dfs(int u,int t){
int v;
for(int i=head[u];i;i=nxt[i]){
v=to[i];
dfs(v,t-1);
for(int j=t;j>0;j--){
for(int k=1;k<=j;k++){
f[u][j]=max(f[u][j],f[u][j-k]+f[v][k-1]+dd[i]);
}
}
}
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
scanf("%d%d",&pre,&d);
adde(pre,i,d);
}
dfs(0,m);
printf"%dn",f[0][m]);
return 0;
}

T3 oiclass1455 周年庆宴
思路：最大独立集裸题。在dfs的过程中dp。让f[i][0]表示不选i的最大值，f[i][1]表示选i的最大值。
状态转移方程： f[i][0]=∑max(f[son][0],f[son[1])f[i][1]=∑f[son][0] f [ i ] [ 0 ] = ∑ m a x ( f [ s o n ] [ 0 ] , f [ s o n [ 1 ] ) f [ i ] [ 1 ] = ∑ f [ s o n ] [ 0 ] 。边界 f[i][0]=0 f [ i ] [ 0 ] = 0 , f[i][1]=选i的值 f [ i ] [ 1 ] = 选 i 的值。
意思：不选i，则i的儿子都可以取或不取，因此max取或不取一下就好了。选i，则i的儿子都不可以取。
代码：

#include<cstdio>
#include<algorithm>
using namespace std;
int n,u,v,cnt,val[6005],head[6005],to[6005],nxt[6005],f[6005][2];
bool ck[6005];
void adde(int u,int v){
to[++cnt]=v;
nxt[cnt]=head[u];
head[u]=cnt;
}
void dfs(int u){
int v;
f[u][1]=val[u];
for(int i=head[u];i;i=nxt[i]){
v=to[i];
dfs(v);
f[u][0]+=max(f[v][0],f[v][1]);
f[u][1]+=f[v][0];
}
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",&val[i]);
}
for(int i=1;i<n;i++){
scanf("%d%d",&u,&v);
ck[u]=true;
adde(v,u);
}
for(int i=1;i<=n;i++){
if(!ck[i]){
dfs(i);
printf("%dn",max(f[i][0],f[i][1]));
return 0;
}
}
return 0;
}

T4 oiclass1456 偷天换日
思路：递归输入。把叶子节点的所有画拆成节点，与叶子代表的那个展厅连边。令cost[i]代表从父亲到i的时间，val[i]代表到达i就可以获得的价值。让f[i][j]代表在以i为根，花j的时间获得的最大价值。
状态转移方程： f[i][j]=max(f[i][j−k]+f[son][k]) f [ i ] [ j ] = m a x ( f [ i ] [ j − k ] + f [ s o n ] [ k ] ) ，边界条件： f[i][cost[i]]=val[i] f [ i ] [ c o s t [ i ] ] = v a l [ i ] 。
代表：在之前的子树内花 j−k j − k 的时间，在当前子树内花 k k 的时间的最大价值。
细节：非拆出来的节点的val设为0，否则设为对应画的价值。非叶节点的cost值要*2，因为小偷要回去。可用时间要-1，因为小偷要时间来逃跑。
常数巨大，开O2才过 = =
代码：

#include<cstdio>
#define int unsigned int
#pragma GCC optimize(2)
const int N=2505;
int m,t,x,w,c,tot=1,cnt,val[N],cost[N],head[N],to[N*2],nxt[N*2],f[N][605];
char ch[100005],*p;
inline int rd(){
register int ret=0;
while(*p<'0'||*p>'9'){
p++;
}
while(*p>='0'&&*p<='9'){
ret=ret*10+*p-'0';
p++;
}
return ret;
}
inline void adde(int u,int v){
to[++cnt]=v;
nxt[cnt]=head[u];
head[u]=cnt;
}
void build(int u){
cost[++tot]=rd()*2;
x=rd();
adde(u,tot);
u=tot;
if(!x){
build(u);
build(u);
}else{
for(register int i=1;i<=x;i++){
val[++tot]=rd();
cost[tot]=rd();
adde(u,tot);
}
}
}
void dfs(int u,int t){
int v;
for(int i=head[u];i;i=nxt[i]){
v=to[i];
if(t-cost[u]>=cost[v]){
f[v][cost[v]]=val[v];
dfs(v,t-cost[u]);
for(register int j=t;j>=cost[u]+cost[v];j--){
for(register int k=cost[v];k<=j-cost[u];k++){
f[u][j]=f[u][j]>f[u][j-k]+f[v][k]?f[u][j]:f[u][j-k]+f[v][k];
}
}
}
}
}
main(){
p=ch;
fread(ch,1,100000,stdin);
m=rd();
build(1);
dfs(1,m-1);
printf("%un",f[1][m-1]);
return 0;
}

T5 oiclass1457 黑手党
思路：其实就是树的重心。让 $m a x n [i]$ 代表以i为重心剩下各部分的最大节点数， siz[i] s i z [ i ] 代表以i为根的子树的大小。 siz[i]=1+∑siz[son] s i z [ i ] = 1 + ∑ s i z [ s o n ] ， maxn[i]=max(siz[son) m a x n [ i ] = m a x ( s i z [ s o n ) 和 n−siz[i] n − s i z [ i ] 的较大值。最后记录所有 maxn m a x n 的最小值 minn m i n n ，循环一次节点1~n，若 maxn[i]==minn m a x n [ i ] == m i n n 就输出i。学了点分治后，这个自然就会了。
代码：

#include<cstdio>
#include<algorithm>
using namespace std;
const int N=50005;
int n,u,v,minn,cnt,head[N],to[N*2],nxt[N*2],maxn[N*2];
void adde(int u,int v){
to[++cnt]=v;
nxt[cnt]=head[u];
head[u]=cnt;
}
int dfs(int pre,int u){
int v,siz,sum=1;
for(int i=head[u];i;i=nxt[i]){
v=to[i];
if(v!=pre){
siz=dfs(u,v);
maxn[u]=max(maxn[u],siz);
sum+=siz;
}
}
maxn[u]=max(maxn[u],n-sum);
minn=min(minn,maxn[u]);
return sum;
}
int main(){
scanf("%d",&n);
minn=n;
for(int i=1;i<n;i++){
scanf("%d%d",&u,&v);
adde(u,v);
adde(v,u);
}
dfs(0,1);
for(int i=1;i<=n;i++){
if(maxn[i]==minn){
printf("%d ",i);
}
}
puts("");
return 0;
}

T6 oiclass1458 电脑网络
思路：其实正解也不难，这里就讲一讲思路。
先dfs一次，求出每个节点i的子树所有叶节点到i的距离的最大值。接着dfs一次，在dfs的过程中dp。
让 f[i][0] f [ i ] [ 0 ] 表示i的子树内叶子节点到i的距离的最大值， f[i][1] f [ i ] [ 1 ] 是次大值， f[i][2] f [ i ] [ 2 ] 是离i最远的节点到i的距离。关键代码大概是这样的：

void dfs(int pre,int u){
for(int i=head[u];i!=-1;i=e[i].next){
int v=e[i].v;
int w=e[i].w;
if(f[u][0]==f[v][0]+w){
f[v][2]=max(f[u][2],f[u][1])+w;
}
else{
f[v][2]=max(f[u][2],f[u][0])+w;
}
dfs(u,v);
}
}

意思就是：如果v到u的距离是最大值，就用u子树内到u的次大值更新 f[v][2] f [ v ] [ 2 ] ，否则就可以用u子树内到u的最大值更新 f[v][2] f [ v ] [ 2 ] 。时间复杂度O(n)。
懒得打了，就没写这种写法^ ^~~是因为太弱想不到正解吧~~
再讲一下我的写法。由于n<=10000，所以裸的暴力O(n²)会超时。我也是暴力，只不过搞了一些优化。虽然最坏情况下也是 O(n²) O ( n ² ) ，但是哪有那么多最坏情况呢233
思路：让maxn[i]表示i的子树内某个节点到i的距离最大值。对于每个节点i，让i往根爬，设当前爬到的节点为j。则fa[j]的每个除j以外的儿子的maxn所对应的节点与i的lca都一定为fa[j]。然后对于fa[j]的每个除j以外的儿子k，它的maxn对应的节点到i的距离就是maxn[k]+fa[j]到k的这条边的距离+i到fa[j]的距离，再更新i的答案即可。时间复杂度O(能过)，跟树的形状有关。
代码：

#include<cstdio>
#include<algorithm>
using namespace std;
const int N=10005;
int n,u,d,cnt,head[N],fa[N],dis[N],maxn[N],to[N*2],nxt[N*2],dd[N*2];
void adde(int u,int v,int d){
to[++cnt]=v;
nxt[cnt]=head[u];
dd[cnt]=d;
head[u]=cnt;
}
void dfs(int pre,int u){
fa[u]=pre;
int v;
for(int i=head[u];i;i=nxt[i]){
v=to[i];
if(v!=pre){
dis[v]=dis[u]+dd[i];
dfs(u,v);
maxn[u]=max(maxn[u],maxn[v]+dd[i]);
}
}
}
int main(){
scanf("%d",&n);
for(int i=2;i<=n;i++){
scanf("%d%d",&u,&d);
adde(u,i,d);
adde(i,u,d);
}
dfs(0,1);
printf("%dn",maxn[1]);
for(int i=2;i<=n;i++){
int ans=maxn[i];
for(int tmp=i;fa[tmp];tmp=fa[tmp]){
int mm=0;
for(int j=head[fa[tmp]];j;j=nxt[j]){
if(to[j]!=tmp&&to[j]!=fa[fa[tmp]]){
mm=max(mm,maxn[to[j]]+dd[j]);
}
}
ans=max(ans,mm+dis[i]-dis[fa[tmp]]);
}
printf("%dn",ans);
}
return 0;
}

T7 oiclass1459 重建道路
打的也是能过的暴力= =
让 f[i][j] f [ i ] [ j ] 表示以i为根的子树内丢掉j的节点要删的最小边数。
状态转移方程：
代码： f[i][j]=min(f[i][j−k]+f[son][k]) f [ i ] [ j ] = m i n ( f [ i ] [ j − k ] + f [ s o n ] [ k ] ) ，边界 f[i][0]=0 f [ i ] [ 0 ] = 0 , f[i][siz[i]]=1 f [ i ] [ s i z [ i ] ] = 1 ，其他为inf。
意思是：在之前的子树内丢掉j-k个节点，再在当前子树内丢掉k个节点的最小值。一个节点都不丢当然只要删掉0条边，整个子树都丢掉要删掉1条边都可以了。
但是在i的子树外删掉的呢？
我就搞了个暴力，以每个节点i为根都dp一次，再取 f[i][n−p] f [ i ] [ n − p ] 的最小值就可以了。这样原本在i的子树外删掉的节点都可以在i的子树内统计。

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=155;
int n,p,u,v,cnt,ans=0x7fffffff,head[N],to[N*2],nxt[N*2],siz[N],f[N][N];
void adde(int u,int v){
to[++cnt]=v;
nxt[cnt]=head[u];
head[u]=cnt;
}
void dfs1(int pre,int u){
siz[u]=1;
int v;
for(int i=head[u];i;i=nxt[i]){
v=to[i];
if(v!=pre){
dfs1(u,v);
siz[u]+=siz[v];
}
}
f[u][siz[u]]=1;
f[u][0]=0;
}
void dfs2(int pre,int u){
int v;
for(int i=head[u];i;i=nxt[i]){
v=to[i];
if(v!=pre){
dfs2(u,v);
for(int j=siz[u]-1;j>0;j--){
for(int k=1;k<=min(siz[v],j);k++){
f[u][j]=min(f[u][j],f[u][j-k]+f[v][k]);
}
}
}
}
}
int main(){
scanf("%d%d",&n,&p);
for(int i=1;i<n;i++){
scanf("%d%d",&u,&v);
adde(u,v);
adde(v,u);
}
for(int i=1;i<=n;i++){
memset(f,42,sizeof(f));
dfs1(0,i);
dfs2(0,i);
ans=min(ans,f[i][n-p]);
}
printf("%dn",ans);
return 0;
}

T8 oiclass1460 战略游戏
思路：其实就是个最小边覆盖，跟上面的周年庆宴基本一样。
~~解法同上，就不写了~~
在dfs的过程中dp。让 f[i][0] f [ i ] [ 0 ] 表示不放i的最小值，f[i][1]表示放i的最小值。
状态转移方程： f[i][1]=∑min(f[son][0],f[son[1])f[i][0]=Σf[son][1] f [ i ] [ 1 ] = ∑ m i n ( f [ s o n ] [ 0 ] , f [ s o n [ 1 ] ) f [ i ] [ 0 ] = Σ f [ s o n ] [ 1 ] 。边界 f[i][0]=0 f [ i ] [ 0 ] = 0 , f[i][1]=1 f [ i ] [ 1 ] = 1 。
意思：放i，则i的儿子都可以取或不取，因此max取或不取一下就好了。不放i，则i的儿子都要放。
代码：

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=1505;
int n,u,t,v,cnt,head[N],to[N*2],nxt[N*2],f[N][2];
void adde(int u,int v){
to[++cnt]=v;
nxt[cnt]=head[u];
head[u]=cnt;
}
void dfs(int pre,int u){
f[u][0]=0;
f[u][1]=1;
int v;
for(int i=head[u];i;i=nxt[i]){
v=to[i];
if(v!=pre){
dfs(u,v);
f[u][0]+=f[v][1];
f[u][1]+=min(f[v][0],f[v][1]);
}
}
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d%d",&u,&t);
u++;
for(int i=1;i<=t;i++){
scanf("%d",&v);
v++;
adde(u,v);
adde(v,u);
}
}
dfs(0,1);
printf("%dn",min(f[1][0],f[1][1]));
return 0;
}

T9 oiclass1461 有线电视网
思路：让 f[i][j] f [ i ] [ j ] 表示以i为根的子树，转播j个用户的最大利润。
状态转移方程： f[i][j]=max(f[i][j−k]+f[son][k]−i到son的边的权值) f [ i ] [ j ] = m a x ( f [ i ] [ j − k ] + f [ s o n ] [ k ] − i 到 s o n 的边的权值 ) 。
意思：取在之前的子树内转播j-k个用户，再在当前子树内转播k个用户的，再扣掉传输的费用的最大值。
代码：

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=3005;
int n,m,u,v,d,cnt,head[N],to[N],nxt[N],dd[N],val[N],siz[N],f[N][N];
void adde(int u,int v,int d){
to[++cnt]=v;
nxt[cnt]=head[u];
dd[cnt]=d;
head[u]=cnt;
}
void dfs(int u){
siz[u]=1;
f[u][0]=0;
int v;
for(int i=head[u];i;i=nxt[i]){
v=to[i];
if(v>n-m){
f[v][1]=val[v];
siz[v]=1;
}
dfs(v);
siz[u]+=siz[v];
for(int j=siz[u];j>0;j--){
for(int k=1;k<=siz[v];k++){
f[u][j]=max(f[u][j],f[u][j-k]+f[v][k]-dd[i]);
}
}
}
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n-m;i++){
scanf("%d",&u);
for(int j=1;j<=u;j++){
scanf("%d%d",&v,&d);
adde(i,v,d);
}
}
for(int i=n-m+1;i<=n;i++){
scanf("%d",&val[i]);
}
memset(f,-63,sizeof(f));
dfs(1);
for(int i=m;i>=0;i--){
if(f[1][i]>=0){
printf("%dn",i);
return 0;
}
}
return 0;
}

T10 oiclass1462 消防站
思路：这道题状态转移方程很难，看了题解才明白的。
让f[i][j]表示节点i依靠节点j，且以i为根的子树内所有节点都有依靠的最小费用。这和前面很不一样，根本想不到。ans[i]表示以i为根的子树内所有节点都有依靠的最小费用。
则：1~n循环一遍j， f[i][j]=w[j]+∑min(f[son][j]−w[j],ans[son]) f [ i ] [ j ] = w [ j ] + ∑ m i n ( f [ s o n ] [ j ] − w [ j ] , a n s [ s o n ] ) 。 f[son][j]−w[j] f [ s o n ] [ j ] − w [ j ] 就是son依靠j， ans[son] a n s [ s o n ] 就是让son依靠一个点，再取个min，就是满足son的子树内所有节点都有依靠。然后 f[i][j] f [ i ] [ j ] 就是在j建消防站的费用再加i的所有son都满足的费用的和。若 dis[i][j]>d[i] d i s [ i ] [ j ] > d [ i ] 或者 min(f[son][j]−w[j],ans[son]) m i n ( f [ s o n ] [ j ] − w [ j ] , a n s [ s o n ] ) 中任有一个为inf，则说明不能满足节点i依靠节点j，且以i为根的子树内所有节点都有依靠，就把f[i][j]赋值为inf。
推完所有f[i]之后就可以推ans[i]了。细节详见代码。
代码：

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=1005,inf=0x7f7f7f7f;
int t,n,u,v,di,cnt,w[N],d[N],head[N],to[N*2],nxt[N*2],dd[N*2],dis[N][N],f[N][N],ans[N];
void adde(int u,int v,int d){
to[++cnt]=v;
nxt[cnt]=head[u];
dd[cnt]=d;
head[u]=cnt;
}
void dfsdis(int pre,int u,int rt){
int v;
for(int i=head[u];i;i=nxt[i]){
v=to[i];
if(v!=pre){
dis[rt][v]=dis[rt][u]+dd[i];
dfsdis(u,v,rt);
}
}
}
void update(int pre,int u,int rt){
ans[rt]=min(ans[rt],f[rt][u]);
int v;
for(int i=head[u];i;i=nxt[i]){
v=to[i];
if(v!=pre){
update(u,v,rt);
}
}
}
void dfs(int pre,int u){
int v;
for(int i=head[u];i;i=nxt[i]){
v=to[i];
if(v!=pre){
dfs(u,v);
}
}
for(int i=1;i<=n;i++){
if(dis[u][i]>d[u]){
f[u][i]=inf;
}else{
f[u][i]=w[i];
for(int j=head[u];j;j=nxt[j]){
v=to[j];
if(v!=pre){
int minn=min(f[v][i]-w[i],ans[v]);
if(minn>=inf-1000){
f[u][i]=inf;
break;
}
f[u][i]+=minn;
}
}
}
}
ans[u]=inf;
update(pre,u,u);
}
int main(){
scanf("%d",&t);
while(t--){
cnt=0;
memset(head,0,sizeof(head));
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",&w[i]);
}
for(int i=1;i<=n;i++){
scanf("%d",&d[i]);
}
for(int i=1;i<n;i++){
scanf("%d%d%d",&u,&v,&di);
adde(u,v,di);
adde(v,u,di);
}
for(int i=1;i<=n;i++){
dfsdis(0,i,i);
}
dfs(0,1);
printf("%dn",ans[1]);
}
return 0;
}