0%

【每日一题】黑白树题解

题目链接

Description

一棵$n$个点的有根树,$1$号点为根,相邻的两个节点之间的距离为$1$。树上每个节点i对应一个值$k[i]$。每个点都有一个颜色,初始的时候所有点都是白色的。
你需要通过一系列操作使得最终每个点变成黑色。每次操作需要选择一个节点$i$,$i$必须是白色的,然后$i$到根的链上(包括节点$i$与根)所有与节点$i$距离小于$k[i]$的点都会变黑,已经是黑的点保持为黑。问最少使用几次操作能把整棵树变黑。

Solution

很显然叶子节点是一定要选择的,但是被这些叶子节点能覆盖的点有时也是需要选择的,比如下面的这种情况。

虽然每次选择的节点一定要是白色节点,如果先选择了叶子节点就不能选择被这个节点覆盖的节点。但是可以先选择深度小的节点,这样再被覆盖也没问题,所以实际上这个点的选择是没有顺序的,而且也可以随意选择。

这样就是一个比较简单的dfs了,遍历到一个节点时,知道覆盖所有子节点的子树所需要的答案、子树中覆盖最大是多少、当前还能往父节点覆盖多少个节点,这样就可以知道遍历下去了。

要记往父节点转移的时候要减去边的长度即$1$。

在dfs我选择返回一个tuple这样理论上能省一点内存。(实际好像没什么用,理解起来还复杂了)

Code

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
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
vector<int> edg[N]; // 邻接表存边
int k[N];
// tuple<答案, 若花费1可得最大覆盖, 此时最大覆盖>
tuple<int, int, int> dfs(int u) {
int tot = 0, mx = k[u], far = 0;
for(int i = 0; i < int(edg[u].size()); i++) {
int a, b, c; tie(a, b, c) = dfs(edg[u][i]);
// 把答案相加,覆盖值均取最大值
tot += a, mx = max(mx, b - 1), far = max(far, c - 1);
}
// 若该节点不能被覆盖则需要花费1获得当前最大覆盖
if(far == 0) tot++, far = mx;
return make_tuple(tot, mx, far);
}
int main() {
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
int n; cin >> n;
for(int i = 2; i <= n; i++) {
int fa; cin >> fa;
edg[fa].push_back(i);
}
for(int i = 1; i <= n; i++) cin >> k[i];
int res; tie(res, ignore, ignore) = dfs(1);
cout << res << '\n';
}

回到开头