[atcoder2307] tree game

The question

There is a tree. , Each node has A[i] A stone ,A Start putting a piece on any node , Then from A Start ,A,B Take turns
Subtract the number of stone nodes of the current chess piece 1
Move the chess pieces to the adjacent nodes
No operator can input
seek A Start putting the pieces where you want to win .

Answer key

nature ： A chess piece will not go where there are more stones than itself （ If you go this way , The other party can come back , One chess piece is missing , The other side is more than themselves , We cannot win the war of attrition ...）
Then we can directly simulate the calculation NP state
Enumerate a point as a starting point , then dfs Traverse , Find out all NP

Code

#include<cstdio> #include<vector> #include<algorithm> using namespace std; const int MAXN=3005; int n,A[MAXN]; vector<int> adj[MAXN]; bool st[MAXN]; void dfs(int u,int fa=0) {
      st[u]=false; A[u]--; for(int i=0;i<(int)adj[u].size();i++) {
      int v=adj[u][i]; if(v==fa||A[v]>A[u]) continue; dfs(v,u); if(st[v]==false) {
      st[u]=true; break; } } A[u]++; } int main() {
      scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&A[i]); for(int i=1;i<n;i++) {
      int u,v; scanf("%d%d",&u,&v); adj[u].push_back(v); adj[v].push_back(u); } for(int i=1;i<=n;i++) {
      dfs(i); if(st[i]) printf("%d ",i); } puts(""); return 0; }