Description
FarmerJohn注意到他的奶牛们如果被关得太紧就容易吵架，所以他想开放一些新的牛棚来分散她们。每当FJ建造一
个新牛棚的时候，他会将这个牛棚用至多一条双向道路与一个现有的牛棚连接起来。为了确保他的奶牛们足够分散
，他有时想要确定从某个特定的牛棚出发，到它能够到达的最远的牛棚的距离（两个牛棚之间的距离等于从一个牛
棚出发到另一个之间必须经过的道路条数）。FJ总共会给出Q（1≤Q≤10^5）次请求，每个请求都是“建造”和“
距离”之一。对于一个建造请求，FJ建造一个牛棚，并将其与至多一个现有的牛棚连接起来。对于一个距离请求，
FJ向你询问从某个特定的牛棚通过一些道路到离它最远的牛棚的距离。保证询问的牛棚已经被建造。请帮助FJ响应 所有的请求。
Input
第一行包含一个整数Q 以下Q行，每行包含一个请求。每个请求的格式都是“B p”或是“Q k”
分别告诉你建造一个牛棚并与牛棚p连接，或是根据定义求从牛棚k出发最远的距离。 如果p=-1，则新的牛棚不会与其他牛棚连接。
否则，p是一个已经建造的牛棚的编号。 牛棚编号从1开始，所以第一个被建造的谷仓是1号谷仓，第二个是2号谷仓，以此类推。
Output
对于每个距离请求输出一行。注意一个没有连接到其他牛棚的牛棚的最远距离为0
Sample Input
7
B -1
Q 1
B 1
B 2
Q 3
B 2
Q 2
Sample Output
0
2
1
HINT
输入样例对应下面的牛棚网：
(1)
\ (2)---(4)/(3)
对于请求1，我们建造牛棚1。对于请求2，我们询问从1出发到最远连接的牛棚的距离。由于牛棚1没有与其他牛棚
连接，所以回答是0。对于请求3，我们建造牛棚2并将其与牛棚1连接。对于请求4，我们建造牛棚3并将其与牛棚2
连接。对于请求5，我们询问从3出发到最远连接的牛棚的距离。在这时，最远的是牛棚1，距离为2单位。对于请求
6，我们建造牛棚4并将其与牛棚2连接。对于请求7，我们询问从2出发到最远连接的牛棚的距离。所有其他三个牛
棚1，3，4都与2相距相同的距离1，所以这就是我们的回答。
题解
考场上只写了个LCT，然后发现LCT只能处理二叉情况以为不能用LCT了
动态点分治？兄弟我不会
LCT是可做的！
可以知道，每次询问的答案一定在一棵树的直径两个上
给一个简单的证明
设直径两个端点为u,v，当前询问节点now，假设找到了一个不在树的直径上的点且与now距离最大的点P
由于树上路径唯一，对于v，P和v有一个公共祖先lca。可以知道，now到lca的距离是一定的，那么根据上面的假设，可以知道lca到P的距离比lca到v的距离长，那么对于u，可以发现这种情况下，u到v的距离也是比u到P的距离短的，那么直径的v端点应该为P而不是v。反之亦然，得证
用LCT维护每一棵树的直径长度，并查集维护直径左端点右端点，插入的时候维护直径即可
对于维护时直径端点的证明类似如上
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
using namespace std;
int fa[110000],belong[110000];
int findfa(int x)
{if(fa[x]!=x)fa[x]=findfa(fa[x]);return fa[x];
}
int l[110000],r[110000];//第i个连通块中树的直径左端点/右端点
struct node
{int f,son[2],c;bool fz;node(){fz=false;}
}tr[110000];int trlen;
void upd(int now){
tr[now].c=tr[tr[now].son[0]].c+tr[tr[now].son[1]].c+1;}
void reverse(int now)
{swap(tr[now].son[0],tr[now].son[1]);int lc=tr[now].son[0],rc=tr[now].son[1];tr[lc].fz^=1;tr[rc].fz^=1;tr[now].fz=false;
}
void rotate(int x,int w)
{int f=tr[x].f,ff=tr[f].f;int R,r;R=f;r=tr[x].son[w];tr[R].son[1-w]=r;if(r!=0)tr[r].f=R;R=ff;r=x;if(tr[R].son[0]==f)tr[R].son[0]=x;else if(tr[R].son[1]==f)tr[R].son[1]=x;tr[r].f=R;R=x;r=f;tr[R].son[w]=r;tr[r].f=R;upd(f);upd(x);
}
int tmp[110000];
void splay(int x,int rt)
{int i=x,s=0;while(tr[i].f!=rt && (tr[tr[i].f].son[0]==i || tr[tr[i].f].son[1]==i)){tmp[++s]=i;i=tr[i].f;}tmp[++s]=i;while(s){int i=tmp[s--];if(tr[i].fz)reverse(i);}while(tr[x].f!=rt && (tr[tr[x].f].son[0]==x || tr[tr[x].f].son[1]==x)){int f=tr[x].f,ff=tr[f].f;if(ff==rt || (tr[ff].son[0]!=f && tr[ff].son[1]!=f)){if(tr[f].son[0]==x)rotate(x,1);else rotate(x,0);}else{if(tr[ff].son[0]==f && tr[f].son[0]==x)rotate(f,1),rotate(x,1);else if(tr[ff].son[1]==f && tr[f].son[0]==x)rotate(x,1),rotate(x,0);else if(tr[ff].son[1]==f && tr[f].son[1]==x)rotate(f,0),rotate(x,0);else rotate(x,0),rotate(x,1); }}
}
void access(int x)
{int y=0;while(x!=0){splay(x,0);tr[x].son[1]=y;if(y!=0)tr[y].f=x;y=x;x=tr[x].f;}
}
void mark_root(int x){access(x);splay(x,0);tr[x].fz^=1;}
void link(int x,int y){mark_root(x);tr[x].f=y;access(x);}
int findsum(int x,int y){mark_root(x);access(y);splay(y,0);return tr[y].c-1;}
char ch[10];
int main()
{
// freopen("c.in","r",stdin);
// freopen("c.out","w",stdout);int T;scanf("%d",&T);while(T--){int u;scanf("%s%d",ch+1,&u);if(ch[1]=='Q')printf("%d\n",max(findsum(u,l[belong[u]]),findsum(u,r[belong[u]])));else{if(u==-1){trlen++;tr[trlen].c=1;fa[trlen]=trlen;belong[trlen]=trlen;l[trlen]=r[trlen]=trlen;}else{int P=belong[u],now=++trlen;tr[now].c=1;link(now,u);belong[now]=belong[u];fa[now]=findfa(u);int d0=findsum(l[P],now),d1=findsum(r[P],now),d2=findsum(l[P],r[P]);if(d0>=d2 && d0>=d1)r[P]=now;else if(d1>=d2 && d1>=d0)l[P]=now;}}}return 0;
}