题解 P7841 【「C.E.L.U-03」100%不公平的游戏】

· · 题解

是真的没有代码能力了/ll

一道大毒瘤题/baojin

SG 定理 + 换根 dp。

首先想到先手标记了一条边后，问题转化成了两个子游戏的和，每个游戏都是一棵有根树，要求变成在有根树中标记边且这些边都要在一条以根为一个端点的链上。

为什么要转化成这样的游戏呢？这是由于在这个游戏中，操作一步转化出的子游戏形态与之相似。以下用 \operatorname{SG}(x) 表示 x 子树的 SG 值。

如在以下一棵树中（根为 1）：

若我们标记了 5-9 这条边，即

显然此时接下来标记的边只可能在 9 的子树中或 1-5 这条链上。在 9 子树中操作的规则与原问题是相同的。故此后继状态的 SG 值为 \operatorname{SG}(9) \oplus \operatorname{SG}(1-5)（记号不是很标准）。

而链的 SG 值为链长 {}\bmod 2（链长计边数）。这个可以设长为 n 的链的 SG 值为 f(n)，由 f(0)=0,f(1)=1，且

f(n)=\operatorname{mex}\{f(i) \oplus f(n-i-1) :i=0,\dots,n-1\}

得到。

故由以上分析，任意选定根后可得

\operatorname{SG}(x)=\operatorname{mex}\{\operatorname{SG}(v) \oplus (dep_v-dep_x-1) \bmod{2} : v \in subtree_x\},

其中 subtree_x 表示 x 的子树中的所有点构成的集合。

于是我们要关注的就是 \operatorname{SG}(v) \oplus (dep_v-dep_x-1) \bmod{2}。我们发现相邻两点的深度奇偶性恰好相反，也就是在点 u 处需要 \oplus1 的值在 u 的父亲处不需要，反之亦然。于是我们记两个集合 S_{x,0} 与 S_{x,1}，S_{x,0} 是所需要用于求 SG 值的集合，S_{x,1} 是 S_{x,0} 中所有元素 \oplus 1 之后的集合。则有转移：

S_{u,0}=\bigcup_{v \in son_u}(\{\operatorname{SG}(v)\} \cup S_{v,1}), S_{u,1}=\bigcup_{v \in son_u}(\{\operatorname{SG}(v)\} \cup S_{v,0}),

且有 \operatorname{SG}(u)=\operatorname{mex}(S_{u,0})。

在这个转移方程的基础上进行换根 dp 即可。用 bitset 维护集合，SG 值最大可能为 37，处理 SG 函数所需时间 \frac{37}{\omega} 是一个小常数，故时间复杂度为 O(n)，实际表现也足够优秀（最慢点 1s 左右）。

具体实现中，我们对每个点用两个 bitset 维护它父亲的儿子中比它先遍历到的点的 S 与比它后遍历到的点的 S 的并集，这个有点类似前缀/后缀和。这样在换根过程中可以直接 O(1) 计算。细节比较多所以调死我了。

bitset 库函数 _Find_first 可以快速找到最低位的 1，取反后调用就是 \operatorname{mex} 函数。

不要像我一样只用脑子想，最好用下草稿纸，不然就像我一样想错了都不知道

Code:

#include<bitset>
#include<cstdio>
#include<vector>
#define rg register
using std::bitset;
using std::vector;
int sg[500003];
int snm[500003];
vector<int> e[500003];
bitset<40> S[500003][2],T;
bitset<40> lS[500003][2],rS[500003][2];
inline void add(int x,int y){e[x].push_back(y),e[y].push_back(x);}
void dfs1(int u,int f)
{
    snm[u]=e[u].size();
    bitset<40> tlS0,trS0;
    bitset<40> tlS1,trS1;
    tlS0.reset(),trS0.reset();
    tlS1.reset(),trS1.reset();
    for(rg int i=1,v;i<snm[u];++i)
    {
        v=e[u][i];if(v==f)continue;dfs1(v,u);
        lS[v][0]=tlS0,tlS0|=S[v][1];
        lS[v][1]=tlS1,tlS1|=S[v][0];
    }
    for(rg int i=1,v;i<snm[u];++i)
    {
        v=e[u][snm[u]-i];if(v==f)continue;
        rS[v][0]=trS0,trS0|=S[v][1];
        rS[v][1]=trS1,trS1|=S[v][0];
    }
    sg[u]=(~tlS0)._Find_first(),S[u][0]=tlS0,S[u][1]=tlS1;
    S[u][0].set(sg[u]^1),S[u][1].set(sg[u]);
}
int dfs2(int u,int f,bitset<40> tS0,bitset<40> tS1)
{
    if(f)
    {
        int tsg=(~tS0)._Find_first();
        if(tsg==sg[u])return 1;
        tS0.set(tsg^1),tS1.set(tsg);
    }
    for(rg int i=1,v;i<snm[u];++i)
    {
        v=e[u][i];if(v==f)continue;
        if(dfs2(v,u,tS1|lS[v][0]|rS[v][0],tS0|lS[v][1]|rS[v][1]))return 1;
    }
    return 0;
}
inline void init(int n)
{
    T.reset();
    for(rg int i=1;i<=n;++i)
    {
        sg[i]=snm[i]=0;
        e[i].clear(),e[i].push_back(0);
        S[i][0].reset(),S[i][1].reset();
        lS[i][0].reset(),rS[i][0].reset();
        lS[i][1].reset(),rS[i][1].reset();
    }
}
int t,n,u,v;
int main()
{
    scanf(" %d",&t);
    while(t--)
    {
        scanf(" %d",&n);init(n);
        for(rg int i=1;i<n;++i)scanf(" %d %d",&u,&v),add(u,v);
        dfs1(1,0);puts((dfs2(1,0,T,T))?"Play now":"Restart");
    }
    return 0;
}