分数: 400 点
问题陈述
我们有一棵树 N 顶点编号 1 to N。 的 i树中的第一条边连接顶点 u_i 和顶点 v_i,其长度为 w_i。 您的目标是将树中的每个顶点绘制为白色或黑色(可以将所有顶点绘制为相同的颜色),以便满足以下条件:
- 对于任何两个涂成相同颜色的顶点,它们之间的距离是偶数。
找到满足条件的顶点着色并打印它。可以证明,在该问题的约束下,至少存在一种这样的着色。
约束
- 输入中的所有值都是整数。
- 1 \leq N \leq 10^5
- 1 \leq u_i < v_i \leq N
- 1 \leq w_i \leq 10^9
输入
输入由标准输入按以下格式给出:
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 如果它被漆成黑色。
如果有多种颜色满足条件,则接受其中任何一种。
示例输入 1
3 1 2 2 2 3 1
示例输出 1
0 0 1
示例输入 2
5 2 5 2 2 3 10 1 3 8 3 4 2
示例输出 2
1 0 1 0 1