https://atcoder.jp/contests/abc126/tasks/abc126_d
解説
https://atcoder.jp/contests/abc126/submissions/5477114
以下のルールで着色していく。
辺の長さが偶数なら2つの頂点は同じ色で着色する。
辺の長さが奇数なら2つの頂点は異なる色で着色する。
これを守ってDFSで着色すれば答えが求まる。
int N; vector<pair<int, int>> E[101010]; //--------------------------------------------------------------------------------------------------- int ans[101010]; void dfs(int cu, int pa = -1, int col = 0) { ans[cu] = col; fore(p, E[cu]) { if (p.first == pa) continue; if (p.second % 2 == 0) dfs(p.first, cu, col); else dfs(p.first, cu, 1 - col); } } //--------------------------------------------------------------------------------------------------- void _main() { cin >> N; rep(i, 0, N - 1) { int a, b, c; cin >> a >> b >> c; a--; b--; E[a].push_back({ b,c }); E[b].push_back({ a,c }); } dfs(0); rep(i, 0, N) printf("%d\n", ans[i]); }