Given a tree with n nodes (≤ 10⁶) and weighted edges, define Min(x, y) as the minimum edge weight along the unique path between nodes x and y. The goal is to compute:

max_{r=1}^n Σ_{v ≠ r} Min(r, v)

A naive approach would compute the sum for each root r by traversing all paths, yielding O(n²) complexity — infeasible for large n.

Instead, reverse the perspective: rather than fixing a root and summing over paths, consider how each edge contributes across all possible root placements. An edge with weight w will be the minimum along all paths that travrese it, provided no smaller-weight edge lies on those paths.

Sort all edges in descending order of weight. Use a Union-Find (Disjoint Set Union) data structure to dynamically maintain connected components. Initially, each node is its own component. As we process each edge from highest to lowest weight, we merge its two endpoints. When merging components A and B of sizes siz[A] and siz[B], every path from a node in A to a node in B must pass through this edge, and since all previously processed edges have higher or equal weight, this edge becomes the minimum for all such paths.

The total contribution of this edge is: w × siz[A] × siz[B]. However, we are not summing over all pairs — we are maximizing the sum over all roots. For each root placement, we want the sum of Min(root, v) over all v ≠ root.

Key insight: when merging A and B, if we later choose the root in A, then all nodes in B contribute w to the sum. Similarly, if the root is in B, then all nodes in A contribute w. So for each merge, we update the best possible sum for the merged component as:

best[new] = max(best[A] + siz[B] × w, best[B] + siz[A] × w)

This reflects the optimal root placement within the merged component. The final answer is the value stored in the single remaining component after processing all edges.

Time complexity: O(n log n) due to sorting and near-constant Union-Find operations.

#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
using namespace std;

typedef long long ll;

const int MAXN = 1e6 + 10;

struct Edge {
    int u, v, w;
};

int n;
int parent[MAXN], size[MAXN];
ll best[MAXN];
Edge edges[MAXN];

int find(int x) {
    return parent[x] == x ? x : parent[x] = find(parent[x]);
}

void merge(int u, int v, int w) {
    int ru = find(u), rv = find(v);
    if (ru == rv) return;
    if (size[ru] < size[rv]) swap(ru, rv);
    ll contribA = best[rv] + (ll)size[rv] * w;
    ll contribB = best[ru] + (ll)size[ru] * w;
    best[ru] = max(contribA, contribB);
    parent[rv] = ru;
    size[ru] += size[rv];
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    for (int i = 1; i <= n; ++i) {
        parent[i] = i;
        size[i] = 1;
        best[i] = 0;
    }

    for (int i = 1; i < n; ++i) {
        cin >> edges[i].u >> edges[i].v >> edges[i].w;
    }

    sort(edges + 1, edges + n, [](const Edge &a, const Edge &b) {
        return a.w > b.w;
    });

    for (int i = 1; i < n; ++i) {
        merge(edges[i].u, edges[i].v, edges[i].w);
    }

    cout << best[find(1)] << '\n';
    return 0;
}