大致题意:有两种操作。
1. 查询节点x到节点y的路径上的第k小。
2. 连接点x和点y。
本题只有一组测试样例,且存在垃圾数据!
需要离散化不必多说。
对于第一种操作,经典的LCA + 主席树问题。每次以父亲节点为上一版本建树,对于一次询问的答案就是在区间 x−lca[x,y]+y−fa[lca[x,y]] 的答案。
对于第二种操作,每次启发式合并即可。对于新加入的点,需要对这些点进行LCA和主席树的相关信息的更新。
总复杂度 O(nlognlogn) 。
#include <bits/stdc++.h>
#define all(x) x.begin(), x.end()
using namespace std;
/*
1. 树上路径第k小。
转化成LCA+主席树
2. 点之间连边,启发式合并
3. 点权大,离散化
*/
const int maxn = ;
int ans, t, n, m, q;
int val[maxn];
vector<int> G[maxn];
vector<int> V, C;
int getid(int x) {
return lower_bound(all(V), x) - V.begin() + ;
}
int getval(int x) {
return V[x-];
}
struct seg{ int l, r, sum;} tr[maxn*100];
int idc, root[maxn];
void update(int &x, int y, int l, int r, int pos, int val) {
x = ++idc; tr[x] = tr[y]; tr[x].sum += val;
if(l == r) return ;
int m = (l + r) >> ;
if(pos <= m) update(tr[x].l, tr[y].l, l, m, pos, val);
else update(tr[x].r, tr[y].r, m+, r, pos, val);
}
int ask(int x, int f1, int y, int f2, int l, int r, int k) {
if(l == r) return l;
int m = (l + r) >> ;
int sum = tr[tr[x].l].sum - tr[tr[f1].l].sum + tr[tr[y].l].sum - tr[tr[f2].l].sum;
if(sum >= k) return ask(tr[x].l, tr[f1].l, tr[y].l, tr[f2].l, l, m, k);
else ask(tr[x].r, tr[f1].r, tr[y].r, tr[f2].r, m+, r, k-sum);
}
int p[maxn][], dep[maxn];
void dfs(int u, int fa) {
C.push_back(u);
dep[u] = dep[fa] + ;
p[u][] = fa;
update(root[u], root[fa], , V.size(), getid(val[u]), );
for(int i = ; i < G[u].size(); i++) {
int v = G[u][i];
if(v == fa) continue;
dfs(v, u);
}
}
int lca_up(int u, int len) {
for(int i = ; i < ; i++) {
if(u != && len&(<<i))
u = p[u][i];
}
return u;
}
int lca(int u, int v) {
if(dep[u] < dep[v]) swap(u, v);
u = lca_up(u, dep[u] - dep[v]);
if(v == u) return v;
for(int i = ; i >= ; i--) {
if(p[u][i] == p[v][i]) continue;
u = p[u][i]; v = p[v][i];
}
return p[u][];
}
void lca_update() {
for(int j = ; j < ; j++) {
for(int = ; < C.size(); ++) {
int i = C[];
if(p[i][j-] == ) p[i][j] = ;
else p[i][j] = p[p[i][j-]][j-];
}
}
C.clear();
}
int fa[maxn], sz[maxn];
int find(int x) {
return x == fa[x]? fa[x] : fa[x] = find(fa[x]);
}
void unite(int x, int y) {
int f1 = find(x), f2 = find(y);
if(f1 == f2) return ;
sz[f1] += sz[f2];
fa[f2] = f1;
}
void init() {
V.clear(); C.clear();
for(int i = ; i < maxn; i++)
G[i].clear(), fa[i] = i, sz[i] = ;
ans = idc = ;
}
int main() {
scanf("%d", &t);
init();
scanf("%d%d%d", &n, &m, &q);
for(int i = ; i <= n; i++)
scanf("%d", &val[i]), V.push_back(val[i]);
sort(all(V));
V.erase(unique(all(V)), V.end());
for(int i = ; i <= m; i++) {
int u, v;
scanf("%d%d", &u, &v);
G[u].push_back(v);
G[v].push_back(u);
unite(u, v);
}
dep[] = ;
for(int i = ; i <= n; i++)
if(!dep[i])
dfs(i, );
lca_update();
while(q--) {
char cmd;
scanf(" %c", &cmd);
if(cmd == 'Q') {
int x, y, k;
scanf("%d%d%d", &x, &y, &k);
x ^= ans, y ^= ans, k ^= ans;
int lc = lca(x, y);
printf("%d\n", ans = getval(ask(root[x], root[lc], root[y], root[p[lc][]], , V.size(), k)));
} else {
int x, y;
scanf("%d%d", &x, &y);
x ^= ans, y ^= ans;
int f1 = find(x), f2 = find(y);
if(sz[f1] < sz[f2]) swap(x, y);
unite(x, y);
G[x].push_back(y); G[y].push_back(x);
dfs(y, x);
lca_update();
}
}
return ;
}