LCA

思路

不是一棵树(这里应该是环)上的，思路很简单，用并查集即可判断
同一棵树上的，可以采用 Tarjan 离线算法

核心伪代码

for(int i = 1;i <= n;i++) {  
    if(!vis[i]) {
        LCA(i);
    }
}

void LCA(int u) {  
    father[u] = u;   //重新指定自己
    vis[u] = 1;      //标记已经完成扫描
    for(int i = head[u]; i != -1; i = edge[i].next) {   // 遍历改点所能到达的其他点
        int to = edge[i].to;                            
        int len = edge[i].len;
        if(!vis[to]) {
            dis[to] = dis[u] + len;            //扫描子节点之前，更新子节点距离root节点长度
            LCA(to);                           //扫描子节点
            f[to] = u;                         //子节点已经完成扫描(递归里面vis[u] = 1)，更新父子关系
        }
    }

    for(int i = qhead[u];i != -1;i = que[i].next) {
        int to = que[i].to;
        if(vis[to]) {
            res[que[i].index] = dis[to] + dis[u] - 2 * dis[find(to)];  // 询问的另一个节点如果已经完成扫描，那么 find(另一个节点) 返回的 就是 共同祖先
        }
    }
}

盗图一张(来源见参考)

当扫描 8节点时候，如果询问的是 8-9，此时可见 9 已经完成扫描了，且find(9)就是共同先祖，但是注意find(8)并不是，因为操作流程是
节点8 的子节点扫描完 =>
查询与节点8相关的节点共同祖先(即前面说的find(9)) =>
该层递归结束，返回上一层，立即执行f[8] = 5，这时候节点8 才能拿到祖先信息

参考

LCA 最近公共祖先

Menu

LCA

最近共同祖先

思路

参考