这题……半年前写了没调出来……
首先不考虑第一个操作，这不就是「Count on a Tree」？
沿用之前的想法，把路径信息转化为到根的路径信息相减。
那么考虑连边，即合并。
于是——
启（大）发（力）式 合 并！
首先用 dsu 找根，然后在合并的时候先判大小，把小的接到大的上去，均摊分析下最多合并 \(O(\log n)\) 次。
然后 DFS 更新重儿子和重链顶（是的没错我用树剖做 LCA）以及主席树。
树剖常数还是比 LCT 和倍增小很多的……
目前 BZOJ 第三优解。
代码： 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
using namespace std;
const int BUFF_SIZE = 1 << 20;
char BUFF[BUFF_SIZE],*BB,*BE;
template<class T>
inline void read(T &x)
{
x = 0;
char ch = 0,w = 0;
while(ch < '0' || ch > '9')
w |= ch == '-',ch = gc();
while(ch >= '0' && ch <= '9')
x = (x << 3) + (x << 1) + (ch ^ '0'),ch = gc();
w ? x = -x : x;
}
const int N = 8e4;
int n,m,t,lastans;
int to[(N << 1) + 5],pre[(N << 1) + 5],first[N + 5];
int a[N + 5],ind[N + 5],len;
inline void add(int u,int v)
{
static int tot = 0;
to[++tot] = v;
pre[tot] = first[u];
first[u] = tot;
}
struct node
{
int sum;
int ls,rs;
} seg[(N << 7) + 10];
void insert(int x,int &p,int tl,int tr)
{
static int tot = 0;
seg[++tot] = seg[p],p = tot,++seg[p].sum;
if(tl == tr)
return ;
int mid = tl + tr >> 1;
x <= mid ? insert(x,ls(p),tl,mid) : insert(x,rs(p),mid + 1,tr);
}
int query(int k,int x,int y,int lca,int fa_lca,int tl,int tr)
{
if(tl == tr)
return tl;
int sum = seg[ls(x)].sum + seg[ls(y)].sum - seg[ls(lca)].sum - seg[ls(fa_lca)].sum;
int mid = tl + tr >> 1;
if(k <= sum)
return query(k,ls(x),ls(y),ls(lca),ls(fa_lca),tl,mid);
else
return query(k - sum,rs(x),rs(y),rs(lca),rs(fa_lca),mid + 1,tr);
}
int fa[N + 5],dep[N + 5],sz[N + 5],son[N + 5],top[N + 5],fat[N + 5];
inline int get(int x)
{
return !fat[x] ? x : fat[x] = get(fat[x]);
}
int rt[N + 5];
void dfs(int p)
{
insert(a[p],rt[p] = rt[fa[p]],1,len);
sz[p] = 1,son[p] = 0;
for(register int i = first[p];i;i = pre[i])
if(to[i] ^ fa[p])
{
fa[to[i]] = fat[to[i]] = p,dep[to[i]] = dep[p] + 1,dfs(to[i]),sz[p] += sz[to[i]];
if(!son[p] || sz[to[i]] > sz[son[p]])
son[p] = to[i];
}
}
void get_top(int p)
{
if(son[p])
top[son[p]] = top[p],get_top(son[p]);
for(register int i = first[p];i;i = pre[i])
if((to[i] ^ fa[p]) && (to[i] ^ son[p]))
top[to[i]] = to[i],get_top(to[i]);
}
inline void link(int u,int v)
{
add(u,v),add(v,u);
if(sz[get(u)] < sz[get(v)])
swap(u,v);
fa[v] = fat[v] = u,dep[v] = dep[u] + 1,dfs(v),top[v] = v,get_top(v);
}
inline int getlca(int x,int y)
{
while(top[x] ^ top[y])
dep[top[x]] > dep[top[y]] ? x = fa[top[x]] : y = fa[top[y]];
return dep[x] < dep[y] ? x : y;
}
int main()
{
read(n),read(n),read(m),read(t);
for(register int i = 1;i <= n;++i)
read(a[i]),ind[i] = a[i];
sort(ind + 1,ind + n + 1),len = unique(ind + 1,ind + n + 1) - ind - 1;
for(register int i = 1;i <= n;++i)
a[i] = lower_bound(ind + 1,ind + len + 1,a[i]) - ind;
int u,v;
while(m--)
read(u),read(v),add(u,v),add(v,u);
for(register int i = 1;i <= n;++i)
if(!fa[i])
dep[i] = 1,dfs(i),top[i] = i,get_top(i);
char op;
int x,y,k;
while(t--)
{
op = 0;
while(op < 'A' || op > 'Z')
op = gc();
if(op == 'Q')
{
read(x),read(y),read(k),x ^= lastans,y ^= lastans,k ^= lastans;
int lca = getlca(x,y);
printf("%d\n",lastans = ind[query(k,rt[x],rt[y],rt[lca],rt[fa[lca]],1,len)]);
}
else
read(x),read(y),link(x ^= lastans,y ^= lastans);
}
}