描述 Description
已知一棵 n 个节点的有根树。有 m 个询问。每个询问给出了一对节点的编号 x 和 y，询问 x 与 y 的祖孙关系。
输入格式 InputFormat
输入第一行包括一个整数 n 表示节点个数。
接下来 n 行每行一对整数对 a 和 b 表示 a 和 b 之间有连边。如果 b 是 - 1，那么 a 就是树的根。
第 n+2 行是一个整数 m 表示询问个数。
接下来 m 行，每行两个正整数 x 和 y。
输出格式 OutputFormat
对于每一个询问，输出 1: 如果 x 是 y 的祖先，输出 2: 如果 y 是 x 的祖先，否则输出 0。
样例输入 SampleInput
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
样例输出 SampleOutput
1
0
0
0
2
来源 Source
2014-10-5 NOIP 模拟赛 by lwher
代码 Code
求 LCA。
#include <stdio.h>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
int i,j,t,n,m,l,r,k,z,y,x;
struct edge
{
int to,next,val;
}e[80005],q[80005];
int head[40005],qhead[40005],fa[40005];
int ans[40005];
bool vis[40005];
pair <int,int> p[40005];
int s,ecnt,qcnt;
inline void ins(int u,int v)
{
e[++ecnt].to=v;e[ecnt].next=head[u];
head[u]=ecnt;
}
inline void qins(int u,int v,int w)
{
q[++qcnt].to=v;q[qcnt].next=qhead[u];q[qcnt].val=w;
qhead[u]=qcnt;
}
int getfa(int s)
{
if (fa[s]==s) return s;
fa[s]=getfa(fa[s]);
return fa[s];
}
void tarjan(int u)
{
int i,j,t;
vis[u]=true;
fa[u]=u;
for (i=qhead[u];i;i=q[i].next) if (vis[q[i].to])
{
ans[q[i].val]=getfa(q[i].to);
}
for (i=head[u];i;i=e[i].next) if (!vis[e[i].to])
{
tarjan(e[i].to);
fa[e[i].to]=u;
}
}
int main()
{
memset(vis,false,sizeof(vis));
scanf("%d",&n);
for (i=1;i<=n;i++)
{
scanf("%d%d",&x,&y);
if (y==-1) s=x;
else
{
ins(x,y);
ins(y,x);
}
}
scanf("%d",&m);
for (i=1;i<=m;i++)
{
scanf("%d%d",&x,&y);
p[i]=make_pair(x,y);
qins(x,y,i);
qins(y,x,i);
}
tarjan(s);
for (i=1;i<=m;i++)
{
if (ans[i]==p[i].first) printf("%d\n",1);
else if (ans[i]==p[i].second) printf("%d\n",2);
else printf("%d\n",0);
}
return 0;
}