题意：
强制在线
1.查询树上两点间权值第k小
2.连接两棵树
题解：
首先这题数据不得不吐槽
数据数字大小都是超过1e7的？？？
洛谷上又不能下载数据又只能显然re的 对拍了半天也没搞出来错（加上生成器还很难写）
查找第k大显然可以用主席树
而连接两棵树又是lct
考虑一下怎么搞，lct显然是不能用splay来维护区间k大的 只能放弃了
考虑用主席树维护每个点到根的路径
建树很简单
那么怎么合并呢
是可以用启发式合并暴力重构的（总共nlogn次插入，插入复杂度logn，总时间nlog2n）
那么考虑查询，平时在普通的主席树上查询是f(y)-f(x-1)
那么在树上就变成了f(x)+f(y)-2f(lca(x,y))再加上一下lca（x,y）
当然为了防止特判可以变成f(x)+f(y)-f(lca(x,y))-f(fa(lca(x,y))
求lca只需要在合并时暴力维护倍增数组就可以了（nlog2n）
所以总的时间复杂度是（nlog2n）
代码：
#include <bits/stdc++.h> using namespace std; #define maxn 100000 #define INF 1000000000 struct re{ int a,b; }a[maxn*2]; struct ree{ int h,t,x; }p[20000000]; int bz[maxn][18],dep[maxn],root[maxn],v[maxn]; int l,now,head[maxn],count2[maxn],faa[maxn],n,m,t; bool f[maxn]; void arr(int x,int y) { a[++l].a=head[x]; a[l].b=y; head[x]=l; } #define mid (h+t)/2 void insert(int &x,int y,int v,int h,int t) { x=++now; p[x]=p[y]; p[x].x++; if (h==t) return; if (mid>=v) insert(p[x].h,p[y].h,v,h,mid); else insert(p[x].t,p[y].t,v,mid+1,t); } void dfs(int x,int fa,int zx) { insert(root[x],root[fa],v[x],1,INF); dep[x]=dep[fa]+1; f[x]=0; bz[x][0]=fa; count2[x]=1; faa[x]=zx; int u=head[x]; while (u) { int v=a[u].b; if (v!=fa) { dfs(v,x,zx); count2[x]+=count2[v]; } u=a[u].a; } } void dfs2(int x,int fa,int zx) { insert(root[x],root[fa],v[x],1,INF); faa[x]=zx; dep[x]=dep[fa]+1; bz[x][0]=fa; for (int i=1;i<=17;i++) bz[x][i]=bz[bz[x][i-1]][i-1]; int u=head[x]; while (u) { int v=a[u].b; if (v!=fa) { dfs2(v,x,zx); } u=a[u].a; } } void merge(int x,int y) { if (count2[faa[x]]<count2[faa[y]]) swap(x,y); count2[faa[x]]+=count2[faa[y]]; dfs2(y,x,faa[x]); } int get_lca(int x,int y) { if (dep[x]<dep[y]) swap(x,y); for (int i=17;i>=0;i--) if (dep[x]-(1<<i)>=dep[y]) x=bz[x][i]; if (x==y) return(x); for (int i=17;i>=0;i--) if (bz[x][i]!=bz[y][i]) { x=bz[x][i]; y=bz[y][i]; } return(bz[x][0]); } int js(int x) { return(p[p[x].h].x); } int query(int c,int d,int x,int y,int k,int h,int t) { if (h==t) return(h); int tmp=js(x)+js(y)-js(c)-js(d); if (tmp<k) return (query(p[c].t,p[d].t,p[x].t,p[y].t,k-tmp,mid+1,t)); else return (query(p[c].h,p[d].h,p[x].h,p[y].h,k,h,mid)); } int main() { freopen("noip.in","r",stdin); freopen("noip.out","w",stdout); int tmp; cin>>tmp; cin>>n>>m>>t; int c,d,e; for (int i=1;i<=n;i++) cin>>v[i]; for (int i=1;i<=m;i++) { cin>>c>>d; arr(c,d); arr(d,c); } memset(f,1,sizeof(f)); for (int i=1;i<=n;i++) if (f[i]) dfs(i,0,i); for (int i=1;i<=17;i++) for (int j=1;j<=n;j++) bz[j][i]=bz[bz[j][i-1]][i-1]; int ans=0; char cc; for (int i=1;i<=t;i++) { cin>>cc; if (cc=='Q') { cin>>c>>d>>e; c=c^ans; d=d^ans; e=e^ans; int x=get_lca(c,d),y=bz[x][0]; ans=query(root[x],root[y],root[c],root[d],e,1,INF); cout<<ans<<endl; } else { cin>>c>>d; c=c^ans; d=d^ans; merge(c,d); arr(c,d); arr(d,c); } // ans=0; } return 0; }