SRM603Div1Easy
問題
コストを持つN個のノードとN-1個のエッジを持つツリーが与えられ、二人のプレイヤーで行うゲームを考える。プレイヤーは1つのエッジを選び、そのエッジとそれにより2つに分割されるどちらかのサブツリーを削除する。最後に残ったひとつのノードのコストがゲームのコストとなる。初めのプレイヤーはコストを最大化したく、次のプレイヤーは最小化したい。お互いが最適な戦略をとった場合の結果を求めよ。
解法
リーフの最大値が結果となる。
二人のプレイヤーの目的は正反対なので、最初のプレイヤーが親となっているノードを最後に残したい場合、次のプレイヤーはそのノードを削除したいということになる。反対も同様であるため、最適な戦略は自分のターンで必ず終えることができるノードを選択することになる。よって、最初のプレイヤーは最大化したいので、リーフの最大値が答えとなる。
計算量