#include using namespace std; const int N = 40010, M = 80010; // 链式前向星 int e[M], h[N], idx, w[M], ne[M]; void add(int a, int b, int c = 0) { e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx++; } int n; int depth[N]; // 每个节点的深度 int f[N][16]; // 设f[i][k]表示节点i向上回溯2^k步的节点标号 // 预处理 // 1、每个点的深度 // 2、记录节点i向上回溯2^k步的节点标号 void bfs(int root) { queue q; // 声明队列,准备从根开始对整棵树进行宽搜 q.push(root); // 根节点入队列 depth[root] = 1; // 根结点深度为1 while (q.size()) { int u = q.front(); q.pop(); for (int i = h[u]; ~i; i = ne[i]) { int v = e[i]; if (!depth[v]) { // 如果深度为0,表示没有访问过,防止走回头路 depth[v] = depth[u] + 1; // 记录每个节点的深度 f[v][0] = u; // f[j][0]表示j跳2^0=1到达的是它的父节点 q.push(v); // 下一次该j发挥作用了 /*举个栗子: j 向上跳 2^0=1,2^1=2,2^2=4,2^3=8,2^4=16,2^5=32,...步, 分别记录这样跳到达的节点是什么编号,这样其实是按二进制思想记录的信息。 f[j][k] = f[f[j][k - 1]][k - 1] 采用了递推的思路,比如i向上想走8级,现在向上走了4级到达了j,也可以继续从j出发向上再走4次,是一回事, 但由于这样利用了已有结果会更快 因为bfs特性,在计算f[j][k]时,前序依赖数据已经被填充过,可以快速利用 */ for (int k = 1; k <= 15; k++) f[v][k] = f[f[v][k - 1]][k - 1]; } } } } // 最近公共祖先 int lca(int a, int b) { // a保持深度更大 if (depth[a] < depth[b]) swap(a, b); // 对齐a,b,跳冒不跳,跳少再跳 for (int k = 15; k >= 0; k--) if (depth[f[a][k]] >= depth[b]) a = f[a][k]; if (a == b) return a; // 同级,跳冒不跳,跳少再跳 for (int k = 15; k >= 0; k--) if (f[a][k] != f[b][k]) a = f[a][k], b = f[b][k]; // a的父节点,就是lca(a,b) return f[a][0]; } int main() { memset(h, -1, sizeof h); scanf("%d", &n); int a, b, m, root; for (int i = 0; i < n; i++) { scanf("%d %d", &a, &b); if (b == -1) root = a; // 找到根节点 else add(a, b), add(b, a); // 无向树 } // 预处理,生成倍增的下2^k级跳位置数据f[i][k] bfs(root); scanf("%d", &m); while (m--) { 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; }