LCA模板

题解

前置知识：

• C++
• 数据结构

题目链接

P3379 【模板】最近公共祖先（LCA）

LCA

LCA 即最近公共祖先
前序遍历中 LCA(S) 出现在所有 S 元素之前 后序遍历在 S 之后
两点的最近公共祖先必定处在树上两点间的最短路上
两点距离 *d(u,v)=h(u)+h(v)-2h(lca(u,v))** 。

代码

#include <cstdio>
#include <iostream>
using namespace std;
const int maxn = 500005;

struct EDGE
{
    int t, next;
} e[2 * maxn];
//邻接表存边
//t表示指向的点 next表示下条边
//head[x]表示x的点存的首条边的号码
int dep[maxn], fa[maxn][22], lg[maxn], head[maxn];
int tot;
void add(int x, int y)
{
    e[++tot].t = y;
    e[tot].next = head[x];
    head[x] = tot;
}

void dfs(int f, int fat)//f表示当前节点 fat表示父亲节点
{
    dep[f] = dep[fat] + 1;//深度+1
    fa[f][0] = fat;//f的父亲是fat
    for (int i = 1; (1<< i) <= dep[f]; i++)
        fa[f][i] = fa[fa[f][i - 1]][i - 1];
        //f的2**i的祖先，是f 的2**(i-1)的祖先的2**(i-1)的祖先
        //2**(i-1)+2**(i-1)==2**i
    for (int i = head[f]; i; i = e[i].next)
        if (e[i].t != fat)
        {
            dfs(e[i].t, f);
        }
}
int lca(int x, int y)
{
    if (dep[x] < dep[y])
    {
        swap(x, y);
    }
    while (dep[x] > dep[y])
    {
        x = fa[x][lg[dep[x] - dep[y]] - 1];
        //跳到同一深度
    }
    if (x == y)
        return x;//如果一个是另一个祖先，直接返回
    for (int k = lg[dep[x]]-1; k >= 0; k--)
        if (fa[x][k] != fa[y][k])
            x = fa[x][k], y = fa[y][k];
    return fa[x][0];
}
int n, m, s;
int main()
{
    scanf("%d%d%d", &n, &m, &s);
    for (int i = 1; i <= n - 1; i++)
    {
        int x, y;
        scanf("%d%d", &x, &y);
        add(x, y);
        add(y, x);
    }
    dfs(s, 0);
    for (int i = 1; i <= n; i++)
    {
        lg[i] = lg[i - 1] + (1 << lg[i - 1] == i);
        cout<<lg[i]<<"   i:"<<i<<"  "<<endl;
        //预先算出log_2(i)+1的值，用的时候直接调用就可以了
    }
    for (int i = 1; i <= m; i++)
    {
        int x, y;
        scanf("%d%d", &x, &y);
        printf("%d\n", lca(x, y));
    }
    return 0;
}