题目描述 Description###
已知一棵(n) 个节点的有根树。有(m) 个询问。每个询问给出了一对节点的编号(x) 和(y) ，询问x与y的祖孙关系。
输入描述 Input Description###
输入第一行包括一个整数n表示节点个数。
接下来(n) 行每行一对整数对(a) 和(b) 表示(a) 和(b) 之间有连边。如果(b) 是(-1) ，那么a就是树的根。
第(n+2) 行是一个整数(m) 表示询问个数。
接下来(m) 行，每行两个正整数(x) 和(y) 。
输出描述 Output Description###
对于每一个询问，输出1:如果(x) 是(y) 的祖先，输出2:如果(y) 是(x) 的祖先，否则输出(0) 。
样例输入 Sample Input###
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
样例输出 Sample Output###
1
0
0
0
2
数据范围及提示 Data Size & Hint###
数据范围：对于30%的数据，(n,m≤1000) ，对于100%的.据,(n,m≤40000) ，每个节点的编号都不超过(40000) 。
之前的一些废话###
题解###
对于一棵树求一下(dfs) 序，根据(dfs) 的顺序，每一个点的子孙都属于(dfs) 序中的一个区间，所以在(dfs) 时维护即可。
代码###
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstdio>
#include<queue>
#include<cstring>
using namespace std;
typedef long long LL;
#define mem(a,b) memset(a,b,sizeof(a))
typedef pair<int,int> PII;
#define X first
#define Y second
#define mp make_pair
inline int read()
{
int x=0,f=1;char c=getchar();
while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
while(isdigit(c)){x=x*10+c-'0';c=getchar();}
return x*f;
}
const int maxn=40010;
int n,first[maxn],ce=-1,q,a,b,rt,l[maxn],r[maxn],dfs_clock,m;
struct Edge
{
int u,v,next;
Edge() {}
Edge(int _1,int _2,int _3):u(_1),v(_2),next(_3) {}
}e[maxn<<1];
void addEdge(int a,int b)
{
e[++ce]=Edge(a,b,first[a]);first[a]=ce;
e[++ce]=Edge(b,a,first[b]);first[b]=ce;
}
void dfs(int now,int fa)
{
l[now]=++dfs_clock;
for(int i=first[now];i!=-1;i=e[i].next)
if(e[i].v!=fa)dfs(e[i].v,now);
r[now]=dfs_clock;
}
int main()
{
mem(first,-1);
n=read();
for(int i=1;i<=n;i++)
{
a=read(),b=read();
if(b!=-1)addEdge(a,b);
else rt=a;
}
dfs(rt,-1);
m=read();
while(m--)
{
a=read();b=read();
if(l[b]<=r[a] && l[b]>l[a])printf("1
");
else if(l[a]<=r[b] && l[a]>l[b])printf("2
");
else printf("0
");
}
return 0;
}