Codeforces 915F(并查集+贡献法)

Codeforces 915F
题意:$n$个点的树,每个点有一个点权$a_i$, 计算树上所有路径的权值的$max(a_i)-min(a_i)$和。

考虑对于每条路径先求$max(a_i)$再求$min(a_i)$,这样就分开成了两个问题。
因为是树上计数问题,而且是整棵树的计数问题,所以我们可以想到求每个点对的贡献。现在求最大值,我们将点排序,取最大的点出来,此时它左边点到右边点的路径最大值一定是它。处理完一个以后删掉这个点(删掉这个点的所有连边),然后继续操作。我们发现连通性可以用并查集维护集合大小。但是这里要删边显然不方便,我们参考星球大战这题将并查集逆向变删除为添加来做就行了。
并查集维护集合大小很简单,见代码。

知识点:
1、计数问题:DP、组合数、贡献法
2、发现自己思路错了要回到本质去看怎么修改,必要时重新梳理思路
3、一个思路发现错了不一定就是错的,有可能是自己脑残或者改一下能用
4、将式子分裂开求解是非常好用的
5、正难则反思想
6、转化思想-删除转化为添加
7、并查集维护集合大小方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<stack>
#include<set>
#include<map>
#include<queue>
#include<climits>
#include<cmath>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
using namespace std;
namespace flyinthesky {
const int MAXN = 1000000 + 5;
vector<int > G[MAXN];
pair<int, int > d[MAXN];
int n, a[MAXN], vis[MAXN], f[MAXN], cnt[MAXN];
LL ans = 0ll;
int find(int x) {return x == f[x] ? x : f[x] = find(f[x]);}
void mg(int x, int y) {f[y] = x, cnt[x] += cnt[y];}//维护集合大小
void gg() {
for (int i = 0; i <= n; i++) f[i] = i, cnt[i] = 1, vis[i] = 1;
for (int o = 1; o <= n; o++) {
int u = d[o].second, val = d[o].first;
vis[u] = 0;
for (int i = 0; i < (int)G[u].size(); i++) {
int v = G[u][i];
if (!vis[v]) {
int x = find(u), y = find(v);
ans += (LL)cnt[x] * (LL)cnt[y] * (LL)val;
if (x != y) mg(x, y);
}
}
}
}
void clean() {
}
int solve() {
scanf("%d", &n);
clean();
for (int i = 1; i <= n; i++) scanf("%d", &a[i]), d[i] = make_pair(a[i], i);
for (int u, v, i = 1; i < n; i++) scanf("%d%d", &u, &v), G[u].push_back(v), G[v].push_back(u);
sort(d + 1, d + 1 + n), gg();
for (int i = 1; i <= n; i++) d[i] = make_pair(-a[i], i);
sort(d + 1, d + 1 + n), gg();
printf("%lld\n", ans);
return 0;
}
}
int main() {
flyinthesky::solve();
return 0;
}

------ 本文结束 ------