はまやんはまやんはまやん

hamayanhamayan's blog

Even Relation [AtCoder Beginner Contest 126 D]

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]);
}