問題概要

構造がわからないN頂点を持つ木が用意されている。M個のクエリが実行される。

ここで言うクエリとは(a,b)という形で与えられ、クエリを実行すると頂点aとbを結ぶときに通るパスに書かれた数を+1する。初期状態ですべての辺には0が書かれている。

クエリをすべて実行した後に、すべての辺に書かれた数が2の倍数になるような木の構造が存在するなら"YES"、それ以外は"NO"を出力せよ！という問題。

考えたこと

すべての頂点において、クエリ(a,b)として現れる回数が、偶数個になるとき"YES"となり、一つでも奇数個になるとき"NO"となる。

理由

まず、ここでaとbのLCAをtと、今回の木の根をrと置く。

(a,b)というクエリを、(a,b)を(a,t), (b,t)と置き変えられる。

(LCAとは、根付き木のある二頂点a,bの共通祖先で最も根から離れている頂点)

aとt間の辺には+1, bとt間の辺には+1とする。

これはaとr間、bとr間に+1をすることと同じである。

なぜなら、aとr間、bとr間に+1をすると、tとr間が+2されてしまうが、それぞれの辺に書かれた辺の数が2の倍数になるかさえわかればいいので、+2と+0は同じに見なされるからだ。

次に、親から一番離れている点でかつクエリ(a,b)として現れる回数が奇数個の点に着目する。

このような点を一つでも含む場合、"NO"になる。

このような点をk、kの親をk'と置く。

このようなkが存在する場合、すべての辺に書かれた数が2の倍数になるような木の構造が存在しない。なぜなら、kとk'を結ぶ辺に書かれた数が奇数になるからだ。また、他のクエリにおける、kとkの親を結ぶ辺に対する加算ではすべて+2される。つまり、(k,k')以外のクエリですべて+2されるから、(k,k')以外による影響を考える必要がない。

上記のような考察が僕の頭では精一杯でした。

ということで、ソースコード！

#include <bits/stdc++.h>
using namespace std;

int main(){
    int n,m;
    cin >> n >> m;
    vector<int> edge_num(n,0);
    for(int i=0;i<m;i++) {
        int a,b;
        cin >> a >> b;
        a--,b--;
        edge_num[a]++;
        edge_num[b]++;
    }
    for(int i=0;i<n;i++) {
        if(edge_num[i]%2 == 1) {
            cout << "NO" << endl;
            return 0;
        }
    }
    cout << "YES" << endl;
    return 0;
}

yapattaのブログ

AtCoder AGC014 B - Unplanned Queries

問題概要

考えたこと

理由