AT_abc126_d [ABC126D] Even Relation

题目描述

有一棵包含 $N$ 个顶点的树。这棵树的第 $i$ 条边连接顶点 $u_i$ 和顶点 $v_i$，其长度为 $w_i$。你需要将这棵树的所有顶点用白色和黑色两种颜色进行染色（允许所有顶点染成同一种颜色），使得满足以下条件：

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

请输出一种满足条件的顶点染色方案。根据本题的限制条件，可以证明一定存在至少一种满足条件的染色方案。

输入格式

输入通过标准输入给出，格式如下：

$N$
$u_1$ $v_1$ $w_1$
$u_2$ $v_2$ $w_2$
$\cdots$
$u_{N-1}$ $v_{N-1}$ $w_{N-1}$

输出格式

请输出一种满足题意条件的顶点染色方案。输出共 $N$ 行，第 $i$ 行输出顶点 $i$ 的颜色：如果染成白色则输出 0，如果染成黑色则输出 1。

如果存在多种满足条件的染色方案，输出任意一种均可。

样例 1

输入

3
1 2 2
2 3 1

输出

0
0
1

样例 2

输入

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$

由 ChatGPT 4.1 翻译