pkucpc2025 L:Game on Tree

题意

两个人在一棵无根树上玩游戏，每次可以删掉若干个叶子节点，不能操作的人输。

思路

比赛的时候我去写H Quintuple了，队友貌似在我写的时候把这道题讨论出来了。
后来补题的时候花了大概花了70分钟左右ac这道题。

首先考虑一条链的情况，那么必败态是链的长度为3的倍数，十分显然。

就是这个结论误导了我很久。

后面发现了一个很有趣的性质，如果存在一个叶子节点，把它删掉以后不会产生新的叶子节点，那么必胜：考虑去掉这个叶子节点以后的树，如果是必败的，那么只需要去掉这个叶子节点；否则去掉这个叶子节点并且并将剩下的部分转移成必败态。

然后就变成了判断是否有叶子节点到一个deg>=3的点的距离为奇数，如果有就是必胜。

#include <bits/stdc++.h>
#define ll long long
using namespace std;const int N = 1e3 + 10;int n; vector<int> e[N];void solve() {cin >> n;for (int i = 1; i <= n; i++) {e[i].clear();}for (int i = 1; i < n; i++) {int x, y;cin >> x >> y;e[x].push_back(y);e[y].push_back(x);}int mx = 0;for (int i = 1; i <= n; i++) {mx = max(mx, (int)e[i].size());}if (mx <= 2) {cout << ((n - 1) % 3 ? "Alice\n" : "Bob\n");return;}for (int i = 1; i <= n; i++) {if (e[i].size() > 1) continue;int x = i; int last = 0;int cnt = 0;while (e[x].size() <= 2) {int nxt;for (int y : e[x]) {if (y == last) continue;nxt = y; break;}last = x, x = nxt, cnt++;}if (cnt & 1) {cout << "Alice\n";return;}}cout << "Bob\n";
}int main() {// freopen("in.in", "r", stdin);ios::sync_with_stdio(false);cin.tie(nullptr);int T; cin >> T;while (T--) {solve();}
}