読者です 読者をやめる 読者になる 読者になる

AtCoder AGC 014 D: Black and White Tree

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int N;
    cin >> N;
    vector<set<int> > G(N);
    rep(i, N - 1) {
        int a, b;
        cin >> a >> b;
        --a;
        --b;
        G[a].insert(b);
        G[b].insert(a);
    }

    /*
    完全マッチングが存在するか判定
    木なので、葉は必ずその親とペアになる。葉から貪欲にペアを作っていく。
    */
    // 頂点vを取り除いた, 頂点vは葉への辺をもつ。
    vi rem(N), lev(N);
    queue<int> q;
    rep(i, N)if (sz(G[i]) == 1)lev[*G[i].begin()] = 1;
    rep(i, N)if (lev[i])q.push(i);

    while (sz(q)) {
        int u = q.front(), flag=0; q.pop();
        // uは葉vと辺(u, v)でつながっている
        each(v, G[u]) {
            if (sz(G[v]) == 1 && !flag++) {
                // vは葉なので黒く塗る
                rem[v] = 1;
            }
            G[v].erase(u);
            if (sz(G[v]) == 1) {
                // 辺を減らすことで、頂点vが葉になった。
                int w = *G[v].begin();
                q.push(w);
            }
        }
        // uを白に塗る
        rem[u] = 1;
    }

    /* 
    完全マッチングが存在しなかった。
    完全マッチングが存在しない木を
    根付き木として考えて
    最も深い葉で共通の頂点を親として持つものがあるならば、その親を白く塗れば先手の勝ち。(1)
    そうでない場合は、この2頂点を取り除く。その木にも当然完全マッチングが存在せず、よりサイズの小さい問題になった。
    これを繰り返すと(1)に至るかまたは頂点数が1になるって先手の番になる。どちらも先手の勝ち。
    */
    rep(i, N)if (!rem[i] && sz(G[i]) == 0) {
        cout << "First" << endl;
        return 0;
    }
    // 完全マッチングが存在した
    // その場合、先手に対して後手は完全マッチングでペアになる頂点を選べばいい。
    cout << "Second" << endl;
}