牛牛和牛妹是一对好朋友,这天他们俩决定在树上玩一个游戏。
游戏的名字是“树行棋”,规则如下:

给定一个含有n个节点分别从1到n编号且以节点1为根的树,一开始每个节点各有1个棋子。
牛牛和牛妹轮流进行操作,且牛牛先手移动。

每次操作可以选择将任意一个棋子移动到其子树中的任意一个节点,但是每次移动必须保证棋子的位置发生变化(不能拿起再放回原处)。
直到无法进行操作,轮到不能操作的一方即为败者。

现在假设双方都采用最优策略,请问牛牛能否赢。
如果牛牛(先手)能够赢,请问牛牛第一步有多少种不同的必胜策略。

我们认为两个策略是不同的,当且仅当这两个策略一开始选择的棋子不同,或者移动的路径不同。

链接 🔗

「牛客练习赛63」牛牛的树行棋

题解 ❓

每个点可以到达其子儿子节点,可以转化成nim游戏的石堆取石子
然后对于每个节点,统计有多少个子儿子满足下一次选取让整棵树的亦或值为0

代码

const int mod = 1e9+7;
const int N = 5e5+10;
V G[N];
ll sum,ans,d[N],cnt[N];
void dfs1(ll x,ll fa)
{
    for(auto v:G[x])
    {
        if(v == fa) continue;
        dfs1(v,x);
        d[x] = max(d[v]+1,d[x]);
    }
    sum ^= d[x];
}
void dfs2(ll x,ll fa)
{
    if(d[x] > (d[x]^sum)) ans -= cnt[d[x]^sum];
    cnt[d[x]]++;
    for(auto v:G[x])
    {
        if(v == fa) continue;
        dfs2(v,x);
    }
    if(d[x] > (d[x]^sum)) ans += cnt[d[x]^sum];
}
int main()
{
//    __IN;__OUT;
    ll n;RLL(n);
    FOR(i,1,n-1)
    {
        ll x,y; RLL2(x,y);
        G[x].pb(y);
        G[y].pb(x);
    }
    dfs1(1,0);
    dfs2(1,0);
    if(sum)
    {
        PS("YES");
        PLN(ans);
    }
    else PS("NO");
    return 0;
}