TopCoder SRM603: MaxMinTreeGame

与えられるグラフは木のため、少なくとも２つは葉がある。

先行は、最初のターンで葉だけを残すことができるため、葉の最大コストのスコアを保証することができる。
後攻は、先行が即ゲーム終了しなかった場合だけ、ターンが回ってくる。初期状態の葉のうちの残っている方だけ残すことで、「葉の最大コスト」より大きいスコアを取らないで済む。

上記より、「葉の最大コスト」が答え。

public class MaxMinTreeGame {
    public int findend(int[] edges, int[] costs) {
        int n = edges.Length + 1;
        var degree = new int[n];
        for (int i = 0; i < edges.Length; i++) {
            degree[i + 1]++;
            degree[edges[i]]++;
        }
        return E.Range(0, n).Where(i => degree[i] == 1).Max(i => costs[i]);
    }
}