题解:#include<cstdio>
#include<cstdlib>
#include<algorithm>
using namespace std;
const int N = 1E6+10;
int n,m,ans,fa[N];
int scan(){
char cc=' ';int re=0,fh=1;while(cc==' '||cc=='\r'||cc=='\n')cc=getchar();
if(cc=='+')cc=getchar(),fh=1;if(cc=='-')cc=getchar(),fh=-1;
while('0'<=cc&&cc<='9'){re=re*10+cc-'0';cc=getchar();}return re*fh;
}
struct Point{
Point(){next=NULL;}
int d;Point *next;
void push(int a){
Point *l = new Point;
l->d = a;l->next = next;
next= l;
}
}point[N];
int f[N][5];
void dfs(int x=1){
bool son=0;
int sum[2]={};
f[x][1]=f[x][2]=1e9;
for(Point *i = point[x].next;i;i=i->next)
if(i->d!=fa[x]){
son=1;
fa[i->d]=x;
dfs(i->d);
f[x][0]+=f[i->d][4];
f[x][3]+=f[i->d][2];
f[x][4]+=f[i->d][3];
}
for(Point *i = point[x].next;i;i=i->next)
if(i->d!=fa[x]){
f[x][1]=min(f[x][1],f[x][4]-f[i->d][3]+f[i->d][0]);
f[x][2]=min(f[x][2],f[x][3]-f[i->d][2]+f[i->d][1]);
}
f[x][0]+=1;
for(int i=1;i<=4;i++)f[x][i]=min(f[x][i],f[x][i-1]);
}
int main(){
//freopen("in.txt","r",stdin);
int i,j,a;
n = scan();
for(i=2;i<=n;i++){
a=scan();
point[i].push(a);
point[a].push(i);
}
dfs();
printf("%d\n",f[1][2]);
return 0;
}
评论