BZOJ原题地址
洛谷原题地址
思路
两个操作，求路径上第k大，还要连边。
前者让我们想到主席树，后者又是典型的LCT。
但是LCT我不会啊，所以我写了一发主席树。
对于查询，LCA一下，差分即可。
对于连边，那就。。。连边吧。因为保证连边之后依然是森林，就可以启发式合并，并查集维护。
注意这道题的输入有一个很坑的地方。第一行输入testcase，用处是什么呢？真的只是标明 testcase 而不是多组数据。
代码
#include <bits/stdc++.h>
#define maxn 100010
#define maxm 40000000//注意主席树一定要开大
#define mid ((l+r)>>1)
using namespace std;
struct Edge{
int to,next;
Edge(int a=0,int b=0){
to=a,next=b;
}
}l[maxn*2];
int head[maxn],cnt,p[maxn][25],d[maxn],fa[maxn],a[maxn],INF;
int n,m,q,id,siz[maxn],L[maxm],R[maxm],tree[maxm],rt[maxn];
int find(int x){
return fa[x]==x?fa[x]:fa[x]=find(fa[x]);
}
void Add(int a,int b){
l[++cnt]=Edge(b,head[a]);
head[a]=cnt;
}
void Merge(int a,int b){
int fx=find(a),fy=find(b);
fa[fx]=fy;siz[fy]+=siz[fx];
}
void insert(int x,int &y,int l,int r,int val){
if (!y) y=++id;
tree[y]=tree[x]+1;
if (l==r) return;
if (val<=mid) R[y]=R[x],insert(L[x],L[y],l,mid,val);
else L[y]=L[x],insert(R[x],R[y],mid+1,r,val);
}
int query(int x,int y,int w,int e,int l,int r,int k){
if (l==r) return l;
int tem=tree[L[x]]+tree[L[y]]-tree[L[w]]-tree[L[e]];
if (tem>=k) return query(L[x],L[y],L[w],L[e],l,mid,k);
else return query(R[x],R[y],R[w],R[e],mid+1,r,k-tem);
}
void Build(int u){
d[u]=d[p[u][0]]+1;
for (int i=1;(1<<i)<=d[u];i++)
p[u][i]=p[p[u][i-1]][i-1];
rt[u]=0;
insert(rt[p[u][0]],rt[u],0,INF,a[u]);
for (int i=head[u];i;i=l[i].next){
int v=l[i].to;if (v==p[u][0]) continue;
p[v][0]=u;Build(v);
}
}
int lca(int a,int b){
if (d[a]<d[b]) swap(a,b);
for (int i=24;i>=0;i--)
if (d[p[a][i]]>=d[b]) a=p[a][i];
if (a==b) return a;
for (int i=24;i>=0;i--)
if (p[a][i]!=p[b][i]) a=p[a][i],b=p[b][i];
return p[a][0];
}
int main(){
ios::sync_with_stdio(false);
int t;cin>>t;
cin>>n>>m>>q;
for (int i=1;i<=n;i++)
fa[i]=i,cin>>a[i],INF=max(INF,a[i]),siz[i]=1;
for (int i=1,t1,t2;i<=m;i++){
cin>>t1>>t2;Add(t1,t2);
Add(t2,t1);Merge(t1,t2);
}
for (int i=1;i<=n;i++)
if (!p[i][0]) Build(i);
int ans=0,x,y,k;char op;
for (int i=1;i<=q;i++){
cin>>op;if (op=='Q'){
cin>>x>>y>>k;
x^=ans,y^=ans,k^=ans;int lc=lca(x,y);
ans=query(rt[x],rt[y],rt[lc],rt[p[lc][0]],0,INF,k);
cout<<ans<<endl;
}else{
cin>>x>>y;x^=ans,y^=ans;
int fx=find(x),fy=find(y);
if (siz[fx]>siz[fy]) swap(x,y);
Add(x,y);Add(y,x);Merge(x,y);
p[x][0]=y;Build(x);
}
}
return 0;
}