题目链接：BZOJ - 2049
题目分析
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 <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm> 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;
}