AGC010F: Tree Game

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";
}