题目描述
输入
输出
样例输入 Copy
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
样例输出 Copy
1
0
0
0
2
提示
思路：
方法1
很明显是一道求lca的题
求出lca判断就可以了
1 #include<bits/stdc++.h> 2 using namespace std; 3 const int mssc=4e4+5; 4 int n,m; 5 int d[mssc],f[mssc][20]; 6 vector<int> g[mssc]; 7 void pre(int u,int fa){//初始化 8 d[u]=d[fa]+1;//求深度 9 for(int i=1;i<=15;i++){//i的范围根据题的数据范围而定 10 f[u][i]=f[f[u][i-1]][i-1]; 11 } 12 int sz=g[u].size();//表示u所连接的边数 13 for(int i=0;i<sz;i++){ 14 if(g[u][i]!=fa){//g[u][i]表示以u为起点所连接的第i条边的终点 15 f[g[u][i]][0]=u; 16 pre(g[u][i],u); 17 } 18 } 19 } 20 int lca(int x,int y){ 21 if(d[x]<d[y]){//让x为深度最深的点 22 swap(x,y); 23 } 24 for(int i=15;i>=0;i--){//跳到同一深度 25 if(d[f[x][i]]>=d[y]){ 26 x=f[x][i]; 27 } 28 if(x==y){//如果此时是同一个点就输出 29 return x; 30 } 31 } 32 for(int i=15;i>=0;i--){//让x，y同时向上跳 33 if(d[f[x][i]]!=d[f[y][i]]){//如果不是同一点就更新x，y的值 34 x=f[x][i]; //如果是同一点那么x的父节点就是答案 35 y=f[y][i]; 36 } 37 } 38 return f[x][0];//答案就是x的父节点 39 } 40 int main(){ 41 scanf("%d",&n); 42 int root; 43 int a,b; 44 for(int i=1;i<=n;i++){ 45 scanf("%d%d",&a,&b); 46 if(b==-1){ 47 root=a; 48 }else{ 49 g[a].push_back(b); 50 g[b].push_back(a); 51 } 52 } 53 pre(root,0); 54 scanf("%d",&m); 55 for(int i=1;i<=m;i++){ 56 scanf("%d%d",&a,&b); 57 int t=lca(a,b); 58 if(t==a&&b!=t){ 59 printf("%d ",1); 60 }else if(t==b&&a!=t){ 61 printf("%d ",2); 62 }else{ 63 printf("%d ",0); 64 } 65 } 66 return 0; 67 }
方法2
求出给定树的dfs序
观察可以发现，如果存在x，y有祖孙关系，那么无非就有两种情况：
第一种是x在y的区间内
第二种就是y在x的区间内
那么我们只要求出x和y进入dfs的时间和离开的时间查看他们的包含情况就可以了
也就是说 求出这棵树所有点dfs序的时间戳 问询的时候判断一下即可
1 #include<bits/stdc++.h> 2 using namespace std; 3 const int maxn=400005; 4 int len,n,m,tim; 5 int st[maxn],et[maxn]; 6 int pos[maxn]; 7 vector<int> g[maxn]; 8 void dfs(int u,int fa){ 9 st[++len]=++tim; 10 pos[u]=len; 11 int sz=g[u].size(); 12 for(int i=0;i<sz;i++){ 13 if(g[u][i]!=fa){ 14 dfs(g[u][i],u); 15 } 16 } 17 et[pos[u]]=++tim; 18 } 19 int main(){ 20 scanf("%d",&n); 21 int a,b,root; 22 for(int i=1;i<=n;i++){ 23 scanf("%d%d",&a,&b); 24 if(b==-1){ 25 root=a; 26 }else{ 27 g[a].push_back(b); 28 g[b].push_back(a); 29 } 30 } 31 dfs(root,0); 32 scanf("%d",&m); 33 for(int i=1;i<=m;i++){ 34 scanf("%d%d",&a,&b); 35 a=pos[a]; 36 b=pos[b]; 37 if(st[a]<st[b]&&st[b]<et[b]&&et[b]<et[a]){//a is elder 38 printf("%d ",1); 39 }else if(st[a]>st[b]&&st[a]<et[a]&&et[b]>et[a]){//b is elder 40 printf("%d ",2); 41 }else{ 42 printf("%d ",0); 43 } 44 } 45 return 0; 46 }