AtCoder Grand Contest 014 B - Unplanned Queries

問題

　頂点の木が与えられ、最初は全ての辺にが書き込まれている。頂点を結ぶパス上の全ての辺に対して書かれている数をするクエリ個あり、最終的に書かれた数が全て偶数になったとする。このような木が存在するかどうかを判定せよ。

解法

　(0-originとして)頂点を根として考える。他の頂点は頂点から距離であるような木を考えたとき、これが条件を満たすかどうかの判定は各頂点がに登場する回数を数えていけば簡単。このような木でできないとき、頂点を根とすることは変えずに上手く繋ぎ変えても結局偶奇性の破綻は解消できないので、この判定が全て。

#include"bits/stdc++.h"
using namespace std;
using ll = long long;

int main() {
    ll N, M;
    cin >> N >> M;

    vector<ll> edge_num(N, 0);
    for (ll i = 0; i < M; i++) {
        ll a, b;
        cin >> a >> b;
        a--; b--;
        if (a > b) {
            swap(a, b);
        }

        if (a == 0) {
            edge_num[b]++;
        } else {
            edge_num[a]++;
            edge_num[b]++;
        }
    }

    for (ll i = 1; i < N; i++) {
        if (edge_num[i] % 2 != 0) {
            cout << "NO" << endl;
            return 0;
        }
    }

    cout << "YES" << endl;
}

反省・感想

　最初に考えた方針が当たって15分くらいでAC。しかし厳密な証明はしていなくて、なんとなくこれで通りそうという雰囲気による提出をしただけである。解説PDFで言われていることが一瞬理解できなかったが、ほぼ同じことを言っている。厳密な証明はこうやってやるのか。

　LCA(Lowest Common Ancestor:最近共通祖先)という考え方は重要そうだ。頂点に対して根をとするとという式が成り立つというのも覚えておいた方がよさそう。

　木が出てきたら根を適当に決めて考えてみるというのが頭に浮かんだ瞬間解けたので、これも良かった。