题目链接：
题目分析
LCT的基本模型，包括 Link ，Cut 操作和判断两个点是否在同一棵树内。
Link(x, y) : Make_Root(x); Splay(x); Father[x] = y;
Cut(x, y) : Make_Root(x); Access(y); 断掉 y 和 Son[y][0]; 注意修改 Son[y][0] 的 isRoot 和 Father
判断 x, y 是否在同一棵数内，我们就看两个点所在树的根是否相同，使用 Find_Root();
Find_Root(x) : Access(x); Splay(x); while (Son[x][0] != 0) x = Son[x][0]; 然后 x 就是树根了。
代码
#include#include #include #include #include #include using namespace std;inline void Read(int &Num){ char c = getchar(); bool Neg = false; while (c < '0' || c > '9') { if (c == '-') Neg = true; c = getchar(); } Num = c - '0'; c = getchar(); while (c >= '0' && c <= '9') { Num = Num * 10 + c - '0'; c = getchar(); } if (Neg) Num = -Num;}const int MaxN = 10000 + 5;int n, m;int Father[MaxN], Son[MaxN][2];bool isRoot[MaxN], Rev[MaxN];inline void Reverse(int x){ Rev[x] = !Rev[x]; swap(Son[x][0], Son[x][1]);}inline void PushDown(int x){ if (!Rev[x]) return; Rev[x] = false; if (Son[x][0]) Reverse(Son[x][0]); if (Son[x][1]) Reverse(Son[x][1]);}void Rotate(int x){ int y = Father[x], f; PushDown(y); PushDown(x); if (x == Son[y][0]) f = 1; else f = 0; if (isRoot[y]) { isRoot[y] = false; isRoot[x] = true; } else { if (y == Son[Father[y]][0]) Son[Father[y]][0] = x; else Son[Father[y]][1] = x; } Father[x] = Father[y]; Son[y][f ^ 1] = Son[x][f]; if (Son[x][f]) Father[Son[x][f]] = y; Son[x][f] = y; Father[y] = x;}void Splay(int x){ int y; while (!isRoot[x]) { y = Father[x]; if (isRoot[y]) { Rotate(x); break; } if (y == Son[Father[y]][0]) { if (x == Son[y][0]) { Rotate(y); Rotate(x); } else { Rotate(x); Rotate(x); } } else { if (x == Son[y][1]) { Rotate(y); Rotate(x); } else { Rotate(x); Rotate(x); } } }}int Access(int x){ int y = 0; while (x != 0) { Splay(x); PushDown(x); isRoot[Son[x][1]] = true; Son[x][1] = y; if (y) isRoot[y] = false; y = x; x = Father[x]; } return y;}void Make_Root(int x){ int t = Access(x); Reverse(t);}int Find_Root(int x){ int t = Access(x); while (Son[t][0] != 0) t = Son[t][0]; return t;}int main(){ scanf("%d%d", &n, &m); for (int i = 1; i <= n; ++i) { isRoot[i] = true; Father[i] = 0; } char Str[10]; int a, b, x, y; for (int i = 1; i <= m; ++i) { scanf("%s", Str); Read(a); Read(b); if (strcmp(Str, "Connect") == 0) { Make_Root(a); Splay(a); Father[a] = b; } else if (strcmp(Str, "Destroy") == 0) { Make_Root(a); Access(b); Splay(b); PushDown(b); isRoot[Son[b][0]] = true; Father[Son[b][0]] = 0; Son[b][0] = 0; } else { x = Find_Root(a); y = Find_Root(b); if (x == y) printf("Yes\n"); else printf("No\n"); } } return 0;}