Removing Weighted Edges

Frequency: Reported

A country is represented as a connected undirected graph with g_nodes cities and g_edges roads. Nodes are numbered from 1 to g_nodes. Edge i connects g_from[i] and g_to[i] and has weight g_weight[i].

Remove roads while keeping every city reachable from every other city. Return the maximum possible sum of the weights of the removed edges.

Example

g_nodes = 3
g_edges = 3
g_from = [1, 1, 3]
g_to = [2, 3, 1]
g_weight = [-2, 4, -1]

It is optimal to remove edge 1, whose weight is 4. No additional edge can be removed while keeping the graph connected. Return 4.

The edge index in that explanation is zero-based; g_from[1] = 1, g_to[1] = 3, and g_weight[1] = 4.

Function

getMaxWeightSum(
    int g_nodes,
    int g_from[g_edges],
    int g_to[g_edges],
    int g_weight[g_edges]
) -> int

Constraints

2 <= g_nodes <= 2 * 10^5
g_nodes - 1 <= g_edges <= 2 * 10^5
1 <= g_from[i], g_to[i] <= g_nodes
-10^9 <= g_weight[i] <= 10^9

The graph may contain parallel edges and self-loops.