牛客 - 黑白树

传送门：牛客 - 黑白树

思路分析

贪心的从儿子节点往上染色
设$f[i]$表示$i$节点能往上染色的最大距离（包含他自己），$f[i]$由儿子节点转移过来
如果$f[i]$为0，说明儿子已经影响不到当前节点了，这个节点就必须选，$f[i]=k[i]$

样例输入

4
1
2
1
1 2 2 1

样例输出

3

AC代码

#include <functional>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <iomanip>
#include <vector>
#include <string>
#include <cstdio>
#include <chrono>
#include <random>
#include <queue>
#include <stack>
#include <cmath>
#include <map>
#include <set>
#if __cplusplus >= 201103L
#include <unordered_map>
#include <unordered_set>
#endif
#define ls x<<1
#define rs x<<1|1
#define fi first
#define se second
#define ll long long
#define pb push_back
#define mp make_pair
#define fun function
#define sz(x) x.size()
#define lowbit(x) x&(-x)
#define all(x) x.begin(),x.end()
#define mem(a,b) memset(a,b,sizeof(a))
#define IOS ios_base::sync_with_stdio(0); cin.tie(0);cout.tie(0);

using namespace std;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int INF = 0x3f3f3f3f;
const int N=1e5+10;

vector<int>e[N];
int f[N],k[N],ans;

void dfs(int u){
    for(auto v:e[u]){
        dfs(v);
        f[u]=max(f[u],f[v]-1);
        k[u]=max(k[u],k[v]-1);
    }
    if(!f[u]){
        ans++;
        f[u]=k[u];
    }
}

int main() {
    IOS;
#ifdef xiaofan
    freopen("1.in","r",stdin);
    freopen("1.out","w",stdout);
#endif

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



    return 0;
}