【每日一题】树上dfs+贪心

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

马上就把题目补完了=.=,实在没啥时间做
首先肯定是从叶子节点开始选点变黑，感觉做过这类题，类似跳跃游戏什么的==；
当选完一个点，选下一个点的策略是：选择这个点第一个覆盖不到的和覆盖到的点中能跳到最远距离的那个点即可。
dfs遍历中，从叶子节点往上维护一个left[]表示节点x可以再往上覆盖多远，left[u]=max(left[child]-1)；当left[i]为0时表示覆盖不到了，那么选择这个点，left就变成了k[i];
因为我们要选择能覆盖到最远距离的点，dfs从下往上用k[i]去维护某个点能跳到的最远距离值就可以了

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define MYINTMAX 0x3f3f3f3f
#define N 100005
ll k[N];//每个点能跳到最远的位置
ll ans, lef[N];//还剩的覆盖距离
ll n,tot,rt,dis[N],fa[N],h[N],ne[N<<1],p[N<<1],wi[N<<1];
void addEdge(int u,int v,int w){p[++tot]=v;ne[tot]=h[u];h[u]=tot;wi[tot]=w;}
void add(int u,int v){p[++tot]=v;ne[tot]=h[u];h[u]=tot;}
void dfs(int u,int father)
{
    int tmp;
    lef[u]=0;
    for(int i=h[u];i;i=ne[i])if(p[i]!=father)
    {
        dfs(p[i],u);
        lef[u]=max(lef[u],lef[p[i]]-1);
        k[u]=max(k[u],k[p[i]]-1);
    }
    if(lef[u]==0){//已经覆盖不到了
        ans++;
        lef[u]=k[u];
    }
}
int main()
{
    scanf("%d", &n);
    for (int i = 2; i <= n; i++)
    {
        int x;
        scanf("%d", &x);
        add(x,i);
    }
    for (int i = 1; i <= n; ++i)
        scanf("%d", &k[i]);
    dfs(1, 0);
    cout << ans << endl;
    return 0;
}