黑白树

逆序（从根）操作，即可选黑点，但代码依然是从叶子操作

#include<bits/stdc++.h>
using namespace std;
#define ll long long
int const INF=0x3f3f3f3f;
int const N=1e5+7;
int const M=1e5+7;
struct node{
    int a,len,next;
}e[M<<1];
int head[N],cnt;
void add(int x,int y,int len){
    e[++cnt].a =y;
    e[cnt].len =len;
    e[cnt].next =head[x];
    head[x]=cnt;
}
int n,ans;
int w[N],vis[N]; //w[i]表示i点以下（包括i点）到i点剩余权值的最大值 
ll f[N];   //f[i]表示上一个涂黑的点到i点时，剩余的权值 
void dfs(int s){
    for(int i=head[s];i!=-1;i=e[i].next ){
        if(vis[e[i].a ]) continue;
        vis[e[i].a ]=1;
        dfs(e[i].a );
        w[s]=max(w[s],w[e[i].a]-1);
        f[s]=max(f[s],f[e[i].a ]-1);
    }
    if(!f[s]) f[s]=w[s],ans++;
}
int main(){
    cin >> n ;
    memset(head,-1,sizeof head);
    memset(e,-1,sizeof e);
    for(int i=2;i<=n;++i){
        int a;cin >> a;
        add(i,a,0);add(a,i,0);
    }
    for(int i=1;i<=n;++i){
        cin >> w[i];
    }
    vis[1]=1;
    dfs(1);
    cout << ans;
    return 0;
}