abc355f 题解

abc355f

直接贺 lct 维护 mst 的代码。

思路

观察到 $w_i\le 10$，考虑分开建 $10$ 个图表示边权小于等于 $i$ 的边组成的图。连并查集，记录当前图连了 $si{z}_i$ 条边。

可以发现第 $i-1$ 个图是第 $i$ 个图的子图。所以差分 $si{z}_i-si{z}_{i-1}$ 可以得到原图的最小生成树中边权为 $i$ 的边数。

复杂度 $O(n\max w_i)$。

code

int n,m;
int f[11][maxn],siz[11];
int fd(int id,int x){
	if(f[id][x]==x)return x;
	return f[id][x]=fd(id,f[id][x]);
}
void work(){
	n=read();m=read();
	for(int i=1;i<=10;i++)for(int j=1;j<=n;j++)f[i][j]=j;
	for(int i=1;i<n;i++){
		int u=read(),v=read(),w=read();
		for(int j=w;j<=10;j++)if(fd(j,u)!=fd(j,v))f[j][fd(j,u)]=fd(j,v),siz[j]++;
	}
	for(int i=1;i<=m;i++){
		int u=read(),v=read(),w=read();
		for(int j=w;j<=10;j++)if(fd(j,u)!=fd(j,v))f[j][fd(j,u)]=fd(j,v),siz[j]++;
		int ans=0;
		for(int j=1;j<=10;j++)ans+=(siz[j]-siz[j-1])*j;
		printf("%lld\n",ans);
	}
}