Giả sử ta bắt đầu với một node bất kỳ với màu đỏ, ta có thể tham lam nếu như cạnh nối với node đó là lẻ thì đầu mút còn lại sẽ tô màu đen, ngược lại sẽ là màu đỏ. Thực hiện như vậy đến khi ~DFS~ toàn bộ cây.

Độ phức tạp: ~O(n)~

Code mẫu

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using ld = long double;
using ull = unsigned long long;
using ii = pair<ll, ll>;

#define fastIO ios::sync_with_stdio(0); cin.tie(0);
#define pb push_back
#define fi first
#define se second
#define numBit(x) (__builtin_popcountll(1ll * (x)))
#define getBit(x, i) ((x) >> (i) & 1)
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()

template<class X, class Y>
    bool minimize(X &x, const Y &y) {
        X eps = 1e-9;
        if (x > y + eps) {
            x = y;
            return true;
        } else return false;
    }
template<class X, class Y>
    bool maximize(X &x, const Y &y) {
        X eps = 1e-9;
        if (x + eps < y) {
            x = y;
            return true;
        } else return false;
    }

const int N = 1e5 + 7;

int n;
bool color[N];
vector<ii> adj[N];

void dfs(int u, int par, bool odd) {
    if (!odd) color[u] = 1;
    for (auto [v, w]: adj[u]) if (v != par) {
        dfs(v, u, (w & 1) ^ odd);
    }
}

int main() {
#ifndef ONLINE_JUDGE
    freopen("test.inp", "r", stdin);
    freopen("test.out", "w", stdout);
#endif
    cin >> n;
    for (int i = 1, u, v, w; i <= n; i++) {
        cin >> u >> v >> w;
        adj[u].pb(ii(v, w)); adj[v].pb(ii(u, w));
    } dfs(1, 1, 0);
    for (int i = 1; i <= n; i++) cout << color[i] << ' ';
}