Min-Fund Prison (Hard)
Contest: Helvetic Coding Contest 2024 online mirror (teams allowed, unrated)
Difficulty rating: 2400
Tags: bitmasks, dfs and similar, dp, graphs, trees

In the hard version, $$$2 \leq \sum n \leq 10^5$$$ and $$$1 \leq \sum m \leq 5 \times 10^{5}$$$

After a worker's strike organized by the Dementors asking for equal rights, the prison of Azkaban has suffered some damage. After settling the spirits, the Ministry of Magic is looking to renovate the prison to ensure that the Dementors are kept in check. The prison consists of $$$n$$$ prison cells and $$$m$$$ bi-directional corridors. The $$$i^{th}$$$ corridor is from cells $$$u_i$$$ to $$$v_i$$$. A subset of these cells $$$S$$$ is called a complex if any cell in $$$S$$$ is reachable from any other cell in $$$S$$$. Formally, a subset of cells $$$S$$$ is a complex if $$$x$$$ and $$$y$$$ are reachable from each other for all $$$x, y \in S$$$, using only cells from $$$S$$$ on the way. The funding required for a complex $$$S$$$ consisting of $$$k$$$ cells is defined as $$$k^2$$$.

As part of your Intro to Magical Interior Design course at Hogwarts, you have been tasked with designing the prison. The Ministry of Magic has asked that you divide the prison into $$$2$$$ complexes with $$$\textbf{exactly one corridor}$$$ connecting them, so that the Dementors can't organize union meetings. For this purpose, you are allowed to build bi-directional corridors. The funding required to build a corridor between any $$$2$$$ cells is $$$c$$$.

Due to budget cuts and the ongoing fight against the Death Eaters, you must find the $$$\textbf{minimum total funding}$$$ required to divide the prison as per the Ministry's requirements or $$$-1$$$ if no division is possible.

Note: The total funding is the sum of the funding required for the $$$2$$$ complexes and the corridors built. If after the division, the two complexes have $$$x$$$ and $$$y$$$ cells respectively and you have built a total of $$$a$$$ corridors, the total funding will be $$$x^2 + y^2 + c \times a$$$. Note that $$$x+y=n$$$.

Input format:
The first line contains one integer $$$t$$$ ($$$1 \leq t \leq 10^5$$$) — the number of test cases. Then $$$t$$$ test cases follow.

The first line of each test case consists of three integers $$$n, m$$$ and $$$c$$$ ($$$2 \leq n \leq 10^5$$$, $$$1 \leq m \leq 5 \times 10^{5}$$$, $$$1 \leq c \leq 10^9$$$)

$$$m$$$ lines follow, each consisting of 2 integers — $$$u_i, v_i$$$ indicating a corridor is present between cells $$$u_i$$$ and $$$v_i$$$ ($$$1 \leq u_i, v_i \leq n$$$, $$$u_i \neq v_i$$$)

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^5$$$.

It is guaranteed that the sum of $$$m$$$ over all test cases does not exceed $$$5 \times 10^5$$$.

It is guaranteed that there exists at most one corridor between any two cells.

Output format:
Print the $$$\textbf{minimum funding}$$$ required to divide the prison as per the Ministry's requirements or $$$-1$$$ if no division is possible.

Constraints:
Time limit: 1.5 s
Memory limit: 256.0 MB

Note:
In the first test case of the sample input, there is no way to divide the prison according to the Ministry's requirements.

In the second test case, consider the corridor between cells $$$1$$$ and $$$5$$$ as the connection between the $$$2$$$ complexes consisting of $$$\{2, 3, 5, 6\}$$$ and $$$\{1, 4\}$$$ cells respectively. There are no new corridors built. The total funding is $$$4^2 + 2^2 = 20$$$. You can verify this is the minimum funding required.

In the third test case, build a corridor between $$$2$$$ and $$$4$$$. Consider the corridor between cells $$$1$$$ and $$$5$$$ as the connection between the $$$2$$$ complexes consisting of $$$\{3, 5, 6\}$$$ and $$$\{1, 2, 4\}$$$ cells respectively. The total funding is $$$3^2 + 3^2 + 7 \times 1 = 25$$$. You can verify this is the minimum funding required.

In the fourth test case, build a corridor between $$$2$$$ and $$$4$$$ and between $$$5$$$ and $$$7$$$. Consider the corridor between cells $$$5$$$ and $$$7$$$ as the connection between the $$$2$$$ complexes consisting of $$$\{1, 2, 4, 7\}$$$ and $$$\{3, 5, 6\}$$$ cells respectively. The total funding is $$$4^2 + 3^2 + 4 \times 2 = 33$$$. You can verify this is the minimum funding required.

Note for all test cases that there may be multiple ways to get the same funding but there is no other division which will have a more optimal minimum funding.

Example input:
4
4 6 5
4 3
2 3
2 4
1 2
4 1
3 1
6 6 2
1 4
2 5
3 6
1 5
3 5
6 5
6 5 7
1 4
2 5
3 6
3 5
6 5
7 5 4
1 4
3 6
3 5
6 5
2 7

Example output:
-1
20
25
33

Editorial:
In the hard subtask, the $$$O(n^2)$$$ solution is too slow.
One way to get it accepted is to use bitsets to speed it up, as the knapsack transitions can simply be expressed as a bitwise shift + bitwise or.
However, there is also an asymptotically faster approach. First of all, instead of remembering the possible splits using a bridge for each component, we will just remember for each component size, how it can be split by a bridge. Since the sum of component sizes is $$$n$$$, this needs only $$$O(n)$$$ memory.
Now, if we have at least four components of the same size $$$x$$$, for the purposes of our knapsack we can replace two of them with a component of size $$$2x$$$, and the set of reachable complex sizes will not change. Since we keep at least two components of size $$$x$$$, the set of reachable complex sizes will not change even if we later split one of the components of size $$$x$$$ using the bridges.
If we repeat the above procedure until we have at most three components of each size, the total number of components will be $$$O(\sqrt{n})$$$. Therefore the knapsack dynamic programming that does not take splitting via a bridge into account will run in $$$O(n\cdot\sqrt{n})$$$.
In order to tackle the splitting via a bridge fast, let us first run the dynamic programming that does not allow to split components, but instead of computing a boolean for each complex size that tells if this size can be reached, we will compute the number of ways to reach it, modulo a large prime.
A step of this dynamic programming is reversible, therefore we can then for each component size compute in $$$O(n)$$$ which sizes can be reached without using one of the components of this size. Now we need to combine this with the ways to split a component of this size using a bridge, and since the sum of squares of the sizes is smaller whenever the sizes are closer to each other, for each way to split the component using a bridge we need to find the reachable state of the dynamic programming that is the closest to $$$\frac{n}{2}$$$ minus the size of the part disconnected by the bridge, which can be done in $$$O(n)$$$ for all ways to split using a bridge via the two pointer method.
Therefore the total running time of this solution is $$$O(n\cdot\sqrt{n})$$$.