题目描述

给定一棵包含 n 个节点的有根无向树，节点编号互不相同，但不一定是 1∼n。

有 m 个询问，每个询问给出了一对节点的编号 x 和 y，询问 x 与 y 的祖孙关系。

输入格式
输入第一行包括一个整数 表示节点个数；

接下来 n 行每行一对整数 a 和 b，表示 a 和 b 之间有一条无向边。如果 b 是 −1，那么 a 就是树的根；

第 n+2 行是一个整数 m 表示询问个数；

接下来 m 行，每行两个不同的正整数 x 和 y，表示一个询问。

输出格式
对于每一个询问，若 x 是 y 的祖先则输出 1，若 y 是 x 的祖先则输出 2，否则输出 0。

数据范围
1≤n,m≤4×104,
1≤每个节点的编号≤4×104

输入样例：

10
234 -1
12 234
13 234
14 234
15 234
16 234
17 234
18 234
19 234
233 19
5
234 233
233 12
233 13
233 15
233 19

输出样例：

1
0
0
0
2

方法学习自：

https://blog.csdn.net/MikeJackSTG/article/details/81806120

C++ 代码

#include<iostream>
#include<vector>
#include<cstring>
#include<algorithm>

const int space = 4e4 + 7, high = 44;
int N, M;
std::vector<int>edge[space], vertex;
int deep[space] = {}, root = -1, max_deep = -1;
int visit[space] = {}, ST[space][high] = { {} };
// root 记录哪个结点是根节点，max_deep 记录的是这棵树最大深度是多少
//因为是无向的树，所以使用 visit 数组避免死循环，vertex记录出现过哪些
//结点， deep 记录所有结点的深度都有多少，ST 稀疏表，ST[i][j]记录了面值
//为 i 的结点，前2^j个结点的面值是多少

void DFS(int now,int pre)
{
    visit[now] = 1;
    deep[now] = deep[pre] + 1;
    max_deep = max_deep > deep[now] ? max_deep : deep[now];
    ST[now][0] = pre;
    for (int i = 0; i < edge[now].size(); i++)
    {
        int son = edge[now][i];
        if (visit[son])continue;
        DFS(son, now);
    }
}

void painting_ST(int max_deep)
{
    for (int j = 1; (1 << j) <= max_deep; j++)
        //若i<<j都超过deep，即使结点深度最大的那个结点的也不会有答案超过了根节点
        for (int i = 0; i < vertex.size(); i++)
            //遍历所有的结点，若不合法的位置直接赋值0，得到该情况的解，才可以下一个深度更大的解
            ST[vertex[i]][j] = ST[ST[vertex[i]][j - 1]][j - 1];
}

int LCA(int u, int v)
{
    int is_change = 0;
    if (deep[u] < deep[v])std::swap(u, v), is_change = 1;
    int utv = deep[u] - deep[v];
    for (int i = 32; i >= 0; i--)
        if (deep[ST[u][i]] >= deep[v])u = ST[u][i];

    if (u == v)
        if (is_change)return 1;
        else return 2;
    else return 0;
    //for (int i = 32; i >= 0; i++)
        //if (ST[u][i] != ST[v][i])u = ST[u][i], v = ST[v][i];
    //寻找最近公共祖先，本题没有必要，
}

int main(void)
{
    int a, b;
    scanf("%d", &N);
    for (int i = 0; i < N; i++)
    {
        scanf("%d %d", &a, &b);
        if (-1 != b)
        {
            edge[a].push_back(b), edge[b].push_back(a);
            if(!visit[a])vertex.push_back(a);
            if (!visit[b])vertex.push_back(b);
            visit[a] = visit[b] = 1;
        }
        else root = a;
    }
    memset(visit, 0, sizeof(visit));
    DFS(root, 0);
    painting_ST(max_deep);
    scanf("%d", &M);
    while (M--)
    {
        int u, v;
        scanf("%d %d", &u, &v);
        printf("%d\n", LCA(u, v));
    }
    return 0;
}