题目

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

输入描述：
第一行一个整数n (1 ≤ n ≤ 10^5)
接下来n-1行，每行一个整数，依次为2号点到n号点父亲的编号。
最后一行n个整数为k[i] (1 ≤ k[i] ≤ 10^5)

输出描述：
一个数表示最少操作次数

解析

先提示一下：这道题是树+贪心。
说实话我一开始没想到这道题可以贪心，我还以为是树上dp之类的，但是我不太会写。

但是重要的是，我们只要知道这道题的贪心策略之后，这道题就简单了不少：

贪心策略排除：
  1. 我们按照常规思想，我们的贪心策略可能会有两种。一个是选出里面最大的优先操作；另一个就是从叶往根逐步删除。
  2. 首先这种题目就不可能给你这么简单的操作，这两种可以排除了。但我还是来讲一下原因：
  3. 直接选最大的操作都难，但是我们的操作思想确实与这个有关：这里直接来的话，如果有大到多余的（大，但离根进），很可能就会浪费。
  4. 那如果逐步删除呢？这个一想就知道不可能，如果浪费了权值大的项岂不是很亏？

本题贪心策略：
  1. 补充一句：这道题只能对上面进行染色，这是整个算法非常重要的一点。
  2. 这道题的贪心策略呢，我已经排除了上面两种，不如换个角度来看。我们不管是选最大的操作，还是逐步删除，都是在选择起点操作。
  3. 我们举个例子：某个点要是被下面其他点变黑，当然是好事，可以减少操作次数。但是好和更好的差别在哪呢？在于影响到这个点的操作还阔以影响什么更多的点。
  4. 这就是我们在操作终点。总结下来就是：我们对某一点最好的是：既满足这一点被染黑的需求，并且可以染黑上面更多的点。
  • 很多思想都是在对终点进行操作，或者说是在用最后的小问题，解决一直到达根部的大问题。

咋操作嘞：
  1. 我们在这里有一个思想：我们起点对上面有作用，但是终点不管起点是哪个，只要我们贪心策略的作用大就好。
  2. 所以我们就可以认为某一个节点的权值就是其大权子节点减一。举个例子就是：父节点为2，子节点为8，在对更上面节点的作用中，我们可以认为这个父节点就是7（8 - 1）。
  3. 假如我们已经知道了每个节点可以最大表示的权值（就是根据第二点转换的）是多少。现在我们一个根有多个子节点，选出可以染色最远的向上走就行了。
  4. 所以我们有了两个问题。一个是要求每个起点可以表示的权值；另一个是所有点都染不到色的点怎么办。
  5. 首先是起点表示的权值，我们一样可以利用dfs用底至上进行计算：每个节点的最大值表示权就是：自己和子节点减一中的最大值。k[u] = max(k[u], k[v] - 1)。
  6. 然后是染不到色的节点，我们可以判断出来，然后给他赋予当前节点最大可染色距离。
  7. 为了第六点，我们添加一个数组f，单纯的表示最大的染色距离，使其到蔓延终点以后无法更新，停下来（此时f[u] == 0）。
  8. 然后让f[u] = f[k]（赋值最大蔓延距离），循环上去。（根节点就是一个无法蔓延节点，我们就会计数）

打代码咯：
  1. 老方法，前向星保存树，主要是用习惯了前向星，发现真好用哈哈哈哈。
  2. 该存的存好了以后就可以进入dfs了。
  3. dfs过程没有很多再去描述的了，记得在蔓延结束时计数就好了。（详情看上面的算法讲解）
  4. 那就看代码吧？哈哈

AC代码 

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
//代码预处理区

const int MAX = 1e5 + 7;
int head[MAX], tot;
struct Node {
    int v, next;
} edge[MAX << 1];
int n, k[MAX]; 
int f[MAX], cnt;
//全局变量区

template<class T>inline void read(T& res);
void add_edge(int u, int v);
void dfs(int u, int fa);
//函数预定义区

int main() {
    read(n);
    tot = 0; memset(head, 0, sizeof head);
    for (int i = 2; i <= n; i++) {
        int v; read(v);
        add_edge(i, v);
        add_edge(v, i);
    }
    for (int i = 1; i <= n; i++) read(k[i]);
    cnt = 0; memset(f, 0, sizeof f);
    dfs(1, 0);
    printf("%d\n", cnt);
    return 0;
}
template<class T>inline void read(T& res) {
    char c; T flag = 1;
    while ((c = getchar()) < '0' || c > '9')
        if (c == '-')
            flag = -1;
    res = c - '0';
    while ((c = getchar()) >= '0' && c <= '9')
        res = res * 10 + c - '0';
    res *= flag;
}
void add_edge(int u, int v) {
    tot++;
    edge[tot].v = v;
    edge[tot].next = head[u];
    head[u] = tot;
}
void dfs(int u, int fa) {
    for (int i = head[u]; i; i = edge[i].next) {
        int v = edge[i].v;
        if (fa == v) continue;
        dfs(v, u);
        f[u] = max(f[u], f[v] - 1);
        //筛选出所有分支中能延伸的最大值
        k[u] = max(k[u], k[v] - 1);
        //更新每个节点可以表示的最大延伸值
    }
    if (!f[u]) {
        cnt++;
        f[u] = k[u];
    }
    //u节点不被子节点覆盖，就从该节点重新操作
}
//函数区