https://agc010.contest.atcoder.jp/tasks/agc010_f
O(N)で心配になった…。
まずある頂点vに対して、隣接している全ての頂点piに対してA[v]<=A[pi]が成り立つ場合、vからゲームを始めると必ず負けます。
なぜなら高橋君がvからどこに動かしても、青木くんがvに駒を戻せばいいです。そうすればA[v]がいずれ0となり高橋君は負けてしまいます。
なので2人はそのような頂点に駒を動かさないようにするわけですが、そうするとvからA[v]<=A[pi]を満たす頂点piに動かすのは両プレーヤーにとって最適ではないことがわかります。
なぜなら次のプレーヤーはvに駒を動かせばvから駒を動かす前の状態とほとんど同じになり、A[v]とA[pi]が1小さくなっただけとなります。
ここでA[v]とA[pi]の大小関係は変わらず、A[v]<=A[pi]を満たす頂点piが新たに出来てしまう可能性があります。
なのでA[v]>A[pi]を満たす頂点にのみ移動するのが最適で、v->piに辺を張った有向グラフでdpすればO(N)で全ての頂点について勝敗がわかります。
大小関係が本質だとわかればそんな難しくはないですね。実際コンテスト中かなり解かれています。
int N; int A[MAX_N]; vector<int> G[MAX_N]; bool used[MAX_N]; int dp[MAX_N]; void loop(int v) { used[v] = true; dp[v] = 0; rep(i, 0, sz(G[v])) { int n = G[v][i]; if(A[v] > A[n]) { loop(n); dp[v] |= (dp[n] ^ 1); } } } void solve() { cin >> N; rep(i, 0, N) cin >> A[i]; rep(i, 0, N - 1) { int a, b; cin >> a >> b; a--; b--; G[a].pb(b); G[b].pb(a); } rep(i, 0, N) { if(!used[i]) loop(i); } vector<int> ans; rep(i, 0, N) { if(dp[i]) ans.pb(i); } rep(i, 0, sz(ans)) { cout << ans[i] + 1 << " "; } cout << "\n"; }