一些前言
每次做树剖时打开题解...
使用 LCT 简单维护即可。
内心：？？？ code 好√8短啊 又很奇怪 有种不知道却又高端大气的感觉
这次来说清楚 LCT 到底是个什么东东
问题引入
有一棵树，需要支持操作：
- 修改节点 \(u\to v\) 路径值
- 查询节点 \(u\to v\) 路径值
很明显，这是一道易研定真的树剖模板。
但是我们加入如下操作：
- 断开边 \(u,v\)
- 链接边 \(u,v\)
这下 我们要使用 Link-Cut tree (LCT) 来维护这个问题。
前置知识
- splay 树 (必备)
- 重链剖分 (最好知道
不是都看这个了怎么能没学过树剖呢)
一些宏定义
ls(x) \(x\) 的左儿子
rs(x) \(x\) 的右儿子
fa(x) \(x\) 的父亲
一些概念
就像树剖一样，我们用一棵大线段树来维护一棵树，每条轻重链对应着一棵独立的线段树，只有在询问子树时才会打破这些线段树直接的壁垒 我们称该线段树为原树的辅助树
LCT ， 又叫实链剖分，在算法中辅助树是由一些 Splay 构成的
一些性质：
- \(1.\) 在 LCT 中，有若干棵辅助树，每棵辅助树对应着原森林的一棵完整的树
- \(2.\) 辅助树中的每个节点与原树的节点一一对应
- \(3.\) 每棵 Splay 连接着原树的一些路径，其中辅助树的中序遍历一定是原树从上到下连成的一条完整的链
- \(4.\) 辅助树中若干棵 Splay 不是独立的 按理来说，每棵 Splay 的根节点的父亲应为空 但在 LCT 中，每棵 Splay 根节点的父亲对应着原树中对应节点的父节点
- \(5.\) 因此，所有的操作都会在辅助树中进行，辅助树是一棵与原树对应且完整的树，并可以很方便的维护
等等！性质 \(4\) 是什么鬼？Splay 不是只有两个儿子节点吗？
这是一种十分特别的链接方式，我们称这种链接为虚边 这种虚边特别之处在于：儿子认父亲，父亲不认儿子
相对的，对于父亲儿子两两相认的边，我们称作实边
这有些抽象，可以借助图片理解
芝士原树：
辅助树可能是这个样子的：
这些实边都是用一棵 Splay 来维护着的。
原树和辅助树的关系
- \(1.\) 原树中的节点都只会在一个 Splay 中 也就是说，没有一个节点会在两个 Splay 里 ，每个 Splay 存储的节点是不同的
- \(2.\) 原树和辅助树的节点父亲没有任何关系
- \(3.\) 辅助树可以在 Splay 的帮助下轻松做到换根操作，这就是 Splay 的重要性质之一：在 \(\text{zig/zag}\) 选择中，树的中序遍历不会发生改变
- \(4.\) 在辅助树上，可以轻松完成轻实链的变换，这样就可以做到动态完成树链剖分
函数讲解
一些定义：
- \(ch_{x,0/1}:\) 节点 \(x\) 的左/右儿子
- \(tr[x].v\) 该节点的权值
- \(tr[x].sum\) 路径的权值
- \(tr[x].lz\) 翻转懒标记 与文艺平衡树差不多
先是一些与 Splay 没有区别的函数：
chk(x)
bool chk(int x){return rs(fa(x))==x;}
Pushup(x)
void Pushup(int x){tr[x].sum=tr[ls(x)].sum^tr[rs(x)].sum^tr[x].v;}
Pushdown(x)
void Pushdown(int x)
{
if(!tr[x].lz) return;
swap(ls(x),rs(x)),tr[ls(x)].lz^=1,tr[rs(x)].lz^=1;
tr[x].lz=0;
}
一些有修改的函数和新的函数：
isroot(x)
isroot(x)可以很轻松的判断当前点是否为当前 Splay 的根
根的定义就是没有父节点
那么如果当前节点的父节点不认当前节点，即父亲的左右儿子都不是当前节点，那么当前节点为此 Splay 树的根
bool isroot(int x){return ls(fa(x))^x&&rs(fa(x))^x;}