hackercupai/hackercup huggingface dataset:
Let \(K\) be the sum of shipping capacities without any roads being blockaded. We can compute \(K\) in \(O(N \log(N))\) time by sorting and processing the roads in non-increasing order of capacity, while maintaining a [disjoint-set data structure](https://en.wikipedia.org/wiki/Disjoint-set_data_structure) of groups of processing plants connected by roads processed so far (with each road initially in its own group). When road \(i\) is processed, it causes all plants in \(A_i\)'s group to become connected to all plants in \(B_i\)'s group, and must be a minimum-capacity road on the paths between those plants. Therefore, we can increment \(K\) by the product of \(C_i\), the number of plants in \(A_i\)'s group, and the number of plants in \(B_i\)'s group. The two groups should then be merged together.

We'll then want to compute, for each road \(i\), the amount \(Z_i\) by which the sum of shipping capacities would decrease if road \(i\) were blockaded (such that \(S_i = K - Z_i\)).

One possible approach involves two stages of dynamic programming, based on treating the network of plants and roads as a tree rooted at an arbitrary node (plant).

First, let \(D_{i,j}\) be the number of nodes within node \(i\)'s subtree which are reachable from node \(i\) using only edges (roads) with capacities greater than or equal to \(j\). We can compute \(D_{i,j}\) for all pairs \((i, j)\) by recursing through the tree — when a node \(i\) has an edge with capacity \(c\) to a child \(k\), we should increase \(D_{i,c'}\) by \(D_{k,c'}\) for each \(c'\) no greater than \(c\).

Next, let \(U_{i,j}\) similarly be the number of nodes *not* within node \(i\)'s subtree which are reachable from node \(i\) using only edges with capacities greater than or equal to \(j\). We'll recurse through the tree once again to compute these values — when a node \(i\) has an edge with capacity \(c\) to a child \(k\), we should set \(U_{k,c'}\) to equal \(U_{i,c'} + D_{i,c'} - D_{k,c'}\) for each \(c'\) no greater than \(c\).

Finally, let's consider each non-root node \(i\), such that the edge connecting node \(i\) and its parent corresponds to some road \(r\). The number of pairs of plants with shipping capacities greater than or equal to some capacity \(c\) whose routes include road \(r\) must be \(P_{i,c} = D_{i,c} * U_{i,c}\). Furthermore, the number of such pairs with shipping capacities equal to exactly \(c\) must be \(P_{i,c+1} - P_{i,c}\). We can therefore compute \(Z_i\) as the sum of \(c * (P_{i,c+1} - P_{i,c})\) over all capacities \(c\).

This algorithm takes a total of \(O(N (\log(N) + \max(C_{1..N})))\) time.

[See David Harmeyer's solution video here](https://youtu.be/BOPq8MkEG5k).