I was looking back on some previous contests, and I got to this problem.

I know the algorithm, which can be found on editorial: check each edge, and add min of subtree sizes when this edge is broken. But how do we extend this to find the pairs that we want to match? This algorithm gives the distance, not the pairs to be matched, and the editorial claims "not many modifications required".

However, I can't see it. If anyone could help, I would be really appreciated!

Thanks,

minimario