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:
#ABC126D-EvenRelation.py

from sys import stdin
from functools import lru_cache

input = stdin.readline

N = int(input())

UVW = []

for i in range(N-1):
    UVW.append(list(map(int, input().split())))

UVW.sort()

@lru_cache(maxsize=None)
def d(i):
    if i == 1:
        return 0
    else:
        for uvw in UVW:
            if uvw[0] == i:
                return d(uvw[1]) + uvw[2]
            elif uvw[1] == i:
                return d(uvw[0]) + uvw[2]

for i in range(N):
    if d(i+1) % 2 == 0:
        print(0)
    else:
        print(1)

Submission status: Runtime Error

Solution code:
from collections import defaultdict
import sys
sys.setrecursionlimit(10000)
n = int(input())
s = [list(map(int,input().split())) for i in range(n-1)]
t = defaultdict(list)
for i in range(n-1):
    p = [s[i][1],s[i][2]]
    q = [s[i][0],s[i][2]]
    t[s[i][0]] += [p]
    t[s[i][1]] += [q]

a = [-1]*n
a[0] = 0

def Tree(dic,a,x,lo):
    for i in range(len(dic[x])):
        if a[dic[x][i][0]-1] != -1:
            continue
        else:
            save = lo
            lo += dic[x][i][1]
            a[dic[x][i][0]-1] = lo
            a = Tree(dic,a,dic[x][i][0],lo)
            lo = save
    return a

lis = Tree(t,a,1,0)
for i in range(n):
    if lis[i] % 2 == 0:
        print(0)
    else:
        print(1)

Submission status: Runtime Error

Solution code:
from collections import defaultdict
n = int(input())
s = [list(map(int,input().split())) for i in range(n-1)]
t = defaultdict(list)
for i in range(n-1):
    p = [s[i][1],s[i][2]]
    q = [s[i][0],s[i][2]]
    t[s[i][0]] += [p]
    t[s[i][1]] += [q]

a = [-1]*n
a[0] = 0

def Tree(dic,a,x,lo):
    for i in range(len(dic[x])):
        if a[dic[x][i][0]-1] != -1:
            continue
        else:
            save = lo
            lo += dic[x][i][1]
            a[dic[x][i][0]-1] = lo
            a = Tree(dic,a,dic[x][i][0],lo)
            lo = save
    return a

lis = Tree(t,a,1,0)
for i in range(n):
    if lis[i] % 2 == 0:
        print(0)
    else:
        print(1)

Submission status: Runtime Error

Solution code:
n = int(input())
d = {}
for i in range(n - 1):
  u, v, w = map(int, input().split())
  u -= 1
  v -= 1
  if u in d:
    d[u].append([v, w])
  else:
    d[u] = [[v, w]]
  if v in d:
    d[v].append([u, w])
  else:
    d[v] = [[u, w]]

rem = {}

for i in range(n):
  rem[i] = 1
  
ans = [0 for _ in range(n)]

def check(p, tmp):
  rem.pop(p)
  for n, w in d[p]:
    if n in rem:
      tmp = (tmp + w) % 2
      ans[n] = tmp
      check(n, tmp)
      
check(0, 0)

for res in ans:
  print(res)

Submission status: Runtime Error

Solution code:
n = int(input())
d = {}
for i in range(n - 1):
  u, v, w = map(int, input().split())
  u -= 1
  v -= 1
  if u in d:
    d[u].append([v, w])
  else:
    d[u] = [[v, w]]
  if v in d:
    d[v] = [[u, w]]
  else:
    d[v] = [[u, w]]

rem = {}

for i in range(n):
  rem[i] = 1
  
ans = [0 for _ in range(n)]

def check(p, tmp):
  rem.pop(p)
  for n, w in d[p]:
    if n in rem:
      tmp = (tmp + w) % 2
      ans[n] = tmp
      check(n, tmp)
      
check(0, 0)

for res in ans:
  print(res)

Submission status: Runtime Error

Solution code:
#ABC126D-EvenRelation.py

from sys import stdin
from functools import lru_cache

input = stdin.readline

N = int(input())

UVW = []

for i in range(N-1):
    UVW.append(list(map(int, input().split())))

