题目概述

给出一棵 $n$ 个节点的二叉树，现在可以修改任意个节点的权值（只能改成整数），问至少多少次能把这棵二叉树改成BST。

解题报告

先中序遍历得到序列，然后就是用最少的次数把这个序列改成上升的。

但是只能改成整数，所以需要满足 $a_j-a_i\ge j-i$ ，转化成 $a_j-j\ge a_i-i$ 就行了。

示例程序

#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=100000;

int n,a[maxn+5],son[maxn+5][2],b[maxn+5],tem[maxn+5],c[maxn+5],ans;

inline int Find(int x) {int L=1,R=tem[0],mid;while (L<=R) tem[mid=L+(R-L>>1)]<=x?L=mid+1:R=mid-1;return R;}
void Dfs(int x) {if (!x) return;Dfs(son[x][0]);b[++b[0]]=a[x];Dfs(son[x][1]);}
inline void Update(int x,int now) {for (int i=x;i<=tem[0];i+=i&-i) c[i]=max(c[i],now);}
inline int Max(int x) {int MAX=0;for (int i=x;i;i-=i&-i) MAX=max(MAX,c[i]);return MAX;}
int main(){
    freopen("program.in","r",stdin);freopen("program.out","w",stdout);
    scanf("%d",&n);for (int i=1;i<=n;i++) scanf("%d",&a[i]);
    for (int i=2,fa,d;i<=n;i++) scanf("%d%d",&fa,&d),son[fa][d]=i;
    Dfs(1);for (int i=1;i<=n;i++) tem[++tem[0]]=(b[i]-=i);
    sort(tem+1,tem+1+tem[0]);tem[0]=unique(tem+1,tem+1+tem[0])-tem-1;
    for (int i=1,now;i<=n;i++) b[i]=Find(b[i]),ans=max(ans,now=Max(b[i])+1),Update(b[i],now);
    return printf("%d\n",n-ans),0;
}