题目链接：?pid=5176题目大意：给一棵树，求任意｛两点路径上的最大边权值-最小边权值｝的总和。题目分析：sigma(maxVal[i]minVal[i])=sigma(maxVal)sigma(minVal) ;所以我们分别求所有两点路径上的最大值的和，还有最小值的和。再相减就可以了。求最大值的和的方法用带权并查集，把边按权值从小到大排序，一条边一条边的算，当我们算第i 条边的时候权值为wi ,两点是ui,vi ,前面加入的边权值一定是小于等于当前wi 的，，假设与ui 连通的点有a 个，与vi 连通的点有b 个，那么在a 个中选一个，在b 个中选一个，这两个点的路径上最大值一定是wi ,一共有a*b 个选法，爱情经验值为a*b*wi 。求最小值的和的方法类似。#include <cstdio>#include <algorithm>#define ull unsigned long longusing namespace std;int const MAX = 150005;int fa[MAX], cnt[MAX], n;ull ma, mi;struct Edge{int u, v;ull val;}e[MAX];bool cmp(Edge a, Edge b){return a.val < b.val;}void init(){for(int i = 0; i <= n; i++){fa[i] = i;cnt[i] = 1;}}int Find(int x){return x == fa[x] ? x : fa[x] = Find(fa[x]);}int Union(int a, int b, ull val, bool flag){int r1 = Find(a);int r2 = Find(b);if(flag)ma += (ull)cnt[r1] * cnt[r2] * val;elsemi += (ull)cnt[r1] * cnt[r2] * val;fa[r1] = r2;cnt[r2] += cnt[r1];}int main(){int ca = 1;while(scanf("%d", &n) != EOF){for(int i = 1; i <= n – 1; i++)scanf("%d %d %llu", &e[i].u, &e[i].v, &e[i].val);sort(e + 1, e + n, cmp);init();ma = 0;for(int i = 1; i <= n – 1; i++)Union(e[i].u, e[i].v, e[i].val, true);init();mi = 0;for(int i = n – 1; i >= 1; i–)Union(e[i].u, e[i].v, e[i].val, false);printf("Case #%d: %llu\n", ca++, ma – mi);}}
少吃点，吃好的。
