AtCoder Regular Contest 162

C - Mex Game on Tree

题意

给出一棵树，其中一些点标有数字。Alice和Bob轮流给剩下的点标数字，如果最终有一棵子树的所有结点 $\mathrm{mex}$ 为 $k$，则Alice胜，否则Bob胜。要求判断两人最优操作下谁能获胜。

题解

很直观的想法是Bob每次操作都会填入 $k$，而若一棵子树中存在一个结点数字为 $k$，那么这棵子树的 $\mathrm{mex}$ 不再可能为 $k$。那么，如果Alice不能在一步以内使得某棵子树的 $\mathrm{mex}$ 为 $k$ 且不再有结点没有填数字，Bob总可以破坏掉这棵子树。

答案就很显然了。我们寻找是否存在 $\mathrm{mex}$ 为 $k-1$ 且有 $1$ 个结点未填数或 $\mathrm{mex}$ 为 $k$ 且有 $0$ 或 $1$ 个结点未填数的子树，若存在则Alice获胜，否则Bob获胜。

这可以利用树上启发式合并在 $O(n\log n)$ 的时间复杂度内完成。

代码

#include <bits/stdc++.h>
using namespace std;
const int maxn=1005;
int n,k,a[maxn];
vector<int> g[maxn];
bool ok,exist;
int tot,res,cnt[maxn];
int dfn,l[maxn],r[maxn],node[maxn],big[maxn],siz[maxn];
void add(int u)
{
    if(~a[u]) 
    {
        if(!cnt[a[u]])
        {
            if(a[u]<k) res--;
            if(a[u]==k) exist=1;
        }
        cnt[a[u]]++;
    }
    else tot++;
}
void del(int u)
{
    if(~a[u]) cnt[a[u]]--;
}
void dfs0(int u,int fa)
{
    l[u]=++dfn;
    node[dfn]=u;
    siz[u]=1;
    for(auto v:g[u])
    {
        if(v==fa) continue;
        dfs0(v,u);
        siz[u]+=siz[v];
        if(!big[u]||siz[big[u]]<siz[v]) big[u]=v;
    }
    r[u]=dfn;
}
void dfs1(int u,int fa,bool keep)
{
    for(auto v:g[u])
    {
        if(v!=fa&&v!=big[u])
            dfs1(v,u,0);
    }
    if(big[u]) dfs1(big[u],u,1);
    for(auto v:g[u])
        if(v!=fa&&v!=big[u])
        {
            for(int i=l[v];i<=r[v];i++) add(node[i]);
        }
    add(u);
    if(!exist&&((res==1&&tot==1)||(res==0&&tot<=1))) ok=1;
    if(!keep)
    {
        for(int i=l[u];i<=r[u];i++) del(node[i]);
        tot=exist=0,res=k;
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;cin>>t;
    while(t--)
    {
        cin>>n>>k;
        dfn=ok=exist=0,res=k;
        for(int i=1;i<=n;i++) big[i]=0;
        for(int i=1;i<=n;i++) g[i].clear();
        for(int i=2;i<=n;i++)
        {
            int x;cin>>x;
            g[x].push_back(i),g[i].push_back(x);
        }
        for(int i=1;i<=n;i++) cin>>a[i];
        dfs0(1,0);
        dfs1(1,0,0);
        cout<<(ok?"Alice":"Bob")<<'\n';
    }
    return 0;
}