AtCoder

Luogu

分析

考虑一个菊花、一开始在中心的情况。显然先手只会往一个 $a_i$ 小的方向走才能胜利,因为双方会在这条边上反复横跳,然后后手先跳完。

考虑加上一层。假设一开始在 $u$,$v$ 子树先手必胜,则先手一定不会往 $v$ 走;假设一开始在 $u$,$v$ 子树先手必败,则先手可以往 $v$ 走,且后手一定回到 $u$,故当 $a_u<a_v$ 时先手胜利。

因此只需要枚举每个点为起点,然后做一遍树形 DP 即可:设 $dp_u$ 表示 $u$ 子树是否先手必胜,转移即判断是否存在满足 $a_v<a_u$ 且 $dp_v=0$ 的子树。

代码

// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

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];
void addEdge(int u,int v) {
    static int cnt=0;
    e[++cnt]=(edge){v,head[u]},head[u]=cnt;
}

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

int main() {
    n=read();
    for (int i=1;i<=n;++i) a[i]=read();
    for (int i=1;i<n;++i) {
        int u=read(),v=read();
        addEdge(u,v),addEdge(v,u);
    }
    for (int i=1;i<=n;++i) { dfs(i,0); if (dp[i]) printf("%d ",i); }
    puts("");
    return 0;
}
最后修改:2020 年 04 月 21 日 09 : 34 PM