Official Analysis

Explanation

For the first few test cases where $t=c$, we can solve the problem by constructing an MST with $t$ being the weights. If we let $T = \sum t$ and $C = \sum c$, $V = T \cdot C = T^2$ will be minimized when $T$ is minimized.

To solve the problem completely, we will have to minimize the product of those two sums, $V = C \cdot T$. The solution space contains all possible MSTs with their respective $T$ and $C$ values. We can view each of those possible solutions as a 2D-point $(T, C)$. There exists a curve $C(T) = \frac{V}{T}$ such that every point on it has the same $V$ value. As an inverse proportion function, it is convex, so the best solution must lie somewhere on the left-most curve, i.e. on the lower convex hull. Therefore, it suffices to check all points on the lower convex hull of our solution space to find the minimal $V$ value. Nevertheless, we cannot really calculate the convex hull since it would require all $\binom{M}{N-1}$ points to be known. Instead, we use another approach below.

At the beginning, we choose two points on the lower convex hull, $A$ and $B$, as our starting points for our search. $A$ should be the point where we minimize $T$ and $B$ where we minimize $C$. We then want to find a point $P$ which is left-most from line $AB$. The area of the triangle $ABP$ is proportional to the distance between the line $AB$ and the point $P$, given $|AB|$ is constant. Therefore, we only have to find out the triangle $ABP$ with maximum area. Using the cross product, we get $-2A_{ABP} = AB \times AP = (x_B - x_A)(y_P - y_A) - (y_B - y_A)(x_P - x_A) = y_P(x_B - x_A) - x_P(y_B - y_A) + x_A(y_B - y_A) - y_A(x_B - x_A)$. Note that $x_A(y_B - y_A) - y_A(x_B - x_A)$ is constant and can be ignored. Thus, $-A_{ABP}$ is proportional to $y_P(x_B - x_A) - x_P(y_B - y_A)$. As our goal was to maximize $A_{ABP}$, we should here minimize $y_P(x_B - x_A) - x_P(y_B - y_A)$ instead. This can be done by taking this value as the weight of our MST algorithm and then build the MST. The result would be our new point $P$. If $P$ is on the right side of vector $AB$ (thus on the left side of line $AB$), it is also on the convex hull. We then use Divide-and-Conquer and solve the same problem with either points $A$, $P$ or $P$, $B$. For each of these points, we update the current best solution if the new point is better. Otherwise, if $P$ is on the right side of line $AB$, we do not have to search further with $P$ since it is not on the lower convex hull anymore.

Since $T$ and $C$ are positive integers, the lower convex hull between $A$ and $B$ consists of $k \leq (N-1) \cdot t_{max} = 50745$ points. For each of those $k$ points, we run Kruskal's algorithm in $\mathcal{O}(M \log M)$. Therefore, the total time complexity is $\mathcal{O}(kM \log M)$. This suffices for the given test cases.

Copy
#include <bits/stdc++.h>
using namespace std;
using ll = long long int;
using pii = pair<int, int>;

 Code Snippet: DSU (Click to expand)

struct Edge {
	int x;
	int y;