hdu 3590 PP and QQ 博弈论

思路：

在贾志豪神牛的论文里，这两种游戏都有

其中树的删边游戏：叶子节点的SG值为0；中间节点的SG值为它的所有子节点的SG值加1 后的异或和。

ANTI-SG:先手必胜当且仅当：（1）游戏的SG函数不为0且游戏中某个单一游戏的SG函数大于1；（2）游戏的SG函数为0且游戏中没有单一游戏的SG函数大于1。

代码如下：

 1 #include<cstdio>
 2 #include<vector>
 3 using namespace std;
 4 vector<int>p[102];
 5 int ans,n;
 6 int dfs(int m,int f)
 7 {
 8     int res=0;
 9     for(int i=0;i<p[m].size();i++){
10         if(p[m][i]!=f){
11             res^=(1+dfs(p[m][i],m));
12         }
13     }
14     return res;
15 }
16 int main()
17 {
18     int t,u,v,cnt,s;
19     while(scanf("%d",&t)!=EOF){
20         cnt=ans=0;
21         while(t--){
22             scanf("%d",&n);
23             for(int i=0;i<=n;i++) p[i].clear();
24             for(int i=0;i<n-1;i++){
25                 scanf("%d%d",&u,&v);
26                 p[u].push_back(v);
27                 p[v].push_back(u);
28             }
29             s=dfs(1,-1);
30             if(s>1) cnt++;
31             ans^=s;
32         }
33         if(ans) puts(cnt>=1?"PP":"QQ");
34         else puts(cnt?"QQ":"PP");
35     }
36 }

View Code