Even Relation

题目描述

我们有一棵包含 $N$ 个顶点、编号为 $1$ 到 $N$ 的树。 树中的第 $i$ 条边连接顶点 $u_i$ 和顶点 $v_i$，其长度为 $w_i$。 你的目标是将树的每个顶点涂成白色或黑色（所有顶点涂成同一颜色也是允许的），使其满足以下条件：

对于任意两个涂成相同颜色的顶点，它们之间的距离为偶数。

找到一个满足该条件的着色并输出。可以证明在本题的约束下至少存在一个这样的着色。

输入格式

输入按以下格式由标准输入给出： $N$ $u_1$ $v_1$ $w_1$ $u_2$ $v_2$ $w_2$ $.$ $.$ $.$ $u_{N - 1}$ $v_{N - 1}$ $w_{N - 1}$

输出格式

输出一个满足条件的顶点着色，格式为 $N$ 行。 第 $i$ 行应当包含 $0$，如果顶点 $i$ 被涂为白色；若被涂为黑色则输出 $1$。 若存在多个满足条件的着色，任意一个均可。

3
1 2 2
2 3 1

0
0
1

5
2 5 2
2 3 10
1 3 8
3 4 2

1
0
1
0
1

提示

所有输入值均为整数。 $1 \leq N \leq 10^5$ 1 \leq u_i < v_i \leq N $1 \leq w_i \leq 10^9$

标签: AtCoder|abc126D

来源

AtCoder|abc126D