对着题目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
",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
",lastans);
}
else{
int x,y;
scanf("%d %d",&x,&y);
x^=lastans;
y^=lastans;
link(x,y);
}
}
return 0;
}