Description
有一棵nn个节点的树，第ii条边连接ai,biai,bi，每个节点ii上有AiAi个石子，高桥君和青木君将在树上玩游戏
首先，高桥君会选一个节点并在上面放一个棋子，然后从高桥君开始，他们轮流执行以下操作：
- 从当前棋子占据的点上移除一个石子
- 将棋子移动到相邻节点
如果轮到一个人执行操作时棋子占据的点上没有石子，那么他就输了
请你找出所有的点vv，使得如果高桥君在游戏开始时把棋子放到vv上，他可以赢
Input
第一行一个整数nn
第二行nn个整数A1⋯nA1⋯n
接下来行每行两个整数ai,biai,bi表示一条边
Output
以编号递增的顺序在一行中输出所有满足条件的点
Sample Input
Sample Input #1
3
1 2 3
1 2
2 3Sample Input #2
5
5 4 1 2 3
1 2
1 3
2 4
2 5Sample Input #3
3
1 1 1
1 2
2 3Sample Output
Sample Output #1
2Sample Output #2
1 2Sample Output #3HINT
注意答案可能是一个空行
2≤n≤30002≤n≤3000
1≤ai,bi≤n1≤ai,bi≤n
0≤Ai≤1090≤Ai≤109
给出的边构成一棵树
Sol
这道题的数据范围非常小，能够承受\(O(n^2)\)暴力，所以我们枚举哪个点为根，然后进行判断，显然如果一个点是必胜的话，那么存在一个子节点，使得\(v[x]>v[sonx]\)且\(sonx\)是必败态。我们视叶子结点为必败态，然后进行一遍dfs，即可得出根节点的状态。
证明：首先如果\(v[x]<=v[sonx]\)，那么后手完全可以和先手在两个点反复耗下去，于是先手就输了，而必胜态->必败态则是常识。如果有一个点满足上述两个条件，那么后手无论如何也没有能力转入新的必败态。
code
#include <bits/stdc++.h>
using namespace std;
int a[3005],x,y,n;vector<int>e[3005];
int dfs(int x,int fa)
{for(int i=0;i<e[x].size();i++) if(e[x][i]!=fa&&a[x]>a[e[x][i]]&&!dfs(e[x][i],x)) return 1;return 0;
}
int main()
{scanf("%d",&n);for(int i=1;i<=n;i++) scanf("%d",&a[i]);for(int i=1;i<n;i++) scanf("%d%d",&x,&y),e[x].push_back(y),e[y].push_back(x);for(int i=1;i<=n;i++) if(dfs(i,0)) printf("%d ",i);
}