树形dp,蒟蒻求助
查看原帖
树形dp,蒟蒻求助
33063
Focus_on楼主2021/8/3 07:09

rt

#include<cstdio>
#include<algorithm>

using namespace std;

const int inf=1e9;

struct EDGE{
	int v,nxt;
}edge[2010];

int n,x,f[1010][5],dep[1010],fa[1010],head[1010],e;
//f[x][st]表示在x结点处向上2,1,0,-1,-2层的最小消防站数 
//即从叶子节点开始覆盖到他自己,他的父亲,爷爷,他儿子,他孙子的最小数量 
//一定有:f[x][0]>=...>=f[x][4],因为覆盖到了他爷爷一定覆盖了他,以此类推 
//同时有:f[x][2]=min(f[i.ch][0~4])+1 **此处是因为若能管到他的爷爷,说明他自己处就有一个消防站,
//        那此时他的儿子,孙子都被覆盖到了,只需要他的曾孙子被覆盖到即可,儿子的0~4状态均可满足
//        以此类推

void adde(int u,int v){
	e++;
	edge[e].v=v;
	edge[e].nxt=head[u];
	head[u]=e;
}

void dfs1(int x,int f,int dp){
	
	fa[x]=f;
	dep[x]=dp;
	
	for(int i=head[x];i;i=edge[i].nxt)
		if(edge[i].v!=f) dfs1(edge[i].v,x,dp+1);
}

void dfs2(int x){
	
	int min1=inf,min2=inf;
	
	f[x][0]=1;
	
	for(int i=head[x];i;i=edge[i].nxt){
		
		int v=edge[i].v;
		if(v!=fa[x]) dfs2(v);
		
		f[x][3]+=f[v][2];
		f[x][4]+=f[v][3];
		f[x][0]+=f[v][4];
		min1=min(min1,f[v][0]-f[v][3]);
		min2=min(min2,f[v][1]-f[v][2]);
	}
	
	f[x][1]=min1+f[x][4];
	f[x][2]=min(f[x][3]+min2,min(f[x][0],f[x][1]));
	f[x][3]=min(f[x][2],f[x][3]);
	f[x][4]=min(f[x][3],f[x][4]);
	
}

int main(){
	
	scanf("%d",&n);
	for(int i=1;i<n;i++){
		scanf("%d",&x);
		adde(x,i+1);
		adde(i+1,x);
	}
	
	dfs1(1,1,0);
	
	dfs2(1);
	
	printf("%d\n",f[1][2]);
	
	return 0;
}
2021/8/3 07:09
加载中...