祖孙询问 （lca或dfs序＋时间戳）

 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\n",1);        
60         }else if(t==b&&a!=t){
61             printf("%d\n",2);
62         }else{
63             printf("%d\n",0);
64         }
65     }
66     return 0;
67 }

 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\n",1);
39         }else if(st[a]>st[b]&&st[a]<et[a]&&et[b]>et[a]){//b is elder
40             printf("%d\n",2);
41         }else{
42             printf("%d\n",0);
43         }
44     }
45     return 0;
46 }