AC题解

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define ok debug("OK\n")
inline ll read(){
	ll x(0),f(1);char c=getchar();
	while(!isdigit(c)){if(c=='-') f=-1;c=getchar();}
	while(isdigit(c)){x=(x<<1)+(x<<3)+c-'0';c=getchar();}
	return x*f;
}
const int N=1e5+100;
const int M=2e4+100;
const int inf=1e9;

int n,tot;

int pl[N][20],dep[N];
int fa[N],u[N],v[N],d[N];
int find(int x){
	return fa[x]==x?x:fa[x]=find(fa[x]);
}
char c;
int x;
inline int Lca(int x,int y){
	if(dep[x]<dep[y]) swap(x,y);
	for(int k=17;k>=0;k--){
		if(dep[pl[x][k]]>=dep[y]) x=pl[x][k];
	}
	if(x==y) return x;
	for(int k=17;k>=0;k--){
		if(pl[x][k]==pl[y][k]) continue;
		x=pl[x][k];y=pl[y][k];
	}
	return pl[x][0];
}
inline int dis(int x,int y){
	int lca=Lca(x,y);
	return dep[x]+dep[y]-2*dep[lca];
}
signed main(){
	#ifndef ONLINE_JUDGE
	//freopen("a.in","r",stdin);
	//freopen("a.out","w",stdout);
	#endif
	n=read();
	while(n--){
		scanf(" %c%d",&c,&x);
		if(c=='B'){
			int now=++tot;
			if(x==-1) x=0;
			pl[now][0]=x;
			for(int k=1;pl[now][k-1];++k) pl[now][k]=pl[pl[now][k-1]][k-1];
			dep[now]=dep[x]+1;
			if(x){
				int o=find(x),tmp(0);
				fa[now]=o;
				if((tmp=dis(now,u[o]))>d[o]){
					v[o]=now;d[o]=tmp;
				}
				if((tmp=dis(now,v[o]))>d[o]){
					u[o]=now;d[o]=tmp;
				}
			}
			else{
				fa[now]=now;u[now]=v[now]=now;d[now]=0;
			}
		}
		else{
			int o=find(x);
			printf("%d\n",max(dis(u[o],x),dis(v[o],x)));
		}
	}
	return 0;
}