LCT
算法简介
LCT 是一种动态维护森林连通性、路径信息的数据结构，时间复杂度为 $O\left(n\log n\right)$。
算法思想
LCT 将树上路径分为实链和虚链，每个非叶结点仅向他的一个儿子结点连实边，其余儿子连虚边。
每个实链用一棵 splay 保存，同一棵树的 splay 之间靠虚边连接，每个 splay 维护一个深度递增的结点序列。
每棵 splay 树的根结点的父结点(注意，不是原树的父结点)设为这个 splay 深度最小的结点的在原树中的父节点。
LCT 的核心操作为 $\text{access}(x)$。
$\text{access}(x)$ 的目的是将 $x$ 结点到根结点的路径变为一条实链，便于后续操作，方法很简单，不断向上修改父子关系即可。
我们还想得到两个非根结点的路径信息，我们可以先将其中一个结点变为根结点，再使用 $\text{access}$ 操作。
将一个结点变为根结点即为 $\text{makeroot}(x)$ 操作，方法为先 $\text{access}(x)$ ，再颠倒这条实链。
颠倒实链可以考虑 $\text{splay}(x)$ ，$x$ 是 splay 中深度最小的点，无右儿子。
因此交换 $x$ 左右儿子， $x$ 无左儿子，成为深度最大的点，最后打上懒标记即可。
考虑到 LCT 维护的是森林，为了判断连通性，我们还需要 $\text{findroot}(x)$ ，即得到结点 $x$ 所在原树的根结点。
方法为先 $\text{access}(x)$ ，便可以得到结点 $x$ 到根结点的路径。
考虑到原树的根结点为深度最小的点，我们只需要 $\text{splay}(x)$ ，然后从结点 $x$ 出发不断访问右节点即可，但要注意下放懒标记。
有了这些基本操作，便可以实现树上的连边、删边、两点间的路径信息维护等操作了。
代码模板
给定 $n$ 个点和权值，接下来 $m$ 个操作。
- 询问 $x$ 到 $y$ 路径的权值的异或和，保证 $x$ 与 $y$ 已经连通
- 连接 $x$ 与 $y$ ，若 $x$ 与 $y$ 已经连通，则无视这个操作
- 删除 $x$ 与 $y$ 的连边，若 $x$ 与 $y$ 无连边，则无视这个操作
- 把结点 $x$ 的权值改为 $y$
代码练习
路径信息维护
例题一
给定一棵 $n$ 个结点的树，每个结点初始权值为 $1$ ，接下来 $q$ 个操作：
- 将 $u$ 到 $v$ 路径上所有点权值加上 $c$
- 删除 $u_1$ 与 $v_1$ 的连边，添加 $u_2$ 与 $v_2$ 的连边，保证操作后仍然是一棵树
- 将 $u$ 到 $v$ 路径上所有点权值乘上 $c$
- 查询 $u$ 到 $v$ 路径上权值和
一道简单LCT练手题，多加几个懒标记即可。
例题二
给定一棵以 $1$ 为根节点的有根树，初始时每个节点的颜色互不相同，定义路径的权值为路径节点的颜色种数。接下来 $m$ 个操作：
- 将根节点到 $u$ 的路径染成一个从未出现的颜色
- 查询 $u\to v$ 路径权值
- 查询所有以 $u$ 为根的子树节点中到 $1$ 节点的路径的最大权值
考虑维护每个点 $u$ 到根节点的路径权值，记为 $\text{dis}(u)$，不难发现操作 $2$ 等效于查询 $\text{dis}(u)+\text{dis}(v)-2\text{dis}(\text{lca}(u,v))+1$。
对于操作 $3$，等价于查询以 $u$ 为根的子树的最大权值。
接下来重点考虑操作 $1$，联想到 $\text{LCA}$ 的 $\text{access}$ 操作。
假如一开始所有连边均为虚边，不难发现 $\text{dis}(u)$ 等于 $u$ 到根节点的虚边数 $+1$，然后操作 $1$ 正好等价于 $\text{access}(u)$ 操作。
然后考虑更新答案，发现 $\text{access}(u)$ 过程中将 $u\to v$ 的实边变成虚边只需要将 $v$ 子树所有点权值加一即可，相对的虚边变实边对应子树点权减一。
考虑再建一棵线段树维护，另外注意 $\text{access}(u)$ 过程中涉及的节点 $v$ 对应的是 $\text{splay}$ 子树的根节点，不是真正需要的深度最小的点。
为了找到深度最小的节点可以考虑利用 $\text{splay}$ 的 $\text{push_up}$ 维护。总时间复杂度 $O(n\log n)$。
ps. 树剖也可做，但比较复杂，需要魔改，可以参考这篇 题解
生成树维护
例题一
求最小生成树。
考虑 $\text{splay}$ 维护一条链上的最长边，如果新加入边 $(u,v)$ 导致成环，且原树中 $u\to v$ 路径上的最长边大于新加入的边。
则删去最长边再加入新加入边。然后发现最长边比较难直接维护，于是考虑将边也是为新节点，点权等于边权，原图中的点的点权为 $0$。
$\text{splay}$ 维护最大点权以及点权最大的点的编号即可。
关于删边操作直接 $\text{split}(u,v)$ 后找到最长边对应的点的编号，然后将该编号 $\text{splay}$ 到根节点。
不难发现该节点在 $\text{splay}$ 中的左树恰好为 $u\to v$ 链删去该边后的一半，而右树代表另一半链。
同时 $\text{split}$ 后 $u$ 为原树中的根节点，于是将该编号在 $\text{splay}$ 中的左右儿子的父节点置 $0$ 即可分裂为两棵树，然后再加入新边即可。
注意空间要开 $O(n+m)$。
例题二
定义生成树的权值为生成树权值最大的边减去权值最小的边，问权值最小的生成树。
考虑从大到小加入边，当遇到环时删去权值最大的边。每次加入边后如果图构成树则计算当前树上最大边减去最小边。
显然这是类似单调队列的贪心做法，但是本人暂时想不出正确性的证明。
例题三
给定 $n$ 个点 $m$ 条边，边 $e_i$ 的边权为 $(a_i,b_i)$。定义路径 $L$ 的长度为 $\max_{e_i\in L}a_i+\max_{e_i\in L}b_i$。求点 $1$ 到点 $n$ 的最短路。
考虑将边按 $a_i$ 排序，然后依次加入边，同时维护生成树 $T$ 使得生成树的最大 $b_i$ 最小，然后答案为 $a_i+\max_{e_i\in T} b_i$。
变根 LCA 维护
$\text{LCT}$ 本身支持换根，所以只需要怎么考虑求 $\text{LCA}(u,v)$。
考虑先 $\text{access}(u)$ 这样根节点到 $u$ 的路径变实边，于是根节点到 $v$ 的路径的第一条虚边一定从 $\text{LCA}(u,v)$ 出发。
不难发现 $\text{access}$ 的过程就是不断从一条实链沿着虚边跳到另一条实链的过程，于是$\text{access}$ 的过程中最后一次 $\text{splay}$ 的节点就是 $\text{LCA}$。
双连通分量维护
题意
给定一个连通图，接下来两种操作：
- 询问 $u,v$ 间的关键路径，定义关键路径为删除改路径讲导致 $u,v$ 不连通的路径
- 删除边 $u,v$，保证删边后图仍然连通
题解
不难发现，如果根据边双连通分量进行缩点，则 $u,v$ 间的关键路径等于 $u,v$ 缩点后两点间的路径长度(同时此时图上所有边都是桥)。
考虑离线操作后逆序处理，加边的同时遇到环就缩点。
利用并查集维护，缩点时暴力将 $u,v$ 路径所代表的 $\text{splay}$ 树的所有点的代表节点设置成根节点即可，可以证明均摊复杂度 $O(1)$。
然后 $\text{LCT}$ 维护树上两点距离，注意由于对 $\text{splay}$ 树进行了缩点，所以需要在跳虚边时更新 $fa$。
发现只需要修改 $\text{access}$ 操作即可。总时间复杂度 $O(n\log n)$。
ps.也可以令初始时所有边权为 $1$，将缩点操作视为将 $u,v$ 路径上的边权置 $0$，其他操作不变，$\text{LCT}$ 或树剖维护均可。
子树信息维护
题意
给定 $n$ 个点，给定两种操作：
- 加边操作，保证加边后不会出现环
- 询问经过 $(u,v)$ 边的路径数
题解
子树信息需要维护虚儿子和实儿子信息和，实儿子利用 $\text{ch}(k,0/1)$ 维护，虚儿子只需要额外记录即可。
以子树节点个数为例，得到 $\text{push_up}$ 操作
void push_up(int k){ s[k]=s[lch(k)]+s[rch(k)]+si[k]+1;//注意只有根节点的信息是正确的 }
然后需要维护 $si$ 的值，发现只需要修改直接涉及增删虚边的函数即可，即 $\text{access}$ 和 $\text{link}$ 操作。
void access(int k){ for(int t=0;k;t=k,k=fa[k]){ splay(k); si[k]-=s[t]; si[k]+=s[rch(k)]; rch(k)=t; push_up(k); } } void link(int u,int v){ makeroot(u); if(findroot(v)!=u){ splay(v);//要确保v没有父结点 si[v]+=s[u]; fa[u]=v; push_up(v); } }
注意，如果需要维护点权极值等信息时，可以用 $\text{set}$ 维护 $si[k]$。
不难发现，对询问操作，可以先断开 $u,v$，则答案为 $\text{sz}(u)\times \text{sz}(v)$。
