适用于解决一棵树中只需要用到少部分点的时候，将需要用到的点提出来单独建一棵树。

在树链剖分时我们把树中结点最多的子树根结点叫做重子结点，也就是说，在树上启发式合并的过程中，我们需要先计算所有轻子结点的信息（每计算一个轻子结点之后都要删除这个结点对当前答案的影响），最后计算重子结点的信息（保留重子结点对当前答案的影响），然后再计算前面的轻子结点（这一次计算要保留结点对当前答案的影响）这样的树中，我们首先计算2子树的信息，然后计算3子树的信息的时候我们又要把2子树清空，每计算一个

（未更新完、做到相关题再更新相关部分。

就是一个长这样的树，树中每个结点都有一个父结点（除了根结点没有父结点）和最多两个子结点，每个结点的左儿子一定比它小，右儿子一定比它大。这棵树的先序遍历很容易知道就是：1 2 3 4 5 6 7 （根左右）我们还可以从另一个角度理解先序遍历：把整棵树映射到 x 轴上，也就是把它压扁也就是这样：先序遍历从左到右读出来就可以了。

对于一个有向图，分量中任意两点u，v，必然可以从u走到v，且从v走到u，这样的分量叫做连通分量如果一个连通分量加上任意一个点都不是连通分量了，就把它叫做。

基环树其实并不是树，是指有n个点n条边的图，我们知道n个点n-1条边的连通图是树，再加一条边就会形成一个环，所以基环树中一定有一个环，长下面这样：由基环树可以引申出和基环内向树如下，特点是每个点的出度为1基环内向树如下，特点是每个点的入度为1下面放点题，做到相关题目随时更新。

/ 分别表示根结点编号和当前用到哪个结点int val[N];// 结点权值int pri[N];// 结点优先级int sz[N];// 结点子树大小// 结点左右儿子fhq-treap依然是一棵中序遍历按照val排序的平衡树，但是它的结构依赖于pri优先级，一个结点的两个儿子的pri一定比这个结点要小，然后我们随机取pri，就可以保证treap基本平衡。

在dp中的具体使用方法就是把前面计算过的dp值存进数据结构中进行维护。

数组记录每个版本的根结点即可。和主席树类似，开一个。

二叉排序树是一颗空树，或者满足：左子树比根小，右子树比根大，且左右子树都是二叉排序树中序遍历一棵二叉排序树可以得到递增的有序序列。