C++11(clang++ 3.9) 解法, 执行用时: 280ms, 内存消耗: 15340K, 提交时间: 2020-03-25 22:26:46

#include<iostream>
#include<cmath>
using namespace std;
int n,idx;
int l[100001],r[100001],fa[100001][37],dep[100001],g[100001],lg[100001];
int LCA(int x,int y)
{
	if(dep[x]<dep[y]) swap(x,y);
	while(dep[x]>dep[y])
	{
		x=fa[x][lg[dep[x]-dep[y]]-1];
	 } 
	 if(x==y) return x;
	 for(int i=lg[dep[x]]-1;i>=0;i--)
	 {
	 	if(fa[x][i]!=fa[y][i]) x=fa[x][i],y=fa[y][i];
	 }
	 return fa[x][0];
}
int range(int x,int y)
{
	return dep[x]+dep[y]-2*dep[LCA(x,y)];
}
void link(int x)
{
	++idx;
	if(x==-1)
	{
		g[idx]=idx;
		fa[idx][0]=idx;
		l[idx]=r[idx]=idx;
		return;
	}
	fa[idx][0]=x;
	dep[idx]=dep[x]+1;
	g[idx]=g[x];
	for(int i=1;(1<<i)<=dep[idx];i++)
	{
		fa[idx][i]=fa[fa[idx][i-1]][i-1];
	}
	int dis1=range(l[g[idx]],r[g[idx]]),dis2=range(idx,l[g[idx]]),dis3=range(idx,r[g[idx]]);
	if(dis2>dis1&&dis2>=dis3) r[g[idx]]=idx;
	if(dis3>dis1&&dis3>dis2) l[g[idx]]=idx;
}
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		lg[i]=lg[i-1]+((1<<lg[i-1])==i);
	}
	for(int i=1;i<=n;i++)
	{
		char opt;
		int x;
		cin>>opt>>x;
		if(opt=='B')
		{
			link(x);
		}
		else
		{
			cout<<max(range(l[g[x]],x),range(x,r[g[x]]))<<endl;
		}
	}
	return 0;
}

C++14(g++5.4) 解法, 执行用时: 103ms, 内存消耗: 8676K, 提交时间: 2020-05-05 17:42:33

#pragma GCC optimize("-Ofast","-funroll-all-loops")
#include<bits/stdc++.h>
//#define int long long
using namespace std;
const int N=1e5+10;
int q,rt[N],f[N][20],dep[N],p1[N],p2[N],cnt;
inline int lca(int x,int y){
	if(dep[x]<dep[y])	swap(x,y);
	for(int i=17;i>=0;i--)	if(dep[f[x][i]]>=dep[y])	x=f[x][i];
	if(x==y)	return x;
	for(int i=17;i>=0;i--)	if(f[x][i]!=f[y][i])	x=f[x][i],y=f[y][i];
	return f[x][0];
}
inline int dis(int x,int y){return dep[x]+dep[y]-2*dep[lca(x,y)];}
signed main(){
	cin>>q;	char op[5];
	for(int i=1,x;i<=q;i++){
		scanf("%s %d",op,&x);
		if(op[0]=='B'){
			++cnt;
			if(x==-1)	dep[cnt]=1,rt[cnt]=cnt,p1[cnt]=p2[cnt]=cnt;
			else{
				dep[cnt]=dep[x]+1,f[cnt][0]=x,rt[cnt]=rt[x];
				for(int j=1;j<=17;j++)	f[cnt][j]=f[f[cnt][j-1]][j-1];
				int d1=dis(p1[rt[x]],p2[rt[x]]),d2=dis(cnt,p1[rt[x]]),d3=dis(cnt,p2[rt[x]]);
				if(d2>d1&&d2>=d3)	p2[rt[x]]=cnt;
				else if(d3>d1&&d3>=d2)	p1[rt[x]]=cnt;
			}
		}else	printf("%d\n",max(dis(p1[rt[x]],x),dis(p2[rt[x]],x)));
	}
	return 0;
}