更新时间：2021-12-02 16:20
动态树问题 ，是一类要求维护一个有根树森林，支持对树的分割, 合并等操作的问题。由RobertE.Tarjan为首的科学家们提出解决算法Link-Cut Trees，简称lct。
动态树问题, 即要求我们维护一个由若干棵子结点无序的有根树组成的森林，支持对树的分割, 合并, 对某个点到它的根的路径的某些操作, 以及对某个点的子树进行的某些操作。
维护一个数据结构, 支持以下操作:
很多资料中将“动态树”特指为link-cut-tree这种数据结构，而事实上动态树是一类问题的通称，说白了就是上文中各种数列的维护改到树上来做，例如查询链上和、子树和、修改节点数值等等。
处理这一类问题的最基本思路就是将树上的问题重新转化到链上，然后套用上文中的各种方法进行解决，而这种转化往往是基于给树上的节点按照某种顺序标号，然后每次处理标号连续的一段或若干段。
而另外一些涉及树的形态变化的问题则难以利用这种“标号”的思路进行维护（因为一个简单的修改可能会导致整棵树的标号出现不规则的更改）。为了解决这些问题，以RobertE.Tarjan为首的科学家们研究出各种实用的、具有良好理论复杂度和较大常数的数据结构，直接对树的形态进行维护。本部分会简要介绍DFS序和树链剖分两种标号法和link-cut-tree的应用，理论部分的最后会提及LCT解决子树问题的一个方案（自调整TopTree）。然后以几道经典题为本文画上句号。
旋转及连接函数
树结构的基础操作之一，可完成节点的旋转操作。
splay
在splay上的一般操作都基于伸展操作：假设想要对一个二叉查找树执行一系列的查找操作，为了使整个查找时间更小，被查频率高的那些条目就应当经常处于靠近树根的位置。于是想到设计一个简单方法， 在每次查找之后对树进行重构，把被查找的条目搬移到离树根近一些的地方。splay应运而生。伸展树是一种自调整形式的二叉查找树，它会沿着从某个节点到树根之间的路径，通过一系列的旋转把这个节点搬移到树根去。
Access
ACCESS 操作是动态树 的所有操作的基础. 假设调用了过程ACCESS(v), 那么从点v 到根结点的路径就成为一条新的链. 如果路径上经过的某个结点u 并不是它的父亲节点parent(u) 的子节点, 那么由于parent(u) 的子节点会变为u , 原本包含parent(u) 的Preferred Path将不再包含结点parent(u) 及其之上的部分.
Find Root
在ACCESS(v) 之后, 根结点一定是v 所属的splay的最小结点. 我们先把v 旋转到它所属的splay的根.。再从v 开始, 沿着splay向左走, 直到不能再向左, 这个点就是我们要找的根结点。由于使用的是Splay Tree数据结构保存splay, 我们还需要对根结点进行Splay操作。
Set Root
在ACCESS(v) 之后, 根结点一定是v 所属的splay的最小结点. 我们先把v 旋转到它所属的splay的根。此时节点v一定是splay深度最小的节点，将整条链旋转就可将v转到实数的根。考虑到时间复杂度，可以打懒标记。
Cut
先访问v, 然后把v 旋转到它所属的splay的根, 然后再断开v 在它的所属splay中与它的左子树的连接, 并设置
Join
先访问v , 然后修改v 所属的splay的Path Parent 为w, 然后再次访问v。
时间复杂度分析
可以看出, 除ACCESS 操作之外的其它操作, 其均摊时间复杂度至多为O(log n). 所以只用分析ACCESS 的时间复杂度.在ACCESS 操作的分析中, 我们将ACCESS 的时间分为两部分计算. 第一部分我们证明切换子节点的次数是均摊O(log n) 的; 第二部分我们证明一次ACCESS 中的所有Splay 操作的总时间是均摊O(log n) 的.
染色[SDOI2011]
题目描述：
给定一棵有n个节点的无根树和m个操作，操作有2类：
1、将节点a到节点b路径上所有点都染成颜色c；
2、询问节点a到节点b路径上的颜色段数量（连续相同颜色被认为是同一段），如“112221”由3段组成：“11”、“222”和“1”。
请你写一个程序依次完成这m个操作。
输入格式：
第一行包含2个整数n和m，分别表示节点数和操作数；
第二行包含n个正整数表示n个节点的初始颜色
下面行每行包含两个整数x和y，表示x和y之间有一条无向边。
下面行每行描述一个操作：
“C a b c”表示这是一个染色操作，把节点a到节点b路径上所有点（包括a和b）都染成颜色c；
“Q a b”表示这是一个询问操作，询问节点a到节点b（包括a和b）路径上的颜色段数量。
输出格式：
对于每个询问操作，输出一行答案。
参考代码：