[博弈论][组合游戏][组合计数] codeforces 812E Sagheer and Apple Tree

题目链接

题意：

给定一棵树，每个节点上有 $a_i$ 个苹果，两个人轮流操作，每次把一个节点的一部分(或全部)苹果移到他的某个儿子中(如果是叶子节点没有儿子那么就吃掉这些苹果)，最后不能走的人输。现在在游戏开始前先手可以选取两个不同的节点交换他们之间的苹果数，问有多少种交换方式可以使得先手必胜。
数据范围： $1\le n \le 10^5,\;1\le a_i \le 10^7$

题解：

博弈本身是很简单的阶梯博弈。由阶梯博弈的知识，求胜负只需要计算奇数位上的SG函数异或和即可，这题只不过把阶梯转移到了树上，但是略微分析就可以发现和链状的阶梯是没有区别的，都是奇数往偶数转移当作拿走，偶数往奇数转移就对称操作。

• 然后考虑计数:
  • 假设初始状态是必胜态，那么可以先计入奇数层自己内部交换和偶数层自己内部交换的对数，分别为 $C_{num\;of\;odd\;level}^2$ 和 $C_{num\;of\;even\;level}^2$；
  • 然后计算奇偶层之间互换的对数，设异或和结果为 $ans$ ，假设一对数 $a_u$ $a_v$ 交换之后可以使得 $ans=0$ ,那么由亦或的性质可得 $a_v=ans\oplus a_u$，那么我们就可以枚举 $a_u$ 的值，找 $a_v$ 有多少个，而后者利用 $map$ 可以很容易的预处理出来。
    

wa点：

• None

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const int maxn=1e5+5;

int ns[maxn],step[maxn];
vector<int> G[maxn];
map<int,int> mp;

ll C2(ll x){
    if(x<2) return 0;
    else return x*(x-1)/2;
}

int dfs(int x){
    if(G[x].size()==0) return step[x]=1;
    for(int v:G[x]) step[x]=dfs(v)+1;
    return step[x];
}

int main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int n,pa,ans=0,cnt=0;
    cin>>n;
    for(int i=1;i<=n;++i) cin>>ns[i];
    for(int i=2;i<=n;++i)cin>>pa, G[pa].push_back(i);
    dfs(1);
    for(int i=1;i<=n;++i){
        if(step[i]&1) ans^=ns[i],++cnt;
        else mp[ns[i]]++;
    }
    ll res=0;
    if(!ans) res+=C2(cnt)+C2(n-cnt);
    for(int i=1;i<=n;++i)
        if(step[i]&1)
            res+=mp[ans^ns[i]];
    cout<<res;
}