每日一题4月8日 黑白树 树形dp

好久没做题了，之前放假稍微出去玩了一下。家里休息惰性又上来了，还是得抓一下自己！
这题其实开了好久了，一直想不出来。
后来去看了题解，其实基本的情况都考虑到了，但是不知道怎么解决。

题意：
给一颗n个节点的树，以1为根节点。
一开始树是白色的，现在每次可以选择一个点进行染黑。每个点上有一个值k[i]。
每次操作需要选择一个节点i，i必须是白色的，然后i到根的链上（包括节点i与根）所有与节点i距离小于k[i]的点都会变黑，已经是黑的点保持为黑。问最少使用几次操作能把整棵树变黑。

思路：
很明显可以想到叶子节点必选。
我一开始的思路是这样的，维护一下节点深度dep[x]，那么对于节点x来说，只要其子节点中存在一个节点y，满足dep[y]-dep[x]<k[y]，就可以通过染y来让x也被染色。
这个式子可以移项一下，变成dep[x]>dep[y]-k[y]。因此只要dfs维护一下每个节点的dep[i]-k[i]，然后如果当前点dep[x]<=min(dep[j]-k[j])，就把当前点染色。
这是一个贪心，很快地可以发现，是存在问题的，问题就在于，如果dep[x]>min(dep[j]-k[j])，x是可以染色也可以不染色的。如果x染色了，可能对上面节点覆盖的更多，令总答案更优。
于是想到，维护每个节点向上覆盖的最大长度。但是依然无法解决，x点可染可不染的情况。
然后盯了题解好久。。
做法比较巧妙：当x选择染色或者不染时，我们把k[x]更新到x的父亲fa上面去。这样子的话，当要染色上面的某个点时，我们可以用子节点中最大的覆盖长度来替代当前染色点的覆盖长度。

代码：

#include<bits/stdc++.h>
using namespace std;
const int maxn=100005;
int n,dp[maxn],k[maxn],tot;
vector<int>vt[maxn];
int dfs(int x,int fa){
    int ans=0;
    for(int i=0;i<vt[x].size();i++){
        int y=vt[x][i];
        if(y==fa)continue;
        ans=max(ans,dfs(y,x)-1);
    }
    if(ans==0){
        tot++;
        return k[x];
    }
    k[fa]=max(k[fa],k[x]-1);
    return ans;
}
int main()
{
    cin>>n;
    for(int i=1;i<n;i++){
        int x;
        cin>>x;
        vt[x].push_back(i+1);
        vt[i+1].push_back(x);
    }
    for(int i=1;i<=n;i++)cin>>k[i];
    dfs(1,0);
    cout<<tot<<endl;
    return 0;
}