UVW.sort()
print(UVW)

@lru_cache(maxsize=None)
def d(i):
    if i == 1:
        return 0
    else:
        for uvw in UVW:
            if uvw[1] == i:
                return d(uvw[0]) + uvw[2]

for _ in range(N):
    if d(i) % 2 == 0:
        print(0)
    else:
        print(1)

Submission status: Runtime Error

Solution code:
import sys
if sys.version_info[0] == 2:
    input = raw_input
#sys.setrecursionlimit(2 ** 31 -1)

res = None
G = None

def dfs(jibun_v, p, jibun_c):
    global res
    global G

    res[jibun_v] = jibun_c
    #print(jibun_v, p, jibun_c)

    tonari_nodes = G[jibun_v]
    for tonari_v, w in tonari_nodes:
        #if tonari_v == p: # only no loop
        #if tonari_v == p or res[tonari_v] != -1:
        if res[tonari_v] != -1:
            continue

        else:
            if w % 2 == 0:
                tonari_c = jibun_c
            else:
                tonari_c = 1 - jibun_c

            dfs(tonari_v, jibun_v, tonari_c)
    

def main():
    N= int(input())

    global G
    G = [[] for _ in range(N)]

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

    global res
    res = [-1 for _ in range(N)]
    
    jibun_v = 0
    p = -1
    jibun_c = 0
    dfs(jibun_v, p, jibun_c)

    for i in range(N):
        print(res[i])

main()

Submission status: Runtime Error

Solution code:
import sys
if sys.version_info[0] == 2:
    input = raw_input
sys.setrecursionlimit(2 ** 31 -1)

res = none
g = none

def dfs(jibun_v, p, jibun_c):
    global res
    global g

    res[jibun_v] = jibun_c
    #print(jibun_v, p, jibun_c)

    tonari_nodes = g[jibun_v]
    for tonari_v, w in tonari_nodes:
        #if tonari_v == p: # only no loop
        #if tonari_v == p or res[tonari_v] != -1:
        if res[tonari_v] != -1:
            continue

        else:
            if w % 2 == 0:
                tonari_c = jibun_c
            else:
                tonari_c = 1 - jibun_c

            dfs(tonari_v, jibun_v, tonari_c)
    

def main():
    n= int(input())

    global g
    g = [[] for _ in range(n)]

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

    global res
    res = [-1 for _ in range(n)]
    
    jibun_v = 0
    p = -1
    jibun_c = 0
    dfs(jibun_v, p, jibun_c)

    for i in range(n):
        print(res[i])

main()

Submission status: Runtime Error

Solution code:
3
1 2 2
2 3 1

Submission status: Runtime Error

Solution code:
import sys
if sys.version_info[0] == 2:
    input = raw_input

res = None
G = None

def dfs(jibun_v, p, jibun_c):
    global res
    global G

    res[jibun_v] = jibun_c
    #print(jibun_v, p, jibun_c)

    tonari_nodes = G[jibun_v]
    for tonari_v, w in tonari_nodes:
        if tonari_v == p:
        #if tonari_v == p or res[tonari_v] != -1:
        #if res[tonari_v] != -1:
            continue

        else:
            if w % 2 == 0:
                tonari_c = jibun_c
            else:
                tonari_c = 1 - jibun_c

            dfs(tonari_v, jibun_v, tonari_c)
    

def main():
    N= int(input())

    global G
    G = [[] for _ in range(N)]

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

    global res
    res = [-1 for _ in range(N)]
    
    jibun_v = 0
    p = -1
    jibun_c = 0
    dfs(jibun_v, p, jibun_c)

    for i in range(N):
        print(res[i])

main()

Submission status: Runtime Error

Solution code:
import sys
if sys.version_info[0] == 2:
    input = raw_input

res = None
G = None

def dfs(jibun_v, p, jibun_c):
    global res
    global G

    res[jibun_v] = jibun_c
    #print(jibun_v, p, jibun_c)

    tonari_nodes = G[jibun_v]
    for tonari_v, w in tonari_nodes:
        #if tonari_v == p or res[tonari_v] != -1:
        if res[tonari_v] != -1:
            continue

        if w % 2 == 0:
            tonari_c = jibun_c
        else:
            tonari_c = 1 - jibun_c

        dfs(tonari_v, jibun_v, tonari_c)
    

