分析
考试的时候sb了......我们发现可以按照先序遍历将一棵树变成一个序列，而不需要删的数的数量便是最长上升子序列的长度，但是还有一个问题就是如果在5和7之间有3个空的位置就无法填入合法的数，但是按照此方法会将5和7划归为合法的。所以我们考虑将第i个数的权值变为原来的权值减去i，然后求一个最长不降子序列就行了。但是由于求解是n^2的，所以我们考虑用线段树来进行优化。我们建立一棵权值线段树，按顺序将其权值的位置变为其dp值，然后对于每次更新即为目前线段树中的权值不大于i的点的dp值的最大值。最终答案即为n减去这个最长不下降子序列的长度。
代码
#include<bits/stdc++.h>
using namespace std;
int n,a[100100],b[100100],son[100100][2],d[400100],cnt,dp[100100],sum;
map<int,int>id;
inline void dfs(int x){
if(son[x][0])dfs(son[x][0]);cnt++;a[cnt]=d[x]-cnt;
if(son[x][1])dfs(son[x][1]);return;
}
inline void build(int le,int ri,int wh,int pl,int sum){
d[wh]=max(d[wh],sum);if(le==ri)return;int mid=(le+ri)>>1;
if(mid>=pl)build(le,mid,wh<<1,pl,sum);
else build(mid+1,ri,wh<<1|1,pl,sum);
}
inline int q(int le,int ri,int x,int y,int wh){
if(le>=x&&ri<=y)return d[wh];int mid=(le+ri)>>1,ans=0;
if(mid>=x)ans=max(ans,q(le,mid,x,y,wh<<1));
if(mid<y)ans=max(ans,q(mid+1,ri,x,y,wh<<1|1));
return ans;
}
int main(){
int i,x,y;scanf("%d",&n);for(i=1;i<=n;i++)scanf("%d",&d[i]);
for(i=2;i<=n;i++)scanf("%d%d",&x,&y),son[x][y]=i;
dfs(1);memset(d,0,sizeof(d));for(i=1;i<=cnt;i++)b[i]=a[i];
sort(b+1,b+cnt+1);for(i=1;i<=n;i++)if(!id[b[i]])id[b[i]]=++sum;
build(1,sum,1,id[a[1]],1);for(i=2;i<=cnt;i++)
x=q(1,sum,1,id[a[i]],1),build(1,sum,1,id[a[i]],x+1);
printf("%d
",n-q(1,sum,1,sum,1));
return 0;
}