题目链接
题解
树剖线段树可以
lct还行
代码
#include<cstdio>
#include<algorithm>
inline int read() {
int x = 0,f = 1;
char c = getchar();
while(c < '0' || c > '9')c = getchar();
while(c <= '9' && c >= '0') x = x * 10 + c - '0',c = getchar();
return x * f;
}
const int maxn = 300007;
int ch[maxn][2],rev[maxn],fa[maxn];
bool isroot(int x) { return ch[fa[x]][1] != x && ch[fa[x]][0] != x;}
void pushdown(int x) {
if(rev[x]) {rev[x] ^= 1,std::swap(ch[x][1],ch[x][0]),rev[ch[x][1]] ^= 1,rev[ch[x][0]] ^= 1;}
}
void rotate(int x) {
int y = fa[x],z = fa[y],d = (ch[y][1] == x) ^ 1;
if(!isroot(y)) ch[z][ch[z][1] == y] = x;
fa[x] = z;
ch[y][d ^ 1] = ch[x][d]; fa[ch[x][d]] = y;
ch[x][d] = y; fa[y] = x;
}
int stack[maxn],top = 0;
void splay(int x) {
stack[++ top] = x;
for(int i = x;!isroot(i);i = fa[i]) stack[++ top] = fa[i];
while(top) pushdown( stack[top --]);
while(!isroot(x)) {
int y = fa[x],z = fa[y];
if(!isroot(y)) {
if((ch[y][1] == x) ^ (ch[z][1] == y)) rotate(x);
else rotate(y);
} rotate(x);
}
}
void access(int x) {
for(int i = 0;x;i = x , x = fa[x])
splay(x), ch[x][1] = i;
}
void makeroot(int x) {access(x),splay(x),rev[x] ^= 1; }
void link(int x,int y) { makeroot(x),fa[x] = y;return splay(x); }
void cut(int x,int y) {makeroot(x),access(y),splay(y),ch[y][0] = fa[x] = 0;}
int find(int x) {
for(access(x),splay(x);ch[x][0];x = ch[x][0]) ;
return x;
}
int p1[maxn],p2[maxn],num = 0;
int main() {
int n,m;
n = read(),m = read();
for(int a,b,i = 1;i < n;++ i) a = read(),b = read(),link(a,b);
char s[10];
while(m -- ) {
int a,b;
scanf("%s",s + 1);
if(s[1] == 'U') {a = read(), link(p1[a],p2[a]);}
else if(s[1] == 'C') {a = read(),b = read();++ num,cut(p1[num] = a,p2[num] = b);}
else {a = read(),b = read();puts(find(a) == find(b) ? "Yes" : "No"); }
}
return 0;
}