← 返回题目列表

AtCoder · abc126_d

D. 偶数关系

中文机器翻译题面 查看原题

分数: 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