题目描述

一棵n个点的有根树，1号点为根，相邻的两个节点之间的距离为1。树上每个节点i对应一个值k[i]。每个点都有一个颜色，初始的时候所有点都是白色的。
你需要通过一系列操作使得最终每个点变成黑色。每次操作需要选择一个节点i，i必须是白色的，然后i到根的链上（包括节点i与根）所有与节点i距离小于k[i]的点都会变黑，已经是黑的点保持为黑。问最少使用几次操作能把整棵树变黑。

题解

首先分析题意，发现题目中 '每次操作需要选择一个节点i，i必须是白色的' 这一限制其实是没有意义的，因为我们只要从上向下染色，是不会碰到染色的点的，因为每个点只能向上传递颜色。
那么问题就转换成最少选几个点，使整颗树变成黑色。
由于根节点是一定要染的，那么我们首先考虑贪心：从根节点向上染色，并记录能染到的最远距离，然后累加。
但其实可以很容易想到一种数据:2 -> 99 -> 1 -> 1 -> 1 (代表ki) 显然用上述的贪心思想不能得到最优解。
那怎么办呢？ 怎么解决向上传递的路径中有可能对答案有贡献的点？
显然，不满足贪心的解法的情况为：选一个点的子节点比选当前点，往上走的距离要远。所以我们要更新每一个节点的K属性，使得当前子树最优(其实就相当于一种等价代换)。
那么我们得到这个新的K之后，继续贪心就可以拉~

代码

#pragma GCC optimize(2)
#include<bits/stdc++.h>
#define ls rt<<1
#define rs rt<<1|1
#define pb push_back
#define fi first
#define se second
#define ios ios::sync_with_stdio(0);
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
typedef vector<int> VI;
const int maxn = 1e5 + 6;
const LL inf = 0x3f3f3f3f3f3f3f3f;
const int mod = 998244353;
LL qp(LL x,LL y){LL ans=1;x%=mod;while(y){if(y&1) ans=ans*x%mod;x=x*x%mod;y>>=1;}return ans;}
LL inv(LL x){return qp(x,mod-2);}
//head

int n,ans,k[maxn],f[maxn];
VI G[maxn];

void dfs(int u,int fa){
     int ff=0;
     for(int v:G[u]) if(v!=fa){
        dfs(v,u);
        ff=max(ff,f[v]-1);
     }
     if(!ff) {ans++;f[u]=k[u];}
     else f[u]=ff;

     k[fa]=max(k[fa],k[u]-1);
}

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