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; }