Description
.jpg)
Input
第一行包含一个正整数testcase，表示当前测试数据的测试点编号。保证1≤testcase≤20。
第二行包含三个整数N，M，T，分别表示节点数、初始边数、操作数。第三行包含N个非负整数表示 N个节点上的权值。
接下来 M行，每行包含两个整数x和 y，表示初始的时候，点x和点y 之间有一条无向边, 接下来 T行，每行描述一个操作，格式为“Q x y k”或者“L x y ”，其含义见题目描述部分。
Output
对于每一个第一类操作，输出一个非负整数表示答案。
Sample Input
1
8 4 8
1 1 2 2 3 3 4 4
4 7
1 8
2 4
2 1
Q 8 7 3 Q 3 5 1
Q 10 0 0
L 5 4
L 3 2 L 0 7
Q 9 2 5 Q 6 1 6
Sample Output
2
2
1
4
2
HINT
.jpg)
其实这题是个暴力。。。
首先考虑没有连边操作，那么就直接令某个点为根，统计4条链的答案即可
如果有加边操作，我们就直接按秩合并，把较小的接到较大的下面，然后将较小的树全部重构
由于每次合并至少会使得树的大小翻倍，因此一个点重构次数不会超过(O(log n))次
至于动态求Lca？暴力更新倍增数组，当然也可以用LCT
/*program from Wolfycz*/
#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define inf 0x7f7f7f7f
using namespace std;
typedef long long ll;
typedef unsigned int ui;
typedef unsigned long long ull;
inline char gc(){
static char buf[1000000],*p1=buf,*p2=buf;
return p1==p2&&(p2=(p1=buf)+fread(buf,1,1000000,stdin),p1==p2)?EOF:*p1++;
}
inline int frd(){
int x=0,f=1; char ch=gc();
for (;ch<'0'||ch>'9';ch=gc()) if (ch=='-') f=-1;
for (;ch>='0'&&ch<='9';ch=gc()) x=(x<<3)+(x<<1)+ch-'0';
return x*f;
}
inline int read(){
int x=0,f=1; char ch=getchar();
if (ch==EOF) exit(0);
for (;ch<'0'||ch>'9';ch=getchar()) if (ch=='-') f=-1;
for (;ch>='0'&&ch<='9';ch=getchar()) x=(x<<3)+(x<<1)+ch-'0';
return x*f;
}
inline void print(int x){
if (x<0) putchar('-'),x=-x;
if (x>9) print(x/10);
putchar(x%10+'0');
}
const int N=8e4,M=1e7;
struct S1{
#define ls(x) tree[x][0]
#define rs(x) tree[x][1]
#define T(x) (rs(f[x])==x)
int tree[N+10][2],f[N+10],stack[N+10];
bool rev[N+10];
void Add_rev(int x){
if (!x) return;
swap(ls(x),rs(x));
rev[x]^=1;
}
void pushdown(int x){
if (!rev[x]) return;
Add_rev(ls(x));
Add_rev(rs(x));
rev[x]^=1;
}
bool isroot(int x){return ls(f[x])!=x&&rs(f[x])!=x;}
void move(int x){
int fa=f[x],son=tree[x][T(x)^1];
tree[x][T(x)^1]=fa;
tree[fa][T(x)]=son;
if (son) f[son]=fa;
f[x]=f[fa];
if (!isroot(fa)) tree[f[x]][T(fa)]=x;
f[fa]=x;
}
void splay(int x){
int top=0; stack[++top]=x;
for (int i=x;!isroot(i);i=f[i]) stack[++top]=f[i];
for (int i=top;i;i--) pushdown(stack[i]);
while (!isroot(x)){
if (!isroot(f[x])) T(x)==T(f[x])?move(f[x]):move(x);
move(x);
}
}
void Access(int x){
int last=0;
while (x){
splay(x);
rs(x)=last;
last=x,x=f[x];
}
}
void make_root(int x){
Access(x);
splay(x);
Add_rev(x);
}
void link(int x,int y){
make_root(x);
f[x]=y;
}
int lca(int x,int y){
Access(x),splay(x);
splay(y);
while (f[y]){
y=f[y];
splay(y);
}
return y;
}
#undef ls
#undef rs
#undef T
}LCT;//Link Cut Tree;
int root[N+10];
struct S2{
int ls[M+10],rs[M+10],cnt[M+10],tot;
void insert(int &k,int p,int l,int r,int x){
cnt[k=++tot]=cnt[p]+1;
ls[k]=ls[p],rs[k]=rs[p];
if (l==r) return;
int mid=(l+r)>>1;
if (x<=mid) insert(ls[k],ls[p],l,mid,x);
else insert(rs[k],rs[p],mid+1,r,x);
}
int Query(int k,int p,int w,int v,int l,int r,int x){
if (l==r) return l;
int mid=(l+r)>>1,res=cnt[ls[k]]+cnt[ls[p]]-cnt[ls[w]]-cnt[ls[v]];
if (x<=res) return Query(ls[k],ls[p],ls[w],ls[v],l,mid,x);
else return Query(rs[k],rs[p],rs[w],rs[v],mid+1,r,x-res);
}
}CT;//Chairman Tree
int pre[(N<<1)+10],now[N+10],child[(N<<1)+10];
int size[N+10],belong[N+10],v[N+10],list[N+10],rt[N+10],f[N+10];
int tot,Time,T;
void join(int x,int y){pre[++tot]=now[x],now[x]=tot,child[tot]=y;}
void insert(int x,int y){join(x,y),join(y,x);}
void dfs(int x,int fa){
size[belong[x]=Time]++,f[x]=fa;
CT.insert(root[x],root[fa],1,T,v[x]);
for (int p=now[x],son=child[p];p;p=pre[p],son=child[p]) if (son!=fa) dfs(son,x);
}
void rebuild(int x,int fa){
belong[x]=belong[fa],f[x]=fa;
CT.insert(root[x],root[fa],1,T,v[x]);
for (int p=now[x],son=child[p];p;p=pre[p],son=child[p]) if (son!=fa) rebuild(son,x);
}
int main(){
read();
int n=read(),m=read(),q=read();
for (int i=1;i<=n;i++) v[i]=list[i]=read();
sort(list+1,list+1+n);
T=unique(list+1,list+1+n)-list-1;
for (int i=1;i<=n;i++) v[i]=lower_bound(list+1,list+1+T,v[i])-list;
for (int i=1;i<=m;i++){
int x=read(),y=read();
LCT.link(x,y);
insert(x,y);
}
for (int i=1;i<=n;i++) if (!belong[i]) rt[++Time]=i,dfs(i,0),LCT.make_root(i);
char s[5]; int Lastans=0;
for (int i=1;i<=q;i++){
scanf("%s",s);
if (s[0]=='L'){
int x=read()^Lastans,y=read()^Lastans;
if (size[belong[x]]>size[belong[y]]) swap(x,y);
LCT.link(x,y),size[belong[y]]+=size[belong[x]];
insert(x,y),rebuild(x,y);
}
if (s[0]=='Q'){
int x=read()^Lastans,y=read()^Lastans,k=read()^Lastans;
int lca=LCT.lca(x,y); LCT.make_root(rt[belong[x]]);
printf("%d
",Lastans=list[CT.Query(root[x],root[y],root[lca],root[f[lca]],1,T,k)]);
}
}
return 0;
}