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;
}