时间限制：1秒
空间限制：32768K
一棵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)
样例解释:
对节点3操作，导致节点2与节点3变黑
对节点4操作，导致节点4变黑
对节点1操作，导致节点1变黑
输出描述:
一个数表示最少操作次数
输入例子:
4
1
2
1
1 2 2 1
输出例子:
3

解法：现场忘记打了。。。基本思路就是染色是向上染色，那么我们肯定要将所有的叶子节点进行染色，那么这里就是一个DAG图了，直接用拓扑排序来模拟每一次都选择度为0的点。但是这样显然是不对的，因为节点还有个k存在，举个栗子，8->7->6->5->4->3->2->1 并且k的大小为4 10 2 2 1 1 1 1。我们直接按照拓扑序去模拟的话得到的答案是5，但是正确答案是2.我们维护一个pre[i]代表染色到点i,以上一个起点开始染色带现在能剩余的长度。那么当pre[i]==0的时候，我们需要一个点要么是节点i，要么是以上一个起点到i这条链子上的某个点作为起点，继续向下跑。我们还需要另外一个数组dp[i].表示跑到点i，以某一个点作为起点，这条链子上跑到节点i还剩余能够染色的最长的长度。上面的样例就是跑到4的时候pre[i]=0，但是这个时候的dp[i]=7，a[i]=1,我们选择以7为最大长度继续跑下去。这个题主要考察的是思维，好题。

#include <bits/stdc++.h>
using namespace std;
const int maxn = 100010;
int n, ans, du[maxn], dp[maxn], a[maxn], pre[maxn];
vector <int> G[maxn];
void topsort()
{
    queue <int> q;
    memset(dp, 0, sizeof(dp));
    memset(pre, 0, sizeof(pre));
    for(int i=1; i<=n; i++){
        if(du[i] == 0){
            q.push(i);
        }
    }
    while(!q.empty()){
        int u = q.front(); q.pop();
        dp[u] = max(dp[u], a[u]);
        if(pre[u] == 0){
            pre[u] = dp[u];
            ans++;
        }
        for(int i = 0; i<G[u].size(); i++){
            int v = G[u][i];
            dp[v] = max(dp[v], dp[u]-1);
            pre[v] = max(pre[v], pre[u]-1);
            du[v]--;
            if(du[v]==0){
                q.push(v);
            }
        }
    }
}
int main()
{
    scanf("%d", &n);
    for(int i=2; i<=n; i++){
        int x; scanf("%d",&x);
        G[i].push_back(x);
        du[x]++;
    }
    for(int i=1; i<=n; i++) scanf("%d", &a[i]);
    topsort();
    printf("%d\n", ans);
    return 0;
}