Gym100685G Gadget Hackwrench（倍增LCA）

题目大概说一棵边有方向的树，q个询问，每次询问结点u是否能走到v。

倍增LCA搞即可：

• 除了par[k][u]表示u结点往上走2^k步到达的结点，
• 再加上upp[k][u]表示u结点往上走2^k步经过边的状态：-1表示边都是向下，1表示都是向上，0混合。
• 这样u、v都往LCA上走就能知道u是否能走到v了。

 #include<cstdio>
 #include<cstring>
 #include<algorithm>
 using namespace std;
 #define MAXN 111111 struct Edge{
     int v,w,next;
 }edge[MAXN<<];
 int NE,head[MAXN];
 void addEdge(int u,int v,int w){
     edge[NE].v=v; edge[NE].w=w; edge[NE].next=head[u];
     head[u]=NE++;
 } int dep[MAXN],par[][MAXN],upp[][MAXN];
 void dfs(int u,int fa){
     for(int i=head[u]; i!=-; i=edge[i].next){
         int v=edge[i].v;
         if(v==fa) continue;
         dep[v]=dep[u]+;
         par[][v]=u;
         upp[][v]=edge[i].w;
         dfs(v,u);
     }
 } void init(int n){
     for(int i=; i<; ++i){
         for(int j=; j<=n; ++j){
             if(par[i-][j]==){
                 par[i][j]=;
                 continue;
             }
             par[i][j]=par[i-][par[i-][j]];
             if(upp[i-][j]== && upp[i-][par[i-][j]]==){
                 upp[i][j]=;
             }else if(upp[i-][j]==- && upp[i-][par[i-][j]]==-){
                 upp[i][j]=-;
             }else{
                 upp[i][j]=;
             }
         }
     }
 }
 bool lca(int u,int v){
     if(dep[u]>dep[v]){
         for(int i=; i<; ++i){
             if((dep[u]-dep[v])>>i&){
                 if(upp[i][u]!=) return ;
                 u=par[i][u];
             }
         }
         if(u==v) return ;
         for(int i=; i>=; --i){
             if(par[i][u]!=par[i][v]){
                 if(upp[i][u]!= || upp[i][v]!=-) return ;
                 u=par[i][u]; v=par[i][v];
             }
         }
         if(upp[][u]!= || upp[][v]!=-) return ;
     }else{
         for(int i=; i<; ++i){
             if((dep[v]-dep[u])>>i&){
                 if(upp[i][v]!=-) return ;
                 v=par[i][v];
             }
         }
         if(u==v) return ;
         for(int i=; i>=; --i){
             if(par[i][u]!=par[i][v]){
                 if(upp[i][u]!= || upp[i][v]!=-) return ;
                 u=par[i][u]; v=par[i][v];
             }
         }
         if(upp[][u]!= || upp[][v]!=-) return ;
     }
     return ;
 } int main(){
     int n,q,a,b;
     while(~scanf("%d",&n)){
         NE=;
         memset(head,-,sizeof(head));
         for(int i=; i<n; ++i){
             scanf("%d%d",&a,&b);
             addEdge(a,b,-);
             addEdge(b,a,);
         }         dfs(,);
         init(n);         scanf("%d",&q);
         while(q--){
             scanf("%d%d",&a,&b);
             if(lca(a,b)) puts("Yes");
             else puts("No");
         }
     }
     return ;
 }