黑白树

https://ac.nowcoder.com/acm/problem/13249

题意：把整棵树涂黑，每个点都可以往根上涂k[i]个点，选最少的点。
思路：
可以想到叶子节点必须要选，然后一开始觉得没被选的点一定要被选其实是错的，例如该图

如果有部分点k很大不选就亏了，这样我们可以通过k[u]=max(k[u],k[son]-1)来更新最优的k，如何判断某点是否被覆盖？用个dp数组就行了，如果!dp[u]那么就选择该点，同时维护个数量就可以啦。
#include<bits/stdc++.h>
using namespace std;
const int N=100010;
int n,k[N];
vector<int>v[N];
int ans;
int dp[N];
void dfs(int u,int fa)
{
    for(auto j:v[u])
    {
        dfs(j,u);
        dp[u]=max(dp[u],dp[j]-1);
        k[u]=max(k[j]-1,k[u]);
    }
    if(!dp[u])
    {
        ans++;
        dp[u]=k[u];
    }

}
int main()
{
    cin>>n;
    for(int i=2;i<=n;i++)
    {
        int x;
        cin>>x;
        v[x].push_back(i);
    }
    for(int i=1;i<=n;i++)
        cin>>k[i];
    dfs(1,0);
    cout<<ans<<endl;
    return 0;
}