Solution

由题意可知叶子节点必定要染色。对于其他节点：

• 若此节点的已经染色的子节点中，可以将它覆盖，那么不需要染色，并借助这个点能覆盖的范围更新最大范围。
• 若此节点的已经染色的子节点中，不能将它覆盖，那么需要将其子节点中范围最大的点染色，并更新最大范围。

可以发现这是一个由子节点向父节点更新的过程，所以可以使用 。每次贪心地更新能覆盖的最大距离，不能覆盖就进行染色。

时间复杂度： 。

Code

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int maxn=1e5+10;
struct edge{
    int t;
    int v;
}e[maxn<<1];
int ans,tot,n,k[maxn],hd[maxn];
void add(int x,int y){
    tot++;
    e[tot].t=hd[x];
    e[tot].v=y;
    hd[x]=tot;
}
int dfs(int u,int fa){
    int sum=0;
    for(int i=hd[u];i!=0;i=e[i].t)
        if(e[i].v!=fa)
            sum=max(sum,dfs(e[i].v,u));
    if(!sum){
        ans++;
        return k[u]-1;
    }
    k[fa]=max(k[fa],k[u]-1);//将所有子节点能覆盖的最大范围更新到父节点上，方便染色后返回
    return sum-1;
}
int main(){
    ios::sync_with_stdio(false);
    cin>>n;
    int x;
    for(int i=2;i<=n;i++){
        cin>>x;
        add(x,i);
        add(i,x);
    }
    for(int i=1;i<=n;i++)
        cin>>k[i];
    dfs(1,0);
    cout<<ans;
    return 0;
}