lca算法思想

lca(least Comment Ancestors,最近公共祖先问题),是指给定一棵有根树,查询LCA(u,v)，每次求树中两个顶点u和v的最近公共祖先，即找到一个节点，同时是u和v的祖先，并且深度尽可能的大，入度尽可能的大。

一、一般解法

一般解法即暴力小跳，同过逐级跳转向上查询，时间复杂度较大。

先找到给出节点，并得到他们的入度，使入度较大的节点先跳转至与较小节点同一入度的父节点。然后同时向上查找，直至两者相遇。

注意：在这里向上查找都是逐步向上查找的。
结束条件：查询到同一节点时。

二、跳表解法（倍增）

此种方法与一般解法思想类似，但是略有不同。它在一般解法的基础上，不猜用逐级跳转的方式，而是跨越式的跳转，即大跳。

这说明他不仅保存其父节点，还保存有节点的多级节点。但若保存过多又会使空间复杂度过大，权衡之下，一般选择保存其二进制倍的多级节点。查询时先获得两节点入度，再根据入度的差值来选择如何进行跳转。例如入度差6，就可以先向上跳转4，在跳转2，从而优化跳转时间。

注意：弹头欧诺个时需注意，在同一入度后，再采用多级跳转的话，结束条件需改变。
结束条件：入度相同，且两节点父节点相同时。

三、基于tarjan算法的解法

该算法对应于倍增是离线算法，运行时先保存全部的查询命令，逐步运算后，最后再输出解。

其思想是先将树与所有的查询保存，再对树进行处理，从而使时间复杂度变为O（n）(+O(1)，对查询的处理)。保存后，对数从根节点开始逐级访问，相当于进行深度优先搜索（dps），并对访问进行记录，并将该节点合并到父节点。当访问到的节点有查询请求时，如果对应节点也已经访问，那么此时查询对应节点就已经被合并到对应的lca，从而完成查询。如果对应节点还未访问则记录，等到访问对应节点是，在查询该节点对应合并的父节点即可。

注意：属于离线查询。
结束条件：整颗树访问结束，没有明显的结束标志。