Problem:


Score : 400 points

Problem Statement

We have a tree with N vertices numbered 1 to N.
The i-th edge in the tree connects Vertex u_i and Vertex v_i, and its length is w_i.
Your objective is to paint each vertex in the tree white or black (it is fine to paint all vertices the same color) so that the following condition is satisfied:

For any two vertices painted in the same color, the distance between them is an even number.

Find a coloring of the vertices that satisfies the condition and print it. It can be proved that at least one such coloring exists under the constraints of this problem.

Constraints

All values in input are integers.

1 \leq N \leq 10^5

1 \leq u_i < v_i \leq N

1 \leq w_i \leq 10^9

Input

Input is given from Standard Input in the following format:

N
u_1 v_1 w_1
u_2 v_2 w_2
.
.
.
u_{N - 1} v_{N - 1} w_{N - 1}

Output

Print a coloring of the vertices that satisfies the condition, in N lines.
The i-th line should contain 0 if Vertex i is painted white and 1 if it is painted black.

If there are multiple colorings that satisfy the condition, any of them will be accepted.

Sample Input 1

3
1 2 2
2 3 1

Sample Output 1

0
0
1

Sample Input 2

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

Sample Output 2

1
0
1
0
1



Sample input:
3
1 2 2
2 3 1


Sample output:
0
0
1

Submission status: Accepted

Solution code:
import sys
INF = 10**18
import sys
from heapq import heapify,heappop,heappush,heappushpop


class PriorityQueue:
    
    #初期化
    def __init__(self,heap):
        self.heap = heap
        heapify(self.heap)
    
    #値の追加
    def push(self,item):
        heappush(self.heap,item)
    
    #値の取り出し
    def pop(self):
        return heappop(self.heap)
    
    #値を追加して取り出し
    def pushpop(self,item):
        return heappushpop(self.heap,item)
    
    #データ構造の中身を見る
    def __call__(self):
        return self.heap
    
    #heapの長さ
    def __len__(self):
        return len(self.heap)

def dijkstra(s):
    #始点sから各頂点への最短距離
    d = [INF] * n
    used = [True] * n #True:未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    q = PriorityQueue(edgelist)
    for e in edge[s]:
        q.push(e)
    while len(edgelist):
        minedge = q.pop()
        #まだ使われてない頂点の中から最小の距離のものを探す
        if not used[minedge[1]]:
            continue
        v = minedge[1]
        d[v] = minedge[0]
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                q.push([e[0]+d[v],e[1]])
    return d

if __name__ == "__main__":
    n = int(input())
    edge = [[] for i in range(n)]
    for i in range(n-1):
        u,v,w = map(int,input().split())
        u-=1
        v-=1
        edge[u].append([w,v])
        edge[v].append([w,u])
    ans = dijkstra(0)
    c_ans = [0]*n
    for i in range(n):
        if ans[i]%2 == 0:
            c_ans[i] = 0
        else:
            c_ans[i] = 1
    for i in range(n):
        print(c_ans[i])

Submission status: Accepted

Solution code:
n = int(input())
v = []
for i in range(n + 10):
    v.append([])

for _ in range(n-1):
    a,b,w = map(int, input().split())
    v[a].append([b,w])
    v[b].append([a,w])

import collections
q = collections.deque([])
used = [None] * (n+10)
q.append([1,0])
while len(q) > 0:
    cur, color = q.pop()
    #print(cur,color)
    used[cur] = color
    for i in range(len(v[cur])):
        nind, w = v[cur][i]
        if used[nind] != None:
            continue
        if w % 2 == 0:
            q.append([nind, color])
        else:
            q.append([nind, 1-color])
for i in range(1, n+1):
    print(used[i])

Submission status: Accepted

Solution code:
N = int(input())
G = [[] for i in range(N)]
for i in range(N-1):
    A,B,C = list(map(int,input().split()))
    G[A-1].append([C,B-1]) #重み、向かう先の順番
    G[B-1].append([C,A-1])

