为什么我不放在学习讨论里呢？
因为我不敢
……
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
在阅读此文之前，建议先阅读OI Wiki-RMQ或ACGO 学习-ST表，或者你已经了解过求解RMQ问题的算法。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
两个点的LCA（Lowest Common Ancestor，最近公共祖先），就是这两个点的公共祖先里面，离根最远的那个。LCA问题在树上问题中比较常见，本文仅介绍四种LCA求法，更多详见OI Wiki-最近公共祖先。
①朴素做法
朴素做法应该是比较好想的算法，它的做法是这样的：
1. 在输入完整棵树之后，跑一遍dfs，记录每一个节点的深度和父节点；
2. 对于每一次查询的两个节点，找到其中深度较大的那个，将它不断向上跳（跳到父节点），直到与深度较小的那个深度相同；
3. 然后，将这两个节点一起向上跳，直到两个节点重合为止。此时重合的节点就是LCA。
很显然，这种算法的预处理（默认为时间）复杂度为 O(n) ，单次查询最坏复杂度也会达到 O(n) ，稍微大一点的数据就会炸掉，因此这种算法仅小范围数据可行。
②倍增法
倍增法是最经典的LCA算法，它是朴素算法的改进算法，运用二进制的思想，将每一次跳转要跳的层数拆成二进制，并在dfs中记录每一个节点的第 k(k=2a,a∈N)k(k=2^a,a\in \mathbb{N})k(k=2a,a∈N) 层祖先，然后在向上跳时，遍历要跳的节点记录了的每一层祖先，从深度最小的开始。
例如：现在，两个节点的深度差为 101010 ，那么较深的节点就应该从可能的最远祖先开始。设 a=⌊log2n⌋a=\lfloor{\log_2 n}\rfloora=⌊log2 n⌋ ，则深度最小的记录祖先就是 2a2^a2a 层祖先（这个祖先可能不存在，但是我们可以将不存在的节点记录为 000 ，并将 000 号节点的深度标为最小的，这样就可以了，原因后面会说，但是现在没时间写了，所以null），
