【博弈】【树形DP】AGC010F Tree Game

分析：

有点坑的NP状态转移的题。
考虑将最开始的点设为根，$f(x)$表示仅在以x为根的子树中的NP状态。
转移就是：
当且仅当$x$的某个儿子$v$，满足$f(v)=0$且$a_v<a_x$时，$f(x)=1$

证明很简单，如果$f(v)=0$，那么当前在x这个玩家，肯定想把游戏转移到v的子树中进行。然而对方肯定要抵抗，那么就会在(v,x)之间来回鬼畜，因为$a_v<a_x$，所以当$a_v$减为1时，这个人就不再敢抵抗了，因为一旦他移动到x，那么下一次对方就再移动到v（然后石子为0个），他就输了。

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#define SF scanf
#define PF printf
#define MAXN 3010
using namespace std;
int n;
int a[MAXN];
struct node{
    int x;node *nxt;	
}edge[MAXN*2];
node *head[MAXN],*ncnt=edge;
int u,v;
void add_edge(int x,int y){
    ++ncnt;ncnt->x=y;ncnt->nxt=head[x];	head[x]=ncnt;
}
bool dfs(int x,int fa){
    bool res=0;for(node *v=head[x];v!=NULL;v=v->nxt){
    int u=v->x;if(u==fa)continue;if(dfs(u,x)==0&&a[u]<a[x])res=1;}return res;
}
int main(){
    SF("%d",&n);for(int i=1;i<=n;i++)SF("%d",&a[i]);for(int i=1;i<n;i++){
    SF("%d%d",&u,&v);add_edge(u,v);add_edge(v,u);}for(int i=1;i<=n;i++)if(dfs(i,0))PF("%d ",i);
}