LCA离线算法

将询问存下来,在dfs过程中对其操作。我们不妨对走过的节点进行染色,如果从父亲经过孩子,那么孩子染成灰色,当回溯的时候将孩子染成黑色。当dfs到某个节点u时,我们将于u有关的询问拿出来,判断询问中与u对应的节点v此时的染色情况。情况分三种:

1.无色,略过。

2.灰色,那么此时u和v必定在同一条路径上,于是v必定是u的父亲,那么lca = v

3.黑色,说明u和v在不同的子树上,所以u和v的lca必定是v向上走第一个出现的灰色节点。

1和2的复杂度是O(1),3的复杂度是路径的长度,如果每次遍历必定很耗时,但是想想并查集的性质,并查集利用路径压缩的方法将复杂度控制在O(n),其实找灰色节点也可以用路径压缩,第一次遍历需要找整条链,但是第二次只要O(1),因此平摊过去整个算法的复杂度就是O(m),m是边的数量。

核心代码:

 

 

LEAVE A COMMENT