二叉樹節點之間的距離

題目描述

對二叉樹，計算任意兩個結點的最短路徑長度。

輸入

第一行輸入測試資料組數 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;
		}
	}
}