[树剖 + bitset + Hall定理] HHHOJ#301. 「湖南省队集训2018 Day5」party

不难的题。显然汇合点是所有的 \(LCA\)

肯定要先把每个点能拿的东西求出来,直接树剖,线段树里维护区间 \(bitset\) 就好了。

考虑答案怎么求。每个东西不能有多个,容易想到匹配。

考虑每人拿 \(x\) 个是否可行,把一个人拆成 \(x\) 个连边一样的点,向物品连边。

然后就是判断是否有完美匹配了。直接套 \(Hall\) 定理,得到需满足: \[ |V(S)| \ge |S|x \\ x \le (\frac{|V(S)|}{|S|})_{min} \]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
#include<cstdio>
#include<cctype>
#include<cstring>
#include<bitset>
#include<algorithm>
using namespace std;
inline char gc(){
static char buf[100000],*p1=buf,*p2=buf;
return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
inline int getint(){
char ch=gc(); int res=0,ff=1;
while(!isdigit(ch)) ch=='-'?ff=-1:0, ch=gc();
while(isdigit(ch)) res=(res<<1)+(res<<3)+ch-'0', ch=gc();
return res*ff;
}
const int maxn=300005,maxe=maxn;
int fir[maxn],nxt[maxe],son[maxe],tot;
void add(int x,int y){
son[++tot]=y; nxt[tot]=fir[x]; fir[x]=tot;
}
int dep[maxn],sz[maxn],hvy[maxn],pre[maxn],top[maxn],pos[maxn],c[maxn];
void dfs_info(int x){
sz[x]=1;
for(int j=fir[x];j;j=nxt[j]){
dep[son[j]]=dep[x]+1; pre[son[j]]=x; dfs_info(son[j]);
sz[x]+=sz[son[j]]; if(sz[hvy[x]]<sz[son[j]]) hvy[x]=son[j];
}
}
void build_chain(int x,int tp){
c[++c[0]]=x; pos[x]=c[0]; top[x]=tp;
if(hvy[x]) build_chain(hvy[x],tp);
for(int j=fir[x];j;j=nxt[j])
if(son[j]!=hvy[x]) build_chain(son[j],son[j]);
}
int typ[maxn];
typedef bitset<1001> Bitset;
Bitset sta[maxn*2],Zero;
int N_seg,ch[maxn*2][2];
void maintain(int p){
sta[p]=sta[ch[p][0]]|sta[ch[p][1]];
}
int Build(int L,int R){
int p=++N_seg;
if(L==R) return sta[p].set(typ[c[L]]), p;
int mid=(L+R)>>1;
ch[p][0]=Build(L,mid); ch[p][1]=Build(mid+1,R);
maintain(p); return p;
}
Bitset Query(int p,int L,int R,int qL,int qR){
if(qR<L||R<qL) return Zero;
if(qL<=L&&R<=qR) return sta[p];
int mid=(L+R)>>1;
return Query(ch[p][0],L,mid,qL,qR)|Query(ch[p][1],mid+1,R,qL,qR);
}
int LCA(int x,int y){
while(top[x]!=top[y]){
if(dep[top[x]]<dep[top[y]]) swap(x,y);
x=pre[top[x]];
}
return dep[x]>dep[y]?y:x;
}
int n,m,Q,a[10],ans;
Bitset v[10];
void Query(int k,int x,int y){
v[k].reset();
while(top[x]!=top[y]){
v[k]|=Query(1,1,n,pos[top[x]],pos[x]);
x=pre[top[x]];
}
v[k]|=Query(1,1,n,pos[y],pos[x]);
}
void dfs(int stp,int cnt,Bitset now){
if(stp>a[0]){
if(cnt) ans=min(ans,(int)now.count()/cnt);
return;
}
dfs(stp+1,cnt,now);
dfs(stp+1,cnt+1,now|v[stp]);
}
int main(){
n=getint(); m=getint(); Q=getint();
for(int i=2;i<=n;i++){
int x=getint(); add(x,i);
}
for(int i=1;i<=n;i++) typ[i]=getint();
dfs_info(1); build_chain(1,1);
Build(1,n);
while(Q--){
a[0]=getint();
for(int i=1;i<=a[0];i++) a[i]=getint();
int lca=a[1]; for(int i=2;i<=a[0];i++) lca=LCA(lca,a[i]);
for(int i=1;i<=a[0];i++) Query(i,a[i],lca);
ans=1e9; dfs(1,0,Zero);
printf("%d\n",ans*a[0]);
}
return 0;
}