树形 dp
因为题目限制对于两个人等价,所以朴素的,考虑将 \(u\) 与祖先和后代连边,构成一个新的无向图。那么题目就变成:在无向图中选一点,每一次操作就是走一步到新的点,谁先不能走,那么另一个人获胜。
先说结论:当无向图有完美匹配时,后手胜,反之先手胜。
证明:若有完美匹配,说明所有点都在匹配中,先手选点后,后手选与之匹配的点,那么一定能选完所有点并且后手选到最后一个,后手胜;反之,说明存在一个点不在最大匹配中,先手选该点,那么后手选择相邻的点一定在匹配中(否则这两点又构成匹配),先手下一次选的点同样在匹配中(否则构成增广路,与最大匹配矛盾),那么就回到上面的情形但角色互换,先手胜。
回到原题,我们无法建出无向图,考虑树形 dp。设 \(f_u\) 表示 \(u\) 子树中最少有多少点没有匹配,设 \(g_u=\sum\limits_{v\in son_u}f_v\),根据 \(u\) 点和子树中任意一点能够形成匹配,转移为:
\[f_u=\begin{cases} g_u-1, & \text{if }g>0 \\ 1, & \text{otherwise} \end{cases} \]答案判断 \(f_1\) 即可。
复杂度 \(O(n)\)。
#include <bits/stdc++.h>
#define pii std::pair<int, int>
#define fi first
#define se second
#define pb push_back
using i64 = long long;
using ull = unsigned long long;
const i64 iinf = 0x3f3f3f3f, linf = 0x3f3f3f3f3f3f3f3f;
const int N = 1e5 + 10;
int n;
int f[N];
std::vector<int> e[N];
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cin >> n;
for(int i = 1; i < n; i++) {
int u, v;
std::cin >> u >> v;
e[u].pb(v);
e[v].pb(u);
}
auto dfs = [&](int u, int fa, auto &self) -> void {
int g = 0;
for(auto v : e[u]) {
if(v == fa) continue;
self(v, u, self);
g += f[v];
}
if(g) f[u] = g - 1;
else f[u] = 1;
};
dfs(1, 0, dfs);
std::cout << (f[1] ? "Alice\n" : "Bob\n");
return 0;
}
标签:std,匹配,int,Tree,long,Game,QOJ2376,dp,define
From: https://www.cnblogs.com/FireRaku/p/18279721