黑白树

题意：
有一颗n个节点的树，每个节点有一个权值k[i]，一开始树上节点全是白色的，你可以选择一个白色的节点进行染色，使该节点到根节点路径上的点距离该节点小于k[i]的节点染成黑色。求使该树所有节点变黑的最少操作次数。

思路：
树形结构+贪心
由于染色的节点在你选择的节点和根之间，所以叶子节点你一定会选择，然后从叶子节点到根的回溯上看，你可以在叶子节点可以染色的范围和不能染色到的第一个节点（考虑同叶子节点）中选择一个可以向根染色更近的一个节点进行贪心，记录你的操作次数。
对于只能在白色节点染色的问题，你可以想象对节点染色顺序使从根节点到页节点进行的，所以你无需考虑。

代码：

#include <bits/stdc++.h>
typedef long long ll;

using namespace std;

const ll inf=1000000007;

inline int read()
{
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9')
    {
        if(ch=='-')
            f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
    {
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x*f;
}

int ans=0, k[100005];

vector<int> g[100005];
struct w
{
    int fa, ma;
}w, w2;

struct w dfs(int v)
{
    if(g[v].size()==0)  //对叶子节点进行操作。
    {
        ans++;
        w.ma=0;
        w.fa=k[v]-1;
        return w;
    }
    struct w pa;   //pa.fa表示染色范围还可以向根前进几个节点，pa.ma表示贪心的结果（既再操作一次可以向根前进节点数目的最大值）。
    pa.fa=0;
    pa.ma=0;
    for(int i=0;i<g[v].size();i++)
    {
        w2=dfs(g[v][i]);
        pa.fa=max(w2.fa,pa.fa);
        pa.ma=max(w2.ma-1,pa.ma);
    }
    pa.ma=max(pa.ma,k[v]);
    if(pa.fa==0)   //染色范围无法再向根前进，说明要再操作一次。
    {
        ans++;
        pa.fa=pa.ma-1;
        pa.ma=0;
        return pa;
    }
    pa.fa--;
    return pa;
}

int main()
{
    int n;
    scanf("%d",&n);
    for(int i=2;i<=n;i++)
    {
        int x;
        scanf("%d",&x);
        g[x].push_back(i);
    }
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&k[i]);
    }
    dfs(1);
    cout << ans << endl;
    return 0;
}