黑白树题解

首先，我要吐槽，我服啦我自己，我开个1e6然后疯狂爆空间，一直以为是数组开小了，结果是re,在此说下开个1e5+100就好啦。
首先。我们贪心。可以肯定的是每个树的叶节点必然是会单独+1次。那么我们就可以直接DFS到叶子节点，然后每次贪心取max（fa,son-1）,题目要求是K[i]>1的范围都可以覆盖，所以要减一；然后再开一个数组来记录每次你的更新操作；

#include <bits/stdc++.h>
#define fio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define debug(x) cout << #x << ": " << x << endl;
#define debug1(x) cout<<"xxx"<<endl;
#define ll long long
#define ull unsigned long long
#pragma GCC optimize("Ofast","inline","-ffast-math")
#pragma GCC target("avx,sse2,sse3,sse4,mmx")
using namespace std;
const int maxx=1e5+100;
const int mod=1e9+7;
vector<ll>ans[maxx];
ll val[maxx];
ll sum;
ll cnt[maxx];
void dfs(ll x)
{
    for(ll i=0; i<ans[x].size(); i++)
    {
        ll son=ans[x][i];
        dfs(son);
        val[x]=max(val[x],val[son]-1);//每次更新找最大的k能够覆盖的范围;
        cnt[x]=max(cnt[x],cnt[son]-1);//选择自己或者儿子的k,然后去覆盖的树,如果是儿子那么距离就要-1的距离
    }
    if(cnt[x]==0)//如果不等于0，那么说明她的儿子节点可以覆盖到当前，当消耗完了，说明之前儿子节点的K最大覆盖点，那么就该更新此时最大的 k新的覆盖范围 
//val 我是用k来说的
    {
        sum++;
        cnt[x]=val[x];
    }
}
int main()
{
    fio;
    ll n;
    cin>>n;
    for(ll i=2; i<=n; i++)
    {
        ll a;
        cin>>a;
        ans[a].push_back(i);
    }
    for(ll i=1; i<=n; i++)
        cin>>val[i];
    dfs(1);
    cout<<sum<<endl;
    return 0;
}