黑白树

#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;
vector<int> tree[100005];
int v[100005],res,deep[100005],fa[100005],ch[100005];
void dfs(int);
int main(){
    int N,i,x;
    //freopen("input.txt","r",stdin);
    for(scanf("%d",&N),i=2;i<=N;i++){
        scanf("%d",&x);
        tree[x].push_back(i);
    }
    for(i=1;i<=N;i++) scanf("%d",&v[i]);
    dfs(1);printf("%d\n",res);
}
void dfs(int x){
    fa[x]=deep[x]-v[x]+1;
    ch[x]=1e9;
    for(int i=0;i<tree[x].size();i++){
        deep[tree[x][i]]=deep[x]+1;
        dfs(tree[x][i]);
        fa[x]=min(fa[x],fa[tree[x][i]]);
        ch[x]=min(ch[x],ch[tree[x][i]]);
    }
    if(ch[x]>deep[x]) res++,ch[x]=fa[x];
}

// memo[i][0]: 以i节点为根的子树所需最少次数
// memo[i][1]: 以i节点为根的子树中所有节点能到达的最大范围
// memo[i][2]: 以i节点为根的子树中实际能够覆盖的范围，注意该值并不与最大值有关
// 该实现方法由力扣跳跃游戏的思路而来

#include <iostream>
#include <vector>
#include <functional>
#include <cmath>
#include <climits>
using namespace std;

struct TreeNode {
    int k;
    vector<int> children;
};

int main() {
    int n;
    cin >> n;
    vector<TreeNode> tree(n + 1, {0});
    vector<vector<int>> memo(n + 1, {0, 0, 0});
    
    function<vector<int>(int)> dfs = [&] (int idx) -> vector<int> {
        if(memo[idx][1] != 0) {
            return memo[idx];
        }

        if(tree[idx].children.empty()) {
            memo[idx] = {1, tree[idx].k, tree[idx].k};          
        }

        memo[idx][1] = tree[idx].k;

        for(auto child: tree[idx].children) {
            auto childRes = dfs(child);
            int childLimit = childRes[2] - 1;

            if(memo[idx][2] < childLimit) {               
                memo[idx][2] = childLimit;
            }
            memo[idx][0] += memo[child][0];
            memo[idx][1] = max(memo[idx][1], memo[child][1] - 1);
        }
        
        if(memo[idx][2] == 0) {
            memo[idx][0] += 1;
            memo[idx][2] = memo[idx][1];
        }

        return memo[idx];
    };

    for(int i = 2; i <= n; ++i) {
        int p;
        cin >> p;
        tree[p].children.push_back(i);
    }

    for(int i = 1; i <= n; ++i) {
        int k;
        cin >> k;
        tree[i].k = k;
    }
    for(int i = 1; i <= n; ++i) {
        dfs(i);
    }
    cout << memo[1][0];
}
// 64 位输出请用 printf("%lld")