C++-hihoCode1545-小Hi和小Ho的对弈游戏[树上Nim]

 #include <set>

 #include <map>

 #include <cmath>

 #include <queue>

 #include <vector>

 #include <cstdio>

 #include <cstdlib>

 #include <cstring>

 #include <iostream>

 #include <algorithm>

 using namespace std;

 const int MAXN=,MAXM=;

 struct edge{

     int v,next;

     edge(int v=,int next=):v(v),next(next){}

 };

 edge E[MAXM];int head[MAXN],cnt,d[MAXN],sg[MAXN],g,rt;

 void add(int u,int v){E[++cnt]=edge(v,head[u]),head[u]=cnt;}

 void init(){

     cnt=g=;

     memset(d,,sizeof(d));

     memset(head,,sizeof(head));

 }

 void dfs(int u,int fa){

     sg[u]=;

     for(int i=head[u];i;i=E[i].next)

         if(E[i].v!=fa)

             dfs(E[i].v,u);

     sg[fa]^=(sg[u]+);

     if(fa==rt)g^=sg[u];

 }

 int main(){

     int q,n;

     for(scanf("%d",&q);q--;){

         init(),scanf("%d",&n);

         for(int i=,u,v; i<n; i++)scanf("%d%d",&u,&v),add(u,v),d[v]++;

         for(int i=;i<=n;i++)if(!d[i])rt=i;//注意题目的隐含意思是加入的单项边

         dfs(rt,);

         putchar(sg[rt]?'':'');

         putchar(g?'':'');

     }

     return ;

 }