Problem Statement

Given a graph with n nodes, each having a weight, the value of a path between any two nodes is defined as the minimum weight of any node on that path. The task is to find the sum of these values for all pairs of nodes in the graph.

Approach

Consider the weight of an edge to be the minimum value of the weights of the nodes it connects. Now, let's consider the edge with the minimum weight, say w. If we remove this edge, it splits the tree into two subtrees. Suppose the sizes of these two subtrees are x and y. There are exactly x * y pairs of nodes with paths passing through this edge, and since this edge has the minimum weight in the tree, all these paths have a value of w. Thus, the contribution of this edge to the answer is x * y * w.

We then repeat this process for the two subtrees until there are no more edges to remove.

To implement this solution, for each edge (u, v) with weight w, we need to find the sizes of the two subtrees it joins. We can use a simple trick: traverse from the edge with the maximum weight, calculate the answer for this edge, and then merge the two trees it joins.

Code

class DSU {

public:
    vector<int> parent;
    vector<int> size;

    DSU(int n) {
        parent.resize(n);
        size.resize(n, 1);
        for (int i = 0; i < n; ++i) {
            parent[i] = i;  // Initialize each node as its own parent
        }
    }

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

    int getSize(int x) {
        x = find(x);
        return size[x];
    }

    bool unite(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);

        if (rootX == rootY) {
            return false;  // Already in the same set
        }

        // Union by size: attach smaller tree under larger tree
        if (size[rootX] < size[rootY]) {
            swap(rootX, rootY);
        }
        parent[rootY] = rootX;
        size[rootX] += size[rootY];

        return true;
    }
};


ll minimumSum(int n, vector<int> weight, vector<vector<int>> edges) {
    ll ans = 0;
    vector<vector<int>> wedges;

    // Create a list of edges sorted by the minimum weight between nodes u and v
    for (vector<int> &edge : edges) {
        int u = edge[0];
        int v = edge[1];
        wedges.push_back({min(weight[u], weight[v]), u, v});
    }

    DSU dsu(n);
    sort(wedges.begin(), wedges.end());

    // Process edges in ascending order of weights
    for (int i = n - 2; i >= 0; --i) {
        int w = wedges[i][0];  // Minimum weight of edge
        int u = wedges[i][1];  // Node u
        int v = wedges[i][2];  // Node v

        // Add the contribution of this edge to the answer
        ans += w * 1ll * dsu.getSize(u) * 1ll * dsu.getSize(v);

        // Union nodes u and v
        dsu.unite(u, v);
    }

    return ans;
}