给你一颗树 每条边有一个权值 选择一个点为中心 定义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 <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <cmath>
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;
}