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: Runtime Error

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


def dfs(now, parent, 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[parent]) % 2

        # 再帰処理
        dfs(i[0], now, 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, 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: Runtime Error

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,h = collections.deque([(1,0)]), { 1:0 }
def dfs(u, h, adj):
	for v,w in adj[u]:
		if v not in h:
			h[v] = (1- h[u]) if (w % 2) else h[u]
			dfs(v, h, adj)
dfs(1, h, adj)
for node in range(1, n + 1): 
	print h[node]

Submission status: Runtime Error

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

adj = collections.defaultdict(list)

for _ in range(n - 1):
	u, v, w = raw_input().split(' ')
	w = int(w)
	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
			q.append((v,1-c))

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

Submission status: Runtime Error

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: Runtime Error

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] = 1 #偶数=1

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: Runtime Error

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] = 1 #偶数=０

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)
for i in color:
    print(i)

Submission status: Runtime Error

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

def dfs(now):
    for to,dis in G[now]:#next_v[0]=次の頂点、[1]=次までの距離
        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] = 1 #偶数=０

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: Runtime Error

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

def dfs(now):
    for to,dis in G[now]:#next_v[0]=次の頂点、[1]=次までの距離
        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] = 1 #偶数=０

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: Runtime Error

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

def dfs(G,v,color):
    #color[v] = True
    for next_v in G[v]:#next_v[0]=次の頂点、[1]=次までの距離
        if color[next_v[0]]==-1:
            color[next_v[0]] = (color[v] + next_v[1]) % 2 
            dfs(G,next_v[0],color)
        else:
            continue
    return color    

N = int(input())
G = [[] for _ in range(N)]
color = [-1] * N
color[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)    
c = (dfs(G,0,color))
print(*c,sep="\n")

Submission status: Runtime Error

Solution code:
def dfs(n,graph,color,i,c):
    if color[i] == 0:
        color[i] = c
        for l in graph[i]:
            if color[l[0]] == 0:
                if l[1] % 2 == 0:
                    color = dfs(n,graph,color,l[0],c)
                else:
                    color = dfs(n,graph,color,l[0],-c)
    return color

