C. 洗
小S有一个$n$个节点的二叉树。每个节点上有一个权值。节点从$1$开始编号。
现在，小S打算把这个二叉树改造成一个二叉排序树。二叉排序树的定义是，对于每个节点，它的权值比它左儿子的权值要大，但是比右儿子要小。
现在，他想要修改某些节点的权值，使得它成为一个二叉排序树。请问最小的修改次数是多少。
输入格式
第一行一个整数$n$。
接下来一行$n$个数，第$i$个表示$i$号节点的权值。
接下来 $n - 1$行，每行两个非负整数f, x，第$i$行描述结点$i + 1$的父亲编号$f$，以及父子关系$x$，($x = 0$ 表示$i + 1$为左儿子，$x = 1$表示$i + 1$为右儿子)。
保证一号点一定是全树的根。
输出格式
一行一个整数，表示最小修改次数。
样例
样例一
input
3
2 2 2
1 0
1 1
output
2
约定与限制
对于$20\%$ 的数据，满足 $ n \le 10,a_i\le 100$。
对于$40\%$ 的数据，满足 $n \le 100,a_i\le 200$。
对于$60\%$ 的数据，满足 $n\le 2000$。
对于$100\%$ 的数据 ，满足 $1 \le n \le 10^5,a_i< 2^{31}$ 。
时间限制:1s
空间限制:512MB
解题报告
$100pts$思路
这道题目，题目给我们一个关键信息，就是要把二叉树变成合法的二叉排序树。
二叉排序树，具有的性质，就是中序遍历后的序列，具有严格单调递增的性质。
既然如此，我们为什么不把这题的结构，通过DFS，进行中序遍历，从树结构变成线性结构。
此时，我们的题面，改成了，在一个长度为$n$的序列，修改尽量少的点的值，使得整个序列严格单调递增。
那么此时，我们来观察一组数据.
1 4 2 5 7
我们发现，在这里.
1,5,7
并不需要动，而
4 2
应该改成
2 3
使得最终序列为
1 2 3 5 7
那么根据上面的例子，我们发现了什么。
我们在这个序列里面，需要修改的数总数，就是序列长度减去不满足不下降子序列的数。
而这里，我们的不下降子序列的定义，却有所不同。
原序列有两个点，分别为$i,j$,且此时满足$i < j$
那么如果说，这两个点要在不下降子序列中，必须满足
$$ s[j]-s[i] \ge j-i $$
否则这两个数，中间无法放置其他数。（若$i,j$紧靠，满足上面性质）
无法构造成为合法序列。
然后我们把不等式可以转换为：
$$ s[j]-j \ge s[i]-i $$
因此所谓的不下降子序列，其实就是指的是，不用修改值的数列，因为他们已经满足了单调性质，改了没有任何用处。
而其他不满足的，都可以通过自身修改，使得整个序列最终成为严格单调递增的序列。
代码解析
#include <bits/stdc++.h>
using namespace std;
const int N=1e5+20;
int n,a[N],f[N],cnt,ans,s[N],t[N][2];
inline void dfs(int x)//中序遍历
{
if (t[x][0])//先遍历左儿子
dfs(t[x][0]);
s[++cnt]=a[x];//中序遍历，计算DFS序
if (t[x][1])//最后遍历右儿子
dfs(t[x][1]);
}
inline void init()
{
scanf("%d",&n);
for(int i=1; i<=n; i++)
scanf("%d",&a[i]);
for(int i=2; i<=n; i++)
{
int f,x;
scanf("%d%d",&f,&x);
if (x==1)//右儿子最后遍历
t[f][1]=i;
else//左儿子最先遍历
t[f][0]=i;
}
}
inline void work()
{
for(int i=1; i<=n; i++)//不等式变形
s[i]-=i;
f[ans=1]=s[1];
for(int i=2; i<=n; i++)//求解不下降子序列
if (s[i]>=f[ans])
f[++ans]=s[i];
else
f[upper_bound(f+1,f+1+ans,s[i])-f]=s[i];
printf("%d\n",n-ans);
}
signed main()
{
init();
dfs(1);
work();
return 0;
}
