AtCoder GrandContest017 D Game On Tree(树上Nim)

雅礼集训的时候讲过树上$Nim$的样子,然而这还是第一次遇到…然后附一下证明。

首先根据$sg$定理,一棵树的$sg$值是它的所有子树的$sg$值的异或和。听上去好像很简单,但是仔细一想的话会发现,单独只有一个节点的树$sg$为0,若一棵树只有一个结点,那异或起来就还是$0$,但是明显的只有一个结点的树是必胜态,$sg=1$。我们发现对于一棵树只有一个子节点的情况,$sg$值为$1$,于是假定对于$1$个结点,它的子树对他的影响是该子树的$sg$值$+1$。

  • 对于只有一个节点的情况,显然成立。
  • 对于一个节点为根,仅有一个结点作为子树的情况,显然成立。
  • 假设对于$n$结点的一子树成立,它的$sg=mex \lbrace b_1,b_2,b_3…\rbrace $,那么整棵树的$sg’=mex \lbrace 0,b_1+1,b_2+1,b_3+1… \rbrace$(因为单独一个结点的$sg$为0),而$mex \lbrace 0,b_1+1,b_2+1,b_3+1…\rbrace =mex \lbrace b_1,b_2,b_3…\rbrace +1$故$sg’=sg+1$,得证。

于是就只需要递归的去求解各个子树的$Nim$值,再$+1$异或就好了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <bits/stdc++.h>
using namespace std;
const int maxn=100000+5;
int n;
vector<int > g[maxn];
int sg[maxn];
void addedge(int from,int to)
{
g[from].push_back(to);
g[to].push_back(from);
}
int dfs(int v,int fa)
{
if(g[v].size()==1 && fa==g[v][0]) return sg[v]=0;
sg[v]=0;
for(int i=0;i<(int)g[v].size();i++)
{
int u=g[v][i];
if(u!=fa) sg[v]=sg[v] xor (1+dfs(u,v));
}
return sg[v];
}
int main()
{
scanf("%d",&n);
for(int i=0;i<n-1;i++)
{int from,to;scanf("%d%d",&from,&to);addedge(from,to);}
dfs(1,-1);
if(sg[1]) printf("Alice\n");
else printf("Bob\n");
return 0;
}