1172. 祖孙询问(LCA)
作者:
闪回
,
2024-03-25 22:40:52
,
所有人可见
,
阅读 2
倍增法求lca
先跳到同一高度,再一起往上跳
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
typedef long long LL;
const int N = 4e4+10,M = N * 2;
int n,m;
int h[N],e[M],ne[M],idx;
int fa[N][16];
int depth[N];
queue<int> q;
void add(int a,int b)
{
e[idx] = b,ne[idx] = h[a],h[a] = idx++;
}
void bfs(int root)
{
memset(depth,0x3f,sizeof depth);
depth[0] = 0,depth[root] = 1;
q.push(root);
while(q.size())
{
int t = q.front();
q.pop();
for(int i = h[t];~i;i = ne[i])
{
int j = e[i];
if(depth[j] > depth[t] + 1)
{
depth[j] = depth[t] + 1;
q.push(j);
fa[j][0] = t;
for(int k = 1;k<=15;k++)
{
fa[j][k] = fa[fa[j][k-1]][k-1];
}
}
}
}
}
int lca(int x,int y)
{
if(depth[x] < depth[y])swap(x,y);
for(int k = 15;k>=0;k--)
{
if(depth[fa[x][k]] >= depth[y])
{
x = fa[x][k];
}
}
if(x == y)return x;
for(int k = 15;k>=0;k--)
{
if(fa[x][k] != fa[y][k])
{
x = fa[x][k];
y = fa[y][k];
}
}
return fa[x][0];
}
int main()
{
memset(h,-1,sizeof h);
cin>>n;
int root;
while (n -- )
{
int a,b;
cin>>a>>b;
if(b == -1)root = a;
else add(a,b),add(b,a);
}
bfs(root);
cin>>m;
while (m -- )
{
int x,y;
cin>>x>>y;
int p = lca(x,y);
if(p == x)cout<<1<<endl;
else if(p == y)cout<<2<<endl;
else cout<<0<<endl;
}
return 0;
}