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,\dots ,b_{N-1}$, then the variance of the spanning tree is equal to the variance of the array $[W[b_1],W[b_2],\dots ,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 500000$
• $N-1\le M\le 500000$
• $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 1000000$ for each $i$ such that $0\le i<M$
• $U[i]\ne 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.

$$\mathrm{Var}(a)=\frac{1}{3}({(2-\frac{10}{3})}^2+{(3-\frac{10}{3})}^2+{(5-\frac{10}{3})}^2)=\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.