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

#include<bits/stdc++.h>
#define LL long long
using namespace std;

int k[100005], f[100005];
int ans=0;
vector<vector<int> > v(100005);
void DFS(int u, int fa){
    for(auto x: v[u]){
        if(x!=fa){
            DFS(x, u);
            f[u]=max(f[u], f[x]-1);
        }
    }
    if(!f[u]) ans++, f[u]=k[u];//没有覆盖到

    k[fa]=max(k[fa], k[u]-1);//没有染色的节点
}

int main(){
    int n, x; scanf("%d", &n);
    for(int i=2; i<=n; i++){
        scanf("%d", &x);
        v[x].push_back(i);
        v[i].push_back(x);
    }
    for(int i=1; i<=n; i++){
        scanf("%d", &k[i]);
    }
    DFS(1, 0);
    printf("%d\n", ans);

    return 0;
}