持续更新中......
导言：
树作为一种在算法竞赛中十分重要的数据结构，也在图论方面有着重要作用，所以我想花一些时间讲一下关于树的知识。
1.树的性质与遍历：
这一部分较为简单，所以简单带过。
树是一种特殊的图，树必须连通。一颗NNN个结点的树有N−1N-1N−1条边。
如图，结点1和结点2为例，结点1被称为结点2的父结点，同时，结点2就是结点1的子结点。
结点1与结点2和结点4是同一个深度，所以被称为兄弟结点，结点1没有直接的上级，所以被称为根结点。再看到结点5他没有任何一个下属，像这样的结点就被称作叶子结点。
此外有根结点的树被称为有根树，自然，没有根结点的树就叫无根树了。
除了这些，还有一些比较重要的概念，比如结点5，从结点5的父结点开始一直到根结点经过的所有结点就称为该结点的祖先，同样，也会有后代这个概念，意思也就是把前面的反着来而已。
讲完基础概念了，现在可以说遍历了，一般使用 DFSDFSDFS 来遍历，也比较简单，如果不会的话，可以自学一下深度优先搜索算法，现在使用一道例题来带过。
LUOGUP5908LUOGUP5908LUOGUP5908:
思路分析：
按照题意添加双向边，然后遍历除了父结点外的边，然后计算深度，判断深度是否小于等于ddd即可，是一道简单的基础题。
2.树的直径与重心：
导言：
树作为一种特殊的结构，其自身也具有一些特殊的性质来帮助解决一些树中的问题，这次将与树的重心与直径为例来求解问题。
树的直径（TREEDIAMETERTREE DIAMETERTREEDIAMETER）:
定义：树中任意两个节点之间的最长路径的长度。
求解直径：
如何求解直径？最朴素的做法就是暴力枚举 i,ji,ji,j 的两个点然后每一个再跑一遍 DFSDFSDFS 就行了，可以是可以，但是 O(N3)O(N^3)O(N3) 的时间复杂度还是逆如天，所以一个高效的 O(N)O(N)O(N) 方法就出现了。
大概的思路就是跑两遍 DFSDFSDFS 来求解，接下来给出具体步骤。
（1）随意选择一个结点 xxx 作为起点，然后进行第一遍 DFSDFSDFS，同时记录下其他结点距离 xxx 的距离。遍历完之后，可以找到距离 xxx 最远的结点，将他记为 yyy。
（2）将 yyy 作为起点，重复上述的操作，再次找到距离 yyy 距离最远的结点，记作 zzz。
（3）此时 yyy 与 zzz 就是直径的两个端点。这样就求出了这棵树的一条直径。
证明比较复杂（实则是我太弱了），所以这里就不证明了，下面给出一道例题。
LUOGUP1099LUOGUP1099LUOGUP1099:
思路分析：
首先按照刚才两遍 DFSDFSDFS 的方法求出树的直径，然后在直径上找最优核，这里可以使用滑动窗口来高效解决，最后再计算非直径节点到直径的最大距离。
树的重心（CENTROIDCENTROIDCENTROID OFOFOF TREETREETREE）:
定义：树的重心是树中的一个特殊节点，满足：将该节点移除后，剩余的各个连通子树的节点数量的最大值是所有节点中最小的。
树的重心的四个重要性质：
1.平衡性：删除重心后，剩余的每一棵子树的节点数都不超过原树总节点数的一半（≤ n/2）。
2.唯一性 / 相邻性：一棵树的重心最多有两个。如果存在两个重心，那么这两个节点一定是相邻的。
3.路径最优性：树中所有节点到重心的距离之和最小。若有两个重心，它们到所有节点的距离之和是相等的。
4.连通性：在一棵树上，所有的重心都位于同一条路径上。
找重心的方法：
1.任选根节点，用 DFS 算出每个节点的子树大小。
2.对每个节点，计算删除后最大连通块大小（子树最大值与父方向连通块取大）。
3.最大连通块最小的节点就是重心，最多两个且相邻。
LUOGUP1395LUOGUP1395LUOGUP1395:
思路分析：
就是关于树的重心，上面已经讲过了，但这里我使用的是 BFSBFSBFS。
3.最近公共祖先（LCALCALCA）:
概念：
什么是最近公共祖先？
每年过年走亲访友的时候，“认亲戚”是一个常见的话题。两个亲戚在聚会中碰面并开始聊天，不可避免的谈论辈分和称呼的话题。对他们而言，最简单的开始方法莫过于：“我爸跟你爸是兄弟”，“咱俩太爷爷是同一个人”等。
而最近公共祖先就是两个结点最接近的直系长辈。
如何求解任意两个结点的 LCALCALCA:
（1）首先找到两个结点中较深的结点，设那个结点为 uuu，不停将 uuu 往上提，直到 uuu 的深度和 vvv 一样。
（2）同时将 uuu 和 vvv 一起往上提，直到它们一样为止。
是不是听起来，求解 LCALCALCA 很简单，接下来我们来看一道例题。
LUOGUP3379LUOGUP3379LUOGUP3379:
思路分析：
和刚才说的步骤一样，但是要先跑一遍 DFSDFSDFS 遍历每一个结点的深度。
但是你交上去会发现超时了，因为对于每一次询问，最坏的情况，就是遍历了整颗树，单次时间复杂度 O(N)O(N)O(N)，显然会超时。
优化：
这里有两种常见的优化方法：倍增算法和 TarjanTarjanTarjan 算法，在这里我只介绍倍增算法。
先观察一下我们之前的代码差在哪里，它每次往上提的速率太低了，有些不必要的结点花了许多时间。所以倍增算法就是将这段时间尽量压缩小一点，下面给出具体思路和方法。
现在将一个结点往上移动 hhh 的高度，可以考虑二进制分解，使得时间和空间上都令人满意。把 hhh 拆分成二进制数，然后如果第 iii 位有 111，就向上提 2i2^i2i 层，这样时间复杂度就是 O(logN)O(logN)O(logN)，空间复杂度也就只有 O(logN)O(logN)O(logN) 完全可以接受。
（1）如何快速求出一个点的所有 2k2^k2k 级祖先？
继续按照套路来思考这个问题：每个结点所需要的信息是由父结点计算而来的，还是在回溯的时候由子结点的信息计算的呢？考虑计算的是某一个结点的祖先，那么肯定是要用它祖先结点的信息来计算。如何计算它的 2k2^k2k 级祖先呢？使用暴力算法显然不行，但是可以考虑到：2k−12^{k-1}2k−1+2k−12^{k-1}2k−1=2k2^k2k。这就启发我们由 2k−12^{k-1}2k−1 来推 2k2^k2k。而本题中 kkk 的上限只有 181818，所以方法可行。
（2）如何优化上提一个结点的过程？
由于可以发现本题里 kkk 的上限非常小，所以只用暴力枚举 kkk 就可以了。
完整代码如下：
4.树的重链部分：
导言：
树的重链部分作为一种进一步划分树的结构的方式，具有良好的性质。它将树上的信息划分到链上，使得大部分处理序列问题的数据结构得以在树上应用，这里会来讲一下树的重链部分。
先给出一道题目，然后慢慢讲。
LUOGUP3384LUOGUP3384LUOGUP3384 :
现在引入一个概念 DFSDFSDFS 序，什么是 DFSDFSDFS 序？假设维护一个序列，初始为空。从树的某个结点开始对树进行 DFSDFSDFS，每到达一个新的结点，就添加这个结点，最后会得到一个长度为 NNN 的序列，如图，从1开始的 DFSDFSDFS 序应为 1,2,4,6,7,8,5,31,2,4,6,7,8,5,31,2,4,6,7,8,5,3。
根据结点编号的 DFSDFSDFS 序，可以得到对应点权照结点 DFSDFSDFS 序排列的序列 www。尝试使用线段树维护这个序列。如果想把 1 到 6 号结点的路径上的点权都加上 zzz，注意到这条路上的结点 DFSDFSDFS 序上恰好是前四个，于是只需要对
