Trancy

3月29日 RMQ->LCA?

在dfs遍历的时候会有一个节点访问序列,(包括进出的),我们可以开一个数组记录某一个节点第一次出现的位置,如果是要求节点X和节点Y的最近公共祖先,设X和Y第一次出现在序列里面的位置为xx和yy,在xx~yy里面序号最小的节点即为他们的最近公共祖先,这里就用到了RMQ。

理论上来说应该是这样的,这是在线的算法,离线的有tarjan算法,还没有会,mark一下记得回来看。

评论