每日一题-黑白树

添加链接描述

之前做过一次，好像是看别人题解的，这次自己再做一次。
考虑一个节点x需要覆盖，假设它的所有子树都已覆盖完全，那么有两种情况。
1.子树中选择的点可以覆盖x，直接覆盖即可。
2.选择的点覆盖不了x，那么这个时候我们需要选择最优的点来覆盖x。

\(f[x],g[x]\)分别表示在子树中已选择的点，和未选择的点最大能向上覆盖多少，同时统计答案即可。

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#define fo(i,a,b) for (int (i)=(a);(i)<=(b);(i)++)
#define fd(i,b,a) for (int (i)=(b);(i)>=(a);(i)--)
#define A puts("Yes") 
#define B puts("No")
using namespace std;
typedef long long ll;
const int N=1e5+5;
int n;
int nex[N],head[N],to[N],tot;
int f[N],g[N],ans,x;
int k[N];
void add(int x,int y){
	to[++tot]=y; nex[tot]=head[x]; head[x]=tot;
}
void dfs(int x){
	int mx=-1,z=-1;
	for (int i=head[x];i;i=nex[i]){
		int v=to[i];
		dfs(v);
		mx=max(mx,f[v]);
		z=max(z,g[v]);
	}
	if (mx>=1) {
		f[x]=mx-1;
		g[x]=max(z-1,k[x]);
	}
	else{
		ans++;
		f[x]=max(k[x],z-1);
	}
}
int main(){
	
//	freopen("data.in","r",stdin);		
	
	scanf("%d",&n);
	fo(i,2,n){
		scanf("%d",&x);
		add(x,i);
	}
	
	fo(i,1,n) scanf("%d",&k[i]),k[i]--;

	
	dfs(1);
	
	printf("%d\n",ans);
	return 0;
}