首页 > 代码库 > 祖孙询问（C++）
祖孙询问（C++）
| 祖孙询问 |
| 难度级别：C； 运行时间限制：1000ms； 运行空间限制：256000KB； 代码长度限制：2000000B |
|
试题描述
|
|
已知一棵n个节点的有根树。有m个询问。每个询问给出了一对节点的编号x和y，询问x与y的祖孙关系。
|
|
输入
|
|
输入第一行包括一个整数n表示节点个数。
接下来n行每行一对整数对a和b表示a和b之间有连边。如果b是-1，那么a就是树的根。 第n+2行是一个整数m表示询问个数。 接下来m行，每行两个正整数x和y。 |
|
输出
|
|
对于每一个询问，输出1:如果x是y的祖先，输出2:如果y是x的祖先，否则输出0。
|
|
输入示例
|
|
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
0 0 0 2 |
|
其他说明
|
|
数据范围：对于30%的数据，n,m≤1000，对于100%的.据,n,m≤40000，每个节点的编号都不超过40000。
|
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<vector>
#define ll long long
using namespace std;
inline ll read()
{
ll x=0,f=1;char ch=getchar();
while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();}
while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();}
return x*f;
}
int bin[16];
int n,m,root,cnt;
int q[40005],deep[40005],fa[40005][16];
bool vis[40005];
struct data{int to,next;}e[80005];int last[40005];
void insert(int u,int v)
{
e[++cnt].to=v;e[cnt].next=last[u];last[u]=cnt;
e[++cnt].to=u;e[cnt].next=last[v];last[v]=cnt;
}
void bfs()
{
int head=0,tail=1;
q[0]=root;vis[root]=1;
while(head!=tail)
{
int now=q[head];head++;
for(int i=1;i<=15;i++)
if(bin[i]<=deep[now])
fa[now][i]=fa[fa[now][i-1]][i-1];
else break;
for(int i=last[now];i;i=e[i].next)
if(!vis[e[i].to])
{
deep[e[i].to]=deep[now]+1;
fa[e[i].to][0]=now;
vis[e[i].to]=1;
q[tail++]=e[i].to;
}
}
}
int lca(int x,int y)
{
if(deep[x]<deep[y])swap(x,y);
int t=deep[x]-deep[y];
for(int i=0;i<=15;i++)
if(t&bin[i])x=fa[x][i];
for(int i=15;i>=0;i--)
if(fa[x][i]!=fa[y][i])
x=fa[x][i],y=fa[y][i];
if(x==y)return y;
return fa[x][0];
}
int main()
{
bin[0]=1;for(int i=1;i<=15;i++)bin[i]=bin[i-1]<<1;
n=read();
for(int i=1;i<=n;i++)
{
int u=read(),v=read();
if(v==-1)root=u;
else insert(u,v);
}
bfs();
m=read();
for(int i=1;i<=m;i++)
{
int a=read(),b=read(),t=lca(a,b);
if(a==t&&b!=t)puts("1");
else if(a!=t&&b==t)puts("2");
else puts("0");
}
return 0;
}
祖孙询问（C++）