CF1559D2 Mocha and Diana (Hard Version)
Description
This is the hard version of the problem. The only difference between the two versions is the constraint on $ n $ . You can make hacks only if all versions of the problem are solved.
A forest is an undirected graph without cycles (not necessarily connected).
Mocha and Diana are friends in Zhijiang, both of them have a forest with nodes numbered from $ 1 $ to $ n $ , and they would like to add edges to their forests such that:
- After adding edges, both of their graphs are still forests.
- They add the same edges. That is, if an edge $ (u, v) $ is added to Mocha's forest, then an edge $ (u, v) $ is added to Diana's forest, and vice versa.
Mocha and Diana want to know the maximum number of edges they can add, and which edges to add.
Input Format
N/A
Output Format
N/A
Explanation/Hint
In the first example, we cannot add any edge.
In the second example, the initial forests are as follows.
We can add an edge $ (2, 4) $ .
