3月29日 RMQ->LCA?
在dfs遍历的时候会有一个节点访问序列，（包括进出的），我们可以开一个数组记录某一个节点第一次出现的位置，如果是要求节点X和节点Y的最近公共祖先，设X和Y第一次出现在序列里面的位置为xx和yy，在xx~yy里面序号最小的节点即为他们的最近公共祖先，这里就用到了RMQ。
理论上来说应该是这样的，这是在线的算法，离线的有tarjan算法，还没有会，mark一下记得回来看。
在dfs遍历的时候会有一个节点访问序列，（包括进出的），我们可以开一个数组记录某一个节点第一次出现的位置，如果是要求节点X和节点Y的最近公共祖先，设X和Y第一次出现在序列里面的位置为xx和yy，在xx~yy里面序号最小的节点即为他们的最近公共祖先，这里就用到了RMQ。
理论上来说应该是这样的，这是在线的算法，离线的有tarjan算法，还没有会，mark一下记得回来看。
评论