题解 | #黑白树#

这道题一遍就过，切水题真爽

这道题考察树上贪心，没看出是dp

对于遍历到每个节点的时候，如果发现当前没有变黑则选择

一种可以往上程度越高的方案变黑，对未来状态更优

#include<bits/stdc++.h>
using namespace std;
#define ll long long
int a[100010];
vector<int>G[100010];
int res;
struct node{
    int ex;
    int now;
}f[100010];
void dfs(int u,int cur){
    if(G[u].size()==0){
        f[u].ex=max(cur-a[u]+1,1);
        f[u].now=max(cur-a[u]+1,1);
        res++;
        return;
    }
    f[u].ex=max(1,cur-a[u]+1);
    f[u].now=cur+1;
    for(int i=0;i<(int)G[u].size();i++){
        int v=G[u][i];
        dfs(v,cur+1);
        f[u].ex=min(f[u].ex,f[v].ex);
        f[u].now=min(f[u].now,f[v].now);
    }
    if(f[u].now>cur) {
        res++;
        f[u].now=f[u].ex;
    }
}
int main(){
    int n;
    cin>>n;
    for(int i=2;i<=n;i++){
        int x;
        cin>>x;
        G[x].push_back(i);
    }
    for(int i=1;i<=n;i++)cin>>a[i];
    dfs(1,1);
    cout<<res;
    return 0;
}