题目描述
给定一个 n 个结点(编号 1∼n)构成的二叉树,其根结点为 1 号点。
进行 m 次询问,每次询问两个结点之间的最短路径长度。
树中所有边长均为 1。
输入格式
第一行包含一个整数 T,表示共有 T 组测试数据。
每组数据第一行包含两个整数 n,m。
接下来 n 行,每行包含两个整数,其中第 i 行的整数表示结点 i 的子结点编号。如果没有子结点则输出 −1。
接下来 m 行,每行包含两个整数,表示要询问的两个结点的编号。
输出格式
每组测试数据输出 m 行,代表查询的两个结点之间的最短路径长度。
数据范围
1≤T≤10,
1≤n,m≤1000
样例
输入样例:
1
8 4
2 3
4 5
6 -1
-1 -1
-1 7
-1 -1
8 -1
-1 -1
1 6
4 6
4 5
8 1
输出样例:
2
4
2
4
算法1
(lca) $O(knlog(n))$
C++ 代码
#include<bits/stdc++.h>
using namespace std;
const int N = 1010;
int l[N], r[N];
int depth[N], f[N][12];
int n, m, t;
void bfs(int root)
{
queue<int> q;
q.push(root);
depth[1] = 1, depth[0] = 0;
while(q.size())
{
auto u = q.front();
q.pop();
if(l[u] != -1) depth[l[u]] = depth[u] + 1, q.push(l[u]);
if(r[u] != -1) depth[r[u]] = depth[u] + 1, q.push(r[u]);
f[l[u]][0] = u;
for(int i = 1;i <= 11;i++) f[l[u]][i] = f[f[l[u]][i-1]][i-1];
f[r[u]][0] = u;
for(int i = 1;i <= 11;i++) f[r[u]][i] = f[f[r[u]][i-1]][i-1];
}
}
int lca(int a, int b)
{
if(depth[a] < depth[b]) swap(a, b);
for(int i = 11;i >= 0;i--) if(depth[f[a][i]] >= depth[b]) a = f[a][i];
if(a == b) return a;
for(int i = 11;i >= 0;i--)
{
if(f[a][i] != f[b][i]) a = f[a][i], b = f[b][i];
}
return f[a][0];
}
int main()
{
cin >> t;
while(t--)
{
memset(depth, 0, sizeof depth);
memset(f, 0, sizeof f);
memset(l, -1, sizeof l);
memset(r, -1, sizeof r);
cin >> n >> m;
for(int i = 1;i <= n;i++) cin >> l[i] >> r[i];
bfs(1);
for(int i = 0;i < m;i++)
{
int a, b;
scanf("%d%d", &a, &b);
int anc = lca(a, b);
//cout << anc << endl;
cout << depth[a] + depth[b] - 2 * depth[anc] << endl;
}
}
return 0;
}