Codeforces F. Imbalance Value of a Tree（并查集加排序，树）

本文主要是介绍Codeforces F. Imbalance Value of a Tree（并查集加排序，树），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意：
求出树中所有路径最大值减去最小值之和

思路：
美团笔试遇到了这题，这里再学习一下。

首先考虑简单版本，求出所有路径最大值之和。可以先将所有点按照值排序，然后依次取，每次只考虑所有取出的点，当前的点就是所有点中的最大值点。通过并查集统计点的数目再计数。最小值和也是一样的，将值取负就可以了。

具体统计的细节可以看代码，挺好懂的，一个计数问题。

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <unordered_map>
#include <set>
using namespace std;
typedef long long ll;const int maxn = 1e6 + 7;
struct Node {int id, w;
}a[maxn];
int head[maxn], nex[maxn * 2], to[maxn * 2], tot;
int fa[maxn], num[maxn], vis[maxn], n;
ll ans;
int cmp(Node a, Node b) {return a.w < b.w;
}
int findset(int i) {if(i == fa[i]) return i;return fa[i] = findset(fa[i]);
}
void add(int x,int y) {to[++tot] = y;nex[tot] = head[x];head[x] = tot;
}
void init() {sort(a, a + n, cmp);for(int i = 0;i < n;i++) {fa[i] = i;num[i] = 1;vis[i] = 0;}
}
void solve() {init();for(int i = 0;i < n;i++) {for(int j = head[a[i].id]; j; j = nex[j]) {int v = to[j];int now = findset(v);if(!vis[now]) {continue;}ans += 1ll * a[i].w * num[now] * num[a[i].id];num[a[i].id] += num[now];fa[now] = a[i].id;}a[i].w = -a[i].w;vis[a[i].id] = 1;}
}
int main() {scanf("%d",&n);for(int i = 0;i < n;i++) {scanf("%d",&a[i].w);a[i].id = i;}for(int i = 0;i < n - 1;i++) {int x, y;scanf("%d%d", &x, &y);x--;y--;add(x, y); add(y, x);}solve();solve();printf("%lld\n", ans);return 0;
}