4312. [LibreOJ Round #10]yanQval 的生成树

【题目描述】

定义一个可重实数集 $\{a_i\}$ 的离差为：对于任意实数 $\mu$，$\sum_{i} \vert a_i-\mu \vert$ 的最小值。记为 $d(\{a_i\})$。例如，数集 $\{1,2,4\}$ 的离差为 $3$，因为当 $\mu = 2$ 时 $\sum_{i}\vert a_i-\mu \vert=\vert 1-2 \vert+\vert 2-2 \vert+\vert 4-2 \vert=3$ 最小。

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

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

【输入格式】

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

接下来 $m$ 行，每行三个正整数 $u$, $v$, $w$，用空格分隔，表示 $u$, $v$ 之间有一条权值为 $w$ 的无向边。点的编号从 $1$ 到 $n$。

【输出格式】

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

【样例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

【数据规模与约定】

对于所有数据，$2\le n\le 2\times 10^5, 1\le m\le 5\times 10^5, 1\le w\le 10^9$。

测试点 $1 \sim 2$：$n \leq 10，m \leq 20$，特殊限制：$w \le 100$;

测试点 $3$：$n，m \leq 100$，特殊限制：$w \le 100$;

测试点 $4$：$n，m \leq 10^3$;

测试点 $5$：$n，m \leq 10^5$，特殊限制：$m==n$;

测试点 $6$：$n，m \leq 10^5$，特殊限制：$n$ 是奇数;

测试点 $7 \sim 10$：$n \leq 2*10^5，m \leq 5*10^5$;

【来源】

LOJ