def main():
    N= int(input())

    global G
    G = [[] for _ in range(N)]

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

    global res
    res = [-1 for _ in range(N)]
    
    jibun_v = 0
    p = -1
    jibun_c = 0
    dfs(jibun_v, p, jibun_c)

    for i in range(N):
        print(res[i])

main()

Submission status: Runtime Error

Solution code:
#input = raw_input

res = None
G = None

def dfs(jibun_v, p, jibun_c):
    global res
    global G

    res[jibun_v] = jibun_c
    #print(jibun_v, p, jibun_c)

    tonari_nodes = G[jibun_v]
    for tonari_v, w in tonari_nodes:
        #if tonari_v == p or res[tonari_v] != -1:
        if tonari_v == p or res[tonari_v] != -1:
            continue

        if w % 2 == 0:
            tonari_c = jibun_c
        else:
            tonari_c = 1 - jibun_c

        dfs(tonari_v, jibun_v, tonari_c)
    

def main():
    N= int(input())

    global G
    G = [[] for _ in range(N)]

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

    global res
    res = [-1 for _ in range(N)]
    
    jibun_v = 0
    p = -1
    jibun_c = 0
    dfs(jibun_v, p, jibun_c)

    for i in range(N):
        print(res[i])

main()

Submission status: Runtime Error

Solution code:
#input = raw_input

res = None
G = None

def dfs(jibun_v, p, jibun_c):
    global res
    global G

    res[jibun_v] = jibun_c
    #print(jibun_v, p, jibun_c)

    tonari_nodes = G[jibun_v]
    for tonari_v, w in tonari_nodes:
        #if tonari_v == p or res[tonari_v] != -1:
        if res[tonari_v] != -1:
            continue

        if w % 2 == 0:
            tonari_c = jibun_c
        else:
            tonari_c = 1 - jibun_c

        dfs(tonari_v, jibun_v, tonari_c)
    

def main():
    N= int(input())

    global G
    G = [[] for _ in range(N)]

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

    global res
    res = [-1 for _ in range(N)]
    
    jibun_v = 0
    p = -1
    jibun_c = 0
    dfs(jibun_v, p, jibun_c)

    for i in range(N):
        print(res[i])

main()

Submission status: Runtime Error

Solution code:
input = raw_input

res = None
G = None

def dfs(jibun_v, p, jibun_c):
    global res
    global G

    res[jibun_v] = jibun_c
    #print(jibun_v, p, jibun_c)

    tonari_nodes = G[jibun_v]
    for tonari_v, w in tonari_nodes:
        #if tonari_v == p or res[tonari_v] != -1:
        if res[tonari_v] != -1:
            continue

        if w % 2 == 0:
            tonari_c = jibun_c
        else:
            tonari_c = 1 - jibun_c

        dfs(tonari_v, jibun_v, tonari_c)
    

def main():
    N= int(input())

    global G
    G = [[] for _ in range(N)]

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

    global res
    res = [-1 for _ in range(N)]
    
    jibun_v = 0
    p = -1
    jibun_c = 0
    dfs(jibun_v, p, jibun_c)

    for i in range(N):
        print(res[i])

main()

Submission status: Runtime Error

Solution code:
#input = raw_input

res = None
G = None

def dfs(jibun_v, p, jibun_c):
    global res
    global G

    res[jibun_v] = jibun_c
    #print(jibun_v, p, jibun_c)

    tonari_nodes = G[jibun_v]
    for tonari_v, w in tonari_nodes:
        if tonari_v == p:
            continue

        if w % 2 == 0:
            tonari_c = jibun_c
        else:
            tonari_c = 1 - jibun_c

        dfs(tonari_v, jibun_v, tonari_c)
    

def main():
    N= int(input())

    global G
    G = [[] for _ in range(N)]

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

    global res
    res = [-1 for _ in range(N)]
    
    jibun_v = 0
    p = -1
    jibun_c = 0
    dfs(jibun_v, p, jibun_c)

    for i in range(N):
        print(res[i])

