树形DP求调
查看原帖
树形DP求调
525402
_Hugoi_楼主2023/6/29 17:56
#include<bits/stdc++.h>
using namespace std;
const int N=1e3+10;
struct Node{
	int nxt,to;
}e[N];
int n,h[N],a,tot,f[N][5],s1,s2,k;
void add(int x,int y){
	e[++tot].nxt=h[x];
	h[x]=tot;
	e[tot].to=y;
}
int min(int a,int b,int c,int d,int e){
	return min(a,min(b,min(c,min(d,e))));
}
int min(int a,int b,int c,int d){
	return min(a,min(b,min(c,d)));
}
int min(int a,int b,int c){
	return min(a,min(b,c));
}
void dfs(int u,int p){
	f[u][0]=1;//被自己覆盖
	f[u][1]=N;//被儿子覆盖
	f[u][2]=N;//被孙子覆盖
	f[u][3]=0;//被爷爷覆盖
	f[u][4]=0;//被爹覆盖
	s1=s2=0;
	for(int i=h[u];i;i=e[i].nxt){
		int v=e[i].to;
		if(v==p) continue;
		dfs(v,u);
		f[u][0]+=min(f[v][0],f[v][1],f[v][2],f[v][3],f[v][4]);
		s1+=min(f[v][0],f[v][1],f[v][2],f[v][3]);
		s2+=min(f[v][1],f[v][2]);
		f[u][3]+=min(f[v][0],f[v][1],f[v][2]);
		f[u][4]+=min(f[v][0],f[v][1],f[v][2],f[v][3]);
	}
	for(int i=h[u];i;i=e[i].nxt){
		int v=e[i].to;
		if(v==p) continue;
		int k1=min(f[v][0],f[v][1],f[v][2],f[v][3]);
		if(f[v][0]==k1) f[u][1]=min(f[u][1],s1);
		else{
			f[u][1]=min(f[u][1],s1-k1+f[v][0]);
		}
		int k2=min(f[v][1],f[v][2]);
		if(f[v][1]==k2) f[u][2]=min(f[u][2],s2);
		else{
			f[u][2]=min(f[u][2],s2-k2+f[v][1]);
		}
	}
}
int main(){
	cin>>n;
	for(int i=2;i<=n;i++){
		cin>>a;
		add(a,i);
		add(i,a);
	}
	dfs(1,0);
	int ans=0x3f3f3f3f;
	for(int i=0;i<=2;i++){
		ans=min(ans,f[1][i]);
	}
	cout<<ans;
	return 0;
}
2023/6/29 17:56
加载中...