D - Sum of Maximum Weights
题意
给定一个有N个结点的树，定义\(f(u,v)\)为u、v最短路中边的最大值，要求求出\(\sum_{i=1}^{N-1}\sum_{j=i+1}^{N}f(i,j)\)。
思路
对于当前的i而言，我们需要求出所有满足\(f(i,j)=w_i\)的对，显然，对于\(f(i,j)=w_i\)来说，一定是最短路上的所有边的值都要小于或者等于\(w_i\)。那么就可以以\(w_i\)为分界线，分成小于等于和大于的两个部分。那么当我们的\(w_i\)连接到小于等于的部分时，对的数量就等于当前小于等于部分连通结点的数量以及这条边连接的结点数量。
基于此，我们就可以先对边按照值从小到大进行排序，利用维护树大小的并查集实现个数询问，最后得到我们的答案。
参考代码
点此展开
#include <bits/stdc++.h>
using namespace std;
#define in(x) scanf("%d",&x)
#define lin(x) scanf("%lld",&x)
#define din(x) scanf("%lf",&x)
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
const int N=1e5+10;
const int mod=1e9+7;
struct edge
{
ll u,v,cost;
bool operator<(const edge& e) const
{
return cost<e.cost;
}
}ns[N];
//p[]存储每个点的祖宗节点，size[]只有祖宗节点的有意思，表示祖宗节点所在集合中的点的数量
int p[N],siz[N];
//初始化
void init(int n)
{
for(int i=1;i<=n;i++)
{
p[i]=i;
siz[i]=1;
}
}
//返回x的祖宗节点
int find(int x)
{
if(p[x]!=x) p[x]=find(p[x]);
return p[x];
}
//合并
void unite(int a,int b)
{
siz[find(b)]+=siz[find(a)];
p[find(a)]=find(b);
}
int main()
{
int n;
in(n);
init(n);
for(int i=0;i<n-1;i++)
{
lin(ns[i].u),lin(ns[i].v),lin(ns[i].cost);
}
ll ans=0;
sort(ns,ns+n-1);
for(int i=0;i<n-1;i++)
{
// cout<<ns[i].u<<' '<<ns[i].v<<endl;
// cout<<ans<<endl;
ans+=ns[i].cost*siz[find(ns[i].v)]*siz[find(ns[i].u)];
unite(ns[i].u,ns[i].v);
}
cout<<ans;
return 0;
}