我的implementation和y老师的不太一样。
1 我直接开pa数组记录,我的爸爸是谁。
2 我的图是儿子指向爸爸的,y老师是爸爸指向儿子,这两个建图方式都满足拓扑序。
3 我算depth是dfs,因为我是儿子指向爸爸。
4 depth更深的往上爬,爬到一样高,看看是否重合。
坑:
倍增的时候一定要先遍历步数,在遍历点。原因是要把每一个点的往上一步都算好了,才能算往上两步的。
#include "bits/stdc++.h"
using namespace std;
typedef long long LL;
#define INF 0x3f3f3f3f
const int MOD = 1e9+7;
typedef pair<int, int> PII;
const int N = 40010;
const int L = 20;
int pa[N];
int depth[N];
int n, m;
int dp[N][L];
int dfs(int curr) {
if (depth[curr] != -1)
return depth[curr];
depth[curr] = 1 + dfs(pa[curr]);
return depth[curr];
}
int main() {
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
cin >> n;
memset(pa, INF, sizeof pa);
for (int i = 0; i < n; i++) {
int a, b;
cin >> a >> b;
pa[a] = max(0, b);
dp[a][0] = max(0, b);
}
for (int l = 1; l < L; l++) {
for (int i = 1; i < N; i++) {
if (pa[i] == INF)
continue;
dp[i][l] = dp[dp[i][l-1]][l-1];
}
}
memset(depth, -1, sizeof depth);
depth[0] = 0;
for (int i = 0; i < N; i++) {
if (pa[i] == INF)
continue;
dfs(i);
}
cin >> m;
while (m--) {
int a, b;
cin >> a >> b;
if (depth[a] > depth[b]) {
int pa = a;
for (int i = L-1; i >= 0; i--) {
if (depth[dp[pa][i]] >= depth[b])
pa = dp[pa][i];
}
if (pa == b)
cout << 2 << endl;
else
cout << 0 << endl;
} else if (depth[a] < depth[b]) {
int pb = b;
for (int i = L-1; i >= 0; i--) {
if (depth[dp[pb][i]] >= depth[a])
pb = dp[pb][i];
}
if (a == pb)
cout << 1 << endl;
else
cout << 0 << endl;
} else {
cout << 0 << endl;
}
}
return 0;
}