这是本文档旧的修订版！
动态树
算法简介
动态树简称 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$ 个操作。
操作 $0$ ：询问 $x$ 到 $y$ 路径的权值的异或和，保证 $x$ 与 $y$ 已经连通。
操作 $1$ ：连接 $x$ 与 $y$ ，若 $x$ 与 $y$ 已经连通，则无视这个操作。
操作 $2$ ：删除 $x$ 与 $y$ 的连边，若 $x$ 与 $y$ 无连边，则无视这个操作。
操作 $3$ ：把结点 $x$ 的权值改为 $y$。
一道LCT裸题，直接上代码。
例题二
给定一棵 $n$ 个结点的树，每个结点初始权值为 $1$ ，接下来 $q$ 个操作：
操作 $1$ ：将 $u$ 到 $v$ 路径上所有点权值加上 $c$。
操作 $2$ ：删除 $u_1$ 与 $v_1$ 的连边，添加 $u_2$ 与 $v_2$ 的连边，保证操作后仍然是一棵树。
操作 $3$ ：将 $u$ 到 $v$ 路径上所有点权值乘上 $c$。
操作 $4$ ：查询 $u$ 到 $v$ 路径上权值和。
一道简单LCT练手题，多加几个懒标记即可。
生成树维护
例题一
求最小生成树。
考虑 $\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$。