from collections import deque
dist = [None]*N
que = deque([0])
dist[0] = 0
while que:
    v = que.popleft()
    d = dist[v]
    for c,w in G[v]:
        if dist[w] is not None:
            continue
        dist[w] = d + c
        que.append(w)
for i in range(N):
    print(dist[i]%2)

Submission status: Accepted

Solution code:
from collections import deque
n = int(input())
to = [[] for _ in range(n)]
for i in range(n-1):
    u, v, w = map(int, input().split())
    u , v = u-1, v-1
    to[u].append([v, w])
    to[v].append([u, w])
color = [-1] * n
color[0] = 0
q = deque([0])
while q:
    v = q.popleft()
    for u, w in to[v]:
        if color[u] != -1:
            continue
        if w % 2 != 0:
            color[u] = color[v] ^ 1
        else:
            color[u] = color[v]
        q.append(u)
for c in color:
    print(c)

Submission status: Accepted

Solution code:
from collections import deque
n = int(input())
to = [[] for _ in range(n)]
for i in range(n-1):
    u, v, w = map(int, input().split())
    u , v = u-1, v-1
    to[u].append([v, w])
    to[v].append([u, w])
color = [-1] * n
color[0] = False
q = deque([0])
while q:
    v = q.popleft()
    for u, w in to[v]:
        if color[u] != -1:
            continue
        if w % 2 != 0:
            color[u] = color[v] ^ 1
        else:
            color[u] = color[v]
        q.append(u)
for c in color:
    print(int(c))

Submission status: Accepted

Solution code:
from collections import deque

n = int(input())
L = [[] for _ in range(n)]
for _ in range(n-1):
    u, v, w = map(int, input().split())
    L[u-1].append((v-1, w))
    L[v-1].append((u-1, w))
d = [-1] * n
d[0] = 0
c = [0] * n
c[0] = 0
q = deque([0])
while q:
    t = q.popleft()
    dist = d[t]
    for v, w in L[t]:
        if d[v] < 0:
            d[v] = dist + w
            if d[v] % 2:
                c[v] = 1
            q.append(v)
for x in c:
    print(x)

Submission status: Accepted

Solution code:
import sys
from collections import deque

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60


def main():
    N = int(readline())
    G = [[] for _ in range(N)]
    for _ in range(N - 1):
        u, v, w = map(int, readline().split())
        G[u - 1].append((v - 1, w))
        G[v - 1].append((u - 1, w))

    color = [0] * N

    def dfs(v, p, c):
        color[v] = c
        for nv, w in G[v]:
            if nv == p:
                continue
            if w % 2:
                dfs(nv, v, 1 - c)
            else:
                dfs(nv, v, c)

    dfs(0, -1, 0)
    print(*color, sep='\n')
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
from collections import deque

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60


def main():
    N = int(readline())
    G = [[] for _ in range(N)]
    for _ in range(N - 1):
        u, v, w = map(int, readline().split())
        G[u - 1].append((v - 1, w))
        G[v - 1].append((u - 1, w))

    dist = [-1] * N
    color = [0] * N
    dist[0] = 0
    queue = deque([0])
    while queue:
        v = queue.popleft()
        for nv, cost in G[v]:
            if dist[nv] == -1:
                dist[nv] = dist[v] + cost
                color[nv] = dist[nv] % 2
                queue.append(nv)

    print(*color, sep='\n')
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n = int(input())
from collections import defaultdict
ns = defaultdict(set)
for i in range(n-1):
    u,v,w = map(int,input().split())
    u -= 1
    v -= 1
    ns[u].add((w, v))
    ns[v].add((w, u))
    
q = [(0,0)]
ans = [None]*n
ans[0] = 0
while q:
    d,u = q.pop()
    for w,v in ns[u]:
        if ans[v] is None:
            val = (w+d)%2
            q.append((val, v))
            ans[v] = val
write("\n".join(map(str, ans)))

Submission status: Accepted

