ABC126-D: Even Relation

問題概要

問題ページへのリンク

N頂点の木がある。頂点u_i, v_i間の辺の長さはw_iとする
同じ色に塗られた任意の2頂点間について、その距離が偶数になることを満たすように各頂点に色を塗る
そのような塗り分け方を1つ見つけて出力せよ

考察

偶数同士、奇数同士の辺でつながっている頂点をそれぞれ別の色で塗りたいが偶数同士だからといって一意に色が定まるわけではない

なんとなく根から各頂点までの距離の累積和の偶奇を取ることにした
以下のような入力を考える

8
1 2 1
1 3 3
3 4 2
3 5 2
5 6 6
5 7 7
7 8 5

図にすると以下のようになる

頂点1を根とし、各頂点までの距離の累積和を取ると以下のようになる

各頂点までの距離の累積和が直前までの累積和と偶奇が同じだったら今までの色、違ったら別の色で塗る

コード

dfsの引数preは前回訪れた頂点で、後戻りさせないようにしている

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, long long> P; // {to, cost}

int n;
const int N = 100010;
vector<P> G[N];
vector<int> Color(N);

void dfs(int now, int pre, int color, long long acost){ // accumulate_cost
    Color[now] = color; 
    for(int i = 0; i < G[now].size(); i++){
        P p = G[now][i];
        if(p.first == pre) continue;
        long long to_acost = p.second + acost;
        if(to_acost % 2 == acost % 2 ) dfs(p.first, now, color, to_acost);
        else dfs(p.first, now, (color == 1 ? 0 : 1), to_acost);
    }
}


int main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);

    cin >> n;
    for(int i = 0; i < n - 1; i++){
        int a, b;
        long long c;
        cin >> a >> b >> c;
        a--; b--;
        G[a].push_back({b, c});
        G[b].push_back({a, c});
    }
    
    Color.resize(n);
    
    dfs(0, -1, 1, 0);

    for(int i = 0; i < n; i++){
        cout << Color[i] << endl;
    }

    return 0;
}

実際のコードへのリンク