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 Let the weight of an edge be the minimum value of weights of nodes it connects. Now consider the edge with minimum weigth say w. Split the tree into two by removing this edge. Say the two subtrees have size x and y. Now there are exactly x * y pairs of nodes that have path passing through this edge, and since the weight of this edge is minimum in the tree they all have a value of w. Thus contribution of this edge to the answer is x * y * w. Now repeat the process for the two trees we have until there are no more edges to remove.

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

Code:

class DSU { public: vector parent; vector 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 weight, vector<vector> edges) { ll ans = 0; vector<vector> 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;

}