题意
给定一颗二叉树，每次操作可以修改一个点的权值为任意整数，求将原树变为二叉搜索树的最小操作次数。
注意：本题中的二叉搜索树定义为：每个左边儿子的权值都严格小于中间儿子,每个右边儿子的权值都严格大于中间儿子。
\(1 \leq n \leq 10^5\)。
思路：
在本题中，一棵二叉树为二叉搜索树的充要条件为：该二叉树的中序遍历权值严格单调递增。
先求出这棵树的中序遍历。由于点的权值只能修改为整数，直接求 $\mathrm{LIS} $ 无法解决有连续若干个相同整数的情况。
设中序遍历的第 \(i\) 个点权值为 \(w_i\)。令 \(w_i \longleftarrow w_i-i\)，那么就可以将严格单调递增转化为非严格单调递增，于是最终的答案就是 \(n-\mathrm{LIS} (a)\)。
code：
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=1e5+10;
int a[N],ch[N][2],q[N],tot,n,f[N],len;
void dfs(int u)
{
if(!u) return ;dfs(ch[u][0]);tot++;q[tot]=a[u]-tot;dfs(ch[u][1]);
}
int main()
{
scanf("%d",&n);for(int i=1;i<=n;i++) scanf("%d",&a[i]);
for(int i=2;i<=n;i++)
{
int fa,op;scanf("%d%d",&fa,&op);ch[fa][op]=i;
}
dfs(1);
for(int i=1;i<=n;i++)
{
if(q[i]>f[len]) f[++len]=q[i];
else
{
int k=upper_bound(f+1,f+len+1,q[i])-f;
f[k]=q[i];
}
}
printf("%d\n",n-len);
return 0;
}