ABC126D Even Relation - urashima0429

考えたこと

求めるグラフの条件は

同じ色に塗られた 任意の 2 頂点について、その距離が偶数である。

であるが、任意の2頂点間の距離を求めて、すべてが偶数かを確認する必要はない。なぜなら考えるグラフは木なので、閉路を持たず、各頂点間の距離は適当に選んだある根からの距離で一意に表現できるからだ。（実際、(1)を見れば一意に表せることがわかる。）

f:id:urashima0429:20190522111847p:plain — 図

そこで頂点iと頂点jの距離を $d(i,j)$ 、根を $r$ とすると $(1) : d(i, j) = d(r, i) + d(r, j) - 2d(r, w)$

と表せる。 $d(i,j)$ が偶数であるという条件について考えると(1)より $d(i,j) = 2n (n \in \mathcal{N})$
$\Leftrightarrow$ $d(r, i) + d(r, j) - 2d(r, w) = 2n$
$\Leftrightarrow$ $d(r, i) + d(r, j) = 2(n + d(r, w))$
すなわち $d(i, j)$ が偶数であることは $d(r, i)$ と $d(r, j)$ の偶奇が一致することと同値であることが分かる。

よってやることは
根 $r$ と各頂点 $i$ との距離 $d(r,i)$ を求めて( $O(N)$ )、 $d(r,i)$ の偶奇で01を出力すればよい。

#include <iostream>
#include <vector>
using namespace std;

const int MAX_N = 1e5;
struct edge{ int to, weight; };
vector<edge> Edges[MAX_N + 10];

int dir[MAX_N];

void dfs(int vertex, int parent, int distance){
    dir[vertex] = distance;
    for (auto e : Edges[vertex]){
        if (e.to == parent) continue;
        dfs(e.to, vertex, distance + e.weight);
    }
}

int main(){
    int N;
    cin >> N;
    for (int i = 0; i < N-1; ++i){
        int u, v, w;
        cin >> u >> v >> w;
        --u; --v;
        Edges[u].push_back(edge{v, w});
        Edges[v].push_back(edge{u, w});
    }

    dfs(0, -1, 0);
    for (int i = 0; i < N; ++i){
        if (dir[i] & 1){
            cout << 1 << endl;
        }else{
            cout << 0 << endl;
        }
    }
}