天梯赛-交通运输

#include <iostream>
#include <algorithm>
#include <cstring>
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;
}