天梯赛-交通运输
#include
#include
#include
using namespace std;
typedef long long LL;
const int N = 200005;
const int INF = 0x3f3f3f3f;
int n, cnt[N], pre[N];
LL res, sum[N];
struct Road
{
int x, y;
int w;
bool operator<(const Road &a)
{
return w > a.w;
}
} road[N];
void init(int n)
{
for (int i = 1; i <= n; i++)
pre[i] = i, cnt[i] = 1;
}
int find(int key)
{
return pre[key] == key ? key : pre[key] = find(pre[key]);
}
int main()
{
while (scanf("%d", &n) != EOF)
{
for (int i = 1; i < n; i++)
cin >> road[i].x >> road[i].y >> road[i].w;
sort(road + 1, road + n);
init(n);
fill(sum, sum + N, res = 0);
for (int i = 1; i < n; i++)
{
int rootx = find(road[i].x), rooty = find(road[i].y);
LL getx = cnt[rooty] * road[i].w + sum[rootx];
LL gety = cnt[rootx] * road[i].w + sum[rooty];
if (getx > gety)
{
pre[rooty] = rootx;
cnt[rootx] += cnt[rooty];
sum[rootx] = getx;
}
else
{
pre[rootx] = rooty;
cnt[rooty] += cnt[rootx];
sum[rooty] = gety;
}
res = max(res, max(getx, gety));
}
cout << res << endl;
}
return 0;
}