|
|
#include <bits/stdc++.h>
|
|
|
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<int> 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;
|
|
|
} |
