给你一颗树 每条边有一个权值 选择一个点为中心 定义S值为中心到其他n-1个点的路径上的最小边权 求所有点S值的和

从大到小排序 每次合并2棵树 设为A集合 B集合 设A集合的最大S值的和为sumA B集合为sumB

中心在A或者B现在加入A-B这条边使得2个集合连通 因为A-B这条边的权值小于等于AB集合里面边的权值 所以如果合并之后中心在A 那么sumA = sumA+B集合的点数*A-B这条边的权值 sumB = sumB+A集合的点数*A-B这条边的权值 2者取大

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        using namespace std; const int maxn = 200010; int n; int f[maxn], rank[maxn]; __int64 sum[maxn]; struct edge { int u, v, w; }e[maxn]; int find(int x) { if(x != f[x]) return f[x] = find(f[x]); return f[x]; } bool cmp(edge a, edge b) { return a.w > b.w; } int main() { while(scanf("%d", &n) != EOF) { for(int i = 0; i < n-1; i++) scanf("%d %d %d", &e[i].u, &e[i].v, &e[i].w); sort(e, e+n-1, cmp); for(int i = 0; i <= n; i++) f[i] = i, sum[i] = 0, rank[i] = 1; for(int i = 0; i < n-1; i++) { int x = find(e[i].u); int y = find(e[i].v); if(x != y) { if(sum[x]+(__int64)e[i].w*rank[y] > sum[y]+(__int64)e[i].w*rank[x]) { f[y] = x; sum[x] = sum[x]+(__int64)e[i].w*rank[y]; rank[x] += rank[y]; } else { f[x] = y; sum[y] = sum[y]+(__int64)e[i].w*rank[x]; rank[y] += rank[x]; } } } int x = find(1); printf("%I64d\n", sum[x]); } return 0; }