def solve(n,graph):
    color = [0]*n
    for i in range(n):
        color = dfs(n,graph,color,i,1)
    for c in color:
        print((c+1)//2)

if __name__ == '__main__':
    n = int(input())
    graph=[[] for i in range(n)]
    for i in range(n-1):
        u,v,w = map(int,input().split())
        graph[u-1].append([v-1,w])
        graph[v-1].append([u-1,w])
    
    solve(n,graph)

Submission status: Runtime Error

Solution code:
def dfs(n,graph,color,i,c):
    if color[i] == 0:
        color[i] = c
        for l in graph[i]:
            if color[l[0]] == 0:
                if l[1] % 2 == 0:
                    color = dfs(n,graph,color,l[0],c)
                else:
                    color = dfs(n,graph,color,l[0],-c)
    return color

def solve(n,graph):
    color = [0]*n
    for i in range(n):
        dfs(n,graph,color,i,1)
    for c in color:
        print((c+1)//2)

if __name__ == '__main__':
    n = int(input())
    graph=[[] for i in range(n)]
    for i in range(n-1):
        u,v,w = map(int,input().split())
        graph[u-1].append([v-1,w])
        graph[v-1].append([u-1,w])
    
    solve(n,graph)

Submission status: Runtime Error

Solution code:
def dfs(n,graph,color,i,c):
    if color[i] == 0:
        color[i] = c
        for l in graph[i]:
            if color[l[0]] == 0:
                if l[1] % 2 == 0:
                    color = dfs(n,graph,color,l[0],c)
                else:
                    color = dfs(n,graph,color,l[0],-c)
    return color

def solve(n,graph):
    color = [0]*n
    for i in range(n):
        dfs(n,graph,color,i,1)
    print(color)
    for c in color:
        print((c+1)//2)

if __name__ == '__main__':
    n = int(input())
    graph=[[] for i in range(n)]
    for i in range(n-1):
        u,v,w = map(int,input().split())
        graph[u-1].append([v-1,w])
        graph[v-1].append([u-1,w])
    
    solve(n,graph)

Submission status: Runtime Error

Solution code:
#D
#https://tech-kyopro.com/atcoder-abc126-d
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: Runtime Error

Solution code:
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: Runtime Error

Solution code:
import sys
sys.setrecursionlimit


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()

Submission status: Runtime Error

Solution code:
import sys
sys.setrecrusionlimit

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()

Submission status: Runtime Error

Solution code:
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()

Submission status: Runtime Error

Solution code:
n=int(input())
path=[[] for i in range(n)]
for i in range(n-1):
    u,v,w=map(int,input().split())
    path[u-1].append((v-1,w%2))
    path[v-1].append((u-1,w%2))
ans=[0]+[-1]*(n-1)
def dfs(i):
    global n,path,ans
    for j in path[i]:
        if ans[j[0]]==-1:
            if j[1]:
                ans[j[0]]=1-ans[i]
                dfs(j[0])
            else:
                ans[j[0]]=ans[i]
                dfs(j[0])
dfs(0)
print("\n".join(map(str,ans)))

Submission status: Runtime Error

Solution code:
n = int(input())
edge = [[] for _ in range(n)]

for i in range(n-1):
    a,b,c=map(int, input().split())
    edge[a-1].append([b-1,c])
    edge[b-1].append([a-1,c])
#任意の点から行ける偶数の距離で行けるところを同じ色で塗る。
col = [-1]*n
visited = [0]*n

def dfs(i,c):
    visited[i]=1
    col[i] = c
    for j in edge[i]:
        if not visited[j[0]]:
            if j[1]%2==0:
                dfs(j[0],c)
            else:
                dfs(j[0],-1*c)


def main():
    dfs(0,1)
    for i in range(n):
        print(max(col[i],0))



if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
from collections import deque
N = int(input())
E = [[] for i in range(N + 1)]
ans = [-1]*(N+1)
ans[1] = 0
for i in range(N - 1):
    u, v, w = map(int, input().split((' ')))
    E[u].append((v, w % 2))
    E[v].append((u, w % 2))


def dfs(c=0,p=1):
    for e,w in E[p]:
        if ans[e] != -1:
            continue
        if w:
            ans[e] = 0 if c else 1
        else:
            ans[e] = c
        dfs(ans[e], e)
dfs()
for i in ans[1:]:
    print(i)

Submission status: Runtime Error

Solution code:
from collections import deque
N = int(input())
E = [[] for i in range(N + 1)]
ans = [-1]*(N+1)
ans[1] = 0
for i in range(N - 1):
    u, v, w = map(int, input().split((' ')))
    E[u].append((v, w % 2))
    E[v].append((u, w % 2))


def dfs(c=0,p=1):
    for e,w in E[p]:
        if ans[e] != -1:
            continue
        if w:
            ans[e] = 0 if c else 1
        else:
            ans[e] = c
        dfs(ans[e], e)
dfs()
print(ans[1:])

Submission status: Runtime Error

Solution code:
from collections import defaultdict
def dfs(node_i, oe):
    if ans[node_i] != -1:
        return
    next_nodes = graph[node_i]
    ans[node_i] = oe
    for next_i, cost in next_nodes:
        dfs(next_i, (oe+cost)%2)
        

N = int(input())
ans = [-1 for i in range(N+1)]
graph = defaultdict(list)
for i in range(N-1):
    u, v, w = map(int, input().split())
    graph[u] += [(v, w)]
    graph[v] += [(u, w)]

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

Submission status: Runtime Error

Solution code:
def dfs(curr_v, pare_v, curr_sum, visited, g):
    if curr_sum%2 == 0:
        visited[curr_v] = 0
    else:
        visited[curr_v] = 1
    for neib_vw in g[curr_v]:
        if neib_vw[0] == pare_v: continue
        dfs(neib_vw[0], curr_v, curr_sum+neib_vw[1], visited, g)
    

N = int(input())
g = [ [] for _ in range(N+1)]
visited = [-1] * (N+1)

for _ in range(N-1):
    u, v, w = map(int, input().split()) 
    w%=2
    g[u].append((v,w))
    g[v].append((u,w))

dfs(1, -1, 0, visited, g)
for p in visited[1:]:
    print(p)

Submission status: Runtime Error

Solution code:
def main():
    n = int(input())
    g = [[] for _ in range(n)]
    for i in range(n - 1):
        u, v, w = map(int, input().split())
        u = u - 1
        v = v - 1
        g[u].append([v, w])
        g[v].append([u, w])
    ans = [-1]*n
 
    def dfs(node, dist):
        for i, size in g[node]:
            if ans[i] == -1:
                ans[i] = (dist + size) % 2
                dfs(i, dist + size)
    dfs(0, 0)
    print(*ans, sep='\n')
if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
def main():
    n = int(input())
    g = [[] for _ in range(n)]
    for i in range(n - 1):
        u, v, w = map(int, input().split())
        u = u - 1
        v = v - 1
        g[u].append([v, w])
        g[v].append([u, w])
    print(g)
    ans = [-1]*n
 
    def dfs(node, dist):
        for i, size in g[node]:
            if ans[i] == -1:
                ans[i] = (dist + size) % 2
                dfs(i, dist + size)
    dfs(0, 0)
    print(*ans, sep='\n')
if __name__ == '__main__':
    main()

Submission status: Runtime Error

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

color = [None] * N
def dfs(n,l):
  if l%2==0:
    color[n] = 1
  else:
    color[n] = 0

  for nei, nl in adj[n]:
    if color[nei] is not None:
      if (l+nl) % 2 == 0 and color[nei] != 1:
        return False
      if (l+nl) % 2 == 1 and color[nei] != 0:
        return False
    else:
      dfs(nei, l+nl)

  return True

for i in range(N):
  if color[i] is None:
    if not dfs(i,0):
      print(-1)
      exit()

for c in color: print(c)

Submission status: Runtime Error

Solution code:
#!/usr/bin python3
# -*- coding: utf-8 -*-

# 二分グラフ

N = int(input())
graph = [[] for _ in range(N)]
color = [-1]*N

# 隣接リストの作成
for i in range(N-1):
    a, b, w = map(int, input().split())
    a -= 1
    b -= 1
    w %= 2
    graph[a].append((b,w))
    graph[b].append((a,w))

# 深さ優先探索
def dfs(g,v,c):
    if color[v]==-1:
        color[v] = c
        for nv, w in g[v]:
            if color[nv]==-1:
                nc = c
                if w!=0:
                    nc = 1-c
                dfs(g,nv,nc)

def main():
    dfs(graph, 0, 1)
    for i in color:
        print(i)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
#!/usr/bin python3
# -*- coding: utf-8 -*-

# 二分グラフ

N = int(input())
M = N-1
graph = [[] for _ in range(N)]
seen = [False]*N
color = [-1]*N

# 隣接リストの作成
for i in range(M):
    a, b, w = map(int, input().split())
    a -= 1
    b -= 1
    w %= 2
    graph[a].append((b,w))
    graph[b].append((a,w))

# 深さ優先探索
def dfs(g,v,c):
    seen[v] = True
    color[v] = c
    for nv, w in g[v]:
        # すでに隣接の色が確定していて同じ色となっている場合終了
        if seen[nv] == True:
            continue
        # 隣接の色が確定していていない場合、先に進めた結果を返す
        nc = c if w==0 else 1-c
        if not dfs(g,nv,nc):
            return False
    return True

def main():
    ret = dfs(graph, 0, 1)
    for i in color:
        print(i)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
#!/usr/bin python3
# -*- coding: utf-8 -*-

# 二分グラフ

N = int(input())
M = N-1
graph = [[] for _ in range(N)]
seen = [False]*N
color = [-1]*N

# 隣接リストの作成
for i in range(M):
    a, b, w = map(int, input().split())
    a -= 1
    b -= 1
    w %= 2
    graph[a].append((b,w))
    graph[b].append((a,w))

# 深さ優先探索
def dfs(g,v,c):
    seen[v] = True
    color[v] = c
    for nv, w in g[v]:
        # すでに隣接の色が確定していて同じ色となっている場合終了
        if seen[nv] == True:
            continue
        # 隣接の色が確定していていない場合、先に進めた結果を返す
        nc = c if w==0 else 1-c
        if not dfs(g,nv,nc):
            return False
    return True

def main():
    ret = dfs(graph, 0, 1)

    print(seen)
    print(color)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
# AtCoder
import sys
sys.setrecursionlimit(10000)

N = int(input())
edges = [list(map(int, input().split())) for _ in range(N-1)]
A = [[] for _ in range(N+1)]

for edge in edges:
    A[edge[0]].append([edge[1], edge[2]])
    A[edge[1]].append([edge[0], edge[2]])

depth = [-1]*(N+1)
depth[1] = 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: Runtime Error

Solution code:
N = int(input())
edges = [list(map(int, input().split())) for _ in range(N-1)]
A = [[] for _ in range(N+1)]

for edge in edges:
    A[edge[0]].append([edge[1], edge[2]])
    A[edge[1]].append([edge[0], edge[2]])

depth = [-1]*(N+1)
depth[1] = 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: Runtime Error

Solution code:
n = int(input())
g = []
s = 0
ans = [-1] * (n+1)
for i in range(n+1):
  g.append([])
#print(g)
for i in range(n-1):
  inp = input()
  if len(inp) == 0:
    continue
  u, v, w = map(int, inp.split())
  g[u].append([v, w])
  g[v].append([u, w])
  if s == 0:
    s = u
#print(n)
#print(g)
#print(s)

def dfs(i):
  next_g = g[i]
  for k in range(len(next_g)):
    to = next_g[k]
    if ans[to[0]] == -1:
      if to[1] % 2 == 0:
        ans[to[0]] = ans[i]
      else:
        ans[to[0]] = '0' if  ans[i] == '1' else '1'
      dfs(to[0])
ans[s] = '0'
if len(g) > 0:
  dfs(s)
for i in range(1, n+1):
  print(ans[i])

Submission status: Runtime Error

Solution code:
n = int(input())
g = []
s = 0
ans = [-1] * (n+1)
for i in range(n+1):
  g.append([])
#print(g)
for i in range(n-1):
  u, v, w = map(int, input().split())
  g[u].append([v, w])
  g[v].append([u, w])
  if s == 0:
    s = u
#print(n)
#print(g)
#print(s)

def dfs(i):
  next_g = g[i]
  for k in range(len(next_g)):
    to = next_g[k]
    if ans[to[0]] == -1:
      if to[1] % 2 == 0:
        ans[to[0]] = ans[i]
      else:
        ans[to[0]] = '0' if  ans[i] == '1' else '1'
      dfs(to[0])
ans[s] = '0'
if len(g) > 0:
  dfs(s)
for i in range(1, n+1):
  print(ans[i])

Submission status: Runtime Error

Solution code:
n = int(input())
g = []
s = 0
ans = [-1] * (n+1)
for i in range(n+1):
  g.append([])
#print(g)
for i in range(n-1):
  u, v, w = map(int, input().split())
  g[u].append([v, w])
  g[v].append([u, w])
  if s == 0:
    s = u
#print(n)
#print(g)
#print(s)

def dfs(i):
  next_g = g[i]
  for k in range(len(next_g)):
    to = next_g[k]
    if ans[to[0]] == -1:
      if to[1] % 2 == 0:
        ans[to[0]] = ans[i]
      else:
        ans[to[0]] = '0' if  ans[i] == '1' else '1'
      dfs(to[0])
ans[s] = '0'
dfs(s)
for i in range(1, n+1):
  print(ans[i])

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
from collections import deque
def bfs(now):
    plan = deque()
    plan.append(now)
    while plan:
        now = plan.popleft()
        for bady, l in LINK[now]:
            if COLOR[bady] != -1:
                continue
            plan.append(bady)
            if l%2:
                COLOR[bady] = 1
            else:
                COLOR[bady] = 0

if __name__ == '__main__':
    N = int(input())
    LINK = [deque()*(N+1) for i in range(N+1)]
    for i in range(N-1):
        a, b, l = map(int, input().split())
        LINK[a].append([b, l])
        LINK[b].append([a, l])
    # print(LINK)
    # print(LINK[1])
    # print(LINK[1][0])
    COLOR= [-1]*(N+1)
    bfs(1)
    for i in range(1,N+1):
        print(COLOR[i])

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
from collections import deque
def bfs(now):
    plan = deque()
    plan.append(now)
    while plan:
        now = plan.popleft()
        for bady, l in LINK[now]:
            print(bady, l)
            if COLOR[bady] != -1:
                continue
            plan.append(bady)
            if l%2:
                COLOR[bady] = 1
            else:
                COLOR[bady] = 0

if __name__ == '__main__':
    N = int(input())
    LINK = [deque()*(N+1) for i in range(N+1)]
    for i in range(N-1):
        a, b, l = map(int, input().split())
        LINK[a].append([b, l])
        LINK[b].append([a, l])
    # print(LINK)
    # print(LINK[1])
    # print(LINK[1][0])
    COLOR= [-1]*(N+1)
    bfs(1)
    for i in range(1,N+1):
        print(COLOR[i])

Submission status: Runtime Error

Solution code:
N = int(input())
adj_list = { i: [] for i in range(N+1) }
for _ in range(N-1):
  u,v,w = map(int, input().split())
  adj_list[u].append([v,w])
  adj_list[v].append([u,w])

res = [None] * N
visited = [False] * (N+1)
def dfs(node, c, w):
  res[node-1] = c
  visited[node] = True

  for nei, nw, in adj_list[node]:
    if not visited[nei]:
      if (w+nw)%2 == 0:
        dfs(nei, 0, w+nw)
      else:
        dfs(nei, 1, w+nw)

dfs(1, 0, 0)
for r in res: print(r)

Submission status: Runtime Error

Solution code:
N = int(input())
uvw = [list(map(int, input().split())) for i in range(N - 1)]
R = [-1] * N
Q = [[] for i in range(N)]
for i in range(N - 1):
    Q[uvw[i][0] - 1].append([uvw[i][1], uvw[i][2]])
    Q[uvw[i][1] - 1].append([uvw[i][0], uvw[i][2]])

def func(i, s, d, l):
    
    if R[i] != -1:
        return

    if R[i] == -1:
        if l %2 == 0:
            R[i] = s
        else:
            R[i] = d
            s = d
            d = s
    for j in range(len(Q[i])):
        func(Q[i][j][0] - 1, s, d, Q[i][j][1])

func(uvw[0][0] - 1, 0, 1, 0)
for i in range(len(R)):
    print(R[i])

Submission status: Runtime Error

Solution code:
N = int(input())
uvw = [list(map(int, input().split())) for i in range(N - 1)]
R = [-1] * N
Q = [[] for i in range(N)]
for i in range(N - 1):
    Q[uvw[i][0] - 1].append([uvw[i][1], uvw[i][2]])
    Q[uvw[i][1] - 1].append([uvw[i][0], uvw[i][2]])

def func(i, s, d, l):
    
    if R[i] != -1:
        return

    if R[i] == -1:
        if l %2 == 0:
            R[i] = s
        else:
            R[i] = d
            s = d
            d = s
    for j in range(len(Q[i])):
        func(Q[i][j][0] - 1, s, d, Q[i][j][1])

func(uvw[0][0] - 1, 0, 1, 0)
print(R)

Submission status: Runtime Error

Solution code:
N = int(input())
uvw = [list(map(int, input().split())) for i in range(N - 1)]
R = [-1] * N
Q = [[] for i in range(N)]
for i in range(N - 1):
    Q[uvw[i][0] - 1].append([uvw[i][1], uvw[i][2]])
    Q[uvw[i][1] - 1].append([uvw[i][0], uvw[i][2]])
def func(i, s, d, l):
    
    if R[i] != -1:
        return

    if R[i] == -1:
        if l %2 == 0:
            R[i] = s
        else:
            R[i] = d
            s = d
            d = s
    for j in range(len(Q[i])):
        func(Q[i][j-1][0] - 1, s, d, Q[i][j-1][1])

func(uvw[0][0] - 1, 0, 1, Q[0][0][1])
print(R)

Submission status: Runtime Error

Solution code:
def dfs(node,w):
  weight = w
  for l in tree[node]:
    if color[l[0]] > -1:
      continue
    if l[1]%2 == 0:
      color[l[0]] = color[node]
    else:
      color[l[0]] = int(not color[node])
    dfs(l[0],l[1])
    


N = int(input())
tree = {}
color = [-1]*(N+1)

for i in range(1,N+1):
  tree[i] = []
for i in range(N-1):
  u,v,w = map(int,input().split())
  tree[u].append([v,w])
  tree[v].append([u,w])
  
color[1] = 0
dfs(1,0)
color = [c  if c>-1 else 0 for c in color]
print('\n'.join(map(str,color[1:])))

Submission status: Runtime Error

Solution code:
def dfs(node,w):
  weight = w
  for l in tree[node]:
    if color[l[0]] > -1:
      continue
    if (l[1]-weight)%2 == 0:
      color[l[0]] = color[node]
    else:
      color[l[0]] = int(not color[node])
    dfs(l[0],l[1])
    


N = int(input())
tree = {}
color = [-1]*(N+1)
color[1] = 0
for i in range(1,N+1):
  tree[i] = []
  
for i in range(N-1):
  u,v,w = map(int,input().split())
  tree[u].append([v,w])
  tree[v].append([u,w])
dfs(1,0)
color = [c  if c>-1 else 0 for c in color]
print('\n'.join(map(str,color[1:])))

Submission status: Runtime Error

Solution code:
def dfs(node,w):
  weight = w
  for l in tree[node]:
    if color[l[0]] > -1:
      continue
    if (l[1]-weight)%2 == 0:
      color[l[0]] = color[node]
    else:
      color[l[0]] = int(not color[node])
    dfs(l[0],l[1])
    


N = int(input())
tree = {}
color = [-1]*(N+1)
color[1] = 0
for i in range(1,N+1):
  tree[i] = []
  
for i in range(N-1):
  u,v,w = map(int,input().split())
  tree[u].append([v,w])
  tree[v].append([u,w])
dfs(1,0)
print('\n'.join(map(str,color[1:])))

Submission status: Runtime Error

Solution code:
N = int(input())
edges = [[]for _ in range(N+1)]
for _ in range(N-1):
    u,v,w = map(int,input().split())
    edges[u].append((v,w%2))
    edges[v].append((u,w%2))
colors = [0]*(N+1)
def dfs(n,p,c):
    colors[n] = c
    for nx,w in edges[n]:
        if nx != p:
            if w%2 == 0:
                dfs(nx,n,c)
            else:
                dfs(nx,n,(c+1)%2)

dfs(1,0,0)
for i in range(1,N+1):
    print(colors[i])

Submission status: Runtime Error

Solution code:
from collections import defaultdict
class edge:
    def __init__(self, to, cost):
        self.to, self.cost = to, cost

def main():
    N = int(input())
    g = defaultdict(list)
    for _ in range(N-1):
        u, v, w = (int(_) for _ in input().split())
        g[u].append(edge(v, w))
        g[v].append(edge(u, w))

    color = [0] * (N+1)

    def dfs(ver):
        for e in g[ver]:
            if color[e.to] == 0 and e.cost%2 == 0:
                color[e.to] = color[ver]
                dfs(e.to)
            elif color[e.to] == 0 and e.cost%2 == 1:
                color[e.to] = (-1) * color[ver]
                dfs(e.to)
    color[1] = 1
    dfs(1)
    for i in range(1, N+1):
        if color[i] == -1: color[i] = 0
    print(*color[1:], sep='\n')
    return

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import numpy as np
from scipy.sparse.csgraph import shortest_path
n = int(input())
Sides = [[0 for i in range(n)] for j in range(n)]
for i in range(n-1):
    u, v, w = map(int, input().split())
    u -= 1
    v -= 1
    Sides[u][v] = w
    Sides[v][u] = w

Path_from_0 = shortest_path(np.array(Sides), indices=0)
for i in range(n):
    print(int(Path_from_0[i]) % 2)

Submission status: Runtime Error

Solution code:
n = int(input())
tree = [[] for i in range(n-1)]
d_list = [0]*n

stack = []
for i in range(n-1):
  u,v,w = map(int,input().split())
  tree[u-1].append((u-1,v-1,w))
while len(tree[0]) > 0:
  stack.append(tree[0].pop())
while len(stack) > 0:
  u,v, w = stack.pop()
  d_list[v] = d_list[u]+w
  while len(tree[v]) > 0:
    stack.append(tree[v].pop())
    
for v in d_list:
  if v % 2 == 0:
    print(0)
  else:
    print(1)

Submission status: Runtime Error

Solution code:
n=int(input())

uvw={}
tree=[[] for _ in range(n)]
for _ in range(n-1):
    u,v,w=list(map(int,input().split()))
    uvw[(u-1,v-1)]=w
    tree[u-1].append(v-1)
    tree[v-1].append(u-1)
    #u<v

result=[-1]*n
#print(tree)
def DEF(x,dis):
    #print("x",x)
    global tree, uvw,result
    for nextNode in tree[x]:
        if result[nextNode]==-1:
            nextDis=dis+uvw[(min(x,nextNode),max(x,nextNode))]
            if (nextDis)%2==0:
                result[nextNode]=0
                DEF(nextNode,nextDis)
            else:
                result[nextNode]=1
                DEF(nextNode,nextDis)
result[0]=0
DEF(0,0)

for item in result:
    print(item)

Submission status: Runtime Error

Solution code:
n = int(input())
tree = [[] for i in range(n)]
d_list = [-1]*n
d_list[0] = 0
stack = []
for i in range(n):
  u,v,w = map(int,input().split())
  tree[u-1].append((u-1,v-1,w))
for e in tree[0]:
  stack.append(e)
while len(stack) > 0:
  u,v, w = stack.pop()
  d_list[v] = d_list[u]+w
  for e in tree[v]:
    stack.append(e)
    
for v in d_list:
  if v % 2 == 0:
    print(0)
  else:
    print(1)