本文共 1803 字，大约阅读时间需要 6 分钟。
【题目分析】
LCT另一道题目，很裸，许多操作都不需要，写起来很爽。
【代码】
#include #include #include #include #include #include #include #include #include #include #include using namespace std; #define maxn 1000005#define inf (0x3f3f3f3f) int read(){ int x=0,f=1; char ch=getchar(); while (ch<'0'||ch>'9') {if (ch=='-') f=-1; ch=getchar();} while (ch>='0'&&ch<='9') {x=x*10+ch-'0'; ch=getchar();} return x*f;} int fa[maxn],ch[maxn][2],n,m,rev[maxn],sta[maxn],top; bool isroot(int x){return ch[fa[x]][0]!=x&&ch[fa[x]][1]!=x;} void pushdown (int x){ if (rev[x]) { rev[x]^=1; rev[ch[x][0]]^=1; rev[ch[x][1]]^=1; swap(ch[x][0],ch[x][1]); }} void rot(int x){ int y=fa[x],z=fa[y],l,r; if (ch[y][0]==x) l=0; else l=1; r=l^1; if (!isroot(y)) { if (ch[z][0]==y) ch[z][0]=x; else ch[z][1]=x; } fa[x]=z; fa[y]=x; fa[ch[x][r]]=y; ch[y][l]=ch[x][r]; ch[x][r]=y;} void splay(int x){ top=0; sta[++top]=x; for (int i=x;!isroot(i);i=fa[i]) sta[++top]=fa[i]; while (top) pushdown(sta[top--]); while (!isroot(x)) { int y=fa[x],z=fa[y]; if (!isroot(y)) { if (ch[y][0]==x^ch[z][0]==y) rot(y); else rot(x); } rot(x); }} void access(int x){for (int t=0;x;t=x,x=fa[x]) splay(x),ch[x][1]=t;} void makeroot(int x){ access(x); splay(x); rev[x]^=1;} void cut(int x,int y){ makeroot(x); access(y); splay(y); ch[y][0]=fa[x]=0;} void link(int x,int y){ makeroot(x); fa[x]=y;} int find(int x){ access(x); splay(x); while (ch[x][0]) x=ch[x][0]; return x;} int main(){ n=read();m=read(); while (m--) { char opt[11]; int x,y; scanf("%s",opt+1); x=read(); y=read(); if (opt[1]=='Q') { if (find(x)==find(y)) printf("Yes\n"); else printf("No\n"); } else if (opt[1]=='C') link(x,y); else cut(x,y); }}
转载于:https://www.cnblogs.com/SfailSth/p/6195062.html