在一棵没有环的树上，每个节点肯定有其父亲节点和祖先节点，而最近公共祖先，就是两个节点在这棵树上深度最大的公共的祖先节点。
ST在线算法：
ST是基于RMQ区间最大最小值编号的，首先dfs确定3个序列：节点序列、深度序列和首位序列。
tarjan（离线）算法：
基于dfs搜索和并查集的算法，时间复杂度O（N+Q）。
大概过程：
1.任选一个点为根节点，从根节点开始。
2.遍历该点u所有子节点v，并标记这些子节点v已被访问过。
3.若是v还有子节点，返回2，否则下一步。
4.合并v到u上。
5.寻找与当前点u有询问关系的点v。
6.若是v已经被访问过了，则可以确认u和v的最近公共祖先为v被合并到的父亲节点a。
伪代码：
网友评论