记录编号	489788	评测结果	AAAAAAAAAA
题目名称	[USACO Feb18] 新牛棚	最终得分	100
用户昵称	Satoshi	是否通过	通过
代码语言	C++	运行时间	2.504 s
提交时间	2018-03-05 12:33:33	内存使用	8.57 MiB

#include <fstream>
#include <algorithm>
#include <vector>
#include <queue>
#include <cmath>
#define N 100010
#define M 20
using namespace std;
ifstream cin("newbarns.in");
ofstream cout("newbarns.out");
vector<int> G[N];
bool vis[N];
int p[N][M]={0};
int n=0,m;
int deep[N]={0},root[N]={0};
int X[N],Y[N];

vector<int> Hash;
int U[N]={0},V[N]={0},MAXDIS[N]={0},cnt[N]={0};

void add(int u,int v)
{
	G[u].push_back(v);
	G[v].push_back(u);
	//cout<<u<<' '<<v<<endl;
}
int LCA(int u,int v)
{
	int i,d;
	if(deep[u]<deep[v])swap(u,v);
	d=deep[u]-deep[v];
	for(i=0;i<M;i++)if((1<<i)&d)u=p[u][i];
	if(u==v)return u;
	for(i=M-1;i>=0;i--)
	{
		if(p[u][i]!=p[v][i])
		{
			u=p[u][i];
			v=p[v][i];
		}
	}
	u=p[u][0];
	return u;
}
void LCB(int u)
{
	int i,v,c;
	vis[u]=1;
	for(i=1;i<M;i++)
	{
		p[u][i]=p[p[u][i-1]][i-1];
		if(!p[u][i])break;
	}
	for(i=0;i<G[u].size();i++)
	{
		v=G[u][i];
		if(!vis[v])LCB(v);
	}
}
void DFS(int u,int s)
{
	int i,v,c;
	vis[u]=1;
	root[u]=s;
	for(i=0;i<G[u].size();i++)
	{
		v=G[u][i];
		if(!vis[v])
		{
			p[v][0]=u;
			deep[v]=deep[u]+1;
			DFS(v,s);
		}
	}
}
int dis(int u,int v)
{
	int w,ans=0;
	w=LCA(u,v);
	ans=deep[u]+deep[v]-2*deep[w];
	return ans;
}
void read()
{
	int i;
	char a;int b;
	cin>>m;
	for(i=1;i<=m;i++)
	{
		cin>>a>>b;
		if(a=='B')
		{
			X[i]=0;
			Y[i]=b;
			n++;
			cnt[i]=n;
			if(b==-1)Hash.push_back(i);
			else add(b,n);
		}
		if(a=='Q')
		{
			X[i]=1;
			Y[i]=b;
		}
	}
}
void init()
{
	int i;
	/*for(i=0;i<Hash.size();i++)cout<<Hash[i]<<' ';
	cout<<endl;*/

	for(i=1;i<=n;i++)vis[i]=0;for(i=0;i<Hash.size();i++)DFS(Hash[i],Hash[i]);
	for(i=1;i<=n;i++)vis[i]=0;for(i=0;i<Hash.size();i++)LCB(Hash[i]);
		//cout<<LCA(3,4)<<endl;
}
void work()
{
	int i,u,v,dist;
	//cout<<m<<endl;
	for(i=1;i<=m;i++)
	{
		if(X[i]==0)
		{
			v=cnt[i];
			u=root[v];
			//cout<<u<<' '<<v<<endl;
			if(Y[i]==-1)U[v]=V[v]=v;
			else
			{
				dist=dis(U[u],v);
				//cout<<dist<<endl;
				if(dist>MAXDIS[u])
				{
					MAXDIS[u]=dist;
					V[u]=v;
				}
				dist=dis(V[u],v);
				if(dist>MAXDIS[u])
				{
					MAXDIS[u]=dist;
					U[u]=v;
				}
			}
			//cout<<i<<' '<<u<<' '<<U[u]<<' '<<V[u]<<endl;
		}
		if(X[i]==1)
		{
			v=Y[i];
			u=root[v];
			cout<<max(dis(U[u],v),dis(V[u],v))<<endl;
		}
	}
}
int main()
{
	//cout<<"10086"<<endl;
	read();
	init();
	//cout<<"10086"<<endl;
	work();
	return 0;
}