Solution code:
from copy import deepcopy
from collections import deque
def main():
    def find(x):
        if par[x] < 0:
            return x
        else:
            par[x] = find(par[x])
            return par[x]
    def unite(x, y):
        x = find(x)
        y = find(y)
        if x == y:
            return False
        else:
            if par[x] > par[y]:
                x, y = y, x
            par[x] += par[y]
            par[y] = x
            return True
    def roots():
        return [i for i, x in enumerate(par) if x < 0]

    n = int(input())
    par = [-1] * n
    uvw = {e:[] for e in range(n)}

    for _ in range(n - 1):
        u, v, w = map(int, input().split())
        u -= 1
        v -= 1
        uvw[u].append((u, v, w))
        uvw[v].append((v, u, w))
        unite(u, v)
    root_node = roots()[0]
    color = [-1] * n
    color[root_node] = 0
    node_next = deque()
    node_next.append(root_node)
    node_next_next = deque()
    node_seen = set()

    while len(node_seen) < n:
        while node_next:
            node_togo = node_next.popleft()
            if node_togo in node_seen:
                continue
            else:
                node_seen.add(node_togo)
            # 次の層のノード群情報を取得し、「次にみるノードlist」にいれる。
            node_adj = uvw[node_togo]
            node_next_next += [i[1] for i in node_adj]
            # 次の層を処理＝色塗りする
            for adj in node_adj:
                if adj[1] in node_seen or color[adj[1]] != -1:
                    continue
                if adj[2] % 2 == 0:
                    color[adj[1]] = color[node_togo]
                else:
                    color[adj[1]] = color[node_togo] ^ 1
        node_next = deepcopy(node_next_next)
        node_next_next = deque()
    print(*color, sep='\n')


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n=int(input())
l=[[] for i in range(n)]
ans=[-1 for i in range(n)]
for i in range(n-1):
  u,v,w=[int(x) for x in input().rstrip().split()]
  l[u-1].append([v-1,w])
  l[v-1].append([u-1,w])

def bfs():
  ans[0]=0
  que=[0]
  while(que):
    now=que.pop(0)
    for i,j in l[now]:
      if ans[i]==-1:
        if j%2==0:
          ans[i]=ans[now]
        else:
          ans[i]=(ans[now]+1)%2
        que.append(i)

bfs()
for i in ans:print(i)

Submission status: Accepted

Solution code:
N=int(input())
links=[set() for _ in [0]*N]
for i in range(1,N):
  u,v,w=map(int,input().split())
  u-=1
  v-=1
  links[u].add((v,w))
  links[v].add((u,w))
ans=[-1]*N
q=[(0,0,-1)]
while q:
  v,d,p=q.pop()
  if d%2==0:
    ans[v]=0
  else:
    ans[v]=1
  for u,w in links[v]:
    if u==p:
      continue
    q.append((u,w+d,v))
print('\n'.join(map(str,ans)))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10000000)
MOD = 10 ** 9 + 7
INF = 10 ** 15

def main():
    N = int(input())
    G = [[] for _ in range(N)]
    for _ in range(N - 1):
        a,b,c = map(int,input().split())
        a -= 1
        b -= 1
        G[a].append((b,c))
        G[b].append((a,c))
    
    color = [0] * N
    dist = [-1] * N
    stack = [0]
    dist[0] = 0
    while stack:
        v = stack.pop()
        for e,c in G[v]:
            if dist[e] >= 0:
                continue
            dist[e] = dist[v] + c
            color[e] = dist[e]%2
            stack.append(e)
    print('\n'.join(map(str,color)))
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque

N = int(input())
edge = [[] for i in range(N)]
color = [-1] * N

for i in range(N-1):
    u, v, w = map(int, input().split())
    edge[u-1].append((v-1, w))
    edge[v-1].append((u-1, w))

q = deque([])
q.append((0,0))

while(q):
    cur, col = q.popleft()
    color[cur] = col
    for next, weight in edge[cur]:
        if color[next] != -1:
            continue

        if weight % 2:
            q.append((next, 1-col))
            color[next] = 1-col
        else:
            q.append((next, col))
            color[next] = col

print(*color, sep="\n")

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict
readline = sys.stdin.buffer.readline
sys.setrecursionlimit(10**8)


