【lis】洛谷P3365 改造二叉树

题面在这里

​

因为要满足\(a_i-a_j\ge i-j\)即\(a_i-i\ge a_j-j\)

那么对\(\{ a_i-i \}\)这个序列做最长不降子序列就好了

​

示例程序：

#include<cstdio>
#include<cstring>
#include<algorithm>
#define cl(x,y) memset(x,y,sizeof(x))
using namespace std;

const int maxn=100005,maxe=maxn;
int n,m,w[maxn],a[maxn],lnk[maxn][2],g[maxn];
void dfs(int x){
	if (lnk[x][0]) dfs(lnk[x][0]);
	a[++m]=w[x];
	if (lnk[x][1]) dfs(lnk[x][1]);
}
int main(){
	scanf("%d",&n);
	for (int i=1;i<=n;i++) scanf("%d",&w[i]);
	for (int i=2,fa,s;i<=n;i++) scanf("%d%d",&fa,&s),lnk[fa][s]=i;
	dfs(1); for (int i=1;i<=n;i++) a[i]-=i;
	int len=1;g[1]=a[1];
	for (int i=2;i<=n;i++)
	 if (g[len]<=a[i]) g[++len]=a[i];else *upper_bound(g+1,g+1+len,a[i])=a[i];
	printf("%d",n-len);
	return 0;
}