那就是最小生成树咯

建树后用LCA求解即可。

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           using namespace std;struct node{ int x,y,d,next;}a[31000];int len,last[21000];void ins(int x,int y,int d){ len++; a[len].x=x;a[len].y=y;a[len].d=d; a[len].next=last[x];last[x]=len;}int Bin[30];int dep[21000],f[30][21000],mx[30][21000];void dfs(int x){ for(int i=1;Bin[i]<=dep[x];i++) { f[i][x]=f[i-1][f[i-1][x]]; mx[i][x]=max(mx[i-1][x],mx[i-1][f[i-1][x]]); } for(int k=last[x];k;k=a[k].next) { int y=a[k].y; if(y!=f[0][x]) { dep[y]=dep[x]+1; f[0][y]=x;mx[0][y]=a[k].d; dfs(y); } }}int LCA(int x,int y){ if(dep[x]
           
            =0;i--) if(dep[x]-dep[y]>=Bin[i]) ans=max(ans,mx[i][x]), x=f[i][x]; if(x==y)return ans; for(int i=25;i>=0;i--) if(dep[x]>=Bin[i]&&f[i][x]!=f[i][y]) ans=max(ans,max(mx[i][x],mx[i][y])), x=f[i][x],y=f[i][y]; return max(ans,max(mx[0][x],mx[0][y]));}struct edge{ int x,y,d;}e[31000];bool cmp(edge n1,edge n2){ return n1.d