记录编号	372849	评测结果	WAAWWWWWWW
题目名称	[HZOI 2015] CrazyBinary	最终得分	20
用户昵称	FoolMike	是否通过	未通过
代码语言	C++	运行时间	0.249 s
提交时间	2017-02-19 11:13:47	内存使用	138.15 MiB

#include<cstdio>
#include<algorithm>
using namespace std;
const int N=6010;
int n,top,a[N],son[N][2];
int dp[N][N];
//dp[i][j]表示子树i上进行j次修改后节点i的取值极值,||>9e8是不合法的 
void solve(int x,int tp){
	int &lc=son[x][0],&rc=son[x][1];
	if (lc) solve(lc,0);
	else{
		lc=++top;
		for (int i=0;i<=n;i++) dp[lc][i]=-9e8;
	}
	if (rc) solve(rc,1);
	else{
		rc=++top;
		for (int i=0;i<=n;i++) dp[rc][i]=9e8;
	}
	if (tp){
		for (int i=0;i<=n;i++) dp[x][i]=-1e9;
		dp[x][n+1]=9e8;
		//修改该点权值 
		for (int i=0,j=n+1;i<=n+1;i++){
			int flag=dp[rc][i]-1;
			while (j&&dp[lc][j-1]<flag) j--;
			dp[x][i+j+1]=max(dp[x][i+j+1],flag);
		}
		//不修改该点权值 
		int l=n+1,r=n+1;
		while (l&&dp[lc][l-1]<a[x]) l--;
		while (r&&dp[rc][r-1]>a[x]) r--;
		dp[x][l+r]=max(dp[x][l+r],a[x]);
	}
	else{
		for (int i=0;i<=n;i++) dp[x][i]=1e9;
		dp[x][n+1]=-9e8;
		//修改该点权值 
		for (int i=0,j=n+1;i<=n+1;i++){
			int flag=dp[lc][i]+1;
			while (j&&dp[rc][j-1]>flag) j--;
			dp[x][i+j+1]=min(dp[x][i+j+1],flag);
		}
		//不修改该点权值 
		int l=n+1,r=n+1;
		while (l&&dp[lc][l-1]<a[x]) l--;
		while (r&&dp[rc][r-1]>a[x]) r--;
		dp[x][l+r]=min(dp[x][l+r],a[x]);
	}
}
int main()
{
	freopen("crazy_binary.in","r",stdin);
	freopen("crazy_binary.out","w",stdout);
	scanf("%d",&n);top=n;
	for (int i=1;i<=n;i++) scanf("%d",&a[i]);
	for (int i=2;i<=n;i++){
		int fa,ch;
		scanf("%d%d",&fa,&ch);
		son[fa][ch]=i;
	}
	solve(1,0);
	for (int i=0;i<=n;i++)
		if (dp[1][i]<=9e8) printf("%d\n",i),exit(0);
	return 0;
}