【每日一题】 黑白树 dfs

思路：
树的题目多半和dfs有点关系 滑稽.jpg
首先对于叶子结点的话 是一定要染色的 这显而易见 关键点在于对于已经被覆盖了的点的操作
根据贪心 可能会想 已经覆盖的点我不再去动它了 但这其实是错的 很容易就举出反例 若其中有一个点覆盖范围巨大 这思路就是错的了
所以对于其他的结点 更新最大染色范围的操作就是必须的 如果该结点的子节点可以染色到它的话 他就不需要再染色 更新最大范围 如果染色不到它 它就需要被染色 同时选择子节点内范围最大的点染色 更新最大范围

#include <bits/stdc++.h>

using namespace std;

const int N = 100005;

struct node
{
    int w;
    int to;
    int next;///相同起点的上一次加入的边的存储位置 (指向下一条边在edge数组中的位置)
} edge[N << 1];

int cnt,n;///边的编号
int head[N];///以i为起点最近加入一条边的位置
int k[N];

void add(int u,int v,int w)
{
    edge[cnt].w = w;
    edge[cnt].to = v;///边的终点
    edge[cnt].next = head[u];///head[u]:上一次加入的边的位置
    head[u] = cnt ++ ;///更新以u为起点的最新加入的边的编号
}

void init()
{
    for(int i = 1; i <= n; i ++)
        head[i] = -1;
    cnt = 0;
}

int res = 0;

int dfs(int u,int fa)
{
    int range = 0;

    for(int i = head[u]; ~i ; i = edge[i].next)
    {
        int to = edge[i].to;
        if(to != fa)
            range = max(range,dfs(to,u));
    }

    if(range == 0)///覆盖不到它 就得染色
    {
        res ++ ;
        return k[u] - 1;///返回染色范围
    }

    k[fa] = max(k[fa],k[u] - 1);///把染色范围都更新到父节点上 方便选择最优的范围
    return range - 1;
}

int main()
{
    cin >> n;

    init();

    for(int i = 2;i <= n;i ++)
    {
        int x;

        cin >> x;

        add(i,x,1);
        add(x,i,1);
    }

    for(int i = 1;i <= n;i ++)
        cin >> k[i];

    dfs(1,0);

    cout << res << '\n';

    return 0;
}