题解 P3365 【改造二叉树】
asuldb
·
·
题解
非常妙的一道题
首先如果看到这是一棵树就往树形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减去这个长度就好了
代码
```cpp
#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;
}
```