AtCoder ABC #246 : G - Game on Tree 3

遅れて参加したため間に合わず。
https://atcoder.jp/contests/abc246/tasks/abc246_g

問題

根付き木を使った以下の2人制ゲームを考える。
各点にはポイントが設定されている。

初期状態で根頂点にコマが置かれており、各ターンで以下を行う。

• 先手は、任意の頂点を選びポイントを0にする
• その後、後手はコマをいずれかの子頂点に移動する。移動先が葉であればゲーム終了、そうでない場合後手はゲームを終了するか次のターンに進むか選択できる。

ゲーム終了時にコマがある頂点に書かれたポイントが、後手の得られるポイントだとする。
先手はポイントを最小化、後手は最大化したい場合、最終的に後手が得られるポイントはいくらか。

解法

後手がXポイント以上得られるか？を考え、解を二分探索しよう。
dp(v) := コマがvにあり、これから後手がコマを動かそうとするとき、後手がXポイント得させないために先手があらかじめ0ポイントにしなければいけない数
B(v) := vに書かれたポイントがX以上かどうかを示す0/1のバイナリ値
とする。

vにX以上のポイントが書かれていなければ、vのSubTree内の頂点を1つ0ポイントにできるので、子頂点cに対し
dp(v) = max(sum(dp(c))-1,0) + B(v)
となる。
あとは根頂点rに対しdp(r)が0かどうかを判定しよう。

int N;
int A[202020];
int B[202020];
vector<int> E[202020];

int dfs(int cur,int pre) {
	int dp=0;
	FORR(e,E[cur]) if(e!=pre) dp+=dfs(e,cur);
	
	return max(dp-1,0)+B[cur];
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N-1) cin>>A[i+1];
	FOR(i,N-1) {
		cin>>x>>y;
		E[x-1].push_back(y-1);
		E[y-1].push_back(x-1);
	}
	
	int ma=0;
	for(i=29;i>=0;i--) {
		int tmp=ma+(1<<i);
		FOR(j,N) B[j]=A[j]>=tmp;
		
		if(dfs(0,0)) ma=tmp;
	}
	cout<<ma<<endl;
}

まとめ

先手ではなく後手のポイントを最大化する問題は割と珍しい？