题目概述

有 $n$ 个点的有根树，每个节点只能往上走，且每个节点有一个特产。现在有 $q$ 个询问，每次询问 $c$ 个点，求这些点走到他们的公共祖先，在满足：1.每个人带的特产数量相等。2.没有特产重复出现。的情况下能带的最多的特产数量。

解题报告

首先我们可以利用bitset+树链剖分+线段树得出一条线段上的特产集合，我们要做的是分配特产使得每个人带的特产尽量多（因为每个人必须带相同数量）。

由于是分配问题，我们可以考虑网络流或二分图匹配，假如答案为 $x$ ，那么可以将每个人拆为 $x$ 个点，一个人可以向特产集合中的特产连边，根据霍尔定理，设 $A(S)$ 表示 $S$ 这些人连出去的特产集合，那么 $|A(S)|\ge|S|x$ 。因此 $x=min\{\lfloor{|A(S)|\over |S|}\rfloor\}$ ，答案为 $cx$ 。

示例程序

#include<cstdio>
#include<cctype>
#include<bitset>
#include<algorithm>
using namespace std;
const int maxn=300000,maxm=1000,maxk=5,Log=19;

int n,m,te,dep[maxn+5],si[maxn+5],ST[maxn+5][Log+5],a[maxn+5];
int E,lnk[maxn+5],son[maxn+5],nxt[maxn+5],SH[maxn+5],top[maxn+5],Lt[maxn+5],who[maxn+5];
int cnt[1<<maxk],H[1<<maxk];bitset<maxm> pre[maxn+5],s[(maxn<<2)+5],now,t[maxk+5],S[1<<maxk];

#define Eoln(x) ((x)==10||(x)==13||(x)==EOF)
inline char readc(){
    static char buf[100000],*l=buf,*r=buf;
    return l==r&&(r=(l=buf)+fread(buf,1,100000,stdin),l==r)?EOF:*l++;
}
template<typename T> inline int readi(T &x){
    T tot=0;char ch=readc(),lst='+';
    while (!isdigit(ch)) {if (ch==EOF) return EOF;lst=ch;ch=readc();}
    while (isdigit(ch)) tot=(tot<<3)+(tot<<1)+(ch^48),ch=readc();
    return lst=='-'?x=-tot:x=tot,Eoln(ch);
}
#define Add(x,y) (son[++E]=(y),nxt[E]=lnk[x],lnk[x]=E)
void Dfs(int x,int pre=0){
    dep[x]=dep[pre]+1;ST[x][0]=pre;for (int j=1;j<=Log;j++) ST[x][j]=ST[ST[x][j-1]][j-1];si[x]=1;SH[x]=0;
    for (int j=lnk[x],u;j;j=nxt[j]) Dfs(u=son[j],x),si[x]+=si[u],si[u]>si[SH[x]]?SH[x]=u:0;
}
void HLD(int x,int lst){
    who[Lt[x]=++Lt[0]]=x;top[x]=lst;if (SH[x]) HLD(SH[x],lst);
    for (int j=lnk[x];j;j=nxt[j]) if (son[j]!=SH[x]) HLD(son[j],son[j]);
}
void Build(int L,int R,int p=1){
    if (L==R) {s[p][a[who[L]]]=1;return;}int mid=L+(R-L>>1);
    Build(L,mid,p<<1);Build(mid+1,R,p<<1|1);s[p]=s[p<<1]|s[p<<1|1];
}
inline int LCA(int x,int y){
    if (dep[x]<dep[y]) swap(x,y);for (int j=Log;~j&&dep[x]>dep[y];j--) if (dep[ST[x][j]]>=dep[y]) x=ST[x][j];
    if (x==y) return x;for (int j=Log;~j;j--) if (ST[x][j]!=ST[y][j]) x=ST[x][j],y=ST[y][j];return ST[x][0];
}
bitset<maxm> Ask(int L,int R,int l=1,int r=n,int p=1){
    if (L==l&&r==R) return s[p];int mid=l+(r-l>>1);
    if (R<=mid) return Ask(L,R,l,mid,p<<1); else if (L>mid) return Ask(L,R,mid+1,r,p<<1|1);
    else return Ask(L,mid,l,mid,p<<1)|Ask(mid+1,R,mid+1,r,p<<1|1);
}
inline bitset<maxm> Query(int x,int y){
    static bitset<maxm> now;now=0;
    while (top[x]!=top[y]) {if (dep[x]<dep[y]) swap(x,y);now|=pre[x];x=ST[top[x]][0];}
    if (Lt[x]>Lt[y]) swap(x,y);now|=Ask(Lt[x],Lt[y]);return now;
}
int main(){
    freopen("program.in","r",stdin);freopen("program.out","w",stdout);
    readi(n);readi(m);readi(te);for (int i=2,fa;i<=n;i++) readi(fa),Add(fa,i);
    for (int i=1;i<=n;i++) readi(a[i]),a[i]--;Dfs(1);HLD(1,1);Build(1,n);
    for (int i=1;i<=n;i++) pre[i]=Ask(Lt[top[i]],Lt[i]);
    H[0]=-1;for (int i=1;i<(1<<maxk);i++) cnt[i]=cnt[i>>1]+(i&1),H[i]=H[i>>1]+1;
    for (int K,c[maxk+5],ans;te;te--){
        readi(K);for (int i=0;i<K;i++) readi(c[i]);ans=2e9;
        int lca=c[0];for (int i=1;i<K;i++) lca=LCA(lca,c[i]);
        for (int i=0;i<K;i++) t[i]=Query(c[i],lca);
        for (int i=1;i<(1<<K);i++) S[i]=S[i^(1<<H[i])]|t[H[i]];
        for (int i=1;i<(1<<K);i++) ans=min(ans,(int)S[i].count()/cnt[i]);printf("%d\n",ans*K);
    }return 0;
}