main()

Submission status: Runtime Error

Solution code:
from collections import defaultdict

def search_neighbor_node(node_num):
    for k, v in e[node_num].items():
        if color_list.get(k) is not None:
            continue
        if v % 2 == 0:
            color_list[k] = color_list[node_num]
        else:
            color_list[k] = (color_list[node_num] + 1) % 2
        search_neighbor_node(k)

n = int(input())
e = defaultdict(lambda :defaultdict(list))

color_list = {1: 0}

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


search_neighbor_node(1)

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

Submission status: Runtime Error

Solution code:
def dfs(i, d):
    # print(i, d)
    for j, w in node_array[i]:
        if color_array[j] == -1:
            color_array[j] = (d + w) % 2
            dfs(j, d + w)


N = int(input())
node_array = [[] for i in range(N)]
color_array = [-1] * N

for _ in range(N - 1):
    i, j, w = map(int, input().split())
    node_array[i - 1].append((j - 1, w))
    node_array[j - 1].append((i - 1, w))

color_array[0] = 0
dfs(0, 0)

for i in range(N):
    print(color_array[i])

Submission status: Runtime Error

Solution code:
N = int(input())
 
tree_dic = {i+1:[] for i in range(N)}
bw_list = [0]*N
 
for i in range(1, N):
    ui, vi, wi = map(int, input().split())
    if wi % 2 == 0:
        tree_dic[ui].append((vi, "same"))
        tree_dic[vi].append((ui, "same"))
    else:
        tree_dic[ui].append((vi, "diff"))
        tree_dic[vi].append((ui, "diff"))

print(tree_dic)

def decide_color(tree_dic, current_node, bw_list):
    if 0 not in bw_list:
        return None
    
    for next_node, same_diff in tree_dic[current_node]:
        if bw_list[next_node-1] == 0:
            if same_diff == "same":
                bw_list[next_node-1] = bw_list[current_node-1]
                decide_color(tree_dic, next_node, bw_list)
            else:
                bw_list[next_node-1] = -bw_list[current_node-1]
                decide_color(tree_dic, next_node, bw_list)

bw_list[0] = 1
decide_color(tree_dic, 1, bw_list)
 
for i in range(N):
    if bw_list[i] == 1:
        print(1)
    else:
        print(0)

Submission status: Runtime Error

Solution code:
n = int(input())

ulist = []

for _ in range(n+1):
    ulist.append([])

vlist = [False]*(n+1)

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

def check(checkV, fromV):
    for data in ulist[checkV]:
        if data[0] != fromV:
            vlist[data[0]] = vlist[checkV] if data[1] % 2 == 0 else not vlist[checkV]
            check(data[0], checkV)

check(1, 0)

for i in range(1,n+1):
    print(1 if vlist[i] else 0)

Submission status: Runtime Error

Solution code:
N,M = (int(x) for x in input().split())

#魔法実行回数
magic_act_num = 0

known = []
judge = 0
for i in range(M):
	x,y,z = (int(x) for x in input().split())

	# zは気にしなくてよい
	if i == 0:
		known.append(x)
		known.append(y)
		judge += 2
		magic_act_num+=1
	else:
		if x in known:
			if y in known:
				continue
			else:
				known.append(y)
				judge += 1
		else:
			if y in known:
				known.append(x)
				judge += 1
			else:
				known.append(x)
				known.append(y)
				judge += 2
				magic_act_num+=1

magic_act_num += (N-judge)

print(magic_act_num)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10000000)
N = int(input())
JU = [-1] * N

LI = [[] for _ in range(N)]
for _ in range(N-1):
    u,v,w = map(int,input().split())
    W = w%2
    LI[u-1].append([v-1,W])
    LI[v-1].append([u-1,W])
def dfs(x):
    for i in range(len(LI[x])):
        j = LI[x][i][0]
        k = LI[x][i][1]
        if JU[j] == -1:
            if JU[i] == 0:
                if k == 0:
                    JU[j] = 0
                    dfs(j)
                else:
                    JU[j] = 1
                    dfs(j)
            else:
                if k == 0:
                    JU[j] = 1
                    dfs(j)
                else:
                    JU[j] = 0
                    dfs(j)
	return

