简析
对于每个 \(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;
}