黑白树

链接：https://ac.nowcoder.com/acm/problem/13249
来源：牛客网

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 32768K，其他语言65536K
64bit IO Format: %lld

题目描述

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

输入描述:

第一行一个整数n (1 ≤ n ≤ 10^5)
接下来n-1行，每行一个整数，依次为2号点到n号点父亲的编号。
最后一行n个整数为k[i] (1 ≤ k[i] ≤ 10^5)

样例解释:
对节点3操作，导致节点2与节点3变黑
对节点4操作，导致节点4变黑
对节点1操作，导致节点1变黑

输出描述:

一个数表示最少操作次数

示例1

输入

4
1
2
1
1 2 2 1

输出

3

解决思路

首先，我们将问题简化为一条链(即退化的树)，贪心的想法是从叶子节点开始向根部遍历点，一次能遍历的越多越好，但是这样会出现错误，比如：

2019-04-02_011321.png

如果贪心，我们会从5直接涂黑到3，这样的结果是3；然而，最优解为先从4涂黑到1，然后涂黑5，结果为2。
贪心思想的问题在于：一时的贪心可能会错过涂黑路上k值很大的点。

那么，只要把k值向根部转移不就好了吗

首先明确一点，贪心的做法中，如果涂黑的途中遇到更优质的k值，那么可以将k值转移到涂黑结束的点上。

#include <bits/stdc++.h>
using namespace std;
const int N  = 1e5+100;
int n;
vector<int> v[N];
int k[N],fa[N];
int ans=0;
int dfs(int x){
    int now = 0, siz = v[x].size();
    for(int i=0;i<siz;i++)
        now=max(now,dfs(v[x][i]));
    if(now<=0){
        ans++;
        return k[x]-1;
    }
    k[fa[x]]=max(k[fa[x]],k[x]-1);
    return now-1;
}

int main(){
    int n;
    scanf("%d", &n);
    for(int i=2;i<=n;i++){
        int d;
        scanf("%d", &d);
        v[d].push_back(i);
        fa[i]=d;
    }
    for(int i=1;i<=n;i++)
        scanf("%d", &k[i]);
    dfs(1);
    printf("%d\n",ans);
}