黑白树题解

​ 一道贪心题~

​ 首先，我们将所有点分为已被覆盖点和未被覆盖点。那么首先，因为叶子节点是必选的，所以我们先将叶子节点选中，然后，就会产生若干被覆盖点，然后，由于选了一个点后，会导致这个点到根（1号点）的路径上的若干点被覆盖，所以，如果是在同一个祖先关系的链上的话，我们发现，我们可以贪心的从所有已覆盖点和深度最大的未覆盖点中，选取可以覆盖到根最多的点，这样根据决策包容性，一定是对的

​ 至于如何更新答案，我们当然不可能直接从叶子往根跳来更新，如果这样的话，一个链会直接卡成

​ 我们发现，我们只需要用儿子去更新父亲，这样，我们就有两种方法:

​ dfs和topo(拓扑排序)，而这题，明显用拓扑排序更好，所以我们使用拓扑排序来更新答案

​ 代码：

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+1;
struct node{
    int v,nex;
}t[N];
int fa[N],las[N],len;
int dep[N],du[N],k[N];
int dp[N],pd[N];
bool vis[N];
queue<int>sp;
inline void add(int u,int v){
    t[++len]=(node){v,las[u]},las[u]=len;
}
inline void dfs(int now){
    for(int i=las[now];i;i=t[i].nex){
        int v=t[i].v;
        dep[v]=dep[now]+1;
        k[v]-=dep[v];
        dfs(v);
    }
}
inline void topo(){
    int ans=0;
    while(!sp.empty()){
        int x=sp.front();sp.pop();
        dp[x]=max(dp[x],k[x]);
        if(pd[x]+dep[x]<0){//必选
            ++ans;pd[x]=dp[x];
        }
        dp[fa[x]]=max(dp[fa[x]],dp[x]);
        pd[fa[x]]=max(pd[fa[x]],pd[x]);
        --du[fa[x]];
        if(!du[fa[x]]){
            sp.push(fa[x]);
        }
    }
    printf("%d",ans);
}
int main(){
    memset(dp,~0x3f3f,sizeof(dp));
    memset(pd,~0x3f3f,sizeof(pd));
    int n;
    scanf("%d",&n);
    for(int i=2;i<=n;++i){
        scanf("%d",&fa[i]);
        ++du[fa[i]];
        add(fa[i],i);
    }
    for(int i=1;i<=n;++i){
        scanf("%d",&k[i]);
        --k[i];
        if(!du[i]){
            sp.push(i);
        }
    }
    dep[1]=1;
    dfs(1);
    topo();
    return 0;
}