record

Code:

#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;

#define N 100005
#define int long long

int n;
int a[N];
int b[N],idx;
int lson[N],rson[N];
int dp[N];

void init(int u)
{
	if(u==0)
		return;
	init(lson[u]);
	++idx;
	b[idx]=a[u]-idx;
	// printf("b[%lld]=(a[%lld]=%lld)-%lld=%lld\n",idx,u,a[u],idx,b[idx]);
	init(rson[u]);
}

signed main()
{
	// freopen("binary.in","r",stdin);
	// freopen("binary.out","w",stdout);
	scanf("%lld",&n);
	for(int i=1;i<=n;++i)
		scanf("%lld",&a[i]);
	for(int i=2;i<=n;++i)
	{
		int fa,t;
		scanf("%lld%lld",&fa,&t);
		if(t)
			rson[fa]=i;
		else lson[fa]=i;
	}
	init(1);
	// printf("[%lld]",n);
	for(int i=1;i<=n;++i)
		printf("%lld ",b[i]);
	putchar('\n');
	int ans=1;
	dp[1]=b[1];
	for(int i=2;i<=n;++i)
	{
		int t=upper_bound(dp+1,dp+ans+1,b[i])-dp;
		dp[t]=b[i];
		ans=max(ans,t);
	}
	printf("%lld",n-ans);
	return 0;
}