登录
← 返回首页 | 代码片段 › 4 树上问题 › 4.5 树形DP › 树形DP / 搜索
JSON MD

4.5 树形DP

Crash的文明世界 树形dp
54 行
CPP JSON
【Crash的文明世界(树形dp)】 树形 DP 模板,在树上进行 DFS 递推动态规划。 核心函数: void add(Re x,Re y) — 加法更新 void in(Re &x) — 核心算法函数 void dfs1(Re x,Re fa) — 深度优先搜索遍历 void dfs2(Re x,Re fa) — 深度优先搜索遍历 void Stirling(Re N) — 核心算法函数 核心结构体:QAQ 关键配置: N=5e4+3,M=153,P=10007 复杂度:时间复杂度取决于状态数和转移复杂度 说明:freopen("123.txt","r",stdin); 适用场景:树上的最优化问题(最大独立集、最小支配集、直径等)
C++ 53 行 CPP
#include<algorithm>
#include<cstring>
#include<cstdio>
#define LL long long
#define Re register int
using namespace std;
const int N=5e4+3,M=153,P=10007;
int n,m,x,y,o,K,jc[M],fto[M],head[N],S[M][M],f[N][M],g[N][M];
struct QAQ{int to,next;}a[N<<1];
inline void add(Re x,Re y){a[++o].to=y,a[o].next=head[x],head[x]=o;}
inline void in(Re &x){
    int dp=0;x=0;char c=getchar();
    while(c<'0'||c>'9')dp|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=dp?-x:x;
}
inline void dfs1(Re x,Re fa){
	f[x][0]=1;
	for(Re i=head[x],to;i;i=a[i].next)
		if((to=a[i].to)!=fa){
			dfs1(to,x),(f[x][0]+=f[to][0])%=P;
			for(Re j=1;j<=K;++j)(f[x][j]+=(f[to][j]+f[to][j-1])%P)%=P;
		}
}
inline void dfs2(Re x,Re fa){
	if(fa){
		fto[0]=(g[fa][0]+f[fa][0]-f[x][0]+P)%P;
		for(Re j=1;j<=K;++j)fto[j]=(g[fa][j]+f[fa][j]-(f[x][j]+f[x][j-1])%P+P)%P;
		g[x][0]=fto[0];
		for(Re j=1;j<=K;++j)g[x][j]=(fto[j]+fto[j-1])%P;
	}
	for(Re i=head[x],to;i;i=a[i].next)
		if((to=a[i].to)!=fa)dfs2(to,x);
}
inline void Stirling(Re N){
	for(Re i=0;i<=N;++i)S[i][i]=1;
	for(Re i=1;i<=N;++i)
		for(Re j=1;j<i;++j)
			S[j][i]=(S[j-1][i-1]+j*S[j][i-1]%P)%P;
}
int main(){
//	freopen("123.txt","r",stdin);
	in(n),in(K),m=n-1;
	while(m--)in(x),in(y),add(x,y),add(y,x);
	dfs1(1,0),dfs2(1,0),Stirling(K),jc[0]=1;
	for(Re i=1;i<=K;++i)jc[i]=jc[i-1]*i%P;
	for(Re i=1;i<=n;++i){
		Re ans=0;
		for(Re j=0;j<=K;++j)
			(ans+=S[j][K]*jc[j]%P*(f[i][j]+g[i][j])%P)%=P;
		printf("%d\n",ans);
	}
}
换根dp Great Cow Gathering
34 行
CPP JSON
【换根dp(Great Cow Gathering)】 树形 DP 模板,在树上进行 DFS 递推动态规划。 核心函数: void add(Re x,Re y,Re z) — 加法更新 void in(Re &x) — 核心算法函数 void dfs1(Re x,Re fa) — 深度优先搜索遍历 void dfs2(Re x,Re fa) — 深度优先搜索遍历 核心结构体:QAQ 复杂度:时间复杂度取决于状态数和转移复杂度 说明:freopen("123.txt","r",stdin); 适用场景:树上的最优化问题(最大独立集、最小支配集、直径等)
C++ 33 行 CPP
#include<algorithm>
#include<cstring>
#include<cstdio>
#define LL long long
#define Re register int
using namespace std;
const LL N=1e5+3,inf=1e18;
int n,m,x,y,z,o,A[N],S[N],dis[N],size[N],head[N];LL ans=inf,f[N],g[N];
struct QAQ{int w,to,next;}a[N<<1];
inline void add(Re x,Re y,Re z){a[++o].w=z,a[o].to=y,a[o].next=head[x],head[x]=o;}
inline void in(Re &x){
    int f=0;x=0;char c=getchar();
    while(c<'0'||c>'9')f|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=f?-x:x;
}
inline void dfs1(Re x,Re fa){
	size[x]=1,S[x]=A[x];
	for(Re i=head[x],to;i;i=a[i].next)if((to=a[i].to)!=fa)
		dis[to]=a[i].w,dfs1(to,x),S[x]+=S[to],size[x]+=size[to],f[x]+=f[to]+(LL)S[to]*a[i].w;
}
inline void dfs2(Re x,Re fa){
	if(fa)g[x]=g[fa]+f[fa]-f[x]-(LL)S[x]*dis[x]+(LL)(S[1]-S[x])*dis[x];
	for(Re i=head[x],to;i;i=a[i].next)if((to=a[i].to)!=fa)dfs2(to,x);
	ans=min(ans,f[x]+g[x]);
}
int main(){
//	freopen("123.txt","r",stdin);
	in(n),m=n-1;
	for(Re i=1;i<=n;++i)in(A[i]);
	while(m--)in(x),in(y),in(z),add(x,y,z),add(y,x,z);
	dfs1(1,0),dfs2(1,0),printf("%lld\n",ans);
}
树形dp 没有上司的舞会
28 行
CPP JSON
【树形dp(没有上司的舞会)】 树形 DP 模板,在树上进行 DFS 递推动态规划。 核心函数: void add(int x,int y) — 加法更新 void dfs(int w) — 深度优先搜索遍历 核心结构体:QAQ 复杂度:时间复杂度取决于状态数和转移复杂度 适用场景:树上的最优化问题(最大独立集、最小支配集、直径等)
C++ 27 行 CPP
#include<algorithm>
#include<cstring>
#include<cstdio>
#define R register int
using namespace std;
int head[6010],a,b,t,i,j,n,f[6010][2],pan[6010];
struct QAQ{int next,to;}Q[6010];
inline void add(int x,int y){Q[++t].to=y,Q[t].next=head[x],head[x]=t;}
inline void dfs(int w){
    for(R k=head[w];k;k=Q[k].next){
        int to=Q[k].to;
        dfs(to);
        f[w][0]+=max(f[to][0],f[to][1]);
        f[w][1]+=f[to][0];
    }
}
int main(){
    scanf("%d",&n);
    for(i=1;i<=n;i++)scanf("%d",&f[i][1]);
    for(i=1;i<n;i++)scanf("%d%d",&a,&b),pan[a]++,add(b,a);
    for(i=1;i<=n;i++)
        if(!pan[i]){
            dfs(i);
            printf("%d\n",max(f[i][0],f[i][1]));
            return 0;
        }
}
保安站岗,皇宫看守 树形dp
37 行
CPP JSON
【保安站岗,皇宫看守(树形dp)】 树形 DP 模板,在树上进行 DFS 递推动态规划。 核心函数: void add(int x,int y) — 加法更新 void dfs(int x) — 深度优先搜索遍历 核心结构体:QAQ 复杂度:时间复杂度取决于状态数和转移复杂度 适用场景:树上的最优化问题(最大独立集、最小支配集、直径等)
C++ 36 行 CPP
#include<algorithm>
#include<cstring>
#include<cstdio>
#define R register int
using namespace std;
struct QAQ{int to,next;}a[1505]; 
int m,pan[1505],n,t,w[1505],dp[1505][3],head[1505];
inline void add(int x,int y){a[++t].to=y,a[t].next=head[x],head[x]=t;}
  //dp[i][0] 以及各种情况的具体转移方程和初始状态 