def geta(fn=lambda s: s.decode()):
    return map(fn, readline().split())


def gete(fn=lambda s: s.decode()):
    return fn(readline().rstrip())


def main():
    N = gete(int)
    g = [set() for _ in range(N+1)]
    for _ in range(N-1):
        u, v, w = geta(int)
        g[u].add((v, w))
        g[v].add((u, w))

    dist = [-1] * (N+1)
    color = [-1]*(N+1)

    dist[1] = 0
    color[1] = 0

    def dfs(i, d):

        dist[i] = d
        color[i] = 0 if d & 1 == 0 else 1

        for j, wj in g[i]:
            if dist[j] < 0:
                dfs(j, d + wj)

    dfs(1, 0)

    print(*color[1:], sep="\n")


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
@author: H_Hoshigi
49min 40sec
"""
# 0番目の頂点から各頂点までの距離を求めて、
# その距離の偶奇を判定すればよいだろう。
# 木だから頂点同士の距離は1通りしかない。

def main():
    N = int(input())
    edge_list = [list(map(int, input().split()))  for i in range(N-1)]

    # 頂点uから頂点vに距離wの辺があることを、
    # 隣接リストadj_listのu番目の要素に[v, w]があることとして書く。
    # 今距離wは偶奇しか興味が無いので、w%2に置き換える。
    # 頂点の番号は、入力では1インデックスなので、0インデックスに変える。
    # 無向グラフなので、両向きとも入力する。
    adj_list = [[] for i in range(N)]
    for edge in edge_list:
        adj_list[edge[0]-1].append([edge[1]-1, edge[2]%2])
        adj_list[edge[1]-1].append([edge[0]-1, edge[2]%2])

    # 各頂点の頂点0からの距離のリスト
    INF = 2
    distance_list = [ INF for i in range(N)]
    distance_list[0] = 0

    # dfsのためのスタック
    dfs_list = [0]

    # dfs
    while dfs_list:
        now_node = dfs_list.pop(-1)
        now_dist = distance_list[now_node]
        for edge in adj_list[now_node]:
            if distance_list[edge[0]] == INF:
                distance_list[edge[0]] = (now_dist+edge[1])%2
                dfs_list.append(edge[0])
    
    # 答えの出力
    for dist in distance_list:
        print(dist)
    return

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n = int(input())
edge = [[int(i) for i in input().split()] for j in range(n-1)]
graph = [[] for _ in range(n+1)]
for i in range(n-1):
    u, v, w = edge[i][0], edge[i][1], edge[i][2] % 2
    graph[u].append((v,w))
    graph[v].append((u,w))

color = [-1] * (n+1)
dist = [0] * (n+1)    
stack = [1]
color[1] = 0

while stack:
    x = stack.pop()
    cx = color[x]
    dx = dist[x]
    for y, w in graph[x]:
        if color[y] >= 0:
            continue
        dist[y] = dist[x] + w
        if dist[x] ^ dist[y] == 0:
            color[y] = color[x]
        else:
            color[y] = (color[x] + 1) % 2
        stack.append(y)
print('\n'.join([str(n) for n in color[1:]]))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)
n = int(input())
to = [[] for _ in range(n)]
for _ in range(n - 1):
    u, v, w = map(int, input().split())
    u -= 1
    v -= 1
    to[u].append((v, w))
    to[v].append((u, w))
ans = [-1] * n
def dfs(u=0, c=0, parent=-1):
    ans[u] = c
    for v, w in to[u]:
        if v == parent:
            continue
        dfs(v, (c + w) & 1, u)

dfs()
print(*ans, sep='\n')

Submission status: Accepted

Solution code:
import sys
from io import StringIO
import unittest
import os

sys.setrecursionlimit(999999999)


def dfs(now, edge, colors):
    # 枝を全て調査
    for i in edge[now]:
        # 色を設定済みなら何もしない
        if not colors[i[0]] == -1:
            continue

        # 色の設定
        # 親子の距離%2(偶数0:奇数:1) + 親(偶数0:奇数:1) の余りを子に設定(偶数なら0 奇数なら1を設定できるロジック)
        colors[i[0]] = (i[1] % 2 + colors[now]) % 2

        # 再帰処理
        dfs(i[0], edge, colors)


# 実装を行う関数
def resolve():
    n = int(input())
    uvw = [list(map(int, input().split())) for i in range(n - 1)]

    edge = [[] for i in range(n + 1)]

    # 例：edge[0] = [[1, 100][2, 300]]
    # 点0は点1と距離100、点2と距離300でつながっている。
    for i in uvw:
        edge[i[0]].append([i[1], i[2]])
        edge[i[1]].append([i[0], i[2]])

    # -1は「未設定」の意味
    colors = [-1 for i in range(n + 1)]

    # 初期(適当な点を黒に塗る)
    colors[1] = 1

    dfs(1, edge, colors)

    for i in range(1, len(colors)):
        print(colors[i])


# テストクラス
class TestClass(unittest.TestCase):
    def assertIO(self, assert_input, output):
        stdout, sat_in = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(assert_input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, sat_in
        self.assertEqual(out, output)

    def test_input_1(self):
        test_input = """3
