因为是二分图，所以最大独立集$=$总点数$-$最大匹配。
因为是树，所以具有贪心性质，设$f_i$表示$i$是否与其孩子匹配，$a_i$表示$i$的孩子里$f$为$0$的个数，则$f_i=[a_i>0]$。
加入一个新的叶子的时候，影响的$a$是连续的一段，这一段上与它距离为奇数的点的$a$都要是$0$，距离为偶数的点都要是$1$。
树链剖分+线段树维护即可。
时间复杂度$O(nlog^2n)$。
#include<cstdio>
const int N=100010,M=262150;
int n,i,y,f[N],g[N],nxt[N],d[N],size[N],son[N],loc[N],top[N],q[N],dfn;
int len[M],v[M],mx[M][2],tag[M][2],rev[M];
inline void read(int&a){char c;while(!(((c=getchar())>='0')&&(c<='9')));a=c-'0';while(((c=getchar())>='0')&&(c<='9'))(a*=10)+=c-'0';}
void dfs(int x){
size[x]=1;
for(int i=g[x];i;i=nxt[i]){
d[i]=d[x]+1;
dfs(i),size[x]+=size[i];
if(size[i]>size[son[x]])son[x]=i;
}
}
void dfs2(int x,int y){
q[loc[x]=++dfn]=x;top[x]=y;
if(son[x])dfs2(son[x],y);
for(int i=g[x];i;i=nxt[i])if(i!=son[x])dfs2(i,i);
}
inline int max(int a,int b){return a>b?a:b;}
inline void tag1(int o,int x,int p){mx[x][o]+=p;tag[x][o]+=p;}
inline void rev1(int x){v[x]=len[x]-v[x];rev[x]^=1;}
inline void pb(int x){
for(int o=0;o<2;o++)if(tag[x][o])tag1(o,x<<1,tag[x][o]),tag1(o,x<<1|1,tag[x][o]),tag[x][o]=0;
if(rev[x])rev1(x<<1),rev1(x<<1|1),rev[x]=0;
}
inline void up(int x){
v[x]=v[x<<1]+v[x<<1|1];
for(int o=0;o<2;o++)mx[x][o]=max(mx[x<<1][o],mx[x<<1|1][o]);
}
void build(int x,int a,int b){
len[x]=b-a+1;v[x]=rev[x]=0;
for(int o=0;o<2;o++)mx[x][o]=tag[x][o]=0;
if(a==b)return;
int mid=(a+b)>>1;
build(x<<1,a,mid),build(x<<1|1,mid+1,b);
}
void ask(int x,int a,int b,int c,int d,int o){
if(c<=a&&b<=d){
if(mx[x][o]<=1&&mx[x][o^1]<=0){y=a;return;}
if(a==b){if(!y)y=N;return;}
}
pb(x);
int mid=(a+b)>>1;
if(d>mid){
ask(x<<1|1,mid+1,b,c,d,o);
if(y>mid+1)return;
}
if(c<=mid)ask(x<<1,a,mid,c,d,o);
}
void change(int x,int a,int b,int c,int d,int o){
if(c<=a&&b<=d){tag1(o,x,-1);tag1(o^1,x,1);return;}
pb(x);
int mid=(a+b)>>1;
if(c<=mid)change(x<<1,a,mid,c,d,o);
if(d>mid)change(x<<1|1,mid+1,b,c,d,o);
up(x);
}
void reverse(int x,int a,int b,int c,int d){
if(c<=a&&b<=d){rev1(x);return;}
pb(x);
int mid=(a+b)>>1;
if(c<=mid)reverse(x<<1,a,mid,c,d);
if(d>mid)reverse(x<<1|1,mid+1,b,c,d);
up(x);
}
inline void modify(int x,int o){
for(;x;x=f[top[x]]){
y=0;
ask(1,1,n,loc[top[x]],loc[x],o);
if(y<N)y=q[y];
if(y==N){
change(1,1,n,loc[x],loc[x],o);
return;
}
change(1,1,n,loc[y],loc[x],o);
reverse(1,1,n,loc[y],loc[x]);
if(y!=top[x]){
y=f[y];
change(1,1,n,loc[y],loc[y],o);
return;
}
}
}
int main(){
while(~scanf("%d",&n)){
for(dfn=0,i=1;i<=n;i++)g[i]=son[i]=0;
for(i=2;i<=n;i++){
read(f[i]),f[i]++;
nxt[i]=g[f[i]],g[f[i]]=i;
}
dfs(1),dfs2(1,1),build(1,1,n);
for(i=2;i<=n;i++)modify(f[i],d[i]&1),printf("%d
",i-v[1]);
}
return 0;
}