【JZOJ3894】改造二叉树【树】【LIS】

题目大意：

题目链接：https://jzoj.net/senior/#main/show/3894
给出一棵二叉树，求这棵二叉树需要修改多少个值（且保证均为整数）才能变成一棵二叉搜索树？
二叉搜索树指的是对于任意一个结点，有左儿子$<$根节点$<$右儿子。

---

思路：

由于有左儿子$<$根节点$<$右儿子，所以就先在树上跑一遍中序便利，将每一个子节点的值储存到一个数组$s$中。
此时我们就希望满足$s_i<s_{i+1}$。那么明显的，有最少修改个数=总个数-最大保留个数。
所以就跑一遍$LIS$就可以了。但是为了保证一定是整数，所以要先将$s_i-i$，然后用$upper\_bound$即可。

时间复杂度：$O(n logn)$。

---

代码：

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

const int N=100010;
int n,x,y,tot,maxn,a[N],f[N],s[N],lson[N],rson[N],q[N],tail;

void dfs(int x)  //求中序遍历
{
	if (lson[x]) dfs(lson[x]);
	s[++tot]=a[x];
	if (rson[x]) dfs(rson[x]);
}

int main()
{
	scanf("%d",&n);
	for (int i=1;i<=n;i++)
		scanf("%d",&a[i]);
	for (int i=2;i<=n;i++)
	{
		scanf("%d%d",&x,&y);
		if (y) rson[x]=i;
			else lson[x]=i;
	}
	dfs(1);
	q[0]=-1e9;
	for (int i=1;i<=n;i++)  //二分求LIS
	{
		s[i]-=i;
		if (q[tail]<=s[i]) q[++tail]=s[i];
			else q[upper_bound(q+1,q+tail+1,s[i])-q]=s[i];
	}
	printf("%d
",n-tail);
	return 0;
}