JU[0] = 0
dfs(0)
for i in range(N):
    print(JU[i])

Submission status: Runtime Error

Solution code:
N = int(input())
G = [[] for i in range(N)]
for i in range(N-1):
  u, v, w = list(map(int, input().split()))
  u -= 1
  v -= 1
  w = w % 2
  G[u].append([v, w])
  G[v].append([u, w])
  
res = [-1] * N
def dfs(u, p, c):
  res[u] = c
  for n in G[u]:
    if n[0] == p or res[n[0]] != -1:
      continue
    if n[1] == 1:
      dfs(n[0], u, 1-c)
    else:
      dfs(n[0], u, c)
  
def main():
  dfs(0, -1, 1)
  for i in res:
    print(i)
  
  
if __name__ == "__main__":
  main()

Submission status: Runtime Error

Solution code:
N = int(input())
G = [[] for i in range(N)]
for i in range(N-1):
  u, v, w = list(map(int, input().split()))
  u -= 1
  v -= 1
  w = w % 2
  G[u].append([v, w])
  G[v].append([u, w])
  
res = [-1] * N
def dfs(u, p, c):
  if res[u] == -1:
    res[u] = c
    for n in G[u]:
      if n[0] == p:
        continue
      if n[1] == 1:
        dfs(n[0], u, 1-c)
      else:
        dfs(n[0], u, c)
  
def main():
  dfs(0, -1, 1)
  for i in res:
    print(i)
  
  
if __name__ == "__main__":
  main()

Submission status: Runtime Error

Solution code:
N = int(input())
G = [[] for i in range(N)]
for i in range(N-1):
  u, v, w = list(map(int, input().split()))
  u -= 1
  v -= 1
  w = w % 2
  G[u].append([v, w])
  G[v].append([u, w])
  
res = [-1] * N
def dfs(u, p, c):
  if res[u] != -1:
    return 0
  res[u] = c
  for n in G[u]:
    if n[0] == p:
      continue
    if n[1] == 1:
      dfs(n[0], u, 1-c)
    else:
      dfs(n[0], u, c)
  
def main():
  dfs(0, -1, 1)
  for i in res:
    print(i)
  
  
if __name__ == "__main__":
  main()

Submission status: Runtime Error

Solution code:
from collections import defaultdict

class Tree:
  def __init__(self):
    self.edges = defaultdict(set)
  
  def add(self, x, y, w):
    self.edges[x].add((y, w))
    self.edges[y].add((x, w))
  
  def traverse(self, start):
    return self._traverse(start, 0, set([start]))
  
  def _traverse(self, start, dist, already_visited):
    out_nodes = self.edges[start]
    for out_node, w in out_nodes:
      if out_node in already_visited:
        continue
      new_dist = dist + w
      yield (out_node, new_dist)
      already_visited.add(out_node)
      for res in self._traverse(out_node, new_dist, already_visited):
        yield res
      
n = int(input())
tree = Tree()
for _ in range(n-1):
  xyw = list(map(int, input().split()))
  tree.add(*xyw)

start = 1
node_dists = list(tree.traverse(start))
node_dists.append((start, 0))
node_dists = sorted(node_dists, key=lambda x: x[0])

for node, dist in node_dists:
  print(1 if dist % 2 == 0 else 0)

Submission status: Runtime Error

Solution code:
from collections import defaultdict

class Tree:
  def __init__(self):
    self.edges = defaultdict(set)
  
  def add(self, x, y, w):
    self.edges[x].add((y, w))
    self.edges[y].add((x, w))
  
  def traverse(self, start):
    return self._traverse(start, 0, set([start]))
  
  def _traverse(self, start, dist, already_visited):
    out_nodes = self.edges[start]
    for out_node, w in out_nodes:
      if out_node in already_visited:
        continue
      new_dist = dist + w
      yield (out_node, new_dist)
      for res in self._traverse(out_node, new_dist, already_visited | set([out_node])):
        yield res
      
n = int(input())
tree = Tree()
for _ in range(n-1):
  xyw = list(map(int, input().split()))
  tree.add(*xyw)

