代码

#include<cmath> 
#include<vector>
#include<iostream>
using namespace std;

const int MAXN=3e5+5;
int n,d,dep[MAXN],fa[MAXN][20];
vector<int> v1,v2;

void init(int u,int v){
    fa[v][0]=u;
    for(int i=1;i<20;i++){
		fa[v][i]=fa[fa[v][i-1]][i-1];
	}
	return;
}

int LCA(int x,int y){
	if(dep[y]>dep[x]) swap(x,y);
	for(int i=19;i>=0;i--){
		if(dep[x]-dep[y]>=pow(2,i)){
			x=fa[x][i];
		}
	}
	if(x==y) return x;
	for(int i=19;i>=0;i--){
		if(fa[x][i]!=fa[y][i]){
			x=fa[x][i];
			y=fa[y][i];
		}
	}	
	return fa[x][0];
}

int dis(int x,int y){
	int lca=LCA(x,y);
	return dep[x]+dep[y]-dep[lca]*2;
}

int main(){
	cin>>n;
	v1.push_back(1);	
	for(int v=2;v<=n+1;v++){
		int u;
		cin>>u;
		dep[v]=dep[u]+1;
		init(u,v);
		int d1,d2;
		if(!v1.empty()) d1=dis(v,v1[0]);
		if(!v2.empty()) d2=dis(v,v2[0]);
		if(max(d1,d2)>d){
			d=max(d1,d2);
			if(d1==d){
				for(int i=0;i<v2.size();i++){
					if(dis(v,v2[i])==d) v1.push_back(v2[i]);
				}
				v2.clear();
			}else{
				for(int i=0;i<v1.size();i++){
					if(dis(v,v1[i])==d) v2.push_back(v1[i]);
				}
				v1.clear();
			}
		}
		if(max(d1,d2)==d){
			if(d1==d) v2.push_back(v);
			else v1.push_back(v);
		}
		cout<<v1.size()+v2.size()<<'\n';
	}
	return 0;
}

样例输入

4
1
1
2
1

CF输出

洛谷在线IDE输出