题解 AT2307 【Tree Game】

2019-10-14 08:32:02


广告

考虑 $u$ 是必胜点的条件是什么。显然,应该存在一个相连的节点 $v$ ,满足 $a_v<a_u$ 且 $v$ 是必败点。

这样子的话,先后手就会在 $(u,v)$ 上反复横跳,然后后手就输了。

正确性应该比较显然...?

那么只需要 dfs 判断即可。

// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=3000+10;

int n,a[N];

struct edge { int v,nxt; } e[N<<1];
int head[N];
inline void addEdge(int u,int v) {
    static int cnt=0;
    e[++cnt]=(edge){v,head[u]},head[u]=cnt;
}

int f[N];
inline void dfs(int u,int fa) {
    f[u]=0;
    for (re int i=head[u];i;i=e[i].nxt) {
        int v=e[i].v; if (v==fa||a[v]>=a[u]) continue;
        dfs(v,u); if (!f[v]) f[u]=1;
    }
}

int main() {
    n=read();
    for (re int i=1;i<=n;++i) a[i]=read();
    for (re int i=1;i<n;++i) {
        int u=read(),v=read();
        addEdge(u,v),addEdge(v,u);
    }
    for (re int i=1;i<=n;++i) {
        dfs(i,0);
        if (f[i]) printf("%d ",i);
    }
    puts("");
    return 0;
}