用Splay解决序列区间问题
用树剖解决序列问题上树
用LCT解决形状变化的树剖 ——VCode
前置技能：树链剖分，Splay
树剖要求到知道怎么回事的程度。
Splay要求到能支持基本操作的程度。
P1 给一个序列，问区间xor和。
A1 前缀和
P2 给一个序列，带修改，问区间xor和。
A2 树状数组/线段树
P3 给一棵树，带修改，问链xor和。
A3 树剖
P4 给一棵树，带修改，可以改变树上连边的情况，问链xor和。
这时候就需要我们的LCT出场了！
树链剖分与LCT
我们大家都会熟练剖分（啪）。
树链剖分常见有几种剖法。一种按长度剖，一种按重量剖。
当然为了解决我们的link和cut的问题，我们还需要一种剖分方法，就是瞎剖。
当然不是随机剖分，而是按照最近访问过的儿子和不是最近访问过的儿子来剖分。
也就是说，当我们访问了一个节点，我们就让根到这个节点之间的路径变成重链。
当然我们知道一个节点是不会有两个重儿子的，所以如果有冲突的地方就把原来的重边变回轻边，它已经不适合现在这个版本了。
特殊地，我们所想访问的那个节点的重儿子摸掉，使其变成轻儿子。因为这样一来，根到这个节点的的路径就是一条完整的重链了。
好了，现在你已经学会了LCT。
那么问题来了，这么个恶心的东西，代码要怎么写？！
Splay与树链剖分与LCT
树链剖分是用数据结构维护链的。但是这个链如此善变，肯定不能再用线段树了。于是我们需要考虑同样善变的Splay。
Splay可以解决一切线段树可以解决的问题，除了线段树优化建图。 ——VCode
这句话有bug吧。Splay怎么做SegmentTreeBeats。 ——Xenoacid
对于每个LCT上的节点，我们对应Splay上的一个节点。
对于每个LCT上的重链，我们开一棵以深度为关键字排序的Splay来维护。
当重链断开时，我们让Splay断开。
当有重链连接时，我们将Splay连接。
当询问一条链上的信息时，我们直接在Splay上操作。
现在我们知道用Splay可以维护所有重边了，但是轻边怎么办？
我们回忆一下Splay的根节点的父亲，一般都是空。但是我们可以利用一下这个信息，让轻边下面的点所对应的Splay的根节点的父亲设置为轻边上面的点。
于是我们就会看到一个神奇的现象，一个点 $A$ 是另一个点 $B$ 的父亲（Splay上），但点 $B$ 却既不是 $A$ 的左儿子也不是 $A$ 的右儿子。这时候我们就知道 $A$ 和 $B$ 之间有一条轻边。
也许你看到这里还是很迷，不知道怎么写。没关系，让我们继续看下去，你会发现，根本不需要维护原树，你所需要维护的只有一堆Splay而已。
实现
首先，假设我们已经会写了一个 $access(x)$ 操作，表示访问一下节点 $x$ ，使根到 $x$ 的路径变为重链。
当然还有你应该早就会了的 $splay(x)$ 操作，表示把 $x$ 转为这棵Splay的根。
Let’s go!
makeRoot(x)
反正我们都是动态树了，我们干脆就让它动一动，让它可以换根。
我们可以先访问一下新的根节点并 $splay$ 一下，然后打上子树反转标记。
这样一来，原来在左子树的东西就都跑到右子树了，相当于在原树上深度大小变了，也就是换了根。
void makeRoot(int now) {
access(now);
splay(now);
reverse(now);//Splay子树翻转
}
split(a, b)
让 $a$ 与 $b$ 之间的路径成为一条重链。
void split(int a, int b) {
makeRoot(a);
access(b);
splay(b);//礼貌性splay一下，同时可以简化cut代码。
}
link(a, b)
把 $a$ 和 $b$ 之间连一条新边。
先考虑一定合法，也就是 $a$ 和 $b$ 不在同一棵LCT中的情况。
void link(int a, int b) {
makeRoot(a);
node[b].fa = a;
//access(b);可以礼貌性访问一下，但没必要。
}
完美。
但是如果在同一棵LCT怎么办？
void link(int a, int b) {
makeRoot(a);
if(findRoot(b) == a) return;//加这一句就好了。
node[b].fa = a;
//access(b)
}
$findRoot(x)$ 就是找到 $x$ 的LCT的根。怎么写一会再说。
cut(a, b)
断开 $a$ 和 $b$ 之间的边。
先考虑一定合法，也就是 $a$ 和 $b$ 之间有边的情况。
void link(int a, int b) {
split(a, b);
node[b].son[0] = NIL;
node[a].fa = NIL;
update(a);//更新Splay信息
}
然后考虑什么情况下不合法：
- a和b不在一棵LCT里
- a和b在一棵LCT里，但a和b之间还有其他节点
优先考虑第二种情况。此时在Splay中的表现有两种情况：
- b为根时，a不是b的左儿子
- b为根时，a是b的左儿子，但a有右儿子
再考虑a和b不在同一棵LCT中的情况。显然满足第二种情况中说的“b为根时，a不是b的左儿子”。
于是可以在代码里加一句就可以了：
void cut(int a, int b) {
split(a, b);
if(node[b].son[0] != a || node[a].son[1] != NIL) return;
node[b].son[0] = NIL;
node[a].fa = NIL;
update(b);
}
还有我们刚才跳过的两个操作， $access(x)$ 和 $findRoot(x)$
access(x)
你会发现我们没有记录LCT的根，所以我们需要从下往上走。
沿着重链向上跳，遇到轻链就修改成重链，直到Splay根为空就可以了。
void access(int now) {
int last = NIL;//NIL = -1
while(~now) {
splay(now);//now变为Splay根
node[now].son[1] = last;//更改轻重边状态
update(now);
last = now;
now = node[now].fa;
}
}
findRoot(x)
看完 $access(x)$ 你真的就一点想法都没有吗？
int findRoot(int now) {
access(now);
splay(now);
while(now != NIL) {
pushdown(now);//Splay pushdown
if(node[now].son[0] == NIL) break;
now = node[now].son[0];
}
return now;
}
现在我们已经可以写出LCT了，需要区间异或就在Splay维护异或，需要深度就维护深度之类的即可，矛盾具有特殊性（具体问题具体分析）。
复杂度分析
不会，Tarjan告诉我是 $nlogn$
题
【模板】Link Cut Tree （动态树）
[HNOI2010]弹飞绵羊
LCT乍一看很难，但熟练之后会发现其实挺好写的。