Hi again,

For a few weeks I have tried to solve the task here (Toll). I have still not been able to come up with a solution, but I have garnered some ideas:

1. We will brute force over all 2^K subsets of edges to add.
2. Let's add the edges in Kruskal order, except with the K edges as weight -inf. (So if none of the K edges form a cycle, all of them will be added.) Now, all the edges (except the K edges) will be in EVERY MST. So now for each subset of edges we choose in step 1, we can calculate which edges will be in the MST in O(K) time. What I am not so sure about is how to find the length of the K edges.

If anyone could help me continue in this way, or provide a different solution, I would be very appreciative. I have read some blogs like these, but it's still not so clear to me as I don't know Chinese too well.

Thanks,

-minimario