LOJ 6175

发表于 |

题目

一棵 $N$个点的有根树，$1$ 号点为根。树上每个节点 $i$ 对应一个值$k_i$。每个点都有一个颜色，初始的时候所有点都是白色的，你需要通过一系列操作使得最终每个点变成黑色。

每次操作需要选择一个节点$i$，$i$必须是白色的，然后$i$到根的链上（包括节点$i$与根）所有与节点$i$距离小于$k_i$的点都会变黑，已经是黑的点保持为黑。问最少使用几次操作能把整棵树变黑。

数据范围

$1\le N\le 10^5 \quad 1\le k_i\le 10^5$

做法

这个问题的简化版是在序列上的：选择最少的区间，使得能够完全覆盖某一段区域。贪心的策略是：左端点为端点的最小值的的区间必选，有多个的话，选右端点最右的。之后的区间选择左端点在已覆盖的最右点左边，且右端点最右的区间。现在问题变到了树上，贪心的策略不变。难点在于如何实现这个贪心。

这题还有一个有趣的地方是：在染色的时候，我们不一定非要选白色的点来染色。因为在做染色操作的点一定的情况下，我们总可以找到一种顺序（比如：从深度小的点开始染色）重构染色操作，使得满足题目中“每次选白色的点染色”的条件。

具体实现是：对每个点$v$，记录对$v$为根的子树中所有的点染色后所能所能染到的最小深度$f[v]$，再记录以$v$为根的子树中已染色的点最小能染到的深度$g[v]$。这两组信息可以用树DP处理出来。然后，对于点$v,u$，v是u的父亲，如果$min_u(g[u])>depth[v]$，那么为了染色点$v$，只能从$v$为根的子树中选一个染色后$v$也会被染色的点来染色。这时候就体现出贪心了：选择那个染色之后，使得被染色的点中深度最小的点的深度最小，的点来染色。这样，染色之后，$g[v]$就等于$f[v]$了。解题主要靠$g[]$数组，$f[]$数组起辅助作用。

代码

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX_N = 1e5 + 5;
int N;
vector<int> G[MAX_N];
int k[MAX_N];
int f[MAX_N];
int g[MAX_N];
int dep[MAX_N];
int ans;
inline void addEdge(int s, int t)
{
  G[s].push_back(t);
}
void dfs(int v, int d)
{
  dep[v] = d;
  f[v] = d - k[v] + 1;
  g[v] = INT_MAX;
  for (int u : G[v]) {
    dfs(u, d + 1);
    f[v] = min(f[v], f[u]);
    g[v] = min(g[v], g[u]);
  }
  if (g[v] > d) {
    ++ans;
    g[v] = f[v];
  }
}
int main()
{
#ifdef linjian
freopen("C:\\Users\\linjian\\Documents\\in.txt", "r", stdin);
#endif
  scanf("%d", &N);
  for (int i = 1; i < N; ++i) {
    int p;
    scanf("%d", &p);
    p--;
    addEdge(p, i);
  }
  for (int i = 0; i < N; ++i) {
    scanf("%d", &k[i]);
  }
  dfs(0, 0);
  printf("%d\n", ans);
  return 0;
}