Description
有一棵(n)个节点的树（(n le 3000)），第(i)条边连接(a_i,b_i)，每个节点(i)上有(A_i)个石子，高桥君和青木君将在树上玩游戏。
首先，高桥君会选一个节点并在上面放一个棋子，然后从高桥君开始，他们轮流执行以下操作：
（1）从当前棋子占据的点上移除一个石子；
（2）将棋子移动到相邻节点
如果轮到一个人执行操作时棋子占据的点上没有石子，那么他就输了 。
请你找出所有的点(v)，使得如果高桥君在游戏开始时把棋子放到(v)上，他可以赢。（按编号从小到大输出）
Solution
首先两个人的行动是互相约束的。
假设当前在节点(u)，先手能耗死后手（即先手必胜）当且仅当对于其所有相邻点，至少存在一个点(v)，满足：
（1）(a_u>a_v)
（2）(v)先手必败。
首先（1）是这题对局的一种博弈过程，设想有且只有两个点(u)和(v)，若初始时棋子在(u)，且(a_u>a_v)，那么反复走，后手必死。
因此只要先手走向了如是的(v)，后手必定不会在这条边上反复横跳，之后也不会，因为一旦后手走回来，先手继续走回(v)，可以把后手耗到死。
那么后手必定也只能在(v)中寻找机会。只要(v)是先手必败态，那么(u)即为先手必胜态，因为先手可以主动走到(v)引出必败态。
定义(u)是先手必败态当且仅当不存在上述(v)。
首先，如果先手走向的点(v)满足(a_ule a_v)，后手可以走回(u)，因为反复横跳后先手必死。因此这些点不可走。
走向的点(v)满足(a_u>a_v)时，若(v)为先手必胜态，那么(u)肯定不能走这一步；如果不存在(v)是先手必败态，那么先手就无路可走了。
综上，因为必须走一步，所以(u)是先手必败态，当且仅当不存在(v)满足(a_u>a_v)且(v)先手必败。
对于每一个点，以其为根深搜，设(f_u)表示(u)是必胜还是必败，自底向上DP一遍。
为什么可以自底向上单向考虑？我们是要DP判定每个点(u)是不是必胜态，即要找到是否存在相邻点(v)满足(a_u>a_v)，并深搜计算它们的必胜必败态。而对于不满足条件的(v)，我们甚至不需要递归进去计算，因为先手不会选择走这边。所以，会选择(u)的父亲作为(v)吗？不会。每递归到(u)时，也就意味着，是上一步的先手想逼我（当前先手）反复横跳才走这一步过来，即满足(a_{fa}>a_u)，所以当前先手肯定不能走父亲回去和他反复横跳。因此可以说，DP过程中，是一路向下，走后继递归计算的。
时间复杂度(mathcal O(n^2))。
我真TM可以退役了。
Code
#include <cstdio>
using namespace std;
const int N=3005;
int n,a[N],f[N];
int h[N],tot;
struct Edge{int v,next;}e[N*2];
inline void addEdge(int u,int v){
e[++tot]=(Edge){v,h[u]}; h[u]=tot;
e[++tot]=(Edge){u,h[v]}; h[v]=tot;
}
void readData(){
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",a+i);
int u,v;
for(int i=1;i<n;i++){
scanf("%d%d",&u,&v);
addEdge(u,v);
}
}
void dfs(int u,int fa){
f[u]=0;
for(int i=h[u],v;i;i=e[i].next)
if((v=e[i].v)!=fa&&a[u]>a[v]){
dfs(v,u);
if(f[v]==0){
f[u]=1;
return;
}
}
}
void solve(){
for(int u=1;u<=n;u++){
dfs(u,0);
if(f[u])
printf("%d ",u);
}
}
int main(){
readData();
solve();
return 0;
}