LCT判断联通性
没什么特别的。。还是一个普通的板子题，把LCT当并查集用了，只不过LCT灵活一些，还可以断边话说自从昨天被维修数列那题榨干之后我现在写splay都不用动脑子了，，机械式的码splay23333
#include#define INF 0x3f3f3f3f#define full(a, b) memset(a, b, sizeof a)using namespace std;typedef long long ll;inline int lowbit(int x){ return x & (-x); }inline int read(){ int X = 0, w = 0; char ch = 0; while(!isdigit(ch)) { w |= ch == '-'; ch = getchar(); } while(isdigit(ch)) X = (X << 3) + (X << 1) + (ch ^ 48), ch = getchar(); return w ? -X : X;}inline int gcd(int a, int b){ return a % b ? gcd(b, a % b) : b; }inline int lcm(int a, int b){ return a / gcd(a, b) * b; }template inline T max(T x, T y, T z){ return max(max(x, y), z); }template inline T min(T x, T y, T z){ return min(min(x, y), z); }template inline A fpow(A x, B p, C lyd){ A ans = 1; for(; p; p >>= 1, x = 1LL * x * x % lyd)if(p & 1)ans = 1LL * x * ans % lyd; return ans;}const int N = 10005;int n, m, tot, ch[N][2], fa[N], rev[N], st[N];int newNode(){ fa[++tot] = 0; ch[tot][0] = ch[tot][1] = 0; return tot;}bool isRoot(int x){ return ch[fa[x]][0] != x && ch[fa[x]][1] != x;}void reverse(int x){ rev[x] ^= 1; swap(ch[x][0], ch[x][1]);}void push_down(int x){ if(rev[x]){ rev[x] ^= 1; reverse(ch[x][0]), reverse(ch[x][1]); }}void rotate(int x){ int y = fa[x], z = fa[y], p = (ch[y][1] == x) ^ 1; push_down(y), push_down(x); ch[y][p^1] = ch[x][p], fa[ch[x][p]] = y; if(!isRoot(y)) ch[z][ch[z][1] == y] = x; fa[x] = z, fa[y] = x, ch[x][p] = y;}void splay(int x){ int pos = 0; st[++pos] = x; for(int i = x; !isRoot(i); i = fa[i]) st[++pos] = fa[i]; while(pos) push_down(st[pos--]); while(!isRoot(x)){ int y = fa[x], z = fa[y]; if(!isRoot(y)){ if((ch[y][0] == x) ^ (ch[z][0] == y)) rotate(x); else rotate(y); } rotate(x); }}void access(int x){ for(int p = 0; x; p = x, x = fa[x]) splay(x), ch[x][1] = p;}void makeRoot(int x){ access(x), splay(x), reverse(x);}int findRoot(int x){ access(x), splay(x); while(ch[x][0]) x = ch[x][0]; return x;}void link(int x, int y){ makeRoot(x); if(findRoot(y) != x) fa[x] = y;}void cut(int x, int y){ makeRoot(x), access(y), splay(y); fa[x] = ch[y][0] = 0;}bool isConnect(int x, int y){ return findRoot(x) == findRoot(y);}int main(){ int n = read(), m = read(); for(int i = 1; i <= n; i ++) newNode(); while(m --){ char opt[20]; scanf("%s", opt); int x = read(), y = read(); if(opt[0] == 'Q') printf(isConnect(x, y) ? "Yes\n" : "No\n"); else if(opt[0] == 'C') link(x, y); else if(opt[0] == 'D') cut(x, y); } return 0;}