题目大意
给定一幅 $n$ 个点 $m$ 条边的无向连通图，边有边权，定义 $D(i,j)$ 表示从 $i$ 到 $j$ 的所有路径中，次大边权最小是多少（如果路径只有一条边那么次大边权为 $0$）。
求 $\sum_{i=1}^n \sum_{j=i+1}^n D(i,j)$。
$n \leq 10^5,\ \ m \leq 150000$，边权互不相同且 $\le 10^9$
1s
题解
（第一反应：这不是 JBGG 出的 Pre-Finals ？
（再看一眼：哦每对点都要求一次答案啊那没事了
考虑每条边的贡献。
假设当前边权为 $w$，由于边权互不相同，可以把小于该边权的边视为 $0$ 边，大于该边权的边视为 $1$ 边。那么 $w$ 边有贡献的路径，就是恰好经过一条 $1$ 边和 $w$ 边的路径。
更具体地说，$0$ 边会形成很多连通块，当前的 $w$ 边如果连在同一个 $0$ 连通块上，显然它是没贡献的（因为任何路径如果有 $w$ 这条边，都可以改用若干 $0$ 边来代替）；否则，设该边连接了 $x,y$ 两个连通块，$x$ 连通块通过 $1$ 边相邻的连通块集合为 $X$，$y$ 连通块通过 $1$ 边相邻的连通块集合为 $Y$，那么 $w$ 边贡献的点对数量为 $size_x \cdot size_{Y\backslash X}+size_y \cdot size_{X\backslash Y}$。（其中 $X\backslash Y$ 表示 $\{a | a\in X,a\not\in Y\}$）
于是大的框架就是 Kruskal 那样，把边权从小到大做，用并查集维护每个连通块的大小、相邻连通块的大小之和。（相邻就是仅通过一条未加入的边所能到达的连通块）
相邻连通块的大小之和怎么维护呢？首先可以想到，每个连通块把它的邻居全部记下来，做成一个邻居表（顺便维护一下 $size$ 的和）。合并两个连通块的时候，启发式合并邻居表，并通过邻居表去修改邻居的“相邻连通块大小之和”。
但这里有一个问题，根据启发式合并的规则，如果要把 $x$ 连通块合并到 $y$ 连通块上，那么我只能遍历 $x$ 的邻居表，而不能遍历 $y$ 的邻居表，这样就无法完成修改操作了。
所以为了能够遍历 $y$ 的邻居表，采用另一种方式，根号平衡。
所有邻居表的总大小不超过 $2m$，把邻居表大小 $\le \sqrt{2m}$ 的叫做“小连通块”，邻居表大小 $>\sqrt{2m}$ 的叫做“大连通块”，显然大连通块的数量不超过 $\sqrt{2m}$ 。把每个连通块的邻居表也拆成“小邻居表”和“大邻居表”，大邻居表不直接维护 $size$ 之和，而是要用到的时候一一查询。
具体来说，合并两个连通块的时候，设 $x$ 合并到 $y$ 上，那么首先把 $x$ 的邻居全部遍历一遍，更新邻居的信息（邻居的邻居表里删除 $x$ 加入 $y$、更新“小邻居 $size$ 之和”）（根据启发式合并，这是 $O(m \log m)$ 的）；然后，如果 $y$ 是小连通块，那么遍历 $y$ 的小邻居更新 $size$ 之和（$O(\sqrt m)$），否则不管；最后，合并 $x$ 与 $y$ 的邻居表（根据启发式合并，这是 $O(m \log m)$ 的）。
期间如果 $y$ 从小连通块变成了大连通块，那么会破例遍历一遍 $y$ 的所有邻居，虽然违反启发式合并，但只会发生最多 $\sqrt{2m}$ 次，不影响复杂度。
因此总的复杂度是 $O(m \log m+n \sqrt m)$。（Kruskal 最多只有 $n-1$ 条有效边）
如果邻居表用了 set，那就再多一个 $\log$，但是也能过。
代码
1 |
|