Editorial CNNCT2 OCT Long 19 (Unofficial)

If we choose a spanning tree in each graph, we need to maximize the number of same edges in both trees. If the max number is k, then the answer is 2(n-1)-k.
So we need to choose a set of edges that forms forest in both graphs. Forest is considered as graphic matroid, so all we need is to run a matroid intersection.
This works in O(n^3).

BTW matroid intersection was introduced by yanQval in 2018 in China, and it is well known in China now. Until now plenty of problems using matroid intersection has come out, so maybe it is not hard for Chinese to solve a problem like this.

3 Likes

Thanks for the links. :slight_smile:
Quick check says 11 people out of 26 who solved it are from china :stuck_out_tongue:

3 Likes

Could you explain the step going from the largest forest k to 2(n-1) - k. I don’t see why this is true.