1 2 2
2 3 1"""
        output = """0
0
1"""
        self.assertIO(test_input, output)

    def test_input_2(self):
        test_input = """5
2 5 2
2 3 10
1 3 8
3 4 2"""
        output = """1
0
1
0
1"""
        self.assertIO(test_input, output)

    # 自作テストパターンのひな形(利用時は「tes_t」のアンダーバーを削除すること
    def tes_t_1original_1(self):
        test_input = """データ"""
        output = """データ"""
        self.assertIO(test_input, output)


# 実装orテストの呼び出し
if __name__ == "__main__":
    if os.environ.get("USERNAME") is None:
        # AtCoder提出時の場合
        resolve()

    else:
        # 自PCの場合
        unittest.main()

Submission status: Accepted

Solution code:
import sys
from io import StringIO
import unittest
import os

sys.setrecursionlimit(1000000)

def dfs(now, edge, colors):
    # 枝を全て調査
    for i in edge[now]:
        # 色を設定済みなら何もしない
        if not colors[i[0]] == -1:
            continue

        # 色の設定
        # 親子の距離%2(偶数0:奇数:1) + 親(偶数0:奇数:1) の余りを子に設定(偶数なら0 奇数なら1を設定できるロジック)
        colors[i[0]] = (i[1] % 2 + colors[now]) % 2

        # 再帰処理
        dfs(i[0], edge, colors)


# 実装を行う関数
def resolve():
    n = int(input())
    uvw = [list(map(int, input().split())) for i in range(n - 1)]

    edge = [[] for i in range(n + 1)]

    # 例：edge[0] = [[1, 100][2, 300]]
    # 点0は点1と距離100、点2と距離300でつながっている。
    for i in uvw:
        edge[i[0]].append([i[1], i[2]])
        edge[i[1]].append([i[0], i[2]])

    # -1は「未設定」の意味
    colors = [-1 for i in range(n + 1)]

    # 初期(適当な点を黒に塗る)
    colors[1] = 1

    dfs(1, edge, colors)

    for i in range(1, len(colors)):
        print(colors[i])


# テストクラス
class TestClass(unittest.TestCase):
    def assertIO(self, assert_input, output):
        stdout, sat_in = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(assert_input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, sat_in
        self.assertEqual(out, output)

    def test_input_1(self):
        test_input = """3
1 2 2
2 3 1"""
        output = """0
0
1"""
        self.assertIO(test_input, output)

    def test_input_2(self):
        test_input = """5
2 5 2
2 3 10
1 3 8
3 4 2"""
        output = """1
