题意：
给定一棵树，定义f ( u , v )为u到v路径上权值的最大值。
求∑ i = 1 n − 1 ∑ j = i + 1 n f ( i , j )
思路：
基本思路是考虑每条边对答案的贡献
边权最大的边对答案的贡献是最大的，连接的点数也最多。如果权值从大到小考虑的话还要考虑去重的问题，不好维护；
考虑倒着加边，将权值从小到大排序后进行枚举，每次该边的贡献就是端点的子树大小的乘积
正确性怎么保证呢。由于是倒着加边的，所以不会出现重复的情况
用并查集维护就好了
数据不大，所以不加按秩合并也可以。
代码：
// Problem: D - Sum of Maximum Weights // Contest: AtCoder - AtCoder Beginner Contest 214 // URL: https://atcoder.jp/contests/abc214/tasks/abc214_d // Memory Limit: 1024 MB // Time Limit: 2000 ms // Author:Cutele // // Powered by CP Editor (https://cpeditor.org) #pragma GCC optimize(2) #include<bits/stdc++.h> using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair<ll, ll>PLL; typedef pair<int, int>PII; typedef pair<double, double>PDD; #define I_int ll inline ll read(){ll x = 0, f = 1;char ch = getchar();while(ch < '0' || ch > '9'){if(ch == '-')f = -1;ch = getchar();}while(ch >= '0' && ch <= '9'){x = x * 10 + ch - '0';ch = getchar();}return x * f;} inline void write(ll x){if (x < 0) x = ~x + 1, putchar('-');if (x > 9) write(x / 10);putchar(x % 10 + '0');} #define read read() #define closeSync ios::sync_with_stdio(0);cin.tie(0);cout.tie(0) #define multiCase int T;cin>>T;for(int t=1;t<=T;t++) #define rep(i,a,b) for(int i=(a);i<=(b);i++) #define repp(i,a,b) for(int i=(a);i<(b);i++) #define per(i,a,b) for(int i=(a);i>=(b);i--) #define perr(i,a,b) for(int i=(a);i>(b);i--) ll ksm(ll a, ll b,ll mod){ll res = 1;while(b){if(b&1)res=res*a%mod;a=a*a%mod;b>>=1;}return res;} const int maxn=2e5+100; int siz[maxn],n,root[maxn]; struct node{ int u,v,w; }edge[maxn]; bool cmp(node a,node b){ return a.w<b.w; } int Find(int x){ if(x!=root[x]) root[x]=Find(root[x]); return root[x]; } int main(){ n=read; rep(i,1,n-1){ edge[i].u=read;edge[i].v=read;edge[i].w=read; } sort(edge+1,edge+n,cmp); rep(i,1,n) root[i]=i,siz[i]=1; ll ans=0; rep(i,1,n-1){ int u=edge[i].u,v=edge[i].v,w=edge[i].w; int fu=Find(u),fv=Find(v); ans=ans+1ll*w*siz[fu]*siz[fv]; //cout<<siz[fu]<<"+++"<<siz[fv]<<endl; if(fu!=fv){ //if(siz[fu]>siz[fv]) swap(fu,fv);//按秩合并 root[fu]=fv; siz[fv]+=siz[fu]; } //cout<<ans<<"***\n"; } write(ans); return 0; }
