【题目描述】
已知一棵 n 个节点的有根树。有 m 个询问，每个询问给出了一对节点的编号 x 和 y，询问 x 与 y 的祖孙关系。
【输入】
输入第一行包括一个整数 n 表示节点个数；
接下来 n 行每行一对整数对 a 和 b 表示 a 和 b 之间有连边。如果 b 是 −1，那么 a 就是树的根；
第 n+2 行是一个整数 m 表示询问个数；
接下来 m 行，每行两个正整数 x 和 y，表示一个询问。
【输出】
对于每一个询问，若 x 是 y 的祖先则输出 1，若 y 是 x 的祖先则输出 2，否则输出 0。
【输入样例】
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
【提示】
数据范围与提示：
对于 30% 的数据，1≤n,m≤103 ；
对于 100% 的数据，1≤n,m≤4×104 ，每个节点的编号都不超过 4×104 。
分析
- LCA的板题，使用倍增实现的；首先一个bfs函数进行数组 depth、fa的初始化，一个lca函数来求公共祖先，先一层for让两个点跳到同一层，再一层for同时往上跳到根的下一层，最后再跳一层返回；
- bfs： 先获取到队头u，然后遍历他的邻边v，初始化是自根向下的，所以fa[v][0]=u，说明儿子向上再跳一步就是根节点（就不用在设置fa[u][0]的值了，它是个根还往上跳啥），所以fa的初始化，是对fa[v][i]进行赋值的（自上而下），fa[v][k]可可以跳两次实现，先跳2^(k-1) 步到 fa[v][k-1]，再跳2^(k-1) 步到达fa[v][k]，利用的递推的思想（2^k-1 + 2^k-1 =>2^k）；
- lca： 先判断a,b大小，保证a在b的下面；然后开始处理让他们跳到同一层，当然判断的就是depth，让a往上跳，k从20倒着往下找，不用怕越界（有守卫），至到for结束a,b在同一层；此时判断下a是否=b，等的话说明找到公共祖先了；然后处理a,b同时跳，只要fa[a][k] != fa[b][k]（只要没跳到同一个结点上，就只管跳）就还继续跳，至到跳到他们最近公共祖先的下一层；最后再跳一层返回，从a向上跳一步、b向上跳一步都行；
- 关于哨兵的设置和作用：哨兵一共设置两份，depth[0] = 0和 fa[i,j]=0（fa默认就是0，然后把能到达的在bfs中初始化）；哨兵的作用就是对跳出根节点的操作进行处理，如果a跳出去了，然后fa[a][k]=0，那么无论是depth[fa[a][k]]之间的判断，还是fa[a][k]的判断，如果跳出根节点，自然不满足当时的if条件；
- 吐槽下这个题的假数据范围，需要多开一点（多开一万还不行，那就直接N再乘10），不然会被卡RE、WA；下图为yxc的思路描述：
#include <bits/stdc++.h>using namespace std;
typedef long long LL;
const int N = 400010, M = 400010 * 2;int n, m;
int h[N], e[N], ne[N], idx;
int q[N];
//fa[i,j]表示从i向上走 2^j 步能到的点；depth表示深度
int depth[N], fa[N][21];// 2^16 >40010void add(int a, int b) {e[++idx] = b, ne[idx] = h[a], h[a] = idx;
}//初始化depth、fa
void bfs(int root) {memset(depth, 0x3f, sizeof depth);//哨兵：depth[0] = 0，f[i,j]默认就是0了depth[0] = 0;int hh = 0, tt = 0;//第一个点——根节点q[0] = root;depth[root] = 1;while (hh <= tt) {int u = q[hh++];for (int i = h[u]; ~i; i = ne[i]) {int v = e[i];//如果u,v相差不是一层，说明v还没被搜过，加队列if (depth[v] > depth[u] + 1) {depth[v] = depth[u] + 1;q[++tt] = v;//初始化fa，对v开始的进行处理（自上而下）fa[v][0] = u;for (int k = 1; k <= 20; ++k) {//先跳2^(k-1)步到f[v][k-1]，再跳2^(k-1)步fa[v][k] = fa[fa[v][k - 1]][k - 1];}}}}
}//求两个点的公共祖先
int lca(int a, int b) {//a要在b下面if (depth[a] < depth[b])swap(a, b);//1. a先跳到同一层（一个数肯定能通过二进制表示，这层for结束就到了同一层）for (int k = 20; k >= 0; --k) {//a先向上跳2^k步//不用怕k=16或者20起始值太大，有哨兵，不怕他第一次跳太远，导致直接跳出根节点，如果跳出根节点，f[i][j]=0会出手的//哨兵的作用：如果f[a][k]跳出了根节点，那么左边就是depth[0]=0，自然不满足当前if，i--找下一个iif (depth[fa[a][k]] >= depth[b]) {//=时候，直接跳到同一层，后序就进不了if了//a赋上新位置，继续往上跳a = fa[a][k];}}//找到公共祖先if (a == b)return a;//2. a，b同时往上跳，至到他们最近公共祖先的下一层for (int k = 20; k >= 0; --k) {//说明还没跳到公共祖先（没跳到同一个结点，原目的也就不想让他们直接跳到公共祖先），就一直跳//哨兵的作用：如果a跳出去了，b肯定也跳出去了，因为同一层开始跳的，然后fa[a][k]=0,0!=0自然不满足当前的if，i--if (fa[a][k] != fa[b][k]) {//更新这次跳到的新位置a = fa[a][k];b = fa[b][k];}}//当前在公共祖先的下一层，再往上跳一层即可return fa[a][0];//fa[b][0]也是可以的
}int main() {memset(h, -1, sizeof h);scanf("%d", &n);int root = 0; //根节点for (int i = 0; i < n; ++i) {int a, b;scanf("%d%d", &a, &b);if (b == -1)root = a;elseadd(a, b), add(b, a);//无向边}bfs(root);cin >> m;while (m--) {int x, y;scanf("%d%d", &x, &y);int p = lca(x, y);if (p == x)printf("1\n");else if (p == y)printf("2\n");elseprintf("0\n");}return 0;
}
