题目描述

给定一棵有根树，每次给两个节点询问他们的祖孙关系。

dfs序预处理st表

$dfs$ 预处理出每个节点的深度 $dep[u]$
第一次遍历到这个节点在第几步 $first[u]$
第几步遍历到哪个节点（考虑回溯）$a[i]$

$lca(a, b)$ 一定为 $first[a]$ 到 $first[b]$ 之间遍历过的深度最小的点

预处理出 $a[i]$ 之后即可预处理 $st$ 表存储第 $i$ 步及之后的 $2^j$ 步遍历到的深度最小的节点

对于每个 $lca$ 询问，我们都可以转化为 $st$ 表中区间最小数的查询，即可实现 $O(1)$ 问答

时间复杂度 $O(nlogn + m)$

C++ 代码

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>

using namespace std;

const int N = 40010, M = N * 2;

int h[N], e[M], ne[M], idx;
void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}

int n, m;
int root;

int dep[N], dfn[N], step;       //  dfn[u]表示首次遍历到u号节点是第几步
int a[M];                       //  a[i]表示第i步遍历到的节点编号

void dfs(int u, int fa)
{
    dfn[u] = ++ step;
    a[step] = u;

    for(int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        if(j == fa)  continue;
        dep[j] = dep[u] + 1;
        dfs(j, u);
        a[++ step] = u;
    }
}

int f[M][17];
void init()
{
    for(int j = 0; j < 17; j ++)
        for(int i = 1; i + (1 << j) - 1 <= n * 2; i ++)
            if(!j)  f[i][j] = a[i];
            else
            {
                if(dep[f[i][j - 1]] < dep[f[i + (1 << j - 1)][j - 1]])  f[i][j] = f[i][j - 1];
                else  f[i][j] = f[i + (1 << j - 1)][j - 1];
            }
}

int query(int l, int r)
{
    if(l > r)  swap(l, r);
    int k = log2(r - l + 1);
    int a = f[l][k], b = f[r - (1 << k) + 1][k];
    if(dep[a] < dep[b])  return a;
    return b;
}

int lca(int a, int b)
{
    return query(dfn[a], dfn[b]);
}

int main()
{
    memset(h, -1, sizeof h);
    memset(dfn, 0x3f, sizeof dfn);

    scanf("%d", &n);
    for(int i = 0; i < n; i ++)
    {
        int a, b;
        scanf("%d%d", &a, &b);
        if(b == -1)  root = a;
        else  add(a, b), add(b, a);
    }

    dep[root] = 1;
    dfs(root, -1);
    init();

    //for(int i = 1; i <= n; i ++)  printf("dfn[%d] = %d\n", i, dfn[i]);  puts("");
    //for(int i = 1; i <= step; i ++)  printf("%d ", a[i]);  puts("");

    int m;
    scanf("%d", &m);
    while(m --)
    {
        int a, b;
        scanf("%d%d", &a, &b);
        int t = lca(a, b);
        if(t == a)  puts("1");
        else if(t == b)  puts("2");
        else  puts("0");
    }
    return 0;
}

倍增求lca

时间复杂度 $O((n + m)logn)$

C++ 代码

#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>

using namespace std;

const int N = 40010, M = N * 2;

int h[N], e[M], ne[M], idx;
void add(int a, int b)
{
    e[idx] = b;
    ne[idx] = h[a];
    h[a] = idx ++;
}

int n, m;
int depth[N];
int fa[N][17];
void bfs(int root)
{
    depth[root] = 1;

    queue<int> q;
    q.push(root);
    while(q.size())
    {
        int u = q.front();  q.pop();

        for(int i = h[u]; ~i; i = ne[i])
        {
            int j = e[i];

            if(depth[j])  continue;

            depth[j] = depth[u] + 1;
            q.push(j);

            fa[j][0] = u;
            for(int k = 1; k < 17; k ++)
                fa[j][k] = fa[fa[j][k - 1]][k - 1];
        }
    }
}

int lca(int a, int b)
{
    if(depth[a] < depth[b])  swap(a, b);

    for(int i = 16; i >= 0; i --)
        if(depth[fa[a][i]] >= depth[b])
            a = fa[a][i];

    if(a == b)  return a;

    for(int i = 16; i >= 0; i --)
        if(fa[a][i] != fa[b][i])
        {
            a = fa[a][i];
            b = fa[b][i];
        }
    return fa[a][0];
}

int main()
{
    scanf("%d", &n);

    memset(h, -1, sizeof h);
    int root;
    for(int i = 0; i < n; i ++)
    {
        int a, b;
        scanf("%d%d", &a, &b);
        if(b == -1)  root = a;
        else{
            add(a, b);
            add(b, a);
        }
    }

    bfs(root);
    scanf("%d", &m);
    while(m --)
    {
        int a, b;
        scanf("%d%d", &a, &b);
        int p = lca(a, b);

        if(p == a)  puts("1");
        else if(p == b)  puts("2");
        else  puts("0");
    }
    return 0;
}