AcWing 3555. 二叉树
原题链接
简单
作者:
求是君
,
2022-03-31 20:00:23
,
所有人可见
,
阅读 179
借鉴大佬题解 用栈真的很方便
#include<iostream>
#include<stack>
using namespace std;
//直接通过两个栈分别存放两个节点到根结点的路径
const int N=1010;
stack<int> s1,s2;
int father[N]; // 存储 N 结点的父节点
int main(){
int t;
cin>>t;
while(t--){
int n,m;
cin>>n>>m;
father[1]=-1; //根节点的父节点为-1
for(int i=1;i<=n;i++){ // 把输入的 n 行进行相应的存储
int a,b;
cin>>a>>b;
if(a!=-1){
father[a]=i;
}
if(b!=-1){
father[b]=i;
}
}
for(int i=0;i<m;i++){
int l,r;
cin>>l>>r;
while(s1.size()) s1.pop(); //每次询问之前将栈清空
while(s2.size()) s2.pop();
//然后从子节点向上到根节点依次入栈
s1.push(l);
while(father[l]!=-1){
l=father[l];
s1.push(l);
}
s2.push(r);
while(father[r]!=-1){
r=father[r];
s2.push(r);
}
//然后从根节点开始找到l,r节点的公共祖先节点
while(s1.size() && s2.size()){
if(s1.top()==s2.top()){
s1.pop();s2.pop();
}else{
break;
}
}
cout<<s1.size()+s2.size()<<endl;
}
}
return 0;
}
超时啊