TopCoder SRM 603 Div1 Easy MaxMinTreeGame

問題

木が与えられる。各頂点には整数のコストが書かれている。
この木で二人が次のようなゲームをする。

• 二人は交互に手番を繰り返す。
• 手番のプレイヤーは辺を一つ選んで切断し、木を二つに分ける。一方の木を完全に消滅させる。
• 木が頂点一つになったら終了し、それが二人の得点となる。
• 先手は得点を最大化し、後手は得点を最小化する。

互いがベストを尽くすとき、得られる得点を求めよ。

制約条件

頂点≦50
コスト≦10億

方針

一直線のグラフで考えると、両端のうちコストの大きいノードのコストが答え。
何故なら、先手は大きい方のノードを残して初手で終了させることができるので、
ベストを尽くしたときの得点は必ず大きいノード以上になる。

初手で大きいノード取らなかった場合、後手は大きいノードを取って終了させることができるので、ベストを尽くしたときの得点は必ず大きいノード以下になる。

これと全く同じ議論が木でも適用できて、葉のノードのうち最大のコストが答え。

ソースコード

class MaxMinTreeGame {
	public:
	int findend(vector <int> edges, vector <int> costs) {
		int n = costs.size();
		int deg[50] = {}, ans = 0;
		
		rep(i, n - 1){
			deg[i + 1]++;
			deg[edges[i]]++;
		}
		rep(i, n) if(deg[i] == 1) ans = max(ans, costs[i]);
		return ans;
	}
};