题目描述
已知一棵n个节点的有根树。有m个询问。每个询问给出了一对节点的编号x和y，询问x与y的祖孙关系。
输入输出格式
输入格式：
输入第一行包括一个整数n表示节点个数。 接下来n行每行一对整数对a和b表示a和b之间有连边。如果b是-1，那么a就是树的根。 第n+2行是一个整数m表示询问个数。 接下来m行，每行两个正整数x和y。
输出格式：
对于每一个询问，如果x是y的祖先，输出1；如果y是x的祖先，输出2；否则输出0。
输入输出样例
输入样例#1： 复制
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： 复制
1
0
0
0
2
说明
对于30%的数据，n, m ≤ 1000。
对于100%的数据，n, m ≤ 40000，每个节点的编号都不超过40000。
思路：求出两点的LCA后，若其中有一个点为LCA，则这个点为另一个点的祖先，输出 1 或 2，反之，输出 0
#include<cstdio> #include<algorithm> const int N=40001; int n,m,tot,root,fa[N],ans[N],head[N],_head[N]; struct Edge{ int v,nxt; }edge[N<<1]; struct EDge{ int x,v,nxt,id; }_edge[N<<1]; inline int read() { int n=0,w=1;register char c=getchar(); while(c<'0'||c>'9'){if(c=='-')w=-1;c=getchar();} while(c>='0'&&c<='9')n=n*10+c-'0',c=getchar(); return n*w; } int find(int x) {return fa[x]==x?fa[x]:fa[x]=find(fa[x]);} inline void add(int u,int v) {edge[++tot]=(Edge){v,head[u]};head[u]=tot;} inline void _add(int x,int u,int v,int i) {_edge[++tot]=(EDge){x,v,_head[u],i};_head[u]=tot;} bool vis[N]; void dfs(int now) { vis[now]=true; for(int v,i=head[now];i;i=edge[i].nxt) if(!vis[v=edge[i].v]) dfs(v),fa[v]=now; for(int x,i=_head[now];i;i=_edge[i].nxt) if(vis[_edge[i].v]) { x=find(_edge[i].v); if(x==now) ans[_edge[i].id]=(now==_edge[i].x?1:2); } } int main() { n=read(); for(int i=1;i<=N;++i) fa[i]=i; for(int u,v,i=1;i<=n;++i) { u=read(),v=read(); if(v==-1) root=u; else add(u,v),add(v,u); } tot=0;m=read(); for(int x,y,i=1;i<=m;++i) { x=read(),y=read(); _add(x,x,y,i),_add(x,y,x,i); } dfs(root); for(int i=1;i<=m;++i) printf("%d ",ans[i]); return 0; }