AcWing 1172. 祖孙询问
原题链接
中等
作者:
sohia
,
2024-04-05 16:55:30
,
所有人可见
,
阅读 2
解题注释代码里
样例
10
234 -1
12 234
13 234
14 234
15 234
16 234
17 234
18 234
19 234
233 19
5
234 233
233 12
233 13
233 15
233 19
算法1
参考文献
C++ 代码
#include<bits/stdc++.h>
#define eb emplace_back
using namespace std;
const int N=4*1e4+10;
vector<vector<int>>edg(N);
int fa[N][23];
int dept[N];
void bfs(int root){
queue<int>q;
dept[root]=1;
q.push(root);
while(q.size()){
int t=q.front();
q.pop();
for(int x:edg[t]){
if(!dept[x]){
dept[x]=dept[t]+1;
fa[x][0]=t;
for(int i=1;i<=20;i++){
fa[x][i]=fa[fa[x][i-1]][i-1];
}
q.push(x);
}
}
}
}
int lca(int a,int b){
if(dept[a]<dept[b])swap(a,b);
for(int i=20;i>=0;i--){
if(dept[fa[a][i]]>=dept[b]){
a=fa[a][i];
}
}//让a和b同一层然后方便后面的操作一起往上跳
if(a==b){
return b;
}
for(int i=20;i>=0;i--){
if(fa[a][i]!=fa[b][i]){
a=fa[a][i];
b=fa[b][i];
}
}
return fa[a][0];//此时a和b祖先一样了,返回祖先即可,但不是a,b相等,类似于一个小的二叉树左右儿子,此时他们的father相同,看判断条件可知
}
int main(){
int n;
cin>>n;
int root=0;
for(int i=1;i<=n;i++){
int a,b;
cin>>a>>b;
if(b==-1){
root=a;
}
else{
edg[a].eb(b);
edg[b].eb(a);
}
}
bfs(root);
int q;
cin>>q;
while(q--){
int a,b;
cin>>a>>b;
int p=lca(a,b);
if(p==a)cout<<1<<endl;
else if(p==b)cout<<2<<endl;
else cout<<0<<endl;
}
}