博弈论做题记录

little-corn / 2024-04-28 / 原文

AGC010F Tree Game

Solution:

令 $a[u]$ 是节点 $u$ 上的石子数。

感性理解一下：如果当前节点 $u$ 以及它的唯一子节点 $v$, 满足 $a[u] \le a[v]$，那么如果先手向下到 $v$，后手可以向上走到 $u$，先手就会被硬控住，导致直接死掉。

所以我们可以猜出一个结论：从一个节点走到 $a$ 值比他更大的节点是不优的。

~~（然鹅我是做到这里就不会了e）~~

首先枚举先手把棋子放在哪里，并以该点作为树的根。

由于我们只关心先手赢还是后手赢，所以我们可以令 $f[u] = 0/1$ 为在只考虑 $u$ 为根的子树中，且棋子刚好是放在 $u$ 上时，是先手必胜/必败。

那么 $f[u] = 1$ 当且仅当有某一个 $u$ 的子节点 $v$ 满足 $a[v] < a[u]$ 且 $f[v] = 0$.

因为此时先手移动到 $v$ 上后，后手有两种情况：

向上走到 $u$ ：此时先手再向下走即可。
向下走：由于 $f[v] = 0$，所以必输。

点击查看代码

#include<bits/stdc++.h>
#define int long long 
using namespace std;

const int N = 3000 + 10;

int n, a[N], f[N];
struct edge{
	int v, next;
}edges[N << 1];
int head[N], idx;

void add_edge(int u, int v){
	edges[++idx] = {v, head[u]};
	head[u] = idx;
} 

bool dfs(int u, int fa){
	for(int i = head[u]; i; i = edges[i].next){
		int v = edges[i].v;
		if(v == fa || a[v] >= a[u]) continue;
		f[u] &= dfs(v, u);
	}
	f[u] ^= 1;
	return f[u];
}

signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	cin >> n;
	for(int i = 1; i <= n; i++) cin >> a[i];
	for(int i = 1; i < n; i++){
		int x, y; cin >> x >> y;
		add_edge(x, y); add_edge(y, x);
	}
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= n; j++) f[j] = 1; 
		if(dfs(i, 0)) cout << i << " ";
	} 
	
	return 0;
}