CCPC Harbin 2023

- 2 mins read

一次很乐的vp，简单补下题

J. Game on a Forest

Problem - J - Codeforces

题意是有一个森林，2个人交替取走 一个节点及其所连所有边 或 一条边，无法操作者输。问先手第一步有多少操作能导向胜利局面。

边数、点数$O(1e5)$

森林是由一些分散的树构成的，每个树的情况都有独立性，组合在一起更显复杂。但经典的公平组合游戏 - OI wiki中对这种情况早有叙述。毕竟在Nim游戏中，也有几堆石头，每堆石头的情况是相对独立的。

截图OI wiki上的SG定理 image.png 那么，只要将一棵树建模为有向图，分析它的SG函数即可。 较为复杂的事是，玩家有2种操作：拿边和拿点. 易得1个点的树SG值为1，2个点的树SG值为2（#-# -> # # 或 # , SG分别为0，1）. 3个点的树形态也唯一，可以继续推得是1，进而推得4是2. 开始有规律了，似乎是奇数节点数的树SG值为1，偶数的为2.

在这里先泛泛地想一下，对多个点的树进行操作可能的所有情况：

  • 拿走1个点，可能
    • 这棵树的节点会少一个（拿走的没儿子）
    • 分为多棵树（拿走的有儿子）
  • 拿走1边，会
    • 分为2棵树

那么对那个从奇偶角度提出的假设，用数学归纳的思路，试证明：

  • 拿走1个点，可能
    • 这棵树的节点会少一个（拿走的没儿子）
      • 奇树 变为偶树 (SG为2)
      • 偶树 变为奇树 (SG为1)
    • 分为多棵树（拿走的有儿子）
      • 奇树可能分为：
        • 偶数个奇树 奇数个偶树 (SG为2)
        • 偶数个奇树 偶数个偶树 (SG为0)
      • 偶树可能分为：
        • 奇数个奇树 奇数个偶树 (SG为3)
        • 奇数个奇树 偶数个偶树 (SG为1)
  • 拿走1边，会
    • 分为2棵树
      • 奇树分为
        • 1奇1偶 (SG为3)
      • 偶树可能分为
        • 2偶 (SG为0)
        • 2奇 (SG为0)

发现是对的.

那么，每个局面的SG可以用现存树的SG异或和计算。 统计答案时，枚举先手第一次的每个操作，看看能不能到达必输态，即可.

代码

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

#define int long long
#define endl '\n'
typedef unsigned long long ull;

const int N=1e5;
const int INF=0x3f3f3f3f3f3f3f3f;

void solve()
{
    int n,m;
    cin >> n >> m;
    vector < vector <int> > e (n+1) ;
    vector <array<int,2>> E(m+1);
    for(int i=1;i<=m;++i)
    {
        int u,v;
        cin >> u >> v;
        e[u].emplace_back(v);
        e[v].emplace_back(u);
        E[i]=array<int,2>{u,v};
    }
    vector <int > dep(n+1);
    vector <int> sz(n+1);
    vector <int> r(n+1);

    

    function <void (int,int,int)> dfs=[&](int u,int fa,int rt){
        dep[u]=dep[fa]+1;
        r[u]=rt;      
        sz[u]=1;
        for(auto v:e[u])
        {
            if(fa==v)   continue;
            dfs(v,u,rt);
            sz[u]+=sz[v];
        }
    };

    int all = 0; //所有树SG异或和

    for(int i=1;i<=n;++i)
    {
        if(dep[i]==0)
        {
            dfs(i,0,i);
            all^=(sz[i]%2==0?2:1);
        }     
    }

    int ans = 0;
    for(int i=1;i<=n;++i)
    {
        int tmp = 0; // 相邻节点所在的树 和 其他树
        for(auto v:e[i])
        {
            if(dep[v]>dep[i])//孩子
            {
                tmp^=(sz[v]%2==0?2:1);
            }
            else
            {
                tmp^=((sz[r[i]] - sz[i])%2==0?2:1);
            }
        }
        tmp^=all;
        tmp^=(sz[r[i]]%2==0?2:1);
        if(tmp==0)
        {
            ans++;
        }
    }
    for(int i=1;i<=m;++i)
    {
        auto [u,v]=E[i];
        if(dep[u]>dep[v])
        {
            swap(u,v);
        }
        //u为祖先
        int tmp;// 边分出的2棵树 和 其它的树
        tmp = ((sz[v])%2==0?2:1)^((sz[r[v]]-sz[v])%2==0?2:1);
        tmp^=all;
        tmp^=((sz[r[v]])%2==0?2:1);
        if(tmp==0)  ans++;
    }

    cout << ans << endl;
}

signed main()
{
    //cout.flags(ios::fixed); cout.precision(8);
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int T=1;
   // cin >> T;
    for(int i=1;i<=T;++i)
    {
        solve();
    }
    return 0;
}
/*

*/