CODE THANKS FESTIVAL 2015 F - お祭りとお菓子

問題

code-thanks-festival-2015-open.contest.atcoder.jp

解法

ここでは「勝つ」というのは「実 1 を食べる」ということを指します。また, 「実(み)」と「頂点」はしばしば同じ意味です。

まず, 頂点 1 の次数が 1 なら A さんは速攻で食べれば良いので A が勝ちます。

それ以外の場合は, 実は頂点数のみに依存して勝敗が決まります。これはなぜかというと, どちらも実 1 を取られないようにするために, 頂点 1 に隣接した頂点はなるべく取り除かないようにするはずです。

よって, 最終的に残るのは, 頂点 1 とそれに隣接する頂点のみになり, 次にどちらが実 1 を取るかは 偶奇にのみ依存します。

const int MAXN = 100010;
vector<int> G[MAXN];

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N;
    cin >> N;
    for (int i = 0; i < N-1; i++) {
        int s, t;
        cin >> s >> t;
        s--; t--;
        G[s].push_back(t);
        G[t].push_back(s);
    }
    if (G[0].size() == 1) {
        cout << "A" << endl;
    } else {
        if (N%2) cout << "B" << endl;
        else cout << "A" << endl;
    }
    return 0;
}