0
1
0
1"""
        self.assertIO(test_input, output)

    # 自作テストパターンのひな形(利用時は「tes_t」のアンダーバーを削除すること
    def tes_t_1original_1(self):
        test_input = """データ"""
        output = """データ"""
        self.assertIO(test_input, output)


# 実装orテストの呼び出し
if __name__ == "__main__":
    if os.environ.get("USERNAME") is None:
        # AtCoder提出時の場合
        resolve()

    else:
        # 自PCの場合
        unittest.main()

Submission status: Accepted

Solution code:
import collections
n = int(raw_input())
adj = collections.defaultdict(list)
for _ in range(n - 1):
	u, v, w = map(int, raw_input().split(' '))
	adj[u].append((v,w))
	adj[v].append((u,w))
h = [-1 for _ in range(n+1)]
h[1] = 0
def dfs(h, adj):
	stack = collections.deque([1])
	while(stack):
		u = stack.pop()
		for v,w in adj[u]:
			if h[v] == -1:
				h[v] = (1- h[u]) if (w % 2) else h[u]
				stack.append(v) #(v, h, adj)
dfs(h, adj)
for node in range(1, n + 1):  print h[node]

Submission status: Accepted

Solution code:
import collections
n = int(raw_input())

adj = collections.defaultdict(list)

for _ in range(n - 1):
	u, v, w = map(int, raw_input().split(' '))
	adj[u].append((v,w))
	adj[v].append((u,w))
h = { 1:0 }
def dfs(h, adj):
	stack = collections.deque([1])
	while(stack):
		u = stack.pop()
		for v,w in adj[u]:
			if v not in h:
				h[v] = (1- h[u]) if (w % 2) else h[u]
				stack.append(v) #(v, h, adj)
dfs(h, adj)
for node in range(1, n + 1): 
	print h[node]

Submission status: Accepted

Solution code:
import collections
n = int(raw_input())

adj = collections.defaultdict(list)

for _ in range(n - 1):
	u, v, w = map(int, raw_input().split(' '))
	adj[u].append((v,w))
	adj[v].append((u,w))


q = collections.deque([(1,0)])
h = { 1:0 }
while(q):
	u,c = q.popleft()
	for v,w in adj[u]:
		if v not in h:
			h[v] = (1- c) if (w % 2) else c
			q.append((v,h[v]))

for node in range(1, n + 1): 
	print h[node]

Submission status: Accepted

Solution code:
dic = {1:0,0:1}

from collections import deque 
#スタック
q = deque([])#append pop

N = int(input())
#木
tree = [[]for i in range(0,N+1,1)]
for i in range(1,N,1):
    u,v,w = map(int,input().split())
    tree[u].append([v,w])
    tree[v].append([u,w])
ans = [0]*(N+1)

q.append([1,0,0])#今回のノード、距離、前回のノード

while len(q)>0:
    now,dist,pre = q.pop()
    ans[now] = (ans[pre] + dist%2)%2
    for i in tree[now]:
        if i[0]!=pre:
            q.append([i[0],i[1],now])

for i in range(1,N+1,1):
    print(ans[i])

Submission status: Accepted

Solution code:
from sys import stdin, setrecursionlimit
from collections import deque


def main():
    input = stdin.buffer.readline
    n = int(input())
    g = [[] for _ in range(n)]
    for _ in range(n - 1):
        u, v, w = map(int, input().split())
        g[u - 1].append([v - 1, w])
        g[v - 1].append([u - 1, w])

    ans = [-1] * n

    q = deque([0])
    ans[0] = 0

    while q:
        u = q.popleft()

        for v, w in g[u]:
            if ans[v] == -1:
                ans[v] = (ans[u] + w) % 2
                q.append(v)

    print(*ans, sep='\n')


if __name__ == "__main__":
    setrecursionlimit(10000)
    main()

Submission status: Accepted

Solution code:
n = int(input())
uvw = [0]*(n-1)
for i in range(n-1):
    uvw[i] = list(map(int,input().split()))
V = [[] for i in range(n+1)]
for u,v,w in uvw:
    V[u].append([v,w])
    V[v].append([u,w])
from collections import deque
q = deque([])
now = 1
reach = [0]*(n+1)
reach[now] = 2
q.append(now)
while q:
    x = q.popleft()
    for L in V[x]:
        if reach[L[0]] == 0:
            q.append(L[0])
            reach[L[0]] = reach[x] + L[1]
for A in reach[1:]:
    if A%2 == 0:
        print(0)
    else:
        print(1)

Submission status: Accepted

Solution code:
import sys
from collections import deque
input = lambda: sys.stdin.readline().rstrip()


def solve():
    N = int(input())
    edge = [[] for _ in range(N)]
    for i in range(N - 1):
        u, v, w = map(int, input().split())
        u, v = u - 1, v - 1
        edge[u].append((w, v))
        edge[v].append((w, u))

    q = deque()
    q.append(0)
    color = [-1 for _ in range(N)]
    color[0] = True

    # print(edge)

    while q:
        v = q.popleft()
        for w, nv in edge[v]:
            if color[nv] == -1:
                if w % 2 == 0:
                    color[nv] = color[v]
                else:
                    color[nv] = not color[v]
                q.append(nv)

    # print(color)
    for c in color:
        if c:
            print(0)
        else:
            print(1)


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**9)

def dfs(now):
    for to,dis in G[now]:
        if color[to] == -1:
            color[to] = (color[now] + dis) % 2
            dfs(to)

N = int(input())
G = [[] for _ in range(N)]
color = [-1] * N
color[0] = 0 #偶数=0

for i in range(N-1):
    a,b,c = map(int,input().split())
    a -= 1
    b -= 1
    G[a].append([b,c%2])
    G[b].append([a,c%2])

#print(G)    
dfs(0)
print(*color,sep="\n")

Submission status: Accepted

Solution code:
def BFS(x):
    v = deque([x])
    d[x]=0
    
    while v:
        a = v.popleft()
        for num in L[a]:
            if d[num]==-1:
                d[num]= d[a]+dic[(a,num)]
                v.append(num)

from collections import deque
N=int(input())
u=[0]*(N-1)
v=[0]*(N-1)
w=[0]*(N-1)
d=[-1 for _ in range(N)]
dic={}
L=[ [] for _ in range(N)]
for i in range(N-1):
    u[i],v[i],w[i] = map(int,input().split())
    u[i] -=1
    v[i] -=1
    L[u[i]].append(v[i])
    L[v[i]].append(u[i])
    dic[ (u[i],v[i])]=w[i]
    dic[ (v[i],u[i])]=w[i]
    
#print(L)
#print(dic)

BFS(0)
#print(d)
for num in d:
    if num%2==0:
        print(0)
    else:
        print(1)

Submission status: Accepted

Solution code:
#D
#https://tech-kyopro.com/atcoder-abc126-d

import sys
sys.setrecursionlimit(500*500)
n = int(input())
edges = [list(map(int,input().split())) for _ in range(n-1)]
#頂点iと隣接する頂点とその距離を格納[["隣接する頂点","その距離"]]
a = [[] for _ in range(n+1)]

for i in edges:
    a[i[0]].append([i[1],i[2]])
    a[i[1]].append([i[0],i[2]])
    
#頂点1からの距離をdepth
depth = [-1 for _ in range(n+1)]
depth[0] = 0

def dfs(a,s):
    for v in a[s]:
        if depth[v[0]] == -1:
            depth[v[0]] = depth[s] + v[1]
            dfs(a,v[0])
            
dfs(a,1)

for d in depth[1:]:
    if d % 2 == 0:
        print(0)
    else:
        print(1)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline

def dfs(d, v, p):
    if (d & 1):
        C[v] = 1
    for w, u in E[v]:
        if u == p:
            continue
        dfs(d ^ w, u, v)

N = int(input())
C = [0] * N
E = [[] for _ in range(N)]
for i in range(N-1):
    u, v, w = map(int, input().split())
    u -= 1
    v -= 1
    E[u].append((w % 2, v))
    E[v].append((w % 2, u))
dfs(0, 0, -1)
print(*C, sep='\n')

Submission status: Accepted

Solution code:
from collections import deque
n = int(input())
route = [[] for i in range(n+1)]
for i in range(n-1):
    u , v , w = map(int,input().split())
    route[u].append((v,w))
    route[v].append((u,w))

ans = [-1 for i in range(n+1)]

d = deque()
d.append(1)
ans[1] = 0
while d:
    now = d.popleft()
    for i , j in route[now]:
        if ans[i] == -1:
            if j % 2 == 0:
                ans[i] = ans[now]
            elif j % 2 == 1:
                ans[i] = (ans[now]+1)%2
            d.append(i)

for i in range(1,n+1):
    print(ans[i])

Submission status: Accepted

Solution code:
from collections import deque
N = int(input())
G = [[] for _ in range(N)]
for _ in range(N - 1):
    u, v, w = map(int, input().split())
    G[u - 1].append([v - 1, w])
    G[v - 1].append([u - 1, w])

Q = deque()
Q.append(0)
c = [-1] * N
c[0] = 0
while len(Q) > 0:
    q = Q.popleft()
    pc = c[q]
    for g, w in G[q]:
        if c[g] != -1:
            continue
        if w % 2 == 0:
            c[g] = pc
        else:
            c[g] = 1 - pc
        Q.append(g)

for i in c:
    print(i)

Submission status: Accepted

Solution code:
class Tree(): #weighted
    def __init__(self, n, edge, indexed=1):
        self.n = n
        self.tree = [[] for _ in range(n)]
        for e in edge:
            self.tree[e[0] - indexed].append((e[1] - indexed, e[2]))
            self.tree[e[1] - indexed].append((e[0] - indexed, e[2]))

    def setroot(self, root):
        self.root = root
        self.parent = [None for _ in range(self.n)]
        self.parent[root] = -1
        self.depth = [None for _ in range(self.n)]
        self.depth[root] = 0
        self.distance = [None for _ in range(self.n)]
        self.distance[root] = 0
        self.order = []
        self.order.append(root)
        self.cost = [0 for _ in range(self.n)]
        self.size = [1 for _ in range(self.n)]
        stack = [root]
        while stack:
            node = stack.pop()
            for adj, cost in self.tree[node]:
                if self.parent[adj] is None:
                    self.parent[adj] = node
                    self.depth[adj] = self.depth[node] + 1
                    self.distance[adj] = self.distance[node] + cost
                    self.cost[adj] = cost
                    self.order.append(adj)
                    stack.append(adj)
        for node in self.order[::-1]:
            for adj, cost in self.tree[node]:
                if self.parent[node] == adj:
                    continue
                self.size[node] += self.size[adj]

import sys
input = sys.stdin.readline

N = int(input())
E = [tuple(map(int, input().split())) for _ in range(N - 1)]
t = Tree(N, E)
t.setroot(0)

for i in range(N):
    if t.distance[i] % 2 == 0:
        print(0)
    else:
        print(1)

Submission status: Accepted

Solution code:
import sys
import math
from collections import deque

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()


#隣接リスト 1-order
def make_adjlist_nond(n, edges):
    res = [[] for _ in range(n + 1)]
    for edge in edges:
        res[edge[0]].append([edge[1], edge[2]])
        res[edge[1]].append([edge[0], edge[2]])
    return res


def main():
    N = NI()
    edges = [NLI() for _ in range(N-1)]
    graph = make_adjlist_nond(N, edges)
    colors = [0]*(N+1)

    def dfs(node, prev):
        for goto, dist in graph[node]:
            if goto == prev:
                continue
            colors[goto] = 1 - colors[node] if dist % 2 else colors[node]
            dfs(goto, node)

    dfs(1, 0)
    print("\n".join(map(str, colors[1:])))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10000000)


def main():
    n = int(input())
    
    G=[[] for _ in range(n)]
    for _ in range(n-1):
        u,v,w = map(int, input().split())
        G[u-1].append([v-1,w])
        G[v-1].append([u-1,w])
    ans=[-1]*n
    
    def sub(node,distance):
        for next_node, edge in G[node]:
            if ans[next_node]==-1:
                ans[next_node]=(distance+edge)%2
                sub(next_node,(distance+edge)%2)
    sub(0,0)
    
    for i in ans:
        print(i)
main()