跃迁引擎启动

HDu6634 Salty Fish 题解

发表于 更新于 分类于 阅读次数：

题意

给定一棵树，每个点有权值 $a_i$，有 $m$ 个监控摄像头，每个摄像头可以监控子树内距离根小于等于 $k_i$ 的点，如果一个点被某个摄像头监控，则其不能被选择，每个摄像头你可以花费 $c_i$ 的代价黑掉，使其失效，求最大收益。

其中 $3 \le n,m \le 3 \cdot 10^5$。

分析

考虑最大权闭合子图建图，每次选上一个点会获得一个价值，但是能够监控到他的摄像头必须全部黑掉，也就是失去一个价值，因此原题等价于求这个图的最大流。

显然不能直接建图来流，但是这个图很特殊，把图反过来看，源点的流量是流向所有的摄像头，摄像头的流量从对应深度的子树内流出到汇点。

考虑 $dp[u][j]$ 表示 $u$ 点的子树内，深度为 $j$ 的点能提供多少流量，显然对于每个摄像头，尽量从深度大的点流出，这肯定是优的。

上面关于深度的信息可以长链剖分或者启发式合并在 $O(n\log n)$ 的时间内维护。

代码

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
64
65
66
67
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <utility>
#include <map>
#define ms(a,b) memset(a,b,sizeof(a))
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
const int mod = 998244353;
const int inf = 1 << 30;
const int maxn = 300000 + 5;

int n, m, a[maxn], dep[maxn], fa[maxn];
vector<PII> cam[maxn];
map<int,ll> g[maxn];

int main() {
    int T; scanf("%d", &T);
    while (T--) {
        scanf("%d%d", &n, &m);
        for (int i = 1; i <= n; i++) {
            cam[i].clear(); g[i].clear();
        }
        for (int i = 2; i <= n; i++) {
            scanf("%d", fa + i); 
            dep[i] = dep[fa[i]] + 1;
        }
        ll ans = 0;
        for (int i = 1; i <= n; i++) {
            scanf("%d", a + i);
            ans += a[i];
        }
        for (int i = 1, x, k, c; i <= m; i++) {
            scanf("%d%d%d", &x, &k, &c);
            cam[x].push_back({k, c});
        }
        for (int i = n; i >= 1; i--) {
            g[i][dep[i]] += a[i];
            for (auto& x: cam[i]) {
                int flow = x.second;
                int mxd = dep[i] + x.first;
                while (flow) {
                    auto it = g[i].upper_bound(mxd);
                    if (it == g[i].begin()) break;
                    it--;
                    ll tot = min(1ll * flow, it->second);
                    flow -= tot; ans -= tot;
                    it->second -= tot;
                    if (it->second == 0) g[i].erase(it->first);
                }
            }
            if (i > 1) {
                int f = fa[i];
                if ((int)g[i].size() > (int)g[f].size()) swap(g[i], g[f]);
                for (auto& x: g[i]) {
                    if (x.second) g[f][x.first] += x.second;
                }
            }
        }
        printf("%lld\n", ans);
    }
    return 0;
}