start = 1
node_dists = list(tree.traverse(start))
node_dists.append((start, 0))
node_dists = sorted(node_dists, key=lambda x: x[0])

for node, dist in node_dists:
  print(1 if dist % 2 == 0 else 0)

Submission status: Runtime Error

Solution code:
from collections import defaultdict

class Tree:
  def __init__(self):
    self.edges = defaultdict(set)
  
  def add(self, x, y, w):
    self.edges[x].add((y, w))
    self.edges[y].add((x, w))
  
  def traverse(self, start):
    return self._traverse(start, 0, set([start]), [])
  
  def _traverse(self, start, dist, already_visited, result):
    out_nodes = self.edges[start]
    for out_node, w in out_nodes:
      if out_node in already_visited:
        continue
      new_dist = dist + w
      result.append((out_node, new_dist))
      if len(result) > n:
        break
      self._traverse(out_node, new_dist, already_visited | set([out_node]), result)
    return result
      
n = int(input())
tree = Tree()
for _ in range(n-1):
  xyw = list(map(int, input().split()))
  tree.add(*xyw)

start = n
node_dists = list(tree.traverse(start))
node_dists.append((start, 0))
node_dists = sorted(node_dists, key=lambda x: x[0])

for node, dist in node_dists:
  print(1 if dist % 2 == 0 else 0)

Submission status: Runtime Error

Solution code:
from collections import defaultdict

class Tree:
  def __init__(self):
    self.edges = defaultdict(set)
  
  def add(self, x, y, w):
    self.edges[x].add((y, w))
    self.edges[y].add((x, w))
  
  def traverse(self, start):
    return self._traverse(start, 0, set([start]), [])
  
  def _traverse(self, start, dist, already_visited, result):
    out_nodes = self.edges[start]
    for out_node, w in out_nodes:
      if out_node in already_visited:
        continue
      new_dist = dist + w
      result.append((out_node, new_dist))
      self._traverse(out_node, new_dist, already_visited | set([out_node]), result)
    return result
      
n = int(input())
tree = Tree()
for _ in range(n-1):
  xyw = list(map(int, input().split()))
  tree.add(*xyw)

start = n
node_dists = list(tree.traverse(start))
node_dists.append((start, 0))
node_dists = sorted(node_dists, key=lambda x: x[0])

for node, dist in node_dists:
  print(1 if dist % 2 == 0 else 0)

Submission status: Runtime Error

Solution code:
from collections import defaultdict

class Tree:
  def __init__(self):
    self.edges = defaultdict(set)
  
  def add(self, x, y, w):
    self.edges[x].add((y, w))
    self.edges[y].add((x, w))
  
  def traverse(self, start):
    return self._traverse(start, 0, set([start]), [])
  
  def _traverse(self, start, dist, already_visited, result):
    out_nodes = self.edges[start]
    for out_node, w in out_nodes:
      if out_node in already_visited:
        continue
      new_dist = dist + w
      result.append((out_node, new_dist))
      self._traverse(out_node, new_dist, already_visited | set([out_node]), result)
    return result
      
n = int(input())
tree = Tree()
for _ in range(n-1):
  xyw = list(map(int, input().split()))
  tree.add(*xyw)

start = 2
node_dists = list(tree.traverse(start))
node_dists.append((start, 0))
node_dists = sorted(node_dists, key=lambda x: x[0])

for node, dist in node_dists:
  print(1 if dist % 2 == 0 else 0)

Submission status: Runtime Error

Solution code:
# 再起の回数？
N = int(input())
G = [[] for i in range(N)]
for i in range(N-1):
  u, v, w = list(map(int, input().split()))
  u -= 1
  v -= 1
  w = w % 2
  G[u].append([v, w])
  G[v].append([u, w])
  
res = [0] * N
def dfs(u, p, c):
  res[u] = c
  for n in G[u]:
    if n[0] == p:
      continue
    if n[1] == 1:
      dfs(n[0], u, 1-c)
    else:
      dfs(n[0], u, c)
  
def main():
  dfs(0, -1, 1)
  for i in res:
    print(i)
  
  
if __name__ == "__main__":
  main()

Submission status: Runtime Error

