问题 F: 祖孙询问

时间限制: 1 Sec  内存限制: 128 MB

提交: 13  解决: 6  难度:提高+/省选-

[] [] [] [命题人:]

题目描述

输入

输出

样例输入 Copy

10234 -112 23413 23414 23415 23416 23417 23418 23419 234233 195234 233233 12233 13233 15233 19

样例输出 Copy

10002

提示

 

---

 

 

思路：

　　方法1

　　很明显是一道求lca的题

　　求出lca判断就可以了

1 #include
        
          2 using namespace std; 3 const int mssc=4e4+5; 4 int n,m; 5 int d[mssc],f[mssc][20]; 6 vector
         
           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
          
           =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 }
          
         
        

 

　

方法2

　　求出给定树的dfs序

　　观察可以发现，如果存在x，y有祖孙关系，那么无非就有两种情况：

　　第一种是x在y的区间内

　　第二种就是y在x的区间内

　　那么我们只要求出x和y进入dfs的时间和离开的时间查看他们的包含情况就可以了

　　也就是说 求出这棵树所有点dfs序的时间戳 问询的时候判断一下即可

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