NC13249 黑白树

题目地址：

https://ac.nowcoder.com/acm/problem/13249

基本思路:

我们看清楚题中这句话i到根的链上（包括节点i与根）所有与节点i距离小于k[i]的点都会变黑,所以一个子节点只能影响它到根的这一条链,那么我们考虑dfs回溯从叶子节点向上染色。
我们对于每个节点u记录两个变量：mx[u]记录如果选取子树中最优的节点进行操作,从u节点还能向上再染色多少个节点,black[u]记录之前的操作在当前节点上还能再向上影响几个节点;
那么这两个变量如何转移：

  1. mx[u] = max(k[u],mx[to] - 1)
  2. black[u] = max(black[u],black[to] - 1)
  3. 而且当black[u] <= 0 时 black[u] = mx[u],ans++;

通过以上,我们就能很轻松的求出ans,具体可以参考代码;

参考代码：

#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include <bits/stdc++.h>
using namespace std;
#define IO std::ios::sync_with_stdio(false)
#define ll long long
#define rep(i, l, r) for (int i = l; i <= r; i++)
#define per(i, l, r) for (int i = l; i >= r; i--)
#define mset(s, _) memset(s, _, sizeof(s))
#define pb push_back
#define pii pair <int, int>
#define pdd pair <double, double>
#define mp(a, b) make_pair(a, b)
#define INF 0x3f3f3f3f
inline int read() {
  int x = 0, neg = 1; char op = getchar();
  while (!isdigit(op)) { if (op == '-') neg = -1; op = getchar(); }
  while (isdigit(op)) { x = 10 * x + op - '0'; op = getchar(); }
  return neg * x;
}
inline void print(int x) {
  if (x < 0) { putchar('-'); x = -x; }
  if (x >= 10) print(x / 10);
  putchar(x % 10 + '0');
}
const int maxn = 1e5 + 10;
int n,v;
struct Edge{
    int to,next;
}edge[maxn << 1];
int cnt = 0,head[maxn],k[maxn];
//mx记录选取子节点中最优的节点操作,从当前节点还能向上染色多长;
//black记录之前操作在当前节点上还能再向上影响几个节点;
int mx[maxn],black[maxn],ans = 0;
void add_edge(int u,int v) {
  edge[++cnt].next = head[u];
  edge[cnt].to = v;
  head[u] = cnt;
}
void dfs(int u,int par) {
  black[u] = 0;
  mx[u] = k[u];
  for (int i = head[u]; i != -1; i = edge[i].next) {
    int to = edge[i].to;
    if (to == par) continue;
    dfs(to, u);
    mx[u] = max(mx[u], mx[to] - 1);//每向上走一步,子节点的mx就要减少一;
    black[u] = max(black[u], black[to] - 1);
  }
  if (black[u] <= 0) {//black[u]小于等于0就代表我们要再一次操作了;
    black[u] = mx[u];
    ans++;
  }
}
signed main() {
  IO;
  cnt = 0;
  mset(head, -1);
  cin >> n;
  rep(i, 2, n) {
    cin >> v;
    add_edge(i, v);
    add_edge(v, i);
  }
  rep(i, 1, n) cin >> k[i];
  dfs(1, 0);
  cout << ans << endl;
  return 0;
}