mvst

Description

The variance of an array \(a\) is defined as \(\mathrm{Var}(a) = \frac{1}{|a|} \sum_{x \in a} (x - \mu_a)^2\). Here, \(\mu_a = \frac{1}{|a|} \sum_{x \in a} x\) is the average of the values in \(a\). The variance is a measure of dispersion, meaning it measures how far a set of numbers is spread out from their average value.

Hiura is monitoring a communications network. This network consists of \(N\) devices numbered from \(0\) to \(N - 1\). There are \(M\) two-way communication channels numbered from \(0\) to \(M - 1\). The \(i\)-th communication channel connects two distinct devices \(U[i]\) and \(V[i]\) with a wavelength \(W[i]\), the wavelength used in the communication channel. It is guaranteed that the communication network is connected. In other words, for every pair \(0 \le x < y < N\), devices \(x\) and \(y\) are linked (directly or indirectly) by a series of communication channels.

Hiura, surprisingly, loves conformity. Because of this, he wants to pick a spanning tree of the network with the minimum variance. A spanning tree of the network is a subset of the network which includes all the \(N\) devices, is connected, and contains \(N-1\) two-way communication channels.

The variance of a spanning tree is defined as the variance of the wavelengths of its communication channels. In other words, if a spanning tree consists of the communication channels numbered \(b_1, b_2, \ldots, b_{N - 1}\), then the variance of the spanning tree is equal to the variance of the array \([W[b_1], W[b_2], \ldots, W[b_{N - 1}]]\).

Find the minimum variance over all possible spanning trees of the network.

Implementation Details

You should implement the following procedure.

double solve(int N, int M, std::vector<int> U, std::vector<int> V, std::vector<int> W)

• \(N\): The number of devices in the network.
• \(M\): The number of communication channels in the network.
• \(U, V, W\): arrays of integers of length \(M\), describing the devices that the communication channels connect and the wavelengths the communication channels have.
• This procedure should return one floating point number containing the minimum possible variance of all possible spanning trees of the network.
• The return value will be considered correct if the absolute difference between the return value of your function and the correct answer is at most \(1\).
• This procedure is called exactly once for each test case.

Constraints

• \(2 \le N \le 500 \; 000\)
• \(N - 1 \le M \le 500 \; 000\)
• \(0 \le U[i] \le N - 1\) for each \(i\) such that \(0 \le i < M\)
• \(0 \le V[i] \le N - 1\) for each \(i\) such that \(0 \le i < M\)
• \(0 \le W[i] \le 1 \; 000 \; 000\) for each \(i\) such that \(0 \le i < M\)
• \(U[i] \neq V[i]\) for each \(i\) such that \(0 \le i < M\)
• The network is connected

Subtasks

Examples

Consider the following call.

solve(4, 6, [0, 1, 2, 0, 0, 3], [1, 2, 3, 2, 2, 0], [3, 9, 7, 5, 6, 2])

For this example, the minimum variance spanning tree is achieved when we use the \(0\)-th, \(3\)-rd, and \(5\)-th communication channels.

The wavelengths of the communication channels used is \(a = [2, 3, 5]\).

We can calculate the mean as follows.

\[ \mu_a = \frac{1}{3}(2 + 3 + 5) = \frac{10}{3} \]

After that, we can calculate the variance as follows.

\[ \operatorname{Var}(a) = \frac{1}{3} \left(\left(2 - \frac{10}{3}\right)^2 + \left(3 - \frac{10}{3}\right)^2 + \left(5 - \frac{10}{3}\right)^2\right) = \frac{14}{9} \]

Because the return value is considered correct if the absolute difference is at most one from the correct answer, returning values such as \(1\), \(\frac{23}{9}\), or \(\sqrt{2}\) will also be considered correct.

Sample Grader

Input Format:

N M
U[0] V[0] W[0]
U[1] V[1] W[1]
...
U[M - 1] V[M - 1] W[M - 1]

Output Format:

V

Here, \(V\) is the floating point number returned by solve.