题面：

题解：LCA模版题

代码：

1 #include
     
       2 #include
      
        3 #include
       
         4 using namespace std; 5 const int maxn=1000,max_log=10; 6 int N,Q,F[maxn+5][max_log+2],edge_head[maxn+5],num_edge=0,c,Dep[maxn+5],u,v,w,A,B; 7 int Sig[maxn+5]; 8 struct Edge{ 9     int to,nx,dis;10 }edge[(maxn<<1)+5];11 inline void Add_edge(int from,int to,int dis){12     edge[++num_edge].nx=edge_head[from];13     edge[num_edge].to=to;14     edge[num_edge].dis=dis;15     edge_head[from]=num_edge;16     return;17 }18 inline void Dfs(int x,int fa){19     Dep[x]=Dep[fa]+1;20     F[x][0]=fa;21     for(int i=1;i<=max_log;i++)22         F[x][i]=F[F[x][i-1]][i-1];23     for(int i=edge_head[x];i;i=edge[i].nx){24         int y=edge[i].to;25         if(y==fa)continue;   26         Sig[y]=Sig[x]+edge[i].dis;27         Dfs(y,x);28     }29     return;30 }31 inline int LCA(int x,int y){32     if(Dep[x]
        
         =0;i--){36         int a;a=F[x][i];37         if(Dep[a]>=Dep[y])x=a;38         if(x==y)return x;39     }    40     for(int i=max_log;i>=0;i--){41         int a,b;a=F[x][i];b=F[y][i];42         if(a!=b){43             x=a;y=b;44         }45     }46     return F[x][0];47 }48 int main(){49     scanf("%d%d",&N,&Q);50     for(int i=1;i
        
       
      
     

---

By:AlenaNuna