[参考资料]
一.动态树问题
树上查询问题是指，给定一个图论中的树结构，需要对树上的子树或者链进行一系列改查的问题。
和序列问题中一般常说的“动态”和“静态”不同。 动态树问题一般指在树结构发生改变的情况下，在树上对子树/链进行查询/修改问题。
- 注意：一般对于纯换根（change root）操作，不视为是动态树问题。
二.Link/Cut Tree
LCT本质是splay森林，也理解成“结构树套平衡树”，它的作用是维护一棵有根树的动态链剖分。
实链剖分
树上的每一个非叶子节点，任意选择它的一个儿子，把(x,v)当作实边，那么其它儿子跟x的边就是虚边。可以发现一棵树的实链剖分是很多种的，它的存在只是为了更好构建LCT。
Splay维护一条实链
splay是一棵平衡二叉树，它通过每个节点的深度作为点权，维护一棵二叉树。
中序遍历一棵splay，我们就得到了这个splay维护的一条实链。splay最左侧的节点是实链最顶部的节点(即深度最浅的节点)，splay最右侧的节点是实链最底部的节点(即深度最深的节点)。
虚边发挥什么作用
我们把一棵树划分成很多实链，然后每一棵splay对应一条实链。但是树上的虚边呢？答：它们被保留在最外层的结构树中，用于连接不同的splay，形成一棵结构树。
在结构树上，每一棵splay都有一条虚边指向该splay的父节点(这里的父节点指：splay所维护的实链的最顶端节点的父节点)。但是父节点没有边指向该节点。所以我们在LCT上的一些操作(除了splay的基础操作)都是自底向上的。
- 原树的 Father 指向不等于结构树中splay的 Father 指向。（除了最顶部的splay节点没有father，其它splay都有father - 从宏观角度上看）
在动态维护实链剖分的过程中，LCT会进行虚实边的交换，这也就是实现了动态维护树链剖分。
关于LCT的一些复杂度说明
虽然我不太会证明复杂度，但是可以先提一句LCT的所有操作，都是均摊\(O(logn)\)的。（前提是pushup、pushdown、merge节点..函数的复杂度是\(O(1)\)的）
模板以及相应函数说明
旧函数(注意细节以及原因)
（1）Splay和Rotate：因为一棵splay的根节点和树的根节点并不是同一个根，所以要根据isRoot(x)来判断x是否是splay的根（当一个点既不是它父亲的左儿子，又不是它父亲的右儿子，它就是当前 Splay 的根）。
新函数
（1）Access(x)： 把x到root的路径上的所有的边都变成实边，同时存在同一棵splay中。
（2）MakeRoot(x): 把节点x设置为树的根节点。
（3）Link(x, y): 如果x和y不在同一棵树上，则连接x、y两个节点。
（4）Cut(x, y): 如果x，y两个节点之间存在边，则割掉这条边。
（5）Find(x): 查询x节点在树上的根节点。
（6）Split(x, y)操作？这个操作实际上是通过MakeRoot和Access来实现的，意义是：把x到y的路径从树中抽出来。
模板代码
查看代码
namespace LCT {
const int N = 1e5 + 11;
int son[N][2], fa[N], wt[N], tg[N], Val[N];
// wt是点权，Val是pushup之后的合并权值
int chk(int x) { return son[fa[x]][1] == x; }
// 判断一个节点是不是splay的根节点(注意不是树根)
int isRoot(int x) { return son[fa[x]][1] != x && son[fa[x]][0] != x; }
void reverse(int x) { tg[x] ^= 1, swap(son[x][0], son[x][1]); }
void pushup(int x) {
Val[x] = wt[x];
if (son[x][0]) Val[x] ^= Val[son[x][0]];
if (son[x][1]) Val[x] ^= Val[son[x][1]];
}
void pushdown(int x) {
if (tg[x]) {
if (son[x][0]) reverse(son[x][0]);
if (son[x][1]) reverse(son[x][1]);
tg[x] = 0;
}
}
void rotate(int x) {
int y = fa[x], z = fa[y], k = chk(x), s = son[x][!k];
if (z && !isRoot(y)) son[z][chk(y)] = x;
if (s) fa[s] = y;
son[y][k] = s, son[x][!k] = y, fa[x] = z, fa[y] = x;
pushup(y), pushup(x);
}
// 在splay从上往下pushdown, 只pushdown一个splay而不是结构树
void Update(int x) {
if (fa[x] && !isRoot(x)) Update(fa[x]);
pushdown(x);
}
// 把x节点zig-zag转到splay的根节点
void splay(int x) {
Update(x);
for (; !isRoot(x) && fa[x]; rotate(x))
if (!isRoot(fa[x]))
rotate(chk(fa[x]) == chk(x) ? fa[x] : x);
pushup(x); // 最后不能删
}
// 打通x到当前根节点的通路(x和root放在同一个splay中)
int access(int x) {
int p = 0;
for (; x; p = x, x = fa[x])
splay(x), son[x][1] = p, pushup(x); // fa[p]本来就是x
return p; // access 到根的最浅节点, 两次access就是LCA
}
// 注意：make_root之后x不一定是splay的根，后续按需 splay(x)
void make_root(int x) { access(x), splay(x), reverse(x); }
// 链接两棵子树，先把 v 树转到根， 然后虚链连上 u节点
void link(int u, int v) { make_root(u), splay(u), fa[u] = v; }
// 删掉一条边
void cut(int u, int v) {
make_root(u), access(v), splay(v);
if (fa[u] != v || son[v][0] != u) return; // 特判不合法
fa[u] = son[v][0] = 0, pushup(u), pushup(v);
}
// 获取到当前根节点，即access之后深度最浅的点
int find_root(int x) {
access(x), splay(x);
while (son[x][0]) pushdown(x), x = son[x][0]; // 必须先pushdown
return x;
}
// 获取一条树链 (u - v)
void split(int u, int v) { make_root(u), access(v), splay(v); }
} // namespace LCT
using namespace LCT;
三.LCT能做到解决的问题
1. LOJ2187-三叉神经树【LCT + Splay上维护最长后缀 + LCT上pushdown加法标记】【提交记录】
我们把0设置成-1，那么一个节点的输出就是: sum(son[0], son[1], son[2]) > 0 ? 1 : -1。
每次操作修改一个节点的权值，比如说把：-1变成1，那么对于后缀路径上所有：sum == -1的节点都会切换输出。
所以使用LCT维护一条路径上的最长后缀树链，满足链上的节点sum==-1或者sum==1即可。（注意到，sum=3或者sum=-3的节点遇到儿子切换输出的时候，他们的输出是不受一个儿子的变化而变化的。）
然后考虑LCT的pushdown和splay上维护最长后缀的技巧：
- 维护最长后缀：
- LCT上的pushdown：
标签：splay,LCT,int,son,问题,fa,动态,节点 From： https://www.cnblogs.com/guanjinquan/p/16723534.html