#566. 「LibreOJ Round #10」yanQval 的生成树

内存限制:512 MiB 时间限制:2500 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: liu_cheng_ao

题目描述

定义一个可重实数集 {ai}\{a_i\} 的离差为:对于任意实数 μ\muiaiμ\sum_{i}\lvert a_i-\mu \rvert 的最小值。记为 d({ai})d(\{a_i\})。例如,数集 {1,2,4}\{1,2,4\} 的离差为 33,因为当 μ=2\mu = 2iaiμ=12+22+42=3\sum_{i}\lvert a_i-\mu \rvert=\lvert 1-2 \rvert+\lvert 2-2 \rvert+\lvert 4-2 \rvert=3 最小。

对于一棵带边权的树,我们定义它的离差为所有边的边权组成的可重集的离差。

现在给出一张无向连通图,每条边有一个权值,请求出它的最大离差生成树,即所有生成树中离差最大的一个。你需要输出这个离差。

输入格式

第一行两个正整数 n,mn, m,分别表示图的点数和边数。

接下来 mm 行,每行三个正整数 u,v,wu, v, w,用空格分隔,表示 u,vu, v 之间有一条权值为 ww 的无向边。点的编号从 11nn

输出格式

输出一行一个整数,表示最大离差。

样例

样例输入 1

4 6
1 2 1
1 3 2
2 3 5
3 2 4
2 4 3
3 4 2

样例输出 1

4

样例输入 2

12 14
1 2 786042221
2 3 809044795
1 4 329386659
1 5 238858979
3 6 877890560
5 7 6361273
2 8 152371342
8 9 359313888
4 10 191185696
6 11 299487213
2 12 693994526
10 4 492620814
7 11 233529699
9 11 94590506

样例输出 2

2933881117

数据范围与提示

对于所有数据,2n2×105,1m5×105,1w1092\le n\le 2\times 10^5, 1\le m\le 5\times 10^5, 1\le w\le 10^9

子任务编号 分值 nn \leq mm\leq 特殊限制
1 1515 1010 2020 w100w\le 100
2 1515 100100 100100 w100w\le 100
3 2020 10310^3 10310^3 -
4 1010 10510^5 10510^5 m=nm=n
5 1515 10510^5 10510^5 nn 是奇数
6 2525 2×1052\times 10^5 5×1055\times 10^5 -