Loading... # 爬坡法 ```cpp #include <bits/stdc++.h> using namespace std; const int N = 1e3 + 10; int l[N], r[N], p[N]; int dist[N]; int n, m, t; void dfs(int x, int d) { dist[x] = d; if (l[x] != -1) dfs(l[x], d + 1); if (r[x] != -1) dfs(r[x], d + 1); } int get_lca(int a, int b) { if (dist[a] > dist[b]) swap(a, b); while (dist[a] < dist[b]) b = p[b]; while (a != b) a = p[a], b = p[b]; return a; } int main() { cin >> t; int a, b; while (t--) { cin >> n >> m; memset(l, -1, sizeof l); memset(r, -1, sizeof r); for (int i = 1; i <= n; i++) { cin >> a >> b; l[i] = a, r[i] = b; if (a != -1) p[a] = i; if (b != -1) p[b] = i; } dfs(1, 0); for (int i = 1; i <= m; i++) { cin >> a >> b; int lca = get_lca(a, b); printf("%d\n", dist[a] + dist[b] - dist[lca] * 2); } } return 0; } ``` Last modification：March 10, 2023 © Allow specification reprint Like 0 如果觉得我的文章对你有用，请随意赞赏
Comment here is closed