HDU 3094 A tree game 树删边游戏

叶节点SG值至0 非叶节点SG值至于它的所有子节点SG值添加1 XOR和后

#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
vector <int> G[100010];
int sg[100010];
int dfs(int x, int f)
{
if(sg[x] != -1)
return sg[x];
if(!G[x].size())
return 0;
int ans = 0;
for(int i = 0; i < G[x].size(); i++)
{
int v = G[x][i];
if(v == f)
continue;
ans ^= dfs(v, x)+1;
}
return ans;
}
int main()
{
int T;
scanf("%d", &T);
while(T--)
{
memset(sg, -1, sizeof(sg));
int n;
scanf("%d", &n);
for(int i = 1; i <= n; i++)
G[i].clear();
for(int i = 1; i < n; i++)
{
int u, v;
scanf("%d %d", &u, &v);
G[u].push_back(v);
G[v].push_back(u);
}
int ans = dfs(1, -1);
if(ans)
puts("Alice");
else
puts("Bob");
}
return 0;
}