题解：
加边，减去一条边还是标准的
其他的就暴力好了
代码：
#include<bits/stdc++.h> using namespace std; const int N=400005; char op[10]; int c[N][2],size[N],n,m,y,rev[N],x,t,next[N],fa[N]; int isroot(int x){return c[fa[x]][0]!=x&&c[fa[x]][1]!=x;} void pushup(int x){size[x]=size[c[x][0]]+size[c[x][1]]+1;} void pushdown(int x) { if (rev[x]) { rev[x]^=1;rev[c[x][0]]^=1;rev[c[x][1]]^=1; swap(c[x][0],c[x][1]); } } void down(int x) { if (!isroot(x))down(fa[x]); pushdown(x); } void rotate(int x) { int y=fa[x],z=fa[y],l=c[y][1]==x,r=l^1; if(!isroot(y))c[z][c[z][1]==y] = x; fa[x]=z;fa[y]=x;fa[c[x][r]]=y; c[y][l]=c[x][r];c[x][r]=y; pushup(y);pushup(x); } void splay(int x) { down(x); for (int y=fa[x];!isroot(x);rotate(x),y=fa[x]) if (!isroot(y))rotate((c[y][0]==x)==(c[fa[y]][0]==y)?y:x); } void access(int x) { int t=0; while(x) { splay(x); c[x][1]=t; t=x;x=fa[x]; } } int find(int x) { for (;fa[x];x=fa[x]); return x; } void rever(int x){access(x);splay(x);rev[x]^=1;} void cut(int x,int y){rever(x);access(y);splay(y);c[y][0]=fa[x]=0;} void link(int x,int y){rever(x);fa[x]=y;splay(x);} int main() { scanf("%d%d",&n,&m); while (m--) { scanf("%s%d%d",&op,&x,&y); if (op[0]=='D')cut(x,y); if (op[0]=='C')link(x,y); if (op[0]=='Q') { rever(x); if (find(y)==x)puts("Yes"); else puts("No"); } } }