[??记录]AT2307 [AGC010F] Tree Game
command_block
·
·
个人记录
题意 ： 给出一棵 n 个节点的树，点有点权。树上的某个节点有一个棋子。
A , B 两人在树上轮流操作， A 先手。
每次操作将棋子所在的点点权减一，然后将棋子移动到相邻的点。
若点权已经为 0 ，则操作者判负。
对于每个棋子的起始位置，判定是否先手必胜。
------------
在博弈题中，分析时常常因为两人相互制约，而可以简化方案。
首先将整棵树黑白染色，先后手都只会走各自的颜色的点。
考虑一类较为简单的情况 ： 菊花图。且棋子初始时在中心。
此时，先手一定将棋子移动到 $c$ （点权）最小的分支，而后手只能往回移动。先手必胜等且仅当 $c_u>\min c_v$。
这能推出，若棋子所在点 $u$ 周围的点权都 $\geq c_u$ ，则先手必败。
若棋子在点 $u$ ，想要从 $u$ 走向 $v$ ，若 $c_u\leq c_v$ ，则后手可以将棋子移动回 $c_u$ ，先手无法越过 $v$。
（若存在先手必胜的策略，那么一定不是硬闯 $c_u\leq c_v$ 的 $v$ ，因为会被赶回来）
这样，每个点都只能前往权值比自己小的点，转移就变为了 $\rm DAG$ ，容易一次 $\rm dfs$ 得到答案。
对于每个点都搜一次即可。
```cpp
#include<algorithm>
#include<cstdio>
#include<vector>
#define MaxN 3050
using namespace std;
vector<int> g[MaxN];
bool fl[MaxN];int c[MaxN];
void dfs(int u)
{
fl[u]=0;
for (int i=0;i<g[u].size();i++)
if (c[u]>c[g[u][i]]){
dfs(g[u][i]);
if (!fl[g[u][i]]){
fl[u]=1;
break;
}
}
}
int n;
int main()
{
scanf("%d",&n);
for (int i=1;i<=n;i++)scanf("%d",&c[i]);
for (int i=1,u,v;i<n;i++){
scanf("%d%d",&u,&v);
g[u].push_back(v);
g[v].push_back(u);
}
for (int i=1;i<=n;i++){
dfs(i);
if (fl[i])printf("%d ",i);
}return 0;
}
```