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;
}