[关闭]
@ysner 2018-08-13T14:46:57.000000Z 字数 1518 阅读 1900

[bzoj4919]大根堆

set STL 启发式合并


题面

给定一棵个节点的有根树,编号依次为,其中号点为根节点。每个点有一个权值
选择尽可能多的节点,使对于任意两个点,如果在树上是的祖先,那么
请计算可选的最多的点数,注意这些点不必形成这棵树的一个连通子树。

解析

这题无非想让选出的这些点自下往上都能构成最长上升子序列
于是自下往上每条链都维护一下最长上升子序列。
如果两链相交,把两条序列直接合并(因不影响答案)。
然后尝试把交点()加入序列即可。

关键是怎么维护这东西。
线段树合并???怒码???
神器拯救一切。
而且由于合并时两链(树)互不影响,可以启发式合并。(如果父亲已有序列长度小于儿子,可以父子完全交换)。
复杂度

  1. #include<iostream>
  2. #include<cstdio>
  3. #include<cstdlib>
  4. #include<cstring>
  5. #include<cmath>
  6. #include<algorithm>
  7. #include<vector>
  8. #include<set>
  9. #define re register
  10. #define il inline
  11. #define ll long long
  12. #define max(a,b) ((a)>(b)?(a):(b))
  13. #define min(a,b) ((a)<(b)?(a):(b))
  14. #define fp(i,a,b) for(re int i=a;i<=b;i++)
  15. #define fq(i,a,b) for(re int i=a;i>=b;i--)
  16. using namespace std;
  17. const int mod=1e9+7,N=2e5+100,M=3000;
  18. struct Edge{int to,nxt;}e[N<<1];
  19. int n,h[N],cnt,w[N];
  20. multiset<int>f[N];
  21. il void add(re int u,re int v)
  22. {
  23. e[++cnt]=(Edge){v,h[u]};h[u]=cnt;
  24. e[++cnt]=(Edge){u,h[v]};h[v]=cnt;
  25. }
  26. il ll gi()
  27. {
  28. re ll x=0,t=1;
  29. re char ch=getchar();
  30. while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
  31. if(ch=='-') t=-1,ch=getchar();
  32. while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
  33. return x*t;
  34. }
  35. il void dfs(re int u,re int fa)
  36. {
  37. for(re int i=h[u];i+1;i=e[i].nxt)
  38. {
  39. re int v=e[i].to;
  40. if(v==fa) continue;
  41. dfs(v,u);
  42. if(f[v].size()>f[u].size()) swap(f[v],f[u]);
  43. for(set<int>::iterator j=f[v].begin();j!=f[v].end();j++)
  44. f[u].insert(*j);
  45. f[v].clear();
  46. }
  47. if(f[u].size()>0&&f[u].lower_bound(w[u])!=f[u].end()) f[u].erase(f[u].lower_bound(w[u]));
  48. f[u].insert(w[u]);
  49. }
  50. int main()
  51. {
  52. memset(h,-1,sizeof(h));
  53. n=gi();
  54. fp(i,1,n) w[i]=gi(),add(i,gi());
  55. dfs(1,0);
  56. printf("%lld\n",1ll*f[1].size());
  57. return 0;
  58. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注