ZR #1179. 【线上训练 16】舔到

题目链接：​​传送门​​（没买的看不了）

又是这种树上博弈，在ZR看到好多这种T1了
虽然难度没那么大但做完总是觉得不稳妥
把当前树的集合分成两种情况，一个是所有节点入度都是奇数，一个是有的节点入度是偶数
这两个状态间一定可以互相转移，因为叶子节点的度数一定是奇数
样例1就是最简单的情况，所有的状态都可以转移到这个状态来看，这样是先手赢
如果有一个点的入度为偶数那么Alice就可以把局面转到那种最简单的情况，而且当前是自己操作
那么只要有一个点的入度为偶数那么就是Alice赢，否则Bob赢

#include <bits/stdc++.h>

using namespace std;
int n, d[1000005], a, b, ans = 1;

int main(int argc, char const *argv[]) {
  scanf("%d", &n);
  for (int i = 1; i < n; i++) scanf("%d%d", &a, &b), d[a]++, d[b]++;
  for (int i = 1; i < n; i++) ans = ans & d[i];
  if (n == 1 or !ans) puts("Alice");
  else puts("Bob");
}