abc214D 全部路径最大边权之和

给定一颗包含n个顶点的树，第i条边连接u[i]和v[i]，边权为w[i]。记f(i,j)表示顶点i到j的简单路径上边权的最大值，求 $ \sum_{i=1}^{n-1} \sum_{j=i+1}^{n}f(i,j) $。
2<=n<=1e5; 1<=u[i],v[i]<=n; 1<=w[i]<=1e7

对于每条边，考虑以它作为最大边权的路径数，为两侧节点数的乘积，数点可以用并查集维护，需要按边权从小到大的顺序处理。

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define per(i,a,b) for(int i=b;i>=a;i--)

const int N = 100005;
int n, fa[N], sz[N];
tuple<int,int,int> e[N];
int leader(int x) {
    return x == fa[x] ? x : fa[x] = leader(fa[x]);
}
void join(int x, int y) {
    x = leader(x);
    y = leader(y);
    if (x != y) {
        sz[x] += sz[y];
        fa[y] = x;
    }
}
void solve() {
    cin >> n;
    rep(i,1,n-1) {
        int u, v, w;
        cin >> u >> v >> w;
        e[i] = {w, u, v};
    }
    sort(e+1, e+n);
    rep(i,1,n) fa[i] = i, sz[i] = 1;
    int ans = 0;
    rep(i,1,n-1) {
        auto [w,u,v] = e[i];
        u = leader(u);
        v = leader(v);
        ans += w * sz[u] * sz[v];
        join(u, v);
    }
    cout << ans << "\n";
}

signed main() {
    cin.tie(0)->sync_with_stdio(0);
    int t = 1;
    while (t--) solve();
    return 0;
}