NC13249 黑白树

题意

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

分析

首先呢，涂色肯定是从叶子节点开始涂的，因为没有其他节点可以使叶子节点涂色，如图。

现在我们已经将叶子节点涂色了，要开始涂红色箭头指的点，记为 。
那么，这次我们是使 到 往上 个点都涂色吗？
其实，这样答案并不一定是最优的。
可能某个红色点可以延伸到深度更小的点，这样答案会更优。
因此，我们需要看红色的点中能涂到的最小深度为多少，也就是 。
然后，我们再用一个数组 ，表示这个点往上总共还能覆盖多少个，于是有
如果 为 ，说明下面的点都无法覆盖这个点。因此需要在红色点中找能爬到的最小深度，记为，然后更新 为 ，并使答案加一。

代码如下

#include <bits/stdc++.h>
#include<ext/pb_ds/hash_policy.hpp>
#include<ext/pb_ds/assoc_container.hpp>
#define N 100005
using namespace __gnu_pbds;
using namespace std;
typedef long long LL;
typedef unsigned long long uLL;
struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }
    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};
LL z = 1;
int read(){
    int x, f = 1;
    char ch;
    while(ch = getchar(), ch < '0' || ch > '9') if(ch == '-') f = -1;
    x = ch - '0';
    while(ch = getchar(), ch >= '0' && ch <= '9') x = x * 10 + ch - 48;
    return x * f;
}
int ksm(int a, int b, int p){
    int s = 1;
    while(b){
        if(b & 1) s = z * s * a % p;
        a = z * a * a % p;
        b >>= 1;
    }
    return s;
}
struct node{
    int a, b, n;
}d[N * 2];
int h[N], k[N], dep[N], f[N], g[N], fa[N], tot, cnt;
void cr(int a, int b){
    d[++cnt].a = a; d[cnt].b = b; d[cnt].n = h[a]; h[a] = cnt;
}
void dfs(int a){
    int i, b;
    g[a] = dep[a] - k[a] + 1;
    for(i = h[a]; i; i = d[i].n){
        b = d[i].b;
        if(b == fa[a]) continue;
        fa[b] = a;
        dep[b] = dep[a] + 1;
        dfs(b);
        f[a] = max(f[a], f[b] - 1);
        g[a] = min(g[a], g[b]);
    }
    if(!f[a]) f[a] = dep[a] - g[a] + 1, tot++;
}
int main(){
    int i, j, n, m, a, b;
    n = read();
    for(i = 2; i <= n; i++){
        a = read();
        cr(a, i); cr(i, a);
    }
    for(i = 1; i <= n; i++) k[i] = read();
    dfs(1);
    printf("%d", tot);
    return 0;
}