hdu3197 Game-------树的删边

GameTime Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 210    Accepted Submission(s): 70


Problem Description

  On each step, one player could chop out one edge, and removing that edge and anything not connected to the ground. The one who have nothing to chop with fails.
  Flynn is the one who is going to move. Help him by telling him if it is possible to win by carefully choose the edge to chop with.InputOutputSample InputSample OutputAuthorSourceRecommend#include<iostream>#include<vector>#include<stack>#include<stdio.h>using namespace std;vector<int> V[1010];stack<int> S;int N;int dfs(int v,int pre) //树上博弈{ int i,t; int sum=0; for(i=0;i<V[v].size();i++) { t=V[v][i]; if(t!=pre) sum=sum^(dfs(t,v)+1); } return sum;}int main(){ int i,flag,t; while(scanf("%d",&N)!=EOF) { for(i=0;i<=N;i++) V[i].clear(); while(!S.empty()) S.pop(); for(i=0;i<N;i++) { scanf("%d",&t); if(t!=-1) { V[t].push_back(i); V[i].push_back(t); } else { S.push(i); } } int t,sum=0; while(!S.empty()) //k棵树 { t=S.top(); S.pop(); sum=sum^dfs(t,-1); } if(sum) printf("YES\n"); else printf("NO\n"); } return 0;}