inline void dfs(int x){
    R i,to,dd=0xfffffff;
    dp[x][1]=w[x];dp[x][2]=0;dp[x][0]=0;
    for(i=head[x];i;i=a[i].next){
        dfs(to=a[i].to);
        dd=min(dd,dp[to][1]-min(dp[to][0],dp[to][1]));
        dp[x][0]+=min(dp[to][0],dp[to][1]);
        dp[x][1]+=min(dp[to][1],dp[to][2]);
        dp[x][2]+=min(dp[to][0],dp[to][1]);
    }
    dp[x][0]+=dd;
}
int main(){
	memset(dp,127,sizeof(dp));
    scanf("%d",&n);
    R i,j,a,k,r;
    for(i=1;i<=n;i++){
        scanf("%d%d%d",&a,&k,&m);w[a]=k;
        for(j=1;j<=m;j++)scanf("%d",&r),pan[r]=1,add(a,r);
    }
    for(i=1;i<=n;i++)
        if(!pan[i]){
            dfs(i);
            printf("%d",min(dp[i][1],dp[i][0]));
            return 0;
        }
}
树上背包优化O复杂度 (NOI Online 2 游戏) nk
73 行
CPP JSON
【树上背包优化O复杂度 (NOI Online 2 游戏)(nk)】 树形 DP 模板,在树上进行 DFS 递推动态规划。 核心函数: void add(Re x,Re y) — 加法更新 void in(Re &x) — 核心算法函数 int mi(Re x,Re k) — 核心算法函数 int inv(Re x) — 求模逆元 void dfs0(Re x,Re fa) — 深度优先搜索遍历 void dfs(Re x,Re fa) — 深度优先搜索遍历 int C(Re m,Re n) — 核心算法函数 核心结构体:QAQ 关键配置: N=5003,P=998244353 复杂度:时间复杂度取决于状态数和转移复杂度 适用场景:树上的最优化问题(最大独立集、最小支配集、直径等)
C++ 72 行 CPP
#include<algorithm>
#include<cstring>
#include<cstdio>
#define LL long long
#define Re register int
using namespace std;
const int N=5003,P=998244353;
int n,m,o,x,y,f[N],g[N],A[N],jc[N],head[N];char s[N];
struct QAQ{int to,next;}a[N<<1];
inline void add(Re x,Re y){a[++o].to=y,a[o].next=head[x],head[x]=o;}
inline void in(Re &x){
    int f=0;x=0;char c=getchar();
    while(c<'0'||c>'9')f|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=f?-x:x;
}
inline int mi(Re x,Re k){
	Re s=1;
	while(k){
		if(k&1)s=(LL)s*x%P;
		x=(LL)x*x%P,k>>=1;
	}
	return s;
}
inline int inv(Re x){return mi(x,P-2);}
int sz1[N],sz0[N],lim[N],dp[N][N],tmp[N];
inline void dfs0(Re x,Re fa){
	sz0[x]=(!A[x]),sz1[x]=A[x];
	for(Re i=head[x],to;i;i=a[i].next)
		if((to=a[i].to)!=fa)dfs0(to,x),sz1[x]+=sz1[to],sz0[x]+=sz0[to];
//	lim[x]=min(sz1[x],size[x]-sz1[x]);
}
inline void dfs(Re x,Re fa){
	dp[x][0]=1;
	for(Re i=head[x],to;i;i=a[i].next)
		if((to=a[i].to)!=fa){
			dfs(to,x);
			for(Re j=0;j<=lim[x]+lim[to];++j)tmp[j]=0;
			for(Re j=lim[x];j>=0;--j)
				for(Re k=lim[to];k>=0;--k)
					(tmp[j+k]+=(LL)dp[x][j]*dp[to][k]%P)%=P;
			lim[x]+=lim[to];
			for(Re j=0;j<=lim[x];++j)dp[x][j]=tmp[j];
		}
	++lim[x];
	if(A[x])for(Re j=min(lim[x],sz0[x]);j>=1;--j)
		(dp[x][j]+=(LL)dp[x][j-1]*(sz0[x]-(j-1))%P)%=P;
	else for(Re j=min(lim[x],sz1[x]);j>=1;--j)
		(dp[x][j]+=(LL)dp[x][j-1]*(sz1[x]-(j-1))%P)%=P;
	while(!dp[x][lim[x]])--lim[x];
}
inline int C(Re m,Re n){return (LL)jc[n]*inv(jc[m])%P*inv(jc[n-m])%P;}
int main(){
//	freopen("match.in","r",stdin);
//	freopen("match.out","w",stdout);
	in(n),scanf("%s",s+1),m=n-1,jc[0]=1;
	for(Re i=1;i<=n;++i)A[i]=s[i]-'0',jc[i]=(LL)jc[i-1]*i%P;
	while(m--)in(x),in(y),add(x,y),add(y,x);
	dfs0(1,0),dfs(1,0);
//	for(Re i=1;i<=n;++i)printf("lim[%d]=%d\n",i,lim[i]);
//	for(Re i=0;i<=n/2;++i)printf("dp[%d]=%d\n",i,dp[1][i]);
//	for(Re j=0;j<=lim[1];++j)printf("%d ",dp[1][j]);
	for(Re j=0;j<=lim[1];++j)g[j]=(LL)dp[1][j]*jc[n/2-j]%P;
	for(Re i=lim[1];i>=0;--i){
		f[i]=g[i];
		for(Re j=i+1;j<=lim[1];++j)f[i]=(f[i]-(LL)C(i,j)*f[j]%P+P)%P;
	}
	for(Re i=0;i<=n/2;++i)printf("%d\n",f[i]);
	fclose(stdin);
	fclose(stdout);
	return 0;
}
树上背包优化O复杂度 (树上染色) nk
40 行
CPP JSON
【树上背包优化O复杂度 (树上染色)(nk)】 树形 DP 模板,在树上进行 DFS 递推动态规划。 核心函数: void add(Re x,Re y,Re z) — 加法更新 void in(Re &x) — 核心算法函数 void dfs(Re x,Re fa) — 深度优先搜索遍历 核心结构体:QAQ 关键配置: N=2003 复杂度:时间复杂度取决于状态数和转移复杂度 说明:freopen("123.txt","r",stdin); 适用场景:树上的最优化问题(最大独立集、最小支配集、直径等)
C++ 39 行 CPP
#include<algorithm>
#include<cstring>
#include<cstdio>
#define LL long long
#define Re register int
using namespace std;
const int N=2003;
int n,m,x,y,z,o,K,size[N],head[N];LL tmp[N],dp[N][N];
struct QAQ{int w,to,next;}a[N<<1];
inline void add(Re x,Re y,Re z){a[++o].w=z,a[o].to=y,a[o].next=head[x],head[x]=o;}
inline void in(Re &x){
    int f=0;x=0;char c=getchar();
    while(c<'0'||c>'9')f|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=f?-x:x;
}
inline void dfs(Re x,Re fa){
	size[x]=1,dp[x][0]=dp[x][1]=0;
	for(Re i=head[x],to;i;i=a[i].next)
		if((to=a[i].to)!=fa){
			dfs(to,x);
			for(Re j=0;j<=size[x]+size[to];++j)tmp[j]=dp[0][0];
			for(Re j=size[x];j>=0;--j)
				if(dp[x][j]>=0)for(Re k=size[to];k>=0;--k)
					if(dp[to][k]>=0)
						tmp[j+k]=max(tmp[j+k],dp[x][j]+dp[to][k]+
							(LL)a[i].w*((LL)k*(K-k)+(LL)(size[to]-k)*(n-size[to]-(K-k)))
						);
			size[x]+=size[to];
			for(Re j=0;j<=size[x];++j)dp[x][j]=tmp[j];
		}
}
int main(){
//	freopen("123.txt","r",stdin);
	in(n),in(K),m=n-1;
	while(m--)in(x),in(y),in(z),add(x,y,z),add(y,x,z);
	memset(dp,-20,sizeof(dp));
	dfs(1,0),printf("%lld\n",dp[1][K]);
}
已复制