> ## Content Index
> Fetch the complete content index at: https://blog.hacking.pub/llms.txt
> Use this file to discover other available public pages before exploring further.

# LCA
- URL: https://blog.hacking.pub/2017/06/24/lca/
- Published: 2017-06-24T10:59:34.000Z
- Updated: 2017-06-24T10:59:47.000Z
- Author: chainhelen
- Tags: LCA, 算法, 最近公共祖先, hdu, oj

#### 最近共同祖先

[看题](http://acm.hdu.edu.cn/showproblem.php?pid=2874&ref=blog.hacking.pub)

> 从1到n标号的城市，m条含有权重边，c次询问任意两城市之间的最小加权路径

#### 思路

不是一棵树(这里应该是环)上的，思路很简单，用并查集即可判断  
同一棵树上的，可以采用 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(另一个节点) 返回的 就是 共同祖先
        }
    }
}

```

盗图一张(来源见参考)

![LCA.jpg](https://blog.hacking.pub/qiniu/LCA.jpg)

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

#### 参考

> [LCA 最近公共祖先](http://www.cnblogs.com/JVxie/p/4854719.html?ref=blog.hacking.pub)