「Luogu P3365」改造二叉树 解题报告

题面

前言

在打模拟赛的时候好像$sha$了一样想不出来，（肯定是我太菜了

解题思路

题目中描述的是一棵二叉搜索树，但是实际上题目不要求改变树的形态，所以我们就把树形结构转化为线性结构，这应该是一个比较有用的小$tip$吧

转化为线性的数组之后，就变成了这样的问题：

求 使数组 严格上升 最少 要改变的元素个数

一开始想不出来，那就可以先打打暴力找灵感

for(i=1;i<=n;++i) {//DP，f数组表示在保留i这个元素的情况下，
    for(j=i-1;j>=0;--j)//最多可以保留多少元素
        if(b[i]-b[j]>=i-j)
            f[i]=max(f[i],f[j]+1);
    ans=max(f[i],ans);
}

其实还是有点像$LIS$的感觉的

那从哪里入手呢？

$b[i]-b[j]>=i-j$

好像这个式子可以移项啊

然后就变成

$b[i]-i>=b[j]-j$！！

这下真的可以用最长不下降子序列那套东西了

将$O(n^2)$优化成$O(nlogn)$ 就是这么优秀

Code

献上极短丑陋的代码

#include<bits/stdc++.h>
#define getchar() *(p++)
#define INF 0x7f7f7f7f
#define rgt register
#define N 100007//有巨佬说这里开奇数的数组能快一点
using namespace std;
int son[N][2],n,t,a[N],b[N];
char bf[1<<23],*p;
inline int read() {//快读不管
    rgt int s=0;
    rgt char c=getchar();
    while(!isdigit(c)) c=getchar();
    while(isdigit(c)) s=(s<<1)+(s<<3)+c-'0',c=getchar();
    return s;
}
inline void built(rgt int x) {
    if(son[x][0]) built(son[x][0]);a[++t]=b[x];
    if(son[x][1]) built(son[x][1]);
}
int main()
{
    int i;
    bf[fread(bf,1,1<<23,stdin)]='\0',p=bf;//快读一部分不管
    n=read();
    for(i=1;i<=n;i++) b[i]=read();//读入每个原宿
    for(i=2;i<=n;i++) son[read()][read()]=i;//偷懒读入边
    built(1),b[t=0]=-INF;//因为b[i]-i之后可能为负数，保险就赋一个极小值
    for(i=1;i<=n;++i) {
        a[i]-=i;//处理一下
        if(b[t]<=a[i]) b[++t]=a[i];//最长不下降子序列板子
        else *upper_bound(b+1,b+t+1,a[i])=a[i];//直接指针
    }
    printf("%d",n-t);
    return 0;
}