思路应该知道吧QAQ

WA了。。。有没有dalao能康康啊/kel

不卡路径压缩差评，我是直接在Splay树中寻找根节点，居然不卡。。。

#include<cstdio>
const int M=1e5+5;
int n,m,tot,f[M],val[M],siz[M],chi[M][2];
inline bool son(int u){
    return chi[f[u]][1]==u;
}
inline void connect(int u,int v,bool son){
    chi[f[u]=v][son]=u;
}
inline void update(int u){
    siz[u]=siz[chi[u][0]]+siz[chi[u][1]]+1;
}
inline void rotate(int x){
    int y=f[x],z=f[y],f1=son(x),f2=son(y);
    connect(chi[x][!f1],y,f1);
    connect(x,z,f2);
    connect(y,x,!f1);
    update(y);
}
inline void Splay(int u){
    for(int v;v=f[u];rotate(u))if(f[v]){
        rotate(son(u)^son(v)?u:v);
    }
    update(u);
}
inline void Insert(int u,int v){
    chi[v][0]=chi[v][1]=0;siz[v]=1;f[v]=u;
    while(u)u=chi[f[v]=u][val[v]>val[u]];
    Splay(chi[f[v]][val[v]>val[f[v]]]=v);
}
inline int Find(int u,int k){
    while(u){
        int&siz=val[chi[u][0]];
        if(k==siz+1)return u;
        if(k<=siz)u=chi[u][0];
        else u=chi[u][1],k-=siz+1;
    }
    return -1;
}
void merge(int u,int v){
    if(!u)return;
    merge(chi[u][0],v);
    merge(chi[u][1],v);
    Insert(v,u);
}
int Find(int u){
    return f[u]?Find(f[u]):u;
}
inline void Merge(int u,int v){
    if((u=Find(u))==(v=Find(v)))return;
    if(siz[u]>siz[v])u^=v^=u^=v;
    merge(u,v);
}
signed main(){
    int i,x,y;char s;
    scanf("%d%d",&n,&m);
    for(i=1;i<=n;++i){
        siz[i]=1;
        scanf("%d",val+i);
    }
    for(i=1;i<=m;++i)scanf("%d%d",&x,&y),Merge(x,y);
    scanf("%d",&m);
    for(i=1;i<=m;++i){
        getchar();
        scanf("%c%d%d",&s,&x,&y);
        if(s=='Q'){
            printf("%d\n",Find(Find(x),y));
        }
        if(s=='B'){
            Merge(x,y);
        }
    }
}