https://www.luogu.org/problemnew/show/P3302
看到查询第 k 小，而且是一颗树，可以联想到在树上的主席树，a 和 b 路径中第 k 小可以通过在 a, b, lca(a, b), fa[lca(a, b)] 四个节点对应的主席树上二分得到
实现主席树是很简单的，连接两个点可以启发式合并，现在最大的问题是连接两个点后还要高效的求出 LCA，一种做法是启发式合并的时候重构倍增数组，也有一种用 LCT 维护 LCA 的方法，相对简单。博主的实现是后者
需要注意的就是找到 fa[lca(a, b)] 的时候，可以模仿 LCT findroot 函数的实现，先 access(lca)，然后 splay(lca)，找到深度次大的点即可。link 之后 root 会变，进行新操作的时候要 makeroot，才能求出正确的 LCA
总而言之，需要注意的细节还是很多的，具体还是看代码实现吧
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
template <typename _T>
inline void read(_T &f) {
f = 0; _T fu = 1; char c = getchar();
while(c < '0' || c > '9') {if(c == '-') fu = -1; c = getchar();}
while(c >= '0' && c <= '9') {f = (f << 3) + (f << 1) + (c & 15); c = getchar();}
f *= fu;
}
const int N = 80000 + 10;
int fa[N], ch[N][2], rev[N], st[N], len;
int n, m, t;
int isroot(int u) {return ch[fa[u]][0] != u && ch[fa[u]][1] != u;}
int get(int u) {return ch[fa[u]][1] == u;}
void pushdown(int u) {
if(rev[u]) {
swap(ch[u][0], ch[u][1]);
rev[ch[u][0]] ^= 1;
rev[ch[u][1]] ^= 1;
rev[u] ^= 1;
}
}
void rotate(int u) {
int old = fa[u], oldd = fa[old], k = get(u);
if(!isroot(old)) ch[oldd][get(old)] = u; fa[u] = oldd;
fa[ch[u][k ^ 1]] = old; ch[old][k] = ch[u][k ^ 1];
fa[old] = u; ch[u][k ^ 1] = old;
}
void splay(int u) {
st[len = 1] = u;
for(int i = u; !isroot(i); i = fa[i]) st[++len] = fa[i];
for(int i = len; i >= 1; i--) pushdown(st[i]);
for(; !isroot(u); rotate(u)) if(!isroot(fa[u])) rotate(get(u) == get(fa[u]) ? fa[u] : u);
}
int access(int u) {
int tmp;
for(int i = 0; u; i = u, u = fa[u]) {
splay(u);
ch[u][1] = i;
tmp = u;
}
return tmp;
}
void makeroot(int u) {
access(u);
splay(u);
rev[u] ^= 1;
}
void link(int x, int y) {
makeroot(x);
fa[x] = y;
}
int LCA(int x, int y) {
access(x);
return access(y);
}
int rt[N], val[N * 600], lc[N * 600], rc[N * 600], a[N], b[N];
int tot = 0;
void build(int &u, int l, int r) {
u = ++tot;
if(l == r) return;
int mid = (l + r) >> 1;
build(lc[u], l, mid);
build(rc[u], mid + 1, r);
}
void ins(int &u, int pre, int l, int r, int x) {
u = ++tot;
val[u] = val[pre] + 1, lc[u] = lc[pre], rc[u] = rc[pre];
if(l == r) return;
int mid = (l + r) >> 1;
if(mid >= x) ins(lc[u], lc[pre], l, mid, x);
else ins(rc[u], rc[pre], mid + 1, r, x);
}
int query(int a, int b, int c, int d, int l, int r, int k) {
if(l == r) return l;
int lsum = val[lc[a]] + val[lc[b]] - val[lc[c]] - val[lc[d]];
int rsum = val[rc[a]] + val[rc[b]] - val[rc[c]] - val[rc[d]];
int mid = (l + r) >> 1;
if(lsum >= k) return query(lc[a], lc[b], lc[c], lc[d], l, mid, k);
else return query(rc[a], rc[b], rc[c], rc[d], mid + 1, r, k - lsum);
}
int blen;
vector <int> g[N];
int siz[N], head[N];
int f[N]; int find(int x) {return f[x] == x ? x : f[x] = find(f[x]);}
inline void addedge(int u, int v) {
g[u].push_back(v);
g[v].push_back(u);
}
void dfs1(int u, int f) {
ins(rt[u], rt[f], 1, blen, a[u]);
for(vector <int> :: iterator it = g[u].begin(); it != g[u].end(); it++) {
int v = *it; if(v == f) continue; dfs1(v, u);
}
}
void Merge(int a, int b) {
int x = find(a), y = find(b);
if(siz[x] < siz[y]) swap(a, b), swap(x, y);
siz[x] += siz[y]; addedge(a, b);
link(a, b); f[y] = x;
dfs1(b, a);
}
int lastans = 0;
int main() {
cin >> n;
cin >> n >> m >> t;
for(int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
b[i] = a[i];
f[i] = i; siz[i] = 1;
}
sort(b + 1, b + n + 1);
blen = unique(b + 1, b + n + 1) - b - 1;
for(int i = 1; i <= n; i++) a[i] = lower_bound(b + 1, b + blen + 1, a[i]) - b;
build(rt[0], 1, blen);
for(int i = 1; i <= n; i++) {
ins(rt[i], rt[0], 1, blen, a[i]);
}
for(int i = 1; i <= m; i++) {
int A, B;
scanf("%d %d", &A, &B);
Merge(A, B);
}
for(int i = 1; i <= t; i++) {
char c = getchar();
while(c != 'Q' && c != 'L') c = getchar();
if(c == 'L') {
int A, B;
scanf("%d %d", &A, &B);
A ^= lastans; B ^= lastans;
Merge(A, B);
} else {
int A, B, K;
scanf("%d %d %d", &A, &B, &K);
A ^= lastans; B ^= lastans; K ^= lastans;
makeroot(find(A));
int lca = LCA(A, B), father;
if(find(A) == lca) father = 0;
else {
access(lca); splay(lca);
father = ch[lca][0];
while(ch[father][1]) {
father = ch[father][1];
pushdown(father);
}
}
printf("%d
", lastans = b[query(rt[A], rt[B], rt[lca], rt[father], 1, blen, K)]);
}
}
return 0;
}