4476: 「2018 集训队互测 Day 2」最小方差生成树
内存限制：512 MB
时间限制：5.000 S
评测方式：文本比较
命题人：
提交：0
解决：0
题目描述
给定一个 $n$ 个点 $m$ 条边的带权图，每条边的边权为 $w_i$ ，有两种询问。
1.求其最小方差生成树。
2.对于每条边，问如果删除它，残余图（包含 $n$ 个点 $m-1$ 条边）的最小方差生成树。
你只需要求出最小的方差值。如果图不连通，输出 $-1$。
一个生成树的方差定义为它的所有边的权值的方差。
对于 $N$ 个变量 $x_1,x_2...x_N$，其方差计算方式为 $\sigma^2 = \frac{\sum_{1\leq i\leq N}(x_i-\mu)^2}{N}$
其中 $\sigma^2$ 为方差，$\mu$ 为平均值，由于是生成树，所以 $N=n-1$。
你需要将方差乘 $N^2$ 后输出，可以证明这是一个整数。
输入
第 $1$ 行包含 $3$ 个整数 $n,m,T$，表示点数，边数和询问类型。
接下来 $m$ 行，每行包含 $3$ 个正整数 $u_i,v_i,w_i$ ，表示第 $i$ 条边连接 $u_i$ 和 $v_i$ ，权值为 $w_i$ ，保证无自环，但可能有重边。
输出
当 $T=1$，输出一个数表示答案。
当 $T=2$，输出 $m$ 行，每行一个数表示删除第 $i$ 条边的答案。
如果图不连通，输出-1。
样例输入 复制
4 4 2
1 2 1
2 3 3
1 3 2
3 4 5样例输出 复制
14
26
24
-1提示
数据范围： | 子任务 | 分值 | $T$ | $n \le$ | $m \le$ | $C \le$ | |:-:|:-:|:-:|:-:|:-:|:-:| | $1$ | $5$ | $1$ | $m$ | $20$ | $10^6$ | | $2$ | $10$ | $1$ | $m$ | $200$ | $10^6$ | | $3$ | $10$ | $1$ | $m$ | $1000$ | $10^4$ | | $4$ | $10$ | $1$ | $m$ | $1000$ | $10^6$ | | $5$ | $10$ | $1$ | $m$ | $10^5$ | $10^9$，且满足特性 1 | | $6$ | $15$ | $1$ | $m$ | $10^5$ | $10^9$ | | $7$ | $20$ | $2$ | $300$ | $10^5$ | $10^6$ | | $8$ | $20$ | $2$ | $300$ | $10^5$ | $10^{18}$ | 特性1：第 $i$ 条边连接点 $(i\bmod n)+1$ 和点 $((i+1)\bmod n)+1$，且 $w_i\le w_{i+1}$。