hdu3590 PP and QQ-----删边游戏&&anti--sg

#include<iostream>#include<cstdlib>#include<stdio.h>#include<vector>using namespace std;vector<int>v[110];int dfs(int x,int pre){    int ans=0;    for(int i=0;i<v[x].size();i++)    {        if(v[x][i]!=pre)        ans^=(1+dfs(v[x][i],x));    }    return ans;}int main(){    int n,m,a,b;    while(scanf("%d",&n)!=EOF)    {        int ans=0,cnt=0;        while(n--)        {            scanf("%d",&m);            for(int i=1;i<=m;i++)            v[i].clear();            for(int i=1;i<m;i++)            {                scanf("%d%d",&a,&b);                v[a].push_back(b);                v[b].push_back(a);            }            int s=dfs(1,-1);            if(s>1) cnt++;            ans^=s;        }        if(cnt>=1)        {            if(ans) puts("PP");            else puts("QQ");        }        else        {            if(ans) puts("QQ");            else puts("PP");        }    }}

PP and QQTime Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 209    Accepted Submission(s): 81


Problem Description

Then they took turns to cut a branch of a tree, and removed the part of the tree which had already not connected with the root. A step shows as follows:



PP always moved first.
PP and QQ took turns (PP was always the first person to move), to cut an edge in the graph, and removed the part of the tree that no longer connected to the root. The person who cannot make a move won the game.
Your job is to decide who will finally win the game if both of them use the best strategy.
InputOutputSample InputSample OutputAuthorSourceRecommendzhouzeyong多棵树，每次可以删掉和根相连的一部分树，谁不能操作谁就输了。结合一下anti-sg，先手有必胜策略是：如果某个单一游戏的sg值大于1并且整个游戏的sg值不为0，或者游戏的sg值为0，且游戏中没有单一的游戏的sg值大于1.