[关闭]
@ysner 2018-05-19T16:51:29.000000Z 字数 1301 阅读 2019

改造二叉树

DP


题面

给定一颗带点权的二叉树,询问把它修改成每个点至少需要改几个数。
戳我

解析

此题就是询问一颗树中序遍历的最长不下降子序列。
但注意到每两个数差至少为(否则插不进数)。
有个小技巧是把原数列转化为
Update:标准模板

  1. // luogu-judger-enable-o2
  2. #include<iostream>
  3. #include<cmath>
  4. #include<cstring>
  5. #include<cstdio>
  6. #include<cstdlib>
  7. #include<algorithm>
  8. #define ll long long
  9. #define re register
  10. #define il inline
  11. #define fp(i,a,b) for(re int i=a;i<=b;i++)
  12. #define fq(i,a,b) for(re int i=a;i>=b;i--)
  13. using namespace std;
  14. const int N=1e5+100;
  15. struct node{int w,id;}t[N];
  16. int n,son[2][N],dp[N],top,cnt,lin[N];
  17. il int gi()
  18. {
  19. re int x=0,t=1;
  20. re char ch=getchar();
  21. while((ch<'0'||ch>'9')&&ch!='-') ch=getchar();
  22. if(ch=='-') t=-1,ch=getchar();
  23. while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
  24. return x*t;
  25. }
  26. il void wri(re int x)
  27. {
  28. if(x<0) putchar('-'),x=-x;
  29. if(x>9) wri(x/10);
  30. putchar(x%10+'0');
  31. }
  32. bool cmp(node a,node b){return a.id<b.id;}
  33. il void dfs(re int u)
  34. {
  35. if(son[0][u]) dfs(son[0][u]);
  36. lin[++cnt]=t[u].w-cnt;
  37. if(son[1][u]) dfs(son[1][u]);
  38. }
  39. int main()
  40. {
  41. n=gi();
  42. fp(i,1,n) t[i].w=gi();
  43. fp(i,2,n)
  44. {
  45. re int x=gi(),y=gi();
  46. son[y][x]=i;
  47. }
  48. dfs(1);
  49. fp(i,1,n)
  50. {
  51. if(!top||dp[top]<=lin[i]) dp[++top]=lin[i];
  52. else dp[lower_bound(dp+1,dp+top+1,lin[i])-dp]=lin[i];
  53. }
  54. printf("%d\n",n-top);
  55. fclose(stdin);
  56. fclose(stdout);
  57. return 0;
  58. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注