[关闭]
@ysner 2018-08-07T00:31:35.000000Z 字数 3247 阅读 1937

[bzoj5404]party

线段树 bitset 树链剖分


题面

这题面不好概括啊

解析

算法

既然,打上文件输入输出即可。
当然不开够空间且不特判的小朋友就拿不到了。

算法


所有人在聚会是显然的吧(毕竟每个人只能往上走)。
这怎么乱搞都可以。
可以枚举每个特产被哪个人带,再检查一下是否可行和合法(每个人带的特产数相同)即可。
复杂度似乎是???

算法

,两个人讨论起来比较方便。
先统计出三个信息表示两个人都可取到的特产数,表示第一个人可取到的,表示第二个人可取到的。
显然,若,则
,则
若以上均不满足,则
复杂度

算法

,估计出题人想让我们维护个信息再讨论。。。
如果你能写出来,你会发现复杂度同上。

算法

匹配问题是可以用网络流来解的。
我们可以统计一下每个特产能被哪些人选。
然后???

算法

我考场上一直不会维护链上颜色个数,以为需要树上莫队。。。
实际上,因为颜色数只有,开个并没有什么问题。
于是可以树链剖分+线段树+强行预处理每个人能选到的特产
或者说可以预处理出每条链上前缀和(用重儿子),这样就只用在这一段用线段树查询,复杂度降到

然后我们来考虑怎么来求最大的特产数。
注意到每一个人选择的特产的种数是相同的,若每一个人选种特产,则

(神思路时间)
这相当于每一个人都拆成了个点,然后人和特产之间连边跑完美二分图匹配。
怎么保证完美???
根据霍尔定理,左边的任何一个子集都要满足和右边的相邻的点数大于等于子集大小
右边相邻的点数就是当前状态中包括的人总共能取到的特产数,所以答案很明显就是}了。
指当前状态包含的人数。
复杂度

  1. #include<iostream>
  2. #include<cstdio>
  3. #include<cstdlib>
  4. #include<cstring>
  5. #include<cmath>
  6. #include<algorithm>
  7. #include<vector>
  8. #include<bitset>
  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=5e5+100;
  18. struct Edge{int to,nxt;}e[N<<1];
  19. int n,m,Q,a[N],f[N],d[N],top[N],sz[N],c,son[N],ans,h[N],cnt,q[N],id[N],now[N],tim;
  20. il void add(re int u,re int v){e[++cnt]=(Edge){v,h[u]};h[u]=cnt;}
  21. il ll gi()
  22. {
  23. re ll x=0,t=1;
  24. re char ch=getchar();
  25. while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
  26. if(ch=='-') t=-1,ch=getchar();
  27. while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
  28. return x*t;
  29. }
  30. bitset<1010>dp[50];
  31. bitset<1010>pre[N];
  32. namespace seg_T
  33. {
  34. #define ls (x<<1)
  35. #define rs (x<<1|1)
  36. #define mid ((l+r)>>1)
  37. bitset<1010>w[N<<2];
  38. il void Build(re int x,re int l,re int r)
  39. {
  40. if(l==r) {w[x][a[q[l]]]=1;return;}
  41. Build(ls,l,mid);Build(rs,mid+1,r);
  42. w[x]=w[ls]|w[rs];
  43. }
  44. il void Query(re int x,re int l,re int r,re int ql,re int qr,bitset<1010>* res)
  45. {
  46. if(ql<=l&&r<=qr) {*res|=w[x];return;}
  47. if(ql<=mid) Query(ls,l,mid,ql,qr,res);
  48. if(qr>mid) Query(rs,mid+1,r,ql,qr,res);
  49. }
  50. }
  51. il void dfs1(re int u,re int fa)
  52. {
  53. f[u]=fa;d[u]=d[fa]+1;sz[u]=1;pre[u][a[u]]=1;
  54. for(re int i=h[u];i+1;i=e[i].nxt)
  55. {
  56. re int v=e[i].to;
  57. if(v==fa) continue;
  58. dfs1(v,u);
  59. sz[u]+=sz[v];
  60. if(sz[son[u]]<sz[v]) son[u]=v;
  61. }
  62. }
  63. il void dfs2(re int u,re int up)
  64. {
  65. q[id[u]=++tim]=u;
  66. top[u]=up;
  67. if(son[u])
  68. {
  69. pre[son[u]]|=pre[u];
  70. dfs2(son[u],up);
  71. }
  72. for(re int i=h[u];i+1;i=e[i].nxt)
  73. {
  74. re int v=e[i].to;
  75. if(v==f[u]||v==son[u]) continue;
  76. dfs2(v,v);
  77. }
  78. }
  79. il int LCA(re int u,re int v)
  80. {
  81. while(top[u]^top[v])
  82. {
  83. if(d[top[u]]<d[top[v]]) swap(u,v);
  84. u=f[top[u]];
  85. }
  86. return d[u]<d[v]?u:v;
  87. }
  88. il void calc(bitset<1010>* res,re int u,re int v)
  89. {
  90. while(top[u]^top[v])
  91. {
  92. *res|=pre[u];
  93. u=f[top[u]];
  94. }
  95. seg_T::Query(1,1,n,id[v],id[u],res);
  96. }
  97. int main()
  98. {
  99. freopen("party.in","r",stdin);
  100. freopen("party.out","w",stdout);
  101. memset(h,-1,sizeof(h));
  102. n=gi();m=gi();Q=gi();
  103. fp(i,2,n)
  104. {
  105. re int u=i,v=gi();
  106. add(v,u);
  107. }
  108. fp(i,1,n) a[i]=gi();
  109. dfs1(1,0);dfs2(1,1);
  110. seg_T::Build(1,1,n);
  111. while(Q--)
  112. {
  113. c=gi();
  114. fp(i,0,c-1) now[i]=gi();
  115. re int lca=now[0];
  116. fp(i,1,c-1) lca=LCA(lca,now[i]);
  117. fp(i,0,c-1)
  118. {
  119. dp[(1<<i)].reset();
  120. calc(&dp[(1<<i)],now[i],lca);
  121. }
  122. ans=m/c;
  123. fp(i,1,(1<<c)-1)
  124. {
  125. re int x=i,t=0;
  126. while(x) {x-=x&-x;++t;}
  127. if(t^1)
  128. {
  129. re int tt=(i-1)&i;
  130. dp[i]=dp[tt]|dp[i^tt];
  131. }
  132. ans=min(ans,(int)dp[i].count()/t);
  133. }
  134. printf("%d\n",ans*c);
  135. }
  136. fclose(stdin);
  137. fclose(stdout);
  138. return 0;
  139. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注