LCT学习笔记

板子

从问题看起：P3690

本题需要在一个动态图上实时查询各条链的状态（异或和）。因为两点联通时不连边，所以该图始终具有以下性质：

任意联通两点间有唯一路径。

因此该图是一个森林。

LCT 存储森林中的每条边，同时可以查询森林中任意一条链。当然也可以加边或删边。

思路：

对于每一棵子树，参考树链剖分，我们可以将树分为若干条链。那么每条链之间都可能有边相连。但边是动态的，这就导致链的结构不固定，无法用线段树维护。那么可以用什么来维护这么多结构不固定的链呢？

Tarjan 选择了结构同样不固定的 Splay。与树链剖分时相同，我们所维护的链中节点深度（指定某个节点为根的意义下）都是连续的。既然这样，节点深度就可以成为 Splay 的中序遍历。

也就是说我们为每一条链用一个 Splay 维护，其中序遍历即为根据从小到大遍历链上节点。

于是就有了实边与虚边。

现在主要来看在那几条定义的基础上，如何初步达到本题目标：访问任意一条链。

所有的虚边都是子能认父，因此一棵子树的根节点是该树内所有节点的祖先节点。又因为该树的任何一个非根节点都知道它的父节点，所以每一个节点都能通过不断访问父节点来跳到根部。

我们就可以在这样的过程中建一条链。这就是 access 函数：建立一个节点到它的根节点的链。

inline void access(int p){
    int r = p;
    for (int c = 0; p; c = p, p = a[p].pa)
        splay(p), a[p].rs = c, pushup(p);
    splay(r);
    return;
}

观察代码，发现在此过程中我们通过覆盖右 Splay 中的右子节点去除了该链上所有其他节点。这样不会影响图的结构，因为这仍然是一条虚边：被覆盖的子节点的父节点未变化。

目前为止，我们已经可以建立一条从任意节点到树根的链了。但如果我们想要的两个端点都不是树根怎么办？

把其中一个变成根不就行了：

```cpp
inline void makeroot(int p){
access(p);
revit(p);
return;
}
```

$revit$ 函数为区间反转，作用是将整个 Splay 的中序遍历倒转。当我们建出由根到需求节点的链时，由于链中只有路径上的点，$access$ 的节点必然在链上**深度最大**。此时反转整个 Splay，自然将该点变为了深度最小的节点——根节点。

现在就可以访问任意一条链了：

```cpp
inline void split(int x, int y){
makeroot(x);
access(y);
return;
}
```

至此，访问链的操作已经完成，还需要支持加边和删边。

我们需要一个判断两点是否联通的方法。很简单，只要看它们所在的树的根节点是否相同就行了。

如何找到当前节点的根？在 $access$ 后，我们得到了一条从根到当前节点的链。这条链中序遍历的第一个节点显然就是树根。但是，记得处理懒标记。

```cpp
inline int findroot(int p){
access(p);
while (p && a[p].ls) pushdown(p), p = a[p].ls;
splay(p);
return p;
}
```

根据边的定义，$link$ 和 $cut$ 如下：

```cpp
inline void link(int x, int y){
makeroot(x);
if (findroot(y) == x) return;
a[x].pa = y;
return;
}
inline void cut(int x, int y){
makeroot(x);
if (findroot(y) != x || a[y].pa != x || a[y].ls) return;
a[x].rs = a[y].pa = 0;
pushup(x);
return;
}
```

总代码：

```cpp
#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
#define isdigit(x) ('0' <= x && x <= '9')
using namespace std;

const int MAXN = 100010;

template<typename types>
inline void read(types &x){
x = 0; int f = 1; char c = getchar();
while (!isdigit(c)){ if (c == '-') f = -1; c = getchar(); }
while (isdigit(c)) x = x * 10 + c - '0', c = getchar();
x *= f; return;
}
template<typename types>
void write(types x){
if (x < 0) putchar('-'), x = - x;
types k = x / 10;
if (k) write(k);
putchar(x - 10 * k + '0'); return;
}

int n, m;

#define ls ch[0]
#define rs ch[1]
struct Node{
int ch[2], pa;
int val, sum, rev;
} a[MAXN];
stack<int> s;
inline void pushup(int p){
a[p].sum = a[a[p].ls].sum ^ a[a[p].rs].sum ^ a[p].val;
return;
}
inline bool check(int p){
return a[a[p].pa].rs == p;
}
inline void revit(int p){
a[p].rev ^= true;
swap(a[p].ls, a[p].rs);
return;
}
inline void pushdown(int p){
if (a[p].rev){
revit(a[p].ls), revit(a[p].rs);
a[p].rev = false;
}
return;
}
inline bool isroot(int p){
return a[a[p].pa].ls != p && a[a[p].pa].rs != p;
}
inline void rotate(int x){
int y = a[x].pa, z = a[y].pa, dir = check(x), w = a[x].ch[!dir];
a[x].pa = z; if (!isroot(y)) a[z].ch[check(y)] = x;
a[y].pa = x; a[x].ch[!dir] = y;
a[w].pa = y; a[y].ch[dir] = w;
pushup(y), pushup(x);
return;
}
inline void splay(int p){
if (!p) return;
int r = p;
s.push(r);
while (!isroot(r)) s.push(r = a[r].pa);
while (!s.empty()) pushdown(s.top()), s.pop();
for (int pa = a[p].pa; pa = a[p].pa, !isroot(p); rotate(p))
if (!isroot(pa)) rotate(check(p) == check(pa) ? pa : p);
return;
}
inline void access(int p){
int r = p;
for (int c = 0; p; c = p, p = a[p].pa)
splay(p), a[p].rs = c, pushup(p);
splay(r);
return;
}
inline void makeroot(int p){
access(p);
revit(p);
return;
}
inline int findroot(int p){
access(p);
while (p && a[p].ls) pushdown(p), p = a[p].ls;
splay(p);
return p;
}
inline void split(int x, int y){
makeroot(x);
access(y);
return;
}
inline void link(int x, int y){
makeroot(x);
if (findroot(y) == x) return;
a[x].pa = y;
return;
}
inline void cut(int x, int y){
makeroot(x);
if (findroot(y) != x || a[y].pa != x || a[y].ls) return;
a[x].rs = a[y].pa = 0;
pushup(x);
return;
}

int main(){
read(n), read(m);
for (int i = 1; i <= n; ++i) read(a[i].val);
while (m--){
int op, x, y; read(op), read(x), read(y);
if (op == 0){
split(x, y);
write(a[y].sum), puts("");
}
else if (op == 1) link(x, y);
else if (op == 2) cut(x, y);
else{
makeroot(x);
a[x].val = y;
pushup(x);
}
}
return 0;
}
```