黑白树

这大概是清楚姐姐的题解的题解。
看着清楚姐姐的题解和代码做的个人笔记。因为不太会写= =。
（这里绝壁是最菜最菜最菜的一员）

Step 0（个人错误）

1. 审题问题，初步没有注意到是该结点i至根的链的染色，以为有向上和向下，对于结点的染色选择就迷茫了。
2. 关于数据处理。对于染色与否，及整棵树的关系，当时想用结构体，包含fa,dis,flag,vec。
   1）flag：想直接用flag来模拟染色过程。然而属于无用信息，浪费内存，只需要数字位置抽象化即可。
   2）vec/fa：储存的是向下的和向上的，想用单结点函数染色所有关联结点。有重复染色，不可取。
   3）树的结构是以一点为中心扩散，无法遍历，无法找到根结点。

Step 1

3. 发现审题问题。却不知道怎么找到根。从数据储存的方式上就出了问题。
   1）使用vector G[N]，单维限制的变长数组。使用从父向子的方向储存。可遍历。
   2）使用dfs，找到叶子。后序遍历处理。
   3）得到树和dfs的框架了，填补对其处理信息。
4. 对于题目要求的处理。
   发现叶子必染色，对于其上的结点应该在‘已经被覆盖’直到‘未被染色的第一个结点’之中找可以到达最远的-->选择。但是不知道怎么实现。if未被染 else比较 ？
   0）叶子结点染色。
   1）如何找最远？发现可以用距离数值覆盖的方法。max f[x] f[son]-1 找最远。
   2）找最远的操作何时开始，何时停下？一直在更新当前结点的最远距离，结束则在碰到未覆盖结点时。
   3）碰到未覆盖结点是如何定义的？是在染完色后，此染色结点的k[i]值即为行走步数。在行走步数为0时。
   4）边界即首次染色是什么？是叶子结点。

Step 3

#include <cstdio>
#include <vector>
using namespace std;
const int N = 1e5 + 10;
int k[N], f[N], ans;
vector<int> G[N]; 
void dfs(int now) {
    for (int i = 0; i < G[now].size(); i++) {
        int y = G[now][i]; 
        dfs(y);
        k[now] = max(k[now], k[y] - 1); //k[]初始是被题目赋予
        f[now] = max(f[now], f[y] - 1); //f[]是步数，直到0
    }
    //k值是作为在本题中持续更新的值。每次染色只是使用一次k值(赋予步数)
    //但凡步数未走到0就不进入染色。
    if (f[now] == 0) {    //叶子为0，或当步数走到0时，才进入染色
        ans++;            
        f[now] = k[now];    //赋予步数
    }
}
int main(void) {
    int n, temp;
    scanf("%d", &n);
    for (int i = 2; i <= n; i++) {
        scanf("%d", &temp);
        G[temp].push_back(i);
    }
    for (int i = 1; i <= n; i++) {
        scanf("%d", &k[i]);
    }
    dfs(1);
    printf("%d", ans);
    return 0;
}