对着题目yy了一天加上看了一中午题解，终于搞明白了我太弱了

连边就是合并线段树，把小的集合合并到大的上，可以保证规模至少增加一半，复杂度可以是\(O(logn)\)

合并的时候暴力dfs修改倍增数组和维护主席树即可

然后树上主席树就是维护节点到根节点的信息即可，

询问链上的第k大时，画图后可以发现维护一个rootx,rooty,rootlca和rootfalca即可解决问题

注意空间要开够

然后注意细节，没了

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

int vis[100000],root[100000],fa[100000],jump[100000][19],sonnum[100000],u[100000<<2],v[100000<<2],fir[100000],nxt[100000<<2],cnt,dep[100000],midax[100000],w_p[100000],n,m,T,Nodecnt,testcase;

const int MAXlog = 18;

int lastans=0,nx;

struct PTNode{

    int sz,lson,rson;

}PT[100000 * 100];

void addedge(int ui,int vi){

    ++cnt;

    u[cnt]=ui;

    v[cnt]=vi;

    nxt[cnt]=fir[ui];

    fir[ui]=cnt;

}

int findroot(int x){

    return (fa[x]==x)?x:fa[x]=findroot(fa[x]);

}

int query(int L,int R,int xroot,int yroot,int lcaroot,int falcaroot,int kth){

    if(L==R)

        return L;

    int mid=(L+R)>>1,lch=PT[PT[xroot].lson].sz+PT[PT[yroot].lson].sz-PT[PT[lcaroot].lson].sz-PT[PT[falcaroot].lson].sz;

    if(lch<kth)

        return query(mid+1,R,PT[xroot].rson,PT[yroot].rson,PT[lcaroot].rson,PT[falcaroot].rson,kth-lch);

    else

        return query(L,mid,PT[xroot].lson,PT[yroot].lson,PT[lcaroot].lson,PT[falcaroot].lson,kth);

}

void insert(int L,int R,int &now,int c){

    PT[++Nodecnt]=PT[now];

    now=Nodecnt;

    PT[now].sz++;

    if(L==R)

        return;

    int mid=(L+R)>>1;

    if(c<=mid)

        insert(L,mid,PT[now].lson,c);

    else

        insert(mid+1,R,PT[now].rson,c);

}

void dfs(int u,int father,int d,int rootu){

    dep[u]=d;

    vis[u]=1;

    fa[u]=father;

    jump[u][0]=father;

    sonnum[rootu]++;

    for(int i=1;i<=MAXlog;i++)

        jump[u][i]=jump[jump[u][i-1]][i-1];

    int pos = lower_bound(midax+1,midax+nx+1,w_p[u])-midax;

    root[u]=root[father];

    insert(1,nx,root[u],pos);

    for(int i=fir[u];i;i=nxt[i]){

        if(v[i]==father)

            continue;

        dfs(v[i],u,d+1,rootu);

    }

}

int lca(int x,int y){

    if(dep[x]<dep[y])

        swap(x,y);

    for(int i=MAXlog;i>=0;i--)

        if(dep[x]-(1<<i)>=dep[y])

            x=jump[x][i];

    if(x==y)

        return x;

    for(int i=MAXlog;i>=0;i--)

        if(jump[x][i]!=jump[y][i])

            x=jump[x][i],y=jump[y][i];

    return jump[x][0];

}

void link(int x,int y){

    addedge(x,y);

    addedge(y,x);

    int rootx=findroot(x);

    int rooty=findroot(y);

    if(sonnum[rootx]<sonnum[rooty])

        swap(x,y),swap(rootx,rooty);

    dfs(y,x,dep[x]+1,rootx);

    x+=sonnum[y];

}

int main(){

    scanf("%d",&testcase);

    scanf("%d %d %d",&n,&m,&T);

    for(int i=1;i<=n;i++)

        scanf("%d",&w_p[i]),midax[i]=w_p[i],fa[i]=i;

    nx=unique(midax+1,midax+n+1)-midax-1;

    sort(midax+1,midax+nx+1);

    for(int i=1;i<=m;i++){

        int a,b;

        scanf("%d %d",&a,&b);

        addedge(a,b);

        addedge(b,a);

    }

    for(int i=1;i<=n;i++)

        if(!vis[i]){

            dfs(i,0,0,i);

            fa[i]=i;

        }

    for(int i=1;i<=T;i++){

        char opt=getchar();

        while(opt!='Q'&&opt!='L')

            opt=getchar();

        if(opt=='Q'){

            int x,y,k;

            scanf("%d %d %d",&x,&y,&k);

            x^=lastans;

            y^=lastans;

            k^=lastans;

            // printf("lca(%d,%d) = %d\n",x,y,lca(x,y));

            lastans=midax[query(1,nx,root[x],root[y],root[lca(x,y)],root[jump[lca(x,y)][0]],k)];

            printf("%d\n",lastans);

        }

        else{

            int x,y;

            scanf("%d %d",&x,&y);

            x^=lastans;

            y^=lastans;

            link(x,y);

        }

    }

    return 0;

}