[AGC010F] Tree Game 题解

题目链接：[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;
}

---

参考文献：

[1] https://yhx-12243.github.io/OI-transit/records/ac2307%3Bagc010F.html