loj#P2469. 「2018 集训队互测 Day 2」最小方差生成树
「2018 集训队互测 Day 2」最小方差生成树
题目描述
给定一个 个点 条边的带权图,每条边的边权为 ,有两种询问。
1.求其最小方差生成树。
2.对于每条边,问如果删除它,残余图(包含 个点 条边)的最小方差生成树。
你只需要求出最小的方差值。如果图不连通,输出 。
一个生成树的方差定义为它的所有边的权值的方差。
对于 个变量 ,其方差计算方式为 $\sigma^2 = \frac{\sum_{1\leq i\leq N}(x_i-\mu)^2}{N}$
其中 为方差, 为平均值,由于是生成树,所以 。
你需要将方差乘 后输出,可以证明这是一个整数。
输入格式
第 行包含 个整数 ,表示点数,边数和询问类型。
接下来 行,每行包含 个正整数 ,表示第 条边连接 和 ,权值为 ,保证无自环,但可能有重边。
输出格式
当 ,输出一个数表示答案。
当 ,输出 行,每行一个数表示删除第 条边的答案。
如果图不连通,输出-1。
4 4 2
1 2 1
2 3 3
1 3 2
3 4 5
14
26
24
-1
数据范围与提示
子任务 | 分值 | ||||
---|---|---|---|---|---|
,且满足特性 1 | |||||
特性1:第 条边连接点 和点 ,且 。