链接：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);
}
