Codeforces #300 Div1 E. Demiurges Play Again

適度に迷う良い問題。
http://codeforces.com/contest/538/problem/E

問題

N頂点の根付き木を考える。
この木に葉がM個あるとして、各葉に1～Mのスコアを1個ずつふる。

ここで2人でゲームを行う。
初期状態で駒が根にあり、2人は交互に駒を何れかの子頂点に動かす。
最終的に到達した葉のスコアがゲームのスコアである。
この際、先手はスコアを最大化、後手は最小化しようとする。

葉へのスコア配置を任意に選べるとき、ゲームの結果のスコアの最大値と最小値を求めよ。

解法

最大値と最小値をそれぞれ個別に求める。
最初に前処理として各頂点のサブツリーの頂点数を求めておくと良い。

• 最大値の方は、後手が避けることができる葉に対し、スコアを多い順に割り当てればよい。
  • そのためには後手が避けることができる頂点の最大数を求めればよい。
  • 先手は、子頂点のうち、結果的に後手が避けられる数が最小になる頂点を選ぶ。
  • 後手は、各子頂点に行ったときに避けられる頂点の和が避けられる頂点の和。

• 最小値の方は、先手が避けることができる葉に対し、スコアを小さい順に割り当てればよい。
  • そのためには先手が避けることができる頂点の最大数を求めればよい。
  • 先手は、各子頂点に行ったときに避けられる頂点の和が避けられる頂点の和。
  • 後手は、子頂点のうち、結果的に避けられる数が最小になる頂点を選ぶ。

int N;
int NL[202000];
vector<int> E[202000];

int dfs(int cur) {
	if(E[cur].empty()) {
		NL[cur]=1;
	}
	else {
		FORR(r,E[cur]) NL[cur]+=dfs(r);
	}
	return NL[cur];
}

int getmin(int cur,int depth) {
	if(NL[cur]==1) return 1;
	int ret=0;
	if(depth==0) {
		FORR(r,E[cur]) ret += getmin(r,1);
	}
	else {
		ret=300000;
		FORR(r,E[cur]) ret = min(ret,getmin(r,0));
	}
	return ret;
}

int getmax(int cur,int depth) {
	if(NL[cur]==1) return 1;
	
	int ret=0;
	if(depth==0) {
		FORR(r,E[cur]) ret = max(ret,NL[cur]-NL[r]+getmax(r,1));
	}
	else {
		ret=1;
		FORR(r,E[cur]) ret += getmax(r,0)-1;
	}
	return ret;
}


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N-1) cin>>x>>y, E[x-1].push_back(y-1);
	dfs(0);
	_P("%d %d\n",getmax(0,0),getmin(0,0));
}

まとめ

この問題結構迷ったけど、無事解けて良かった。