求助,方程感觉没问题,但是全WA,QWQ
查看原帖
求助,方程感觉没问题,但是全WA,QWQ
247540
tongyf楼主2020/6/26 12:10

RTRT

#include<bits/stdc++.h>
using namespace std;
int n,cnt,hd[1005],f[1005][5];
struct node{
	int to,next;
}e[2005];
void addedge(int x,int y){
	e[++cnt].next=hd[x];
	e[cnt].to=y;
	hd[x]=cnt;
} 
void dfs(int x,int fa){
	f[x][0]=1;
	int min1=19260817,min2=19260817;
	for(int i=hd[x];i;i=e[i].next){
		int to=e[i].to;
		if(to==fa) continue;
		dfs(to,x);
		f[x][0]+=f[x][4];
		f[x][1]+=f[to][3];
		f[x][2]+=f[to][2];
		f[x][3]+=f[to][2];
		f[x][4]+=f[to][3];
		min1=min(min1,f[to][0]-f[to][3]);
		min2=min(min2,f[to][1]-f[to][2]);
	}
	f[x][1]+=min1;
	f[x][2]+=min2;
	f[x][2]=min(f[x][2],min(f[x][1],f[x][0]));
	f[x][3]=min(f[x][3],f[x][2]);
	f[x][4]=min(f[x][4],f[x][3]);
}
int main(){
	cin>>n;
	for(int i=1;i<n;i++){
		int a;
		cin>>a;
		addedge(a,i);
		addedge(i,a);
	}
	dfs(1,0);
	cout<<f[1][2]<<endl;
	return 0;
}

2020/6/26 12:10
加载中...