题目链接：点击打开链接
题目大意：
给你一个n，表示有n个关系，每个关系有，a，b两个数
表示b是a的父节点
然后输入一个t
进行t次访问，对于每次访问包含两个数，x，y，如果x是y的父节点输出2，如果y是x的父节点输出1
如果两个没关系输出0
这道题当然最先想到的思路是并查集
这里的并查集并不需要把树扁平化，不用优化（如果优化反而做不了）
这样找一个点的所有父节点，看是不是另一个点，顺便看一下另一个点的所有父节点
这样想想，这样的代码肯定超时
毕竟4W个数据不是骗你的
那如何是好
下面给大家介绍一种方法
对于每个数我们用一个区间表示
即开两个数组a，b。a用来记录左端点，b用来记录友端点
拿样例说话
对于234，他是12，13,14,15,16,17,18,19的父节点
19是233的父节点（建议大家自己手动画图）
这样，对于234的区间是【0,9】
对于12的区间为【1,1】，13的区间是【2,2】，14的区间是【3,3】15的区间是【5,5】
一直到19的区间是【8,9】那么233的区间是【9,9】如果233下面还有一个子节点232
那么232的区间是【9,9】
这样如果一个数的区间正好完全包含了另一个数，那么这个数是另一个数的子节点
方法很巧，具体的实现也不难！
#include<stdio.h> #include<string.h> #include<vector> using namespace std; int l[40005],r[40005],vis[40005]; vector<int>s[40005]; int num,first; void dfs(int x)//可能这个递归有些难以理解 { vis[x]=1; //这个点搜过了标记一下 l[x]=num++; //先确定左区间（每递归一次num++） for(int i=0;i<s[x].size();i++)//将数组的数遍历一遍 { int k=s[x][i];//找出递归的下一个点 if(!vis[k])//如果点没被标记，可以走 { dfs(k); } } r[x]=num-1; //找出右区间 } int main() { int n; scanf("%d",&n); int a,b; for(int i=1;i<=n;i++) { scanf("%d%d",&a,&b); if(b==-1) { first=a; } else { s[b].push_back(a); } } num=0; memset(l,0,sizeof(l)); memset(r,0,sizeof(r)); memset(vis,0,sizeof(vis)); dfs(first); int t; scanf("%d",&t); int x,y; for(int i=1;i<=t;i++) { scanf("%d%d",&x,&y); //printf("l[%d]=%d r[%d]=%d\n",y,l[y],y,r[y]); //输出点的两个边界有助于理解 if(l[x]<=l[y]&&r[y]<=r[x]) { printf("1\n"); } else if(l[y]<=l[x]&&r[x]<=r[y]) { printf("2\n"); } else { printf("0\n"); } } }
