party[bzoj5404]

发表于 分类于

题面

bzoj5404

题解

分析数据范围

首先一看 $c$ 比较小，再看颜色数也只有 $1000$，这些十分有用，以后必定会用到。

分析题意

为了尽快到齐，那就一定会到达这 $c$ 的人的 $LCA$ 处。

这时我们需要求出每个人到达 $LCA$ 的特产有哪些。

考虑第1步做法

我们并不关心这些特产的出现次数，只关心有没有出现就可以了。

那就是状态压缩，每一位表示有没有，然后or起来就可以了。

这个东东可以用 bitset 搞一搞，一次的时间是 $O(\frac{m}{w})$，其中 $w$ 为 $64$，大概是在 $15$ 左右。

那么如何求出一个点到它某个祖先的出现颜色的集合呢？

维护树上前缀和？显然不行，这个or操作不支持删除。

那么只能暴力树剖了，然后上线段树，时间复杂度 $O(q\frac{m}{w}\log^2n)$，不太行。

这时需要一个技巧：我们可以维护每个点到其重链顶端的路径的集合。

那么就只需要一直跳重链，跳到最后和 $LCA$ 同重链的时候再用线段树就可以了。

这样就可以省掉一个 $log$ 的时间。

考虑第2步做法

求出了上面那个东西，接下考虑如何通过这 $c$ 个集合求得答案。

这个答案是满足单调性的，试试二分？

考虑一个人选 $k$ 种颜色是否可行。

无法很快地判断出来，先试试暴力（假设只有一个询问）？

建一个二分图，$X$ 集合中 $ck$ 个点，每个人有 $k$ 个点；$Y$ 集合有 $m$ 个点，代表每种颜色。

若第 $i$ 个人的集合中出现了颜色 $j$ ，则 $i$ 的 $k$ 个点都连一条边到 $j$。

转换成判断是否存在完美匹配。

根据Hall定理，每个 $X$ 集合的子集连出去的点的集合大小必须大于等于该子集的大小。

只要一个人中的某个点出现在该子集中，那么这个人的所有点都要出现该子集中。

所以有 $2^c-1$ 种情况需要考虑。

那么就对于所有的 $S\subseteq X$ 有 $|S|k\leq |N_g(S)|$，也就是 $k\leq \min(\frac{|N_G(S)|}{|S|})$

那么二分的步骤都省略了，答案即为 $\min(\frac{|N_G(S)|}{|S|})$。

复杂度

记 $t=\frac{m}{w}$，则时间复杂度 $O(nt\log n+qt(c\log n+2^c))$

代码

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
#define N 300010
#define M 1004
int n,m,a[N];
namespace SGT{
	bitset<M> f[N<<2];
	#define lc (u<<1)
	#define rc (u<<1|1)
	#define ls lc,l,mid
	#define rs rc,mid+1,r
	void add(int x,int p,int u=1,int l=1,int r=n)
	{
		if(l==r) return (void)(f[u][p]=1);
		int mid=l+r>>1;
		if(x<=mid) add(x,p,ls);
		else add(x,p,rs);
		f[u]=f[lc]|f[rc];
	}
	void ask(int u,int l,int r,int L,int R,bitset<M>* A)
	{
		if(L<=l&&r<=R) return (void)((*A)|=f[u]);
		int mid=l+r>>1;
		if(L<=mid) ask(ls,L,R,A);
		if(mid<R)  ask(rs,L,R,A);
	}
}
namespace Tree{
	vector<int> adj[N];
	bitset<M> f[N];
	int siz[N],son[N],fa[N],dep[N],top[N],dfn[N],tim;
	inline void add(int x,int y){adj[x].pb(y);}
	void dfs1(int u,int pre)
	{
		siz[u]=1; fa[u]=pre; dep[u]=dep[pre]+1;
		fo(i,0,adj[u].size()-1)
		{
			int v=adj[u][i];
			dfs1(v,u);
			siz[u]+=siz[v];
			if(siz[son[u]]<siz[v]) son[u]=v;
		}
	}
	void dfs2(int u,int tp)
	{
		f[u][a[u]]=1;
		dfn[u]=++tim;
		SGT::add(dfn[u],a[u]);
		top[u]=tp;
		int v=son[u];
		if(v) f[v]=f[u],dfs2(v,tp);
		fo(i,0,adj[u].size()-1)
			if(!top[v=adj[u][i]])
				f[v].reset(),dfs2(v,v);
	}
	inline int lca(int x,int y)
	{
		for(;top[x]!=top[y];x=fa[top[x]])
			if(dep[top[x]]<dep[top[y]]) swap(x,y);
		return dep[x]>=dep[y]?y:x;
	}
	inline void get(int u,int z,bitset<M>* A)
	{
		for(;top[z]!=top[u];u=fa[top[u]]) *A|=f[u];
		SGT::ask(1,1,n,dfn[z],dfn[u],A);
	}
}
int q,c,cnt,ans,p[10];
bitset<M> dp[34];
int main()
{
	n=read(); m=read(); q=read();
	fo(i,2,n) Tree::add(read(),i);
	fo(i,1,n) a[i]=read();
	Tree::dfs1(1,0);
	Tree::dfs2(1,1);
	fo(_,1,q)
	{
		c=read(); cnt=1<<c;
		fo(i,0,c-1) p[i]=read();
		int LCA=p[0];
		fo(i,1,c-1) LCA=Tree::lca(LCA,p[i]);
		fo(i,0,cnt-1) dp[i].reset();
		fo(i,0,c-1) Tree::get(p[i],LCA,&dp[1<<i]);
		ans=1e9;
		fo(s,1,cnt-1)
		{
			int tmp=lowbit(s),k=0;
			if(tmp!=s) dp[s]=dp[s^tmp]|dp[tmp];
			fo(i,0,c-1) if(s&(1<<i)) k++;
			ans=min(ans,(int)dp[s].count()/k);
		}
		printf("%d\n",ans*c);
	}
	return 0;
}