差不多一道LCA模板题目~ 学完tarjan算法 看自己能不能AC掉

 

1 #include 
     
       2 #include 
      
        3   4 int dis[33333],head[33333],fa[33333][33],deep[33333]; 5 int Count,n,q,ans,last=1; 6   7   8 struct node{ 9     int v,next,w;10     node(){}11     node(int _v,int _next,int _w){12         v = _v;13         next = _next;14         w = _w;15     }16 }Edge[233333];17  18 void AddEdge(int u,int v,int w){19     Count++;20     Edge[Count] = node(v,head[u],w);21     head[u] = Count;22 }23  24 void dfs(int now,int f){25     for(int i=head[now];i;i=Edge[i].next){26         if(f==Edge[i].v) continue;27         deep[Edge[i].v] = deep[now]+1;28         fa[Edge[i].v][0]=now;29         dis[Edge[i].v]=dis[now]+Edge[i].w;30         dfs(Edge[i].v,now);31     }32 }33  34 int lca(int x,int y){35     if(deep[x]
       
        =0&&k;i--){38         if((1<
        
         =0;i--){45         if(fa[x][i]!=fa[y][i]){46             x = fa[x][i];47             y = fa[y][i];48         }49     }50     if(x!=y) x = fa[x][0];51     return x;52 }53  54 int main(){55     //freopen("fuckyou.out","w",stdout);56     scanf("%d",&n);57     for(int i=1;i