[AGC010F] Tree Game 题解

题意：

有一棵 $n$ 个节点的树，第 $i$ 条边连接 $a_i,b_i$，每个节点 $i$ 上有 $A_i$ 个石子，高桥君和青木君将在树上玩游戏

首先，高桥君会选一个节点并在上面放一个棋子，然后从高桥君开始，他们轮流执行以下操作：

从当前棋子占据的点上移除一个石子，将棋子移动到相邻节点

如果轮到一个人执行操作时棋子占据的点上没有石子，那么他就输了。

请你找出所有的点 $v$，使得如果高桥君在游戏开始时把棋子放到 $v$ 上，他可以赢。

输入格式：

第一行一个整数 $n$

第二行 $n$ 个整数 $A_{1..n}$

接下来行每行两个整数 $a_i,b_i$ 表示一条边

输出格式：

以编号递增的顺序在一行中输出所有满足条件的点

数据范围：

$2 \le n \le 3000,~0 \le A_i \le 10^9$

根据博弈论的套路，记 $f_u = \mathrm{N/P}$ 表示点 $u$ 先手为必胜态/必败态。

显然叶子节点都为 $\mathrm{N}$ 。考虑一个两层的树，即 $u$ 有若干儿子 $v_i$ 的极小树。

尝试一下就能发现，当且仅当 $A_u > \min\{A_{v_i}\}$ 时 $u$ 为 $\mathrm{N}$ 。

接着考虑一般情况的 $u$ 。可以发现，如果 $u$ 存在必胜态的 $v_i$ ，那么先手一定不会往那走。

因此只需考虑必败态的 $v_i$ 是否真能“让先手在 $v_i$ 的必败”。

根据刚才的结论我们可以猜测并证明， $u$ 当且仅当 $v_i$ 为 $\mathrm{P}$ 且 $A_u > \min\{A_{x}\} \quad (x \in T(v_i))$ 时为 $\mathrm{N}$ 。

那么可以发现这道题就是个难度虚高的憨憨博弈论题，~~专挑不会博弈论的人吓唬~~。

时间复杂度 $\mathcal{O}(n)$

代码：

#include <bits/stdc++.h> using namespace std; #define int long long #define INF 0x3f3f3f3f3f3f3f3f void up(int &x,int y) { x < y ? x = y : 0; } void down(int &x,int y) { x > y ? x = y : 0; } #define N ((int)(3e3 + 15)) int n, pos = 1, a[N], head[N]; struct Edge { int u,v,next; } e[N * 2]; void addEdge(int u, int v) { e[++pos] = {u, v, head[u]}; head[u] = pos; } bool dfs(int u, int fa) { bool r = true; for(int i = head[u], v; i && r; i = e[i].next) if((v = e[i].v) != fa && a[v] < a[u]) r &= dfs(v, u); return !r; } signed main() { ios::sync_with_stdio(0); cin.tie(0);cout.tie(0); // freopen("check.in","r",stdin); // freopen("check.out","w",stdout); cin >> n; bool ok = 1; for(int i = 1; i <= n; i++) cin >> a[i]; for(int i = 1, u, v; i < n; i++) { cin >> u >> v; addEdge(u,v); addEdge(v,u); } for(int i = 1; i <= n; i++) if(dfs(i, 0)) { ok ? ok = false : (cout << ' ', 1); cout << i; } return cout << '\n', 0; }

参考文献：

2024-01-18 OI