分析

考试的时候sb了......我们发现可以按照先序遍历将一棵树变成一个序列，而不需要删的数的数量便是最长上升子序列的长度，但是还有一个问题就是如果在5和7之间有3个空的位置就无法填入合法的数，但是按照此方法会将5和7划归为合法的。所以我们考虑将第i个数的权值变为原来的权值减去i，然后求一个最长不降子序列就行了。但是由于求解是n^2的，所以我们考虑用线段树来进行优化。我们建立一棵权值线段树，按顺序将其权值的位置变为其dp值，然后对于每次更新即为目前线段树中的权值不大于i的点的dp值的最大值。最终答案即为n减去这个最长不下降子序列的长度。

代码

#include
     
      using namespace std;int n,a[100100],b[100100],son[100100][2],d[400100],cnt,dp[100100],sum;map
      
       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
       
        <<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",n-q(1,sum,1,sum,1));      return 0;}