记录编号	206634	评测结果	AAAAAAAAAA
题目名称	[HZOI 2015] CrazyBinary	最终得分	100
用户昵称	stdafx.h	是否通过	通过
代码语言	C++	运行时间	0.352 s
提交时间	2015-11-08 18:50:59	内存使用	64.24 MiB

#define MAXL 100010UL
#define MAXN 2010UL
#define MAXS 2UL

#define ll long long

#include <cstdio>

ll n,val[MAXL],l[MAXL],r[MAXL],f[MAXN][MAXN][MAXS],s[MAXN];
const ll inf=(ll)(1e12);

inline void Clear(ll p){
	for(ll i=0;i<=n;i++){
		f[p][i][0]=inf,f[p][i][1]=-inf;
	}
	return;
}

void tree_dp(ll p){
	s[p]=1;
	if(l[p]) tree_dp(l[p]),s[p]+=s[l[p]];
	if(r[p]) tree_dp(r[p]),s[p]+=s[r[p]];
	Clear(p);
	ll s1=l[p],s2=r[p];
	if((!s1)&&(!s2)){
		f[p][0][0]=val[p];
		f[p][0][1]=val[p];
		f[p][1][0]=-inf;
		f[p][1][1]= inf;
	}
	else if(s1&&s2){
		for(ll i=0,new_;i<=s[p];i++){
			for(ll j=0;j<=i;j++){
				//左面改造j次 右面改造i-j次
				//1 改掉 p 点，左面 j 次右面 i-j-1次 更新f[p][i]
				if(i!=j){
					if(f[s1][j][0]+1<=f[s2][i-j-1][1]-1){
						if(f[s1][j][0]+1<f[p][i][0]) f[p][i][0]=f[s1][j][0]+1;
						if(f[s2][i-j-1][1]-1>f[p][i][1]) f[p][i][1]=f[s2][i-j-1][1]-1;
					}
				}
				// 2 不改 p 点，左面j次右面 i-j次 更新f[p][i]
				if(val[p]>f[s1][j][0]&&val[p]<f[s2][i-j][1]){
					if(val[p]<f[p][i][0]) f[p][i][0]=val[p];
					if(val[p]>f[p][i][1]) f[p][i][1]=val[p];
				}
			}
		}
	}
	else if(s1){
		for(ll i=0;i<=s[p];i++){
			//1 改掉 p 点
			if(f[p][i+1][0]>f[s1][i][0]+1) f[p][i+1][0]=f[s1][i][0]+1;
			if(f[p][i+1][1]<f[s1][i][1]+1) f[p][i+1][1]=f[s1][i][1]+1;
			//2 不动
			if(val[p]>f[s1][i][0]){
				if(val[p]<f[p][i][0]) f[p][i][0]=val[p];
				if(val[p]>f[p][i][1]) f[p][i][1]=val[p];
			}
		}
	}
	else if(s2){
		for(ll i=0;i<=s[p];i++){
			//1 改掉 p 点
			if(f[p][i+1][0]>f[s2][i][0]-1) f[p][i+1][0]=f[s2][i][0]+1;
			if(f[p][i+1][1]<f[s2][i][1]-1) f[p][i+1][1]=f[s2][i][1]+1;
			//2 不动
			if(val[p]<f[s2][i][1]){
				if(val[p]<f[p][i][0]) f[p][i][0]=val[p];
				if(val[p]>f[p][i][1]) f[p][i][1]=val[p];
			}
		}
	}
	return;
}

int main(){
	freopen("crazy_binary.in","r",stdin);
	freopen("crazy_binary.out","w",stdout);
	scanf("%lld",&n);
	for(ll i=1;i<=n;i++) scanf("%lld",&val[i]);
	for(ll i=2,fa,ch;i<=n;i++){
		scanf("%lld%lld",&fa,&ch);
		if(!ch) l[fa]=i;
		else r[fa]=i;
	}
	tree_dp(1);
	for(ll i=0;i<=n;i++) if(f[1][i][0]<=f[1][i][1]){
		printf("%lld",i);
		return 0;
	}
	return 0;
}