AtCoder Beginner Contest 214

AtCoder Beginner Contest 214 - AtCoder

[ABC214D] Sum of Maximum Weights ------------------------------（ 典 ）

题意：给出一颗 N - 1 条边的树，求树上任意两点间路径上的最大值的和

这种问题考虑每条边单独看贡献，但是刚开始没太想明白怎么计算贡献，后面看了洛谷题解才懂了

----------------------------------------------------------------------------------------------------------------------------------------

也就是说加入边 s 是一条连通点 a，b 路径上的最大一条边，那么 a，b两点路径上的边一定是小于 s 的权值的

若对所有边权排了个序，s一定是 a 到 b路径上最后一个加入的边，那么此时用一个并查集维护，sz[ a ] 就是在边权小于s的情况下有多少个点是可以到达 a 的，同理sz[ b ]

那么由乘法原理就可以计算出 a 到 b 有多少种方案（sz[ a ] * sz[ b ]），贡献也就算出来了

#include<bits/stdc++.h>
using namespace std;
#define endl "\n"
#define int long long
typedef long long ll;

const int N = 1e5 + 5;

struct Node{
    int x, y, v;
}a[N];

bool cmp(Node a,Node b){
    return a.v < b.v;
}

int fa[N], sz[N];

int Findset(int x){
    return (x == fa[x]) ? x : fa[x] = Findset(fa[x]);
}

signed main(){
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    int n; cin >> n;
    for(int i = 1; i < n; i++){
         cin >> a[i].x >> a[i].y >> a[i].v;
    }
    for(int i = 1; i <= n; i++)fa[i] = i, sz[i] = 1;
    sort(a + 1, a + n, cmp);
    int  ans = 0;
    for(int i = 1; i < n; i++){
        int x = a[i].x, y = a[i].y, v = a[i].v;
        int fx = Findset(x), fy = Findset(y);
        //fx != fy其实是不必要的
        if(fx != fy){
            ans += sz[fx] * sz[fy] * v;
            sz[fx] += sz[fy];
            sz[fy] = 0;
            fa[fy] = fx;
        }
    }
    cout << ans;
    return 0;
}