D – Sum of Maximum Weights

题目描述：

给一棵树，定义f(i,j)表示为节点 i 到 j最短路径中价值最大的权值，求$\sum_{i=1}^{n-1}{\sum_{j=i+1}^{n}{f(i,j)}}$

思路：

分析一下f(i,j)，树上的最短路径其实只有一条，是固定下来的

而$\sum_{i=1}^{n-1}{\sum_{j=i+1}^{n}{f(i,j)}}$其实求的是树上的每一个节点到其他节点的f(i,j)值

暴力计算肯定是不可以，但我们可以考虑每条边的影响，做法是对边的权值从小到大排个序，依次连边，对于每个u-v边产生的影响就是u所在联通块的大小 * v所在联通块的大小 * 边的权值，加起来就是答案

这是因为每次加入的边是当前图中边权最大的边，那他一定会是u联通块中任意一个点i和v联通块中任意一个点j形成的的f(i,j)值

//Work by: Chelsea
#include <bits/stdc++.h>
using namespace std;

#define endl '\n'
#define inf 0x3f3f3f3f
#define mod 998244353
#define sd(n) scanf("%d",&n)
#define sdd(n,m) scanf("%d %d",&n,&m)
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)

typedef long long ll;
typedef pair <int,int> pii;
//不开longlong见祖宗!

//不改范围见祖宗!!!
#define MAX 300000 + 50
int n, m, k, op;
int x, y, z;
ll a, b, c;
string s, t;

struct ran{
    int x, y;
    ll z;
}tr[MAX];

bool cmp(ran a, ran b){
    return a.z < b.z;
}

int fa[MAX];
int num[MAX];//联通块的大小
int getfa(int x){
    if(x == fa[x])return x;
    else{
        int ff = fa[x];
        fa[x] = getfa(fa[x]);
        num[x] += num[ff];//路经压缩后更新联通块的大小
    }
    return fa[x];
}
inline void emerge(int x, int y){
    int xx = getfa(x);
    int yy = getfa(y);
    if(xx != yy){
        fa[xx] = yy;
        num[yy] += num[xx];
    }
}
void init(){
    for(int i = 1; i <= n; ++i){
        fa[i] = i;
        num[i] = 1;
    }
}


void work(){
    cin >> n;
    init();
    rep(i, 1, n - 1)cin >> tr[i].x >> tr[i].y >> tr[i].z;
    sort(tr + 1, tr + n, cmp);
    ll ans = 0;
    for(int i = 1; i <= n - 1; ++i){
        int xx = getfa(tr[i].x);
        int yy = getfa(tr[i].y);
        ans += 1ll * num[xx] * num[yy] * tr[i].z;
        emerge(xx, yy);
    }
    cout << ans << endl;
}


int main(){
    io;
    //int tt;cin>>tt;
    //for(int _t = 1; _t <= tt; ++_t){
    //    printf("Case #%d: ", _t);
    work();
    //}
    return 0;
}