Problem

https://www.lydsy.com/JudgeOnline/problem.php?id=5404

Solution

最早到达就是 c 个人取 lca。

考虑一个人（每个人拿 k 种特产）与一类特产连边，二分答案 k 判断左边与右边（特产）是否有完备匹配。这里要用到霍尔定理。

如果我们能搞出每个人到 lca 经过的路径上的特产种类 bitset，就能暴力枚举是否符合霍尔定理。

于是写个树剖维护一下卡卡空间就完事了。

Code

// Code by ajcxsu
// Problem: party

#include<bits/stdc++.h>
using namespace std;

template<typename T> inline void gn(T &x) {
    char ch=getchar(); x=0;
    while(ch<'0' || ch>'9') ch=getchar();
    while(ch>='0' && ch<='9') x=x*10+ch-'0', ch=getchar();
}

const int N=3e5+10;
int h[N], to[N], nexp[N], p=1;
inline void ins(int a, int b) { nexp[p]=h[a], h[a]=p, to[p]=b, p++; }
typedef bitset<1000> bs;
int a[N], ra[N];

int dfn[N], siz[N], fa[N], son[N], dep[N], top[N], idx;
void dfs1(int x, int k) {
    dep[x]=k, siz[x]=1;
    for(int u=h[x];u;u=nexp[u])
        if(!dep[to[u]]) {
            dfs1(to[u], k+1), fa[to[u]]=x, siz[x]+=siz[to[u]];
            if(siz[to[u]]>=siz[son[x]]) son[x]=to[u];
        }
}
void dfs2(int x, int t) {
    top[x]=t, dfn[x]=++idx, ra[idx]=a[x];
    if(son[x]) dfs2(son[x], t);
    for(int u=h[x];u;u=nexp[u])
        if(!dfn[to[u]]) dfs2(to[u], to[u]);
}

#define ls x<<1
#define rs x<<1|1
bs sum[N*4];
void build(int x, int l, int r) {
    if(l==r) { sum[x][ra[l]]=1; return; }
    int mid=(l+r)>>1;
    build(ls, l, mid), build(rs, mid+1, r), sum[x]=sum[ls]|sum[rs];
}
bs query(int x, int l, int r, int xl, int xr) {
    if(xl<=l && r<=xr) return sum[x];
    int mid=(l+r)>>1;
    if(xr<=mid) return query(ls, l, mid, xl, xr);
    else if(xl>mid) return query(rs, mid+1, r, xl, xr);
    else return query(ls, l, mid, xl, mid)|query(rs, mid+1, r, mid+1, xr);
}

int n;
int lca(int s, int t) {
    while(top[s]!=top[t]) { if(dep[top[s]]<dep[top[t]]) swap(s, t); s=fa[top[s]]; }
    return dep[s]>dep[t]?t:s;
}
bs pth(int s, int t) {
    bs ret;
    while(top[s]!=top[t]) {
        if(dep[top[s]]<dep[top[t]]) swap(s, t);
        ret|=query(1, 1, n, dfn[top[s]], dfn[s]), s=fa[top[s]];
    }
    if(dep[s]>dep[t]) swap(s, t);
    return ret|query(1, 1, n, dfn[s], dfn[t]);
}

int c, per[10], k;
bs re[10];
bool dfs3(int x, bs na, int cnt) {
    if(x>c) return na.count()<cnt;
    if(dfs3(x+1, na|re[x], cnt+k)) return true;
    if(dfs3(x+1, na, cnt)) return true;
    return false;
}

int main() {
    int m, q, fa;
    gn(n), gn(m), gn(q);
    for(int i=2;i<=n;i++) gn(fa), ins(fa, i);
    for(int i=1;i<=n;i++) gn(a[i]);
    dfs1(1, 1), dfs2(1, 1), build(1, 1, n);
    int l, r, ans, lc;
    while(q--) {
        gn(c);
        for(int i=1;i<=c;i++) gn(per[i]);
        lc=lca(per[1], per[2]);
        for(int i=3;i<=c;i++) lc=lca(lc, per[i]);
        for(int i=1;i<=c;i++) re[i]=pth(lc, per[i]);
        l=0, r=m, ans=0;
        while(l<=r) {
            k=(l+r)>>1;
            if(dfs3(1, 0, 0)) r=k-1;
            else l=k+1, ans=k;
        }
        printf("%d\n", ans*c);
    }
    return 0;
}

本文链接：https://pst.iorinn.moe/archives/sol-bzoj-5404.html
许可： https://pst.iorinn.moe/license.html
若无特别说明，博客内的文章默认将采用 CC BY 4.0 许可协议 进行许可☆