1.树上删边问题
sg函数的一个简单应用，把树拆成很多条以根节点为起点的链，就可以等效于nim问题。
我们把叶子节点的sg赋值为0，一个节点的sg值为它儿子节点的sg值+1的异或和。
最后判断根节点的sg值是否为0，再判断是先手必胜还是后手。
点击查看代码
#include<bits/stdc++.h>
using namespace std;
const int N=4e5+105;
int n,x,y;
int h[N],to[N],nxt[N],tot;
void add(int x,int y)
{
to[++tot]=y;
nxt[tot]=h[x];
h[x]=tot;
}
int sg[N];
void dfs(int u,int fa)
{
for(int i=h[u];i;i=nxt[i])
{
int v=to[i];
if(v==fa) continue;
dfs(v,u);
sg[u]^=(sg[v]+1);
}
// sg[u]=x;
}
int main()
{
int T;scanf("%d",&T);
while(T--)
{
memset(h,0,sizeof h),memset(to,0,sizeof to);
memset(nxt,0,sizeof nxt);tot=0;memset(sg,0,sizeof sg);
scanf("%d",&n);
for(int i=1;i<=n-1;i++)
{
scanf("%d%d",&x,&y);
add(x,y);add(y,x);
}
dfs(1,0);
printf("%s\n",sg[1]?"gtm1514":"joke3579");
}
}