题意

求使一个二叉树通过修改点权的方式成为二叉搜索（排序）树的最少修改次数。

二叉搜索树指对于任意节点 \(u\) 以及其左右儿子 \(v_1,v_2\)，满足 \(val(v_1)。

对平衡树有一定了解的话，就知道平衡树实际是在维护一个中序遍历不变的，深度接近 \(\log n\) 的二叉搜索树。

分析

因此，本题要求的是，一个数列 \(A\) (指这棵二叉树的中序遍历），修改成一个单调上升序列的最少次数。

显然直接求 \(\operatorname{LIS}\) 再进行一系列操作时错误的，例如 \(A=\{3,5,4\}\) 时，显然不能只修改 \(5\)。抽象的讲，就是映射成的 \(A\) 数列的每个区间不保证值域大于等于定义域。

设 \(f_i\) 表示前 \(i\) 位无需改变的数量，发现当且仅当 $ val_i-val_j\ge i-j$ 时，\(f_i\) 可以由 \(f_j\) 转移。

把这个条件移项，就有 \(val_i-i\ge val_j-j\)，于是处理出一个数组表示 \(val_i-i\)，因为转移次数等于最后的结果，所以要这个转移次数最大，也就是这个数组的最长不降子序列，当然不要忘了结果用 \(n\) 减去。

实现

这里不能用朴素的求 \(\operatorname{LIS}\)，需要带二分的 \(O(n\log n)\) 算法（用 \(\operatorname{STL}\) 中自带的查找也可）。

int n,len;
int val[maxn],a[maxn],tot;
int tr[maxn][2];
inline void dfs(int u){
	if(tr[u][0]) dfs(tr[u][0]);
	a[++tot]=val[u];
	if(tr[u][1]) dfs(tr[u][1]);
}
int f[maxn],g[maxn];
inline int get(int x){
	int l=1,r=len;
	int res=0;
	while(l<=r){
		int mid=(l+r)>>1;
		if(g[mid]<=x){
			res=mid;
			l=mid+1;
		}
		else{
			r=mid-1;
		}
	}
	return res;
}
int main(){
	n=read();
	for(int i=1;i<=n;i++){
		val[i]=read();
	}
	for(int i=2;i<=n;i++){
		int fa=read(),ch=read();
		tr[fa][ch]=i;
	}
	dfs(1);
	for(int i=1;i<=n;i++){
		a[i]-=i;
	}
	for(int i=1;i<=n;i++){
		f[i]=get(a[i])+1;
		g[f[i]]=a[i];
		len=max(len,f[i]);
	}
	printf("%d\n",n-len);
	return 0;
}