二叉树节点之间的距离

题目描述

对二叉树，计算任意两个结点的最短路径长度。

输入

第一行输入测试数据组数 T 第二行输入 n , m 。 n 代表结点的个数， m 代表要查询的数据组数。 接下来 n 行，每行输入两个数，代表1~ n 结点的孩子结点，如果没有孩子结点则输入-1，根节点为1。 接下来 m 行，每行输入两个数，代表要查询的两个结点。

输出

每组测试数据输出 m 行，代表查询的两个结点之间的最短路径长度。

测试样例

输入

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
           

#include<bits/stdc++.h>
using namespace std;
int fa[1005];
int main() {
	int T,m,n;
	int a,b;
	cin>>T;
	while(T--) {
		memset(fa,0,sizeof(fa));
		cin>>n>>m;
		for(int i=1;i<=n;i++){
			cin>>a>>b;
			if(a!=-1){
				fa[a]=i;
			}
			if(b!=-1){
				fa[b]=i;
			}
		}
		while(m--){
			cin>>a>>b;
			stack<int >s1,s2;
			while(a){
				s1.push(a);
				a=fa[a];
			}
			while(b){
				s2.push(b);
				b=fa[b];
			}
			while(!s1.empty()&&!s2.empty()&&s1.top()==s2.top()){
				s1.pop();
				s2.pop();
			}
			cout<<s1.size()+s2.size()<<endl;
		}
	}
}