自动搬运

查看原文

来自洛谷，原作者为

	asuldb 哭晕了喵

搬运于2025-08-24 21:48:10，当前版本为作者最后更新于2018-10-24 14:43:24，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

非常妙的一道题

首先如果看到这是一棵树就往树形$dp$上想那肯定就想不出来了

注意这是一棵二叉搜索树，所以有一些非常奇妙的性质

熟悉平衡树的人应该知道，二叉搜索树的中根遍历是严格上升的

所以我们将中根遍历求出来就好了

现在的问题变成最少修改一个序列上的一些数，使得其严格上升

首先直接求出$LIS$的长度再用$n$一减肯定是错的

我们考虑一下反着做

我们设$f_i$表示前$i$个数里最多有多少个不用修改

对于$i$位置上的数$a_i$如果前面有一个位置$j$满足$a_i-a_j>=i-j$的话，我们就可以把$(i,j)$上的数全部修改而且能使得其严格递增

于是就有这样一个方程

$f_i=max(f_j+1)[a_i-a_j>=i-j]$

也就是$a_i-i>=a_j-j$

那就是所有的数减掉下标之后求一个最长不下降子序列啊，最后拿$n$减去这个长度就好了

$O(nlogn)$就可以求出了

代码

#include<iostream>
#include<cstring>
#include<cstdio>
#define re register
#define maxn 100005
#define max(a,b) ((a)>(b)?(a):(b))
inline int read()
{
    char c=getchar();
    int x=0;
    while(c<'0'||c>'9') c=getchar();
    while(c>='0'&&c<='9')
        x=(x<<3)+(x<<1)+c-48,c=getchar();
    return x;
}
int ch[maxn][2],a[maxn],n,now,key[maxn];
void dfs(int x)
{
    if(ch[x][0]) dfs(ch[x][0]);
    a[++now]=key[x];
    if(ch[x][1]) dfs(ch[x][1]);
}
int f[maxn],d[maxn],len;
inline int find(int x)
{
    int l=1,r=len,ans=0;
    while(l<=r)
    {
        int mid=l+r>>1;
        if(d[mid]<=x) ans=mid,l=mid+1;
            else r=mid-1;
    }
    return ans;
}
int main()
{
    n=read();
    for(re int i=1;i<=n;i++)
        key[i]=read();
    int x,fa;
    for(re int i=2;i<=n;i++)
        fa=read(),x=read(),ch[fa][x]=i;
    dfs(1);
    for(re int i=1;i<=n;i++)
        a[i]-=i;
    for(re int i=1;i<=n;i++)
    {
        f[i]=find(a[i])+1;
        d[f[i]]=a[i];
        len=max(len,f[i]);
    }
    printf("%d\n",n-len);
    return 0;
}