AT AGC D - Game on Tree

AT AGC D - Game on Tree

大意

典型的树上博弈。

思路

利用节点 \(SG\) 值等于其所有子树 \((SG+1)\) 的异或和判定在不断删边过程中谁能赢得比赛。

代码

#include<iostream>
#include<vector>
#include<cstring>
using namespace std;#define int long long
const int MAXN = 100005;
int T;
int n;
vector<int> G[MAXN];
int SG[MAXN];void dfs(int u, int fa){SG[u] = 0;for(int &v : G[u]){if(v != fa){dfs(v, u);SG[u] ^= (SG[v] + 1);}}
}signed main(){cin >> n;for(int i = 1;i < n;i ++){int u, v; cin >> u >> v;G[u].push_back(v);G[v].push_back(u);}dfs(1, 0);if(SG[1] == 0){cout << "Bob\n";}else{cout << "Alice\n";}return 0;
}