2.2　最近公共祖先LCA

最近公共祖先（Lowest Common Ancestors，LCA）指有根树中距离两个节点最近的公共祖先。祖先指从当前节点到树根路径上的所有节点。

u和v的公共祖先指一个节点既是u的祖先，又是v的祖先。u和v的最近公共祖先指距离u和v最近的公共祖先。若v是u的祖先，则u和v的最近公共祖先是v。

可以使用LCA求解树上任意两点之间的距离。求u和v之间的距离时，若u和v的最近公共祖先为lca，则u和v之间的距离为u到树根的距离加上v到树根的距离减去2倍的lca到树根的距离：dist[u]+dist[v]-2×dist[lca]。

求解LCA的方法有很多，包括暴力搜索法、树上倍增法、在线RMQ算法、离线Tarjan算法和树链剖分。

在线算法：以序列化方式一个一个地处理输入，也就是说，在开始时并不需要知道所有输入，在解决一个问题后立即输出结果。

离线算法：在开始时已知问题的所有输入数据，可以一次性回答所有问题。