Solution code:
from collections import defaultdict

class Tree:
  def __init__(self):
    self.edges = defaultdict(set)
  
  def add(self, x, y, w):
    self.edges[x].add((y, w))
    self.edges[y].add((x, w))
  
  def traverse(self, start):
    return self._traverse(start, 0, set([start]), [])
  
  def _traverse(self, start, dist, already_visited, result):
    out_nodes = self.edges[start]
    for out_node, w in out_nodes:
      if out_node in already_visited:
        continue
      new_dist = dist + w
      result.append((out_node, new_dist))
      self._traverse(out_node, new_dist, already_visited | set([out_node]), result)
    return result
      
n = int(input())
tree = Tree()
for _ in range(n-1):
  xyw = list(map(int, input().split()))
  tree.add(*xyw)

node_dists = list(tree.traverse(1))
print(0)
"""
node_dists.append((1, 0))
node_dists = sorted(node_dists, key=lambda x: x[0])

for node, dist in node_dists:
  print(1 if dist % 2 == 0 else 0)
"""

Submission status: Runtime Error

Solution code:
from collections import defaultdict

class Tree:
  def __init__(self):
    self.edges = defaultdict(set)
  
  def add(self, x, y, w):
    self.edges[x].add((y, w))
    self.edges[y].add((x, w))
  
  def traverse(self, start):
    return self._traverse(start, 0, set([start]), [])
  
  def _traverse(self, start, dist, already_visited, result):
    out_nodes = self.edges[start]
    for out_node, w in out_nodes:
      if out_node in already_visited:
        continue
      new_dist = dist + w
      result.append((out_node, new_dist))
      self._traverse(out_node, new_dist, already_visited | set([out_node]), result)
    return result
      
n = int(input())
tree = Tree()
for _ in range(n-1):
  xyw = list(map(int, input().split()))
  tree.add(*xyw)

print(0)
"""
node_dists = list(tree.traverse(1))
node_dists.append((1, 0))
node_dists = sorted(node_dists, key=lambda x: x[0])

for node, dist in node_dists:
  print(1 if dist % 2 == 0 else 0)
""")

Submission status: Runtime Error

Solution code:
from collections import defaultdict

class Tree:
  def __init__(self):
    self.edges = defaultdict(set)
  
  def add(self, x, y, w):
    self.edges[x].add((y, w))
    self.edges[y].add((x, w))
  
  def traverse(self, start):
    return self._traverse(start, 0, set([start]), [])
  
  def _traverse(self, start, dist, already_visited, result):
    out_nodes = self.edges[start]
    for out_node, w in out_nodes:
      if out_node in already_visited:
        continue
      new_dist = dist + w
      result.append((out_node, new_dist))
      self._traverse(out_node, new_dist, already_visited | set([out_node]), result)
    return result
      
n = int(input())
tree = Tree()
for _ in range(n-1):
  xyw = list(map(int, input().split()))
  tree.add(*xyw)

print """
node_dists = list(tree.traverse(1))
node_dists.append((1, 0))
node_dists = sorted(node_dists, key=lambda x: x[0])

for node, dist in node_dists:
  print(1 if dist % 2 == 0 else 0)
"""

Submission status: Runtime Error

Solution code:
N = int(input())
G = {i:[] for i in range(N)}
for i in range(N-1):
  u, v, w = list(map(int, input().split()))
  u -= 1
  v -= 1
  w = w % 2
  G[u].append([v, w])
  G[v].append([u, w])
res = [0] * N

def dfs(u, p, c):
  res[u] = c
  for n in G[u]:
    if n[0] == p:
      continue
    if n[1]:
      dfs(n[0], u, 1-c)
    else:
      dfs(n[0], u, c)
  
def main():
  dfs(0, -1, 1)
  for i in res:
    print(i)
  
  
if __name__ == "__main__":
  main()

Submission status: Runtime Error

Solution code:
from collections import defaultdict

class Tree:
  def __init__(self):
    self.edges = defaultdict(set)
  
  def add(self, x, y, w):
    self.edges[x].add((y, w))
    self.edges[y].add((x, w))
  
  def traverse(self, start):
    return self._traverse(start, 0, set([start]), [])
  
  def _traverse(self, start, dist, already_visited, result):
    out_nodes = self.edges[start]
    for out_node, w in out_nodes:
      if out_node in already_visited:
        continue
      new_dist = ((dist % 2) + (w % 2)) % 2
      result.append((out_node, new_dist))
      self._traverse(out_node, new_dist, already_visited | set([out_node]), result)
    return result
      
n = int(input())
tree = Tree()
for _ in range(n-1):
  xyw = list(map(int, input().split()))
  tree.add(*xyw)

node_dists = list(tree.traverse(1))
node_dists.append((1, 0))
node_dists = sorted(node_dists, key=lambda x: x[0])

for node, dist in node_dists:
  print(1 if dist % 2 == 0 else 0)

Submission status: Runtime Error

Solution code:
from collections import defaultdict

class Tree:
  def __init__(self):
    self.edges = defaultdict(set)
  
  def add(self, x, y, w):
    self.edges[x].add((y, w))
    self.edges[y].add((x, w))
  
  def traverse(self, start):
    return self._traverse(start, 0, set([start]), [])
  
  def _traverse(self, start, dist, already_visited, result):
    out_nodes = self.edges[start]
    for out_node, w in out_nodes:
      if out_node in already_visited:
        continue
      result.append((out_node, dist+w))
      self._traverse(out_node, dist+w, already_visited | set([out_node]), result)
    return result
      
n = int(input())
tree = Tree()
for _ in range(n-1):
  xyw = list(map(int, input().split()))
  tree.add(*xyw)

node_dists = list(tree.traverse(1))
node_dists.append((1, 0))
node_dists = sorted(node_dists, key=lambda x: x[0])

for node, dist in node_dists:
  print(1 if dist % 2 == 0 else 0)

Submission status: Runtime Error

Solution code:
N = int(input())
G = {i:[] for i in range(N)}
for i in range(N-1):
  u, v, w = list(map(int, input().split()))
  u -= 1
  v -= 1
  w = w % 2
  G[u].append([v, w])
  G[v].append([u, w])
res = [0] * N

def dfs(u, p, c):
  res[u] = c
  for n in G[u]:
    if n[0] == p:
      continue
    if n[1]:
      dfs(n[0], u, (c+1)%2)
    else:
      dfs(n[0], u, c)
  
def main():
  dfs(0, -1, 0)
  for i in res:
    print(i)
  
  
if __name__ == "__main__":
  main()

Submission status: Runtime Error

Solution code:
n = int(input())
d = {}
for i in range(n - 1):
  u, v, w = map(int, input().split())
  if u in d:
    d[u].append([v, w])
  else:
    d[u] = [[v, w]]
  if v in d:
    d[v].append([u, w])
  else:
    d[v] = [[u, w]]

start = list(d.keys())[0]
ans = [0 for _ in range(n)]

def walk(poj):
  ans[poj - 1] = 1
  for i, way in enumerate(d[poj]):
    if way[1] % 2 == 0:
      d[poj][i][1] = 1
      walk(way[0])
      
walk(start)
      
for res in ans:
  print(res)

Submission status: Runtime Error

Solution code:
n=int(input())

nodes=[]
for i in range(n+1):
    nodes.append([])
for i in range(n-1):
    s,e,w = map(int,input().split())
    nodes[s].append((e,w))
    nodes[e].append((s,w))

col=[-1]*(n+1)

def dfs(now,color):
    col[now]=color
    for n,w in nodes[now]:
        if col[n]!=-1:
            continue
        if w%2==0:
            dfs(n,color)
        else:
            dfs(n,1-color)

dfs(1,1)

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

Submission status: Runtime Error

Solution code:
def dfs(now,color):
    col[now]=color
    for n,w in nodes[now]:
        if col[n]!=-1:
            continue
        if w%2==0:
            dfs(n,color)
        else:
            dfs(n,1-color)

n=int(input())

nodes=[]
for i in range(n+1):
    nodes.append([])
for i in range(n-1):
    s,e,w = map(int,input().split())
    nodes[s].append((e,w))
    nodes[e].append((s,w))

col=[-1]*(n+1)

dfs(1,1)

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