为次小生成树准备的一篇。重点会放在树上倍增。
题目的题意还是相当明确的。
图示：
图中AB两点的最近公共祖先就是那个红点点。
如何求取最近公共祖先：
已知有两个点A和B。
1.将A和B提高到同一个高度
2.它们一起往上跳。直到跳到最近公共祖先。
不难发现这两个操作都可以靠着暴力模拟完成。不难发现这样立马就会TLE。
这里我们的解决方案有很多种，不过这篇帖子选择介绍倍增的方案。
接下来我会一边讲述代码框架一边讲解倍增。
1.初始化
关于倍增
顾名思义”成倍增长“。一般默认是二次幂成倍增长。
它可以把时间复杂度为O(n)O(n)O(n)的暴力枚举优化成O(logn)O(logn)O(logn)。
这之中的核心诀窍就是：一个数可以有一堆二的次幂拼凑而成。
这个说法的最直观的体现是二进制。
接下来我们会逐渐感受到倍增的魅力。
pospospos和xxx的含义：xxx是当前节点，pospospos是xxx节点的父亲节点。
fff数组的含义：f[i][j]表示第i个点网上爬2j2^j2j个点后到达的祖先节点。
f[x][i]=f[f[x][i−1][i−1]f[x][i]=f[f[x][i-1][i-1]f[x][i]=f[f[x][i−1][i−1]
这个公式是根据数学结论推导出来的。
因为：2i−1∗2i−1=2i2^{i-1}*2^{i-1}=2^i2i−1∗2i−1=2i 所以就有了上面的那行代码。
在根据这行代码更新f[i][j]f[i][j]f[i][j]之前，我们需要把所有的f[x][j−1]f[x][j-1]f[x][j−1]更新好。
所以forforfor循环从小到大遍历。
deepdeepdeep数组的含义：顾名思义，它记录每个结点的深度。
deep[x]=deep[pos]+1deep[x]=deep[pos]+1deep[x]=deep[pos]+1 的意思是：当前节点的深度=其父节点的深度+1
2.将aaa和bbb两个点升到同一高度
首先，我们打算将a往上拎，所以肯定要确保deep[a]>deep[b]deep[a]>deep[b]deep[a]>deep[b]。
把a往上拎的过程需要用到倍增的思想，具体原理前面已经解释过了。（for循环从小到大遍历还是从大到小遍历都可以）
然后这时候如果aaa与bbb相等，那么证明当前已经到达最近公共祖先了，可以（其实是必须，要不然后面就会出问题）直接返回。
3.点aaa和点bbb一起往上跳到最近公共祖先（这一段也是我不太确定的，如果有疑问和质疑欢迎私信我or直接在评论区提出。评论我都会看的，感谢。）
接下来就是一步步往上跳。
这句判断还是很有意思的。
如果点aaa往上跳2j2^j2j到达的顶点和点bbb往上跳2j2^j2j步到达的顶点是相同的就跳过。
可能会有人认为：如果相同那不就代表是最近公共祖先了？直接return不好吗。
它确实是公共祖先，但不一定是最近，看这幅图：
现在点aaa往上跳2j2^j2j个点到达了绿点。绿点确实是公共祖先，但并不是最近。
就算真的是红点。
20+20+21+22+⋅⋅⋅+2n−1=2n2^0+2^0+2^1+2^2+···+2^{n-1}=2^n20+20+21+22+⋅⋅⋅+2n−1=2n
所以说最后是：
而不是：
另：关于为什么是从大到小枚举i而不是从小到大枚举？
由于需要加的距离实际上是固定的，我们先加大的，就可以用小的补（每个2i2^i2i都只能加一次）。
就像是往一个箱子里面装海绵。
前面你不管用大海绵还是小海绵装，最后你的箱子里面总归还是有缝隙。
如果你先用大海绵，你后面就可以用没用的小海绵来填充缝隙。
但是如果你先用小海绵，你后面想填充缝隙时，就会发现大海绵无法使用。
