每日一题 4.8 黑白树

这是一个用树来提升难度的贪心题（蒟蒻理解
首先当你来到一个新节点时有两种情况
1、此节点能被已染色的子节点覆盖 这时只要更新理论最大覆盖范围
2、此节点不能被已染色的子节点覆盖 选择那个提供最大覆盖范围的子节点染***r>菜鸡的其他理解全在代码里面了QAQ

#include <bits/stdc++.h>
#define ll long long 
ll const maxn=1e5+5;
using namespace std;
struct M{///链式前向星存图
    ll to,next,val;///终点，同起点的上一条边的编号，边权
}edge[maxn<<1];///边集
ll n,x,u,v,cnt,head[maxn],k[maxn],ans;
void add(ll u,ll v)
{
  edge[++cnt].next = head[u];///以u为起点上一条边的编号，也就是与这个边起点相同的上一条边的编号
  edge[cnt].to=v;///终点
  //edge[cnt].val=w;///权值
  head[u]=cnt;///更新以u为起点上一条边的编号
}
int dfs(int u,int fa){
    int sum=0;
    for(int i=head[u];i!=0;i=edge[i].next)
        if(edge[i].to!=fa)///深搜
            sum=max(sum,dfs(edge[i].to,u));///确定染色节点
    if(!sum)///该点未被染色范围覆盖  选子节点中的最大范围染色
    {
        ans++;
        return k[u]-1;///向上移一下减一
    }
    k[fa]=max(k[fa],k[u]-1);///更新子节点能覆盖的最大范围
    return sum-1;
}
int main(){
    scanf("%lld",&n);
    for(int i=2;i<=n;i++)
    {
        scanf("%lld",&x);
        add(x,i);
        add(i,x);
    }
    for(int i=1;i<=n;i++)scanf("%lld",&k[i]);
    dfs(1,0);
    cout<<ans<<endl;
    return 0;
}