直接写一波Lca就好了

1 #include
      
        2 #include
       
         3 #include
        
          4 using namespace std; 5 const int maxn=1010; 6 int n,m,x,y,z,ans=0,tot=0,dis[maxn],last[maxn],dep[maxn],p[maxn][32]; 7 struct edge{
    int to,pre,dis;}e[maxn<<1]; 8  9 void read(int &k){10     k=0; int f=1; char c=getchar();11     while (c<'0'||c>'9')c=='-'&&(f=-1),c=getchar();12     while ('0'<=c&&c<='9')k=k*10+c-'0',c=getchar();13     k*=f;14 }15 void add(int x,int y,int z){e[++tot].to=y;e[tot].pre=last[x];e[tot].dis=z;last[x]=tot;}16 void dfs(int u,int fa){17     dep[u]=dep[fa]+1; p[u][0]=fa;18     for (int i=1;i<=log2(dep[u]);i++) p[u][i]=p[p[u][i-1]][i-1];19     for (int i=last[u],to=e[i].to;i;i=e[i].pre,to=e[i].to)20     if (to!=fa) dis[to]=dis[u]+e[i].dis,dfs(to,u);21 }22 int lca(int x,int y){23     if (dep[x]
         
          dep[y])25     for (int i=log2(dep[x]-dep[y]+1);i>=0,dep[x]!=dep[y];i--)26         if (dep[p[x][i]]>=dep[y]) x=p[x][i];27      if (x==y) return x;28      for (int i=log2(dep[x]);i>=0;i--)29      if (p[x][i]!=p[y][i]) x=p[x][i],y=p[y][i];30      return p[x][0];31 }32 int main(){33     read(n); read(m);34     for (int i=1;i