【2020牛客多校第四场 J】Jumping on the Graph 题解

题目大意

  给定一幅 $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$，但是也能过。

代码

#include<bits/stdc++.h>
#define fo(i,a,b) for(int i=a;i<=b;i++)
using namespace std;

typedef long long LL;
typedef pair<int,bool> pr;

const int maxn=1e5+5, maxm=150005;

struct EST{
	int x,y,w;
};
bool cmpE(const EST &a,const EST &b) {return a.w<b.w;}

int n,m,sqrtm;
EST e[maxm];
unordered_map<int,bool> M[maxn];

int ga[maxn],size[maxn],nbrsize[maxn];
unordered_map<int,bool> nbr[maxn],bignbr[maxn];
bool issmall[maxn];
int get(int x) {return ga[x]==x ?x :ga[x]=get(ga[x]) ;}

int main()
{
	scanf("%d %d",&n,&m);
	sqrtm=sqrt(m<<1);//, sqrtm=max(sqrtm,10);
	fo(i,1,m)
	{
		scanf("%d %d %d",&e[i].x,&e[i].y,&e[i].w);
		if (e[i].x==e[i].y) continue;
		M[e[i].x][e[i].y]=1;
		M[e[i].y][e[i].x]=1;
	}
	fo(i,1,n) issmall[i]=(M[i].size()<=sqrtm);
	fo(i,1,n)
		for(pr p:M[i]) if (issmall[p.first]) nbr[i][p.first]=1, nbrsize[i]++;
			else bignbr[i][p.first]=1;
	fo(i,1,n) ga[i]=i, size[i]=1;
	
	sort(e+1,e+1+m,cmpE);
	LL ans=0;
	fo(i,1,m) if (get(e[i].x)!=get(e[i].y))
	{
		int x=get(e[i].x), y=get(e[i].y);
		if (nbr[x].size()>nbr[y].size()) swap(x,y);
		if (issmall[x]) nbr[y].erase(x), nbrsize[y]-=size[x];
			else bignbr[y].erase(x);
		if (issmall[y]) nbr[x].erase(y), nbrsize[x]-=size[y];
			else bignbr[x].erase(y);
		
		#define go p.first
		
		int comsize=0, xsize=nbrsize[x], ysize=nbrsize[y];
		for(pr p:nbr[x]) if (nbr[y].count(go)) comsize+=size[go];
		for(pr p:bignbr[x]) if (!bignbr[y].count(go)) xsize+=size[go];
		for(pr p:bignbr[y]) if (!bignbr[x].count(go)) ysize+=size[go];
		
		ans+=((LL)size[x]*(ysize-comsize)+(LL)size[y]*(xsize-comsize))*e[i].w;
		
		ga[x]=y;
		if (issmall[x])
		{
			for(pr p:nbr[x]) nbr[go].erase(x), nbrsize[go]-=size[x];
			for(pr p:bignbr[x]) nbr[go].erase(x), nbrsize[go]-=size[x];
		} else
		{
			for(pr p:nbr[x]) bignbr[go].erase(x);
			for(pr p:bignbr[x]) bignbr[go].erase(x);
		}
		if (issmall[y] && nbr[y].size()>sqrtm)
		{
			for(pr p:nbr[y]) nbr[go].erase(y), nbrsize[go]-=size[y];
			for(pr p:bignbr[y]) nbr[go].erase(y), nbrsize[go]-=size[y];
			for(pr p:nbr[y]) bignbr[go][y]=1;
			for(pr p:bignbr[y]) bignbr[go][y]=1;
			for(pr p:nbr[x]) bignbr[go][y]=1;
			for(pr p:bignbr[x]) bignbr[go][y]=1;
			issmall[y]=0;
		} else
		{
			if (issmall[y])
			{
				for(pr p:nbr[y]) nbrsize[go]+=size[x];
				for(pr p:bignbr[y]) nbrsize[go]+=size[x];
				for(pr p:nbr[x]) if (!nbr[go].count(y))
					nbr[go][y]=1, nbrsize[go]+=size[x]+size[y];
				for(pr p:bignbr[x]) if (!nbr[go].count(y))
					nbr[go][y]=1, nbrsize[go]+=size[x]+size[y];
			} else
			{
				for(pr p:nbr[x]) bignbr[go][y]=1;
				for(pr p:bignbr[x]) bignbr[go][y]=1;
			}
		}
		for(pr p:nbr[x]) if (!nbr[y].count(go))
			nbr[y][go]=1, nbrsize[y]+=size[go];
		nbr[x].clear();
		for(pr p:bignbr[x]) bignbr[y][go]=1;
		bignbr[x].clear();
		size[y]+=size[x];
	}
	
	printf("%lld\n",ans);
}