黑白树

由admin

11月 28, 2021 code

题解：设k[ x ]为节点x以及它的子树中的点能往上走的最长距离，即 k[ x ] = max ( k[ x ] , k[ v ] -1 ) ,v是x的儿子，设f [ x ] 为选择了节点后还能往上走的距离， f[ x ] = max( f[ x ] , f[ v ] -1 ) ，当 f [ x ] = 0 时，答案加一，且 f [ x ] = k [ x ] 。

#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
#define ll long long

const int maxn=1e5+50;

int n,fa[maxn],k[maxn],f[maxn],ans;
int fir[maxn],nex[maxn<<1],to[maxn<<1],ecnt;

void add(int u,int v){
    nex[++ecnt]=fir[u];fir[u]=ecnt;to[ecnt]=v;
}

void dfs(int x){
    for(int e=fir[x];e;e=nex[e]){
        int v=to[e];
        if(v==fa[x]) continue;
        dfs(v);
        k[x]=max(k[x],k[v]-1);
        f[x]=max(f[x],f[v]-1);
    }
    if(!f[x]){
        ans++;
        f[x]=k[x];
    }
}

template<typename T>void inline read(T &aa){
    ll ff=1;char cc=getchar();aa=0;
    while((cc<'0'||cc>'9')&&cc!='-') cc=getchar();
    if(cc=='-') ff=-1,cc=getchar();
    while(cc<='9'&&cc>='0') aa=aa*10+cc-48,cc=getchar();
    aa*=ff;
}

int main(){
    cin>>n;
    for(int i=2;i<=n;i++){
        read(fa[i]);
        add(fa[i],i);add(i,fa[i]);
    }
    for(int i=1;i<=n;i++) read(k[i]);
    dfs(1);
    cout<<ans<<endl;
    return 0;
}