loj#P2469. 「2018 集训队互测 Day 2」最小方差生成树

    ID: 15739 传统题 5000ms 512MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>数据结构数学图论Link-Cut Tree最小生成树2018集训队互测

「2018 集训队互测 Day 2」最小方差生成树

题目描述

给定一个 nn 个点 mm 条边的带权图,每条边的边权为 wiw_i ,有两种询问。

1.求其最小方差生成树。

2.对于每条边,问如果删除它,残余图(包含 nn 个点 m1m-1 条边)的最小方差生成树。

你只需要求出最小的方差值。如果图不连通,输出 1-1

一个生成树的方差定义为它的所有边的权值的方差。

对于 NN 个变量 x1,x2...xNx_1,x_2...x_N,其方差计算方式为 $\sigma^2 = \frac{\sum_{1\leq i\leq N}(x_i-\mu)^2}{N}$

其中 σ2\sigma^2 为方差,μ\mu 为平均值,由于是生成树,所以 N=n1N=n-1

你需要将方差乘 N2N^2 后输出,可以证明这是一个整数。

输入格式

11 行包含 33 个整数 n,m,Tn,m,T,表示点数,边数和询问类型。

接下来 mm 行,每行包含 33 个正整数 ui,vi,wiu_i,v_i,w_i ,表示第 ii 条边连接 uiu_iviv_i ,权值为 wiw_i ,保证无自环,但可能有重边。

输出格式

T=1T=1,输出一个数表示答案。

T=2T=2,输出 mm 行,每行一个数表示删除第 ii 条边的答案。

如果图不连通,输出-1。

4 4 2
1 2 1
2 3 3
1 3 2
3 4 5
14
26
24
-1

数据范围与提示

子任务 分值 TT nn \le mm \le CC \le
11 55 11 mm 2020 10610^6
22 1010 200200
33 10001000 10410^4
44 10610^6
55 10510^5 10910^9,且满足特性 1
66 1515 10910^9
77 2020 22 300300 10610^6
88 101810^{18}

特性1:第 ii 条边连接点 (imodn)+1(i\bmod n)+1 和点 ((i+1)modn)+1((i+1)\bmod n)+1,且 wiwi+1w_i\le w_{i+1}