洛谷 3379_【模板】最近公共祖先（LCA）

题目描述

如题，给定一棵有根多叉树，请求出指定两个点直接最近的公共祖先。

---

#include 
#define maxn 500001
struct edge
{
    int to, next;
}e[maxn * 2];
int ls[maxn * 2], dep[maxn], f[maxn][21];
bool v[maxn];
int dfs(int now, int de, int fa)
{
    f[now][0] = fa;
    dep[now] = de;
    v[now] = 1;
    for (int i = ls[now]; i; i = e[i].next)
    {
        if (v[e[i].to] == 0)
            dfs(e[i].to, de + 1, now);
    }
}
int LCA(int l, int r)
{
    if (dep[l] < dep[r])
        {l ^= r; r ^= l; l ^= r;}
    for (int i = 20; i >= 0; i--)
        if (dep[r] <= dep[f[l][i]])
            l = f[l][i];
    if (l == r) return l;
    for (int i = 20; i >= 0; i--)
        if (f[l][i] != f[r][i])
        {
            l = f[l][i];
            r = f[r][i];
        }
    return f[l][0];
}
int main()
{
    int n, m, root;
    scanf("%d%d%d", &n, &m, &root);
    v[root] = 1;
    int l = 0;
    for (int i = 1; i < n; i++)
    {
        int x, y;
        scanf("%d%d", &x, &y);
        e[++l] = (edge) {y, ls[x]};
        ls[x] = l;
        e[++l] = (edge) {x, ls[y]};
        ls[y] = l;
    }
    dfs(root, 1, 0);
    for (int j = 1; j <= 20; j++)
        for (int i = 1; i <= n; i++)
            f[i][j] = f[f[i][j - 1]][j - 1];
    for (int i = 1; i <= m; i++)
    {
        int l, r;
        scanf("%d%d", &l, &r);
        printf("%d\n", LCA(l, r));
    }
}