1) Greedy solution

We could always pick the vertex with the lowest removal cost (ties broken arbitrarily). Intuitively, that is because the score we’re minimizing cannot be lower than what the lowest removal cost is right now, so we might as well remove that vertex now and update its neighbors’ costs.

By using a priority queue to find the lowest removal cost (similar to Dijkstra’s shortest path algorithm) this solution can be implemented with running time \(O((N+M) \log (N+M))\).

2) Binary search solution (similar to official editorial)

This is a “minimax” (minimum of maximums) problem, which is often solved by some kind of binary search, and in this case it’s exactly what we do. Note the upper bound might be about \(\sum A_i\).

Having fixed a maximum cost, we can only perform operations not more than that cost. Mark all vertices that can be removed and keep them in a stack. Then when we remove a vertex \(v\), note that the costs of neighbors are reduced by \(A_v\). If this makes an unmarked vertex removable, we can mark them and add them to the stack too. When the stack is empty, we can check if all vertices are marked. If all vertices are marked (i.e. removed) then the answer is not more than our chosen cost, otherwise it has to be more.

Time complexity should be \(O((N+M)\log \sum A_i)\), which should be fast enough.