树上的主席树（利用LCA）+启发式合并
有兴趣的可以去看看简化版（去掉连边操作）题目P2633 Count on a tree。获得双倍经验。
这道题主要有两个操作：
-
求路径 （u，v） 上第k小点。
-
在点 x,y 间连一条无向边。
第一个操作很明显，在树上建立主席树，主席树 i 维护从根节点 root 到点 i 路径上所有点的信息。
查询路径 （u，v） 上第k小点也容易想到，需要用到 LCA 。
我们找到 （u，v） 的最近公共祖先 lca 和 lca 的父节点 fa_lca 。维护这四个点的信息进行查询就可以了。
对于第二个操作，为了使时间更优，我们需要用到启发式合并的思想。启发式合并听上去玄妙无比，其实很普通。简而言之就是记录每棵树的大小，连边时把小树连接到大树上去，重构小树中的主席树、LCA相关数组。
其他的一些操作像离散化大家都会吧。
真正的重点—关于这道题的特性：
在无数次 RE 第2,3,6个测试点后，我终于找到了坑点：问题出在 LCA 上。
下面是错误示范：（ans[i][j] 表示 i 的 2^j 级祖先）
void update_LCA(int u,int fa){
deep[u]=deep[fa]+1;ans[u][0]=fa;
for(int i=1;i<=lg[deep[u]];i++)//这里的上界
ans[u][i]=ans[ans[u][i-1]][i-1];
for(int i=head[u];i;i=nxt[i])
if(to[i]!=fa) update_LCA(to[i],u);
return;
}只需要这里把循环的上界从 lg[deep[u]] 改为 x ，保证 2^x>=n 就可以了，比如 18,19等等。
为什么会这样，lg[deep[u]] 不是 LCA 的通用写法吗，LCA 的模板题也是写的lg[deep[u]]。
我翻讨论区，发现也有人困惑于此。然而，题解都巧妙地回避了这个问题，没有解答。
无奈，我下载了第2个测试点的数据，开始了漫长的探索之路。
终于，在数据中第16058次操作（询问操作），我发现了问题。
lg[deep[u]] 的确是 LCA 的通用写法，没有问题，这道题上行不通是这道题的 特性 ，因为这道题有一个特殊的操作：连边 。
我们来看 get_LCA 操作：
int get_LCA(int u,int v){
if(deep[u]<deep[v]) swap(u,v);
while(deep[u]>deep[v])
u=ans[u][lg[deep[u]-deep[v]]];
if(u==v) return u;
for(int i=lg[deep[u]];i>=0;i--)
if(ans[u][i]!=ans[v][i])//重点
u=ans[u][i],v=ans[v][i];
return ans[u][0];
}如果我们连边重构 update_LCA 时采用 lg[deep[u]] ，可能存在一种情况：这个点 i 原本的 ans[i][j]，j 最大已经大于了 lg[deep[u]] （即原来深度更深），但是我们更新只是更新到 lg[deep[u]] ，它上面的状态没有改变。在执行 get_LCA ，进行判断时：
if(ans[u][i]!=ans[v][i])//重点
u=ans[u][i],v=ans[v][i];本来，这一次 u,v 不能被改变， 由于状态没有全部更新，u,v 被改变了，导致lca找错，进而答案错误，下一次进行异或操作时数字变得很大，数组越界直接导致 RE 。
举个栗子大家就知道了：
假设 ans[x]={root,6},ans[y]={root,7}。
从 u,v 出发，模拟走一遍。
i=2时，u跳到了x。v跳到了y。
i=1时，x跳到了6，v跳到了7。
好了，已经出错了。
这就是这道题的特性，连边重构 update_LCA 时，上界很重要。
至于为什么其他题上界可以是 lg[deep[u]] ，大家自己想想吧，不难。
代码
#include <bits/stdc++.h>
using namespace std;
const int N=8e4+5;
int T,n,m,TT,last;
int tot,row[N],s[N],size[N];
int cnt,to[4*N],nxt[4*N],head[4*N];
int from[N],lg[N],ans[N][35],deep[N];
struct Tree{
int ls,rs,si;
}t[105*N];
int root[N],top;
int in(){
int x=0,f=1;char ch=getchar();
while(ch>'9'||ch<'0'){ if(ch=='-') f=-1; ch=getchar(); }
while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
return x*f;
}
void adds(int x,int y){
to[++cnt]=y;nxt[cnt]=head[x];head[x]=cnt;
return;
}
void pre_work(){
int a,b;lg[0]=-1;
T=in();n=in();m=in();TT=in();
for(int i=1;i<=n;i++)
row[i]=s[i]=in(),lg[i]=lg[i>>1]+1,from[i]=i;
sort(row+1,row+1+n);
tot=unique(row+1,row+1+n)-(row+1);
for(int i=1;i<=n;i++)
s[i]=lower_bound(row+1,row+1+tot,s[i])-row;
for(int i=1;i<=m;i++)
a=in(),b=in(),adds(a,b),adds(b,a);
return;
}
void built(int &pos,int pre,int l,int r,int wi){
t[pos=++top]=t[pre];
t[pos].si++;
if(l==r) return;
int mid=(l+r)>>1;
if(wi<=mid) built(t[pos].ls,t[pre].ls,l,mid,wi);
else built(t[pos].rs,t[pre].rs,mid+1,r,wi);
return;
}
void dfs(int u,int fa,int rt){
built(root[u],root[fa],1,tot,s[u]);
deep[u]=deep[fa]+1;ans[u][0]=fa;
size[rt]++;from[u]=rt;
for(int i=1;i<=18;i++)
ans[u][i]=ans[ans[u][i-1]][i-1];
for(int i=head[u];i;i=nxt[i])
if(to[i]!=fa) dfs(to[i],u,rt);
return;
}
int get_LCA(int u,int v){
if(deep[u]<deep[v]) swap(u,v);
while(deep[u]>deep[v])
u=ans[u][lg[deep[u]-deep[v]]];
if(u==v) return u;
for(int i=lg[deep[u]];i>=0;i--)
if(ans[u][i]!=ans[v][i])
u=ans[u][i],v=ans[v][i];
return ans[u][0];
}
int Answer(int u,int v,int og,int fg,int l,int r,int k){
if(l==r) return row[l];
int sum=t[t[u].ls].si+t[t[v].ls].si-t[t[og].ls].si-t[t[fg].ls].si;
int mid=(l+r)>>1;
if(k<=sum) return Answer(t[u].ls,t[v].ls,t[og].ls,t[fg].ls,l,mid,k);
return Answer(t[u].rs,t[v].rs,t[og].rs,t[fg].rs,mid+1,r,k-sum);
}
int main(){
pre_work();
for(int i=1;i<=n;i++)
if(from[i]==i) dfs(i,0,i);
char ch[5];int x,y,k;
for(int i=1;i<=TT;i++){
scanf("%s",ch);x=in()^last;y=in()^last;
if(ch[0]=='Q'){
k=in()^last;
int og=get_LCA(x,y),fg=ans[og][0];
last=Answer(root[x],root[y],root[og],root[fg],1,tot,k);
printf("%d\n",last);
}
else{
adds(x,y);adds(y,x);
int fx=from[x],fy=from[y];
if(size[fy]<size[fx]) dfs(y,x,fx);
else dfs(x,y,fy);
}
}
return 0;
}