正题

---

题目大意

一棵二叉树，有点权。求修改最少的点使得这是一个$BST$。

---

解题思路

二叉查找树满足点权的中序单调递增。

所以跑一遍中序遍历，就变为了求修改多少遍使一个序列单调递增。

求最长上升就好了。可是要求修改的是整数，所以需要将条件改为$a_i-a_j\ge i-j$

然而$O(n^2)$过不了，我们先将上面那个式子移项为$a_i-i\ge a_j-j$

所以先让$a_i-i$，然后跑一遍$O(nlogn)$的$LIS$就好了。

---

$code$

#include<cstdio> #include<algorithm> #define N 500010 using namespace std; int n,w[N],son[N][2],a[N],f[N],cnt,tail,q[N]; void dfs(int x){if(son[x][0])dfs(son[x][0]);a[++cnt]=w[x];if(son[x][1])dfs(son[x][1]); } int find(int x) {int l=1,r=tail;while(l<=r){int mid=(l+r)/2;if(x>=q[mid]) l=mid+1;else r=mid-1;}return l; } int main() {scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%d",&w[i]);}for(int i=2;i<=n;i++){int fa,ch;scanf("%d%d",&fa,&ch);son[fa][ch]=i;}dfs(1);for(int i=1;i<=n;i++)a[i]=a[i]-i;for(int i=1;i<=n;i++){if(a[i]>=q[tail])q[++tail]=a[i];else q[find(a[i])]=a[i];}printf("%d",n-tail); }

总结

以上是生活随笔为你收集整理的P3365,jzoj3894-改造二叉树【LIS,BST】的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。