This problem can be cracked in polynomial time with various approaches. I'll introduce a few of them.
$$$O(n^3)$$$
As stated in the problem, this problem is a straightforward bipartite matching problem. With a simple DFS or union-find, you can construct a bipartite graph in the statement, and use well-known maximum matching algorithm.
$$$O(n^{1.5}\log n)$$$
By using a similar solution to Codeforces 786E: ALT, you can reduce the time complexity to $$$O(n^{1.5}\log n)$$$. The author didn't manage to squeeze this approach in time.
$$$O(n^2)$$$:
By looking at the sample, it seems that $$$m = n-1$$$ always holds for some reason. In other words, the given graph always has a perfect matching. It turns out that this guess is true. Let's try to prove it using induction.
Inductive Proof. Attempt 1
We induct on the quantity $$$|E(T_1) - E(T_2)|$$$. If the quantity is zero, then we can find an obvious bijection. Otherwise, we can find some edge $$$e \in E(T_1) - E(T_2)$$$. Since our goal is to reduce the difference, it would be reasonable to replace this edge to some other edge $$$f \in E(T_2) - E(T_1)$$$. Hopefully, we can show the following:
Lemma 1. For any $$$e \in E(T_1) - E(T_2)$$$, there exists some edge $$$f \in E(T_2) - E(T_1)$$$ such that $$$T_1 - {e} + {f}$$$ is a tree.
Proof. $$$T_1 - {e}$$$ have two components. If there exists an edge $$$f$$$ that connects these two parts, we are done. Otherwise, $$$T_2$$$ has no edges connecting these parts, finding a cut.
Then, we can simply add the bijection $$${e \rightarrow f}$$$, replace the edge $$$e$$$ with $$$f$$$ in $$$T_1$$$, and continue. Right? Sadly, this is wrong as it is changing the tree $$$T_1$$$. Although we found the pair of tree $$$(T_1 - {e} + {f}, T_2)$$$ with less value $$$|E(T_1) - E(T_2)|$$$, finding a bijection over $$$T_1 - {e} + {f}$$$ to $$$T_2$$$ is a different story, thus the proof fails.
Inductive Proof. Attempt 2
It would be good to make $$$T_1$$$ static, since otherwise our induction will fail. Then, what about repeating induction over $$$(T_1, T_2 + {e} - {f})$$$? Everything is good, but then we should also guarantee $$$T_2 + {e} - {f}$$$ is a tree. Is it possible?
Lemma 2. For any $$$e \in E(T_1) - E(T_2)$$$, there exists some edge $$$f \in E(T_2) - E(T_1)$$$ such that $$$T_1 - {e} + {f}$$$ and $$$T_2 + {e} - {f}$$$ is a tree.
Proof. $$$T_2 + {e}$$$ has exactly one cycle $$$C$$$. Since $$$T_2 + {e} - {f}$$$ should remain acyclic, $$$f \in C$$$ should hold. The cycle consists of edge $$$e$$$ and path from $$$T_2$$$, we should find such $$$f$$$ from the path in $$$T_2$$$, such that its endpoint connects two different component of $$$T_1 - {e}$$$. Label the vertices in the path by its component membership of $$$T_1 - {e}$$$. Since $$$e$$$ itself connects the different component, there should exist a edge in the path, which connects different component. Take it.
Now, as $$$T_1 - {e} + {f}, T_2 - {f} + {e}$$$ is both acyclic, we can create the bijection $$${e \rightarrow f}$$$, and also take $$$(T_1, T_2 - {f} + {e})$$$ for the induction stage. This proof also gives a straightforward $$$O(n^2)$$$ algorithm for finding the answer.
$$$O(n\log n)$$$
When we fix $$$e \in E(T_1) - E(T_2)$$$, finding the component where each vertices lie is easy: This can be done by preprocessing $$$T_1$$$ with a single depth-first search. Using this to find the $$$f$$$ is a different story: We have dynamically changing tree of $$$T_2$$$, which is hard to maintain.
On the other hand, since Lemma 2 is symmetric, we can rather fix $$$f \in E(T_2) - E(T_1)$$$ and find $$$e$$$ instead. In this case, if we can know which subtree that a vertex belongs for $$$T_2 - {f}$$$:
- If $$$f = {u, v}$$$, find the path between $$$u \rightarrow v$$$ in $$$T_1$$$
- If $$$LCA(u, v)$$$ belongs to same component in $$$u$$$, then find $$$f$$$ in path $$$v \rightarrow LCA(u, v)$$$. Otherwise, find $$$f$$$ in path $$$u \rightarrow LCA(u, v)$$$.
- Now, you can find $$$e$$$ using binary search on paths, which can be implemented with binary lifting
Since $$$T_1$$$ is static, we can afford all these operation in $$$O(n \log n)$$$ time preprocessing. Now the point is to maintain $$$T_2$$$ to support subtree membership query. This can be done straightforwardly using Link-Cut tree or Euler Tour tree using $$$O(\log n)$$$ query time, which results in $$$O(n\log^2 n)$$$ time, but this is too slow (at least for us) to pass.
Now from this point, we will assume $$$E(T_1) \cap E(T_2) = \emptyset$$$. We have a freedom over choosing $$$f$$$, so let's choose the $$$f$$$ as the edge connecting the leaf. The good property of leaf is that the subtree membership query is very easy: You can simply compare the vertex number. So, if we choose such $$$f$$$, we can find $$$e$$$ easily.
What about changing the tree $$$T_2$$$ to $$$T_2 - {f} + {e}$$$ ? Note that, After $$$T_2$$$ becomes $$$T_2 - {f} + {e}$$$, we don't have to care about $$$e$$$ because it's in the intersection of $$$T_1$$$ and $$$T_2$$$. We can think about contracting the edge $$$e$$$: After adding an edge $$$e$$$ we can not delete, so in the component point of view, they are always in the same component: So we can remove the leaf edge $$$f$$$, and contract the ends of $$$e$$$. For the data structure to maintain these components, we can use Union-Find.
Writer: ko_osaga
