【ABC 214D】Sum of Maxinum Weights

简析

对于每个 (i,(1≤i<N))，我们将计算使 (f(u,v)=w_i) 的总数目 ((u,v))。当且仅当连接顶点 (u) 和 (v) 的路径包含边 (i) 且路径中任何其他边的权值都小于 (w_i) 时，(f(u,v)=w_i) 成立。

一个只包含权重小于 (w_i)​ 的边的图形成了一个森林，而 (u_i)​ 和 (v_i)​ 总是属于不同的连通分量。当且仅当 (u)​ 属于其中一个连接组件，(v)​ 属于另一个连接组件时，(f(u,v)=w_i) 成立。

因此，可以通过将边按权值递增的顺序添加到图中，并通过并查集这样的数据结构获取连通块的大小来解决这个问题。

（译自官方题解，略有改动）

代码

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
int n,dis[N],fa[N],siz[N];
int getf(int x) {
	if(x^fa[x]) {
		return fa[x]=getf(fa[x]);
	}
	return x;
}
void merge(int x,int y) {
	x=getf(x),y=getf(y);
	if(x==y) {
		return ;
	}
	if(siz[x]<siz[y]) {
		fa[x]=y,siz[y]+=siz[x];
	} else {
		fa[y]=x,siz[x]+=siz[y];
	}
}
struct edge {
	int u,v,w;
	edge() {}
	edge(int x,int y,int z) {
		u=x,v=y,w=z;
	}
};
bool operator<(edge x,edge y) {
	return x.w<y.w;
}
vector<edge> v;
int main() {
	scanf("%d",&n);
	for(int i=1,x,y,z; i<n; i++) {
		scanf("%d %d %d",&x,&y,&z),v.push_back(edge(x,y,z));
	}
	for(int i=1; i<=n; i++) {
		fa[i]=i,siz[i]=1;
	}
	sort(v.begin(),v.end());
	long long ans=0;
	for(auto i:v) {
		int u=getf(i.u),v=getf(i.v),w=i.w;
		ans+=(long long)w*siz[u]*siz[v],merge(u,v);
	}
	printf("%lld",ans);
	return 0;
}