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

发表于 | 分类于 | | + s

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、并查集维护集合大小方法

#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;
}
------ 本文结束 ------