【每日一题】黑白树

这个题可以用贪心的思想。我们要想染色最少次数，那么就一定要从叶子节点开始，因为有可能使得叶子结点的k[i]用得上。
这个题目还有最重要的一点是要更新k[i],就是在dfs的时候，用儿子节点去更新该节点的k[i]，最远染色距离。
那么我们就dfs来维护当前的最远染色距离，从儿子节点转移来的要记得减一，因为用了一个距离在父亲与儿子节点上，然后就快乐dfs就好了~~

#include<bits/stdc++.h>
using namespace std;
int n;
int ans=0;
const int N=2e5+10;
vector<int> e[N];
int k[N];

int dfs(int u,int fa)
{
    int sum=0;
    for(auto x:e[u])
    {
        sum=max(sum,dfs(x,u));
    }
    if(sum==0){
        ans++;
        return k[u]-1;
    }
    k[fa]=max(k[fa],k[u]-1);
    return sum-1;
}
int main()
{
    cin>>n;
    int t;
    for(int i=2;i<=n;i++) cin>>t,e[t].push_back(i);
        for(int i=1;i<=n;i++) cin>>k[i];
    dfs(1,0);
    cout<<ans<<endl;
    return 0;
}