842E - Nikita and game - CodeForces Solution

#include<bits/stdc++.h>
using namespace std;
const int N=3e5+5;
vector<int> s1,s2;
int n,deep[N];
int fa[N][30];
void add(int u,int fath){
	deep[u]=deep[fath]+1,fa[u][0]=fath;
    for(int i=0;fa[u][i];++i){
        fa[u][i+1]=fa[fa[u][i]][i];    
    }
}
int LCA(int u,int v){
	if(deep[u]>deep[v]) swap(u,v);
    for(int i=20;i>=0;--i){
        if(deep[u]<=deep[v]-(1<<i)){
            v=fa[v][i];    
        }    
    }
    if(u==v) return u;
    for(int i=20;i>=0;--i){
        if(fa[u][i]!=fa[v][i]){
            u=fa[u][i],v=fa[v][i];
        }
    } 
    return fa[u][0];
}
int dist(int u,int v){
	return deep[u]+deep[v]-deep[LCA(u,v)]*2+1;
}
int d;
int main(){
	scanf("%d",&n);
	add(1,0);
	s1.push_back(1);
	for(int i=2;i<=n+1;i++){
		int x;
		scanf("%d",&x);
		add(i,x);
		int d1=s1.empty()?0:dist(i,s1.front()),d2=s2.empty()?0:dist(i,s2.front());
		if(max(d1,d2)>d){
			if(d1>d2){
				d=d1;
				for(int j=0;j<(int)s2.size();j++){
					if(dist(s2[j],i)==d)s1.push_back(s2[j]);
				}
				s2.clear();
				s2.push_back(i);
			}
			else{
				d=d2;
				for(int j=0;j<(int)s1.size();j++){
					if(dist(s1[j],i)==d)s2.push_back(s1[j]);
				}
				s1.clear();
				s1.push_back(i);
			}
		}
		else if(max(d1,d2)==d){
			if(d1>d2)s2.push_back(i);
			else s1.push_back(i);
		}
		cout<<s1.size()+s2.size()<<endl;
	}
	
	return 0;
}