SP8791 DYNALCA - Dynamic LCA 题解
Starstream
·
·
题解
题意
动态求 LCA 板子题。
维护一个森林，支持加边、删边和求 LCA 操作。
思路
不难想到 LCT。
现在问题就是如何在 LCT 上求两个点 u,v 的 LCA。
先进行 \operatorname{access}(u)，此时 u 到根的路径已经变成一个实链。
再进行 $\operatorname{access}(v)$，由于 $\operatorname{lca}(u,v)$ 到根的路径上全是实边，那么 $\operatorname{access}$ 最后改变的虚边的父亲就是 $\operatorname{lca}(u,v)$。
**注意**：求 LCA 需要考虑树的父子关系，所以在 cut 时不能使用 makeroot 操作，而 link 无所谓。
***
### 代码
```cpp
#include <iostream>
using namespace std;
const int N = 100010;
int n, m;
struct Splay_Node
{
int s[2], p, v;
}tr[N];
inline bool is_root(int x)
{
int p = tr[x].p;
if (tr[p].s[0] != x && tr[p].s[1] != x) return true;
return false;
}
inline void rotate(int x)
{
int y = tr[x].p, z = tr[y].p;
int k = tr[y].s[1] == x;
if (!is_root(y)) tr[z].s[tr[z].s[1] == y] = x;
tr[x].p = z;
tr[y].s[k] = tr[x].s[k ^ 1], tr[tr[x].s[k ^ 1]].p = y;
tr[x].s[k ^ 1] = y, tr[y].p = x;
}
inline void splay(int x)
{
while (!is_root(x))
{
int y = tr[x].p, z = tr[y].p;
if (!is_root(y))
if ((tr[y].s[1] == x) ^ (tr[z].s[1] == y)) rotate(x);
else rotate(y);
rotate(x);
}
}
inline int access(int x)
{
int z = x, y;
for (y = 0; x; y = x, x = tr[x].p)
splay(x), tr[x].s[1] = y;
splay(z);
return y; // 这里返回的是最后一次虚实链变换时虚边父亲节点的编号。
}
inline int find_root(int x)
{
access(x);
while (tr[x].s[0]) x = tr[x].s[0];
splay(x);
return x;
}
inline void link(int x, int y)
{
if (find_root(y) != find_root(x)) tr[x].p = y;
}
inline void cut(int x) // 一定不能 makeroot！
{
access(x);
tr[x].s[0] = tr[tr[x].s[0]].p = 0;
}
inline int lca(int x, int y)
{
access(x);
return access(y);
}
int main()
{
char op[5]; int x, y;
scanf("%d%d", &n, &m);
while (m -- )
{
scanf("%s%d%d", op, &x, &y);
if (op[1] == 'i') link(x, y);
else if (op[1] == 'u') cut(x);
else printf("%d\n", lca(x, y));
}
return 0;
}
```