NC13249

题意

给你一棵树，每个节点 $i$ 上有一个值 $k[i]$ ，一开始树上所有节点均为白色，要求你每次选择一个白色节点染色，从该节点往根的链上小于 $k[i]$ 的均被染色，求最小染色次数为多少？

思路

DFS 贪心
首先叶子结点是一定要染色的，我们考虑如何返回的时候构造最优方案，我们维护两个数组。
回溯路径所能染色到的最远距离 $k[x]=max(k[x],k[s]-1)$
无须染色所能染色到的最远距离 $d[x]=max(d[x],d[s]-1)$
当 $d[x]=0$ 的时候，意味着到该节点必须进行一次染色，此时不一定是选择该节点进行染色，可以选择回溯路径所能染色到的最远距离那个点进行染色。

#include<bits/stdc++.h>
#pragma GCC optimize(2)
using namespace std;
typedef long long ll;
typedef pair<int,int>P;
const double eps = 1e-8;
const int NINF = 0xc0c0c0c0;
const int INF  = 0x3f3f3f3f;
const ll  mod  = 1e9 + 7;
const ll  maxn = 1e6 + 5;
const int N = 1e5 + 5;

int n,f[N],k[N],d[N],res;
vector<int>G[N];

void dfs(int x,int fa){
    for(int i=0;i<G[x].size();i++){
        int s=G[x][i];
        dfs(s,x);
        k[x]=max(k[x],k[s]-1);
        d[x]=max(d[x],d[s]-1);
    }
    if(!d[x]) ++res,d[x]=k[x];
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n;
    for(int i=2;i<=n;i++){
        int x; cin>>x;
        G[x].push_back(i);
    }
    for(int i=1;i<=n;i++){
        cin>>k[i];
    }
    dfs(1,-1);
    cout<<res<<'\n';
    return 0;
}