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:
from sys import stdin
import numpy as np
# import math
# import random
# import fractions
import sys
sys.setrecursionlimit(100000)
# N = int(stdin.readline().rstrip().split()[0])
# A = [int(x) for x in stdin.readline().rstrip().split()]
# N, X = [int(x) for x in stdin.readline().rstrip().split()]
# S = stdin.readline().rstrip().split()[0]
N = int(stdin.readline().rstrip().split()[0])
mat = np.zeros((N+1,N+1))
for i in range(N-1):
  u,v,w = [int(x) for x in stdin.readline().rstrip().split()]
  if u > v:
    u = v
    v = u
  mat[u,v] = w
color_list = [-1]*(N+1)
def f(i, color):
  nodes = mat[i,:].nonzero()
  for node in nodes[0]:
    if mat[i, node]%2==0:
      color_list[node]=color
      f(node,color)
    else:
      color_list[node] = not color
      f(node,not color)
      
color_list[1]=True
f(1, True)
c_list = [(i+1)//2 for i in color_list]
for i in range(1,N+1):
  print(c_list[i])

Submission status: Runtime Error

Solution code:
from collections import defaultdict
g = defaultdict(list)
visited = defaultdict(bool)
N = int(input())
ans = [0] * N

def dfs(v, d=0):
    if visited[v]:
        return
    visited[v] = True
    if d % 2:
        ans[v-1] = 1
    for c,w in g[v]:
        dfs(c, d+w)

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

dfs(1)

for a in ans:
    print(a)

Submission status: Runtime Error

Solution code:
N = int(input())
W = [ [] for _ in range(N) ]
dist = [-1] * N
dist[0] = 0

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

def dfs(cur, d, prev):
    for v, w in W[cur]:
        if v == prev:
            continue
        dist[v] = d + w
        dfs(v, dist[v], cur)
    

dfs(0, 0, -1)

for ans in dist:
    print(ans % 2)

Submission status: Runtime Error

Solution code:
# 辺と長さが与えられる
# 頂点1からの各点の距離を計算する
sys.setrecursionlimit(100000)
N = int(input())
path = [[] for _ in range(N + 1)]
for _ in range(N - 1):
  u, v, w = map(int, input().split())
  # 無向グラフ
  path[u].append((v, w))
  path[v].append((u, w))
  # d[0]は使わない
  d = [-1] * (N + 1)

  def walk(i, c):
    if d[i] == -1:
      d[i] = c
      for x, w in path[i]:
        walk(x, c + w)

        walk(1, 0)
        for c in d[1:]:
          print(c)

Submission status: Runtime Error

Solution code:
    sys.setrecursionlimit(100000)
    N = int(input())
    path = [[] for _ in range(N + 1)]
    for _ in range(N - 1):
        u, v, w = map(int, input().split())
        # 無向グラフ
        path[u].append((v, w))
        path[v].append((u, w))
    # d[0]は使わない
    d = [-1] * (N + 1)

    def walk(i, c):
        if d[i] == -1:
            d[i] = c
            for x, w in path[i]:
                walk(x, c + w)

    walk(1, 0)
    for c in d[1:]:
        print(c)

Submission status: Runtime Error

Solution code:
n = int(input())
UVW = []
UF = [[0,0] for _ in range(n+1)]
for i in range(n-1):
    u,v,w = map(int,input().split())
    UF[v][0] = u
    UF[v][1] = w

def search(UF,loc):
    if UF[loc][0] == loc:
        return UF[loc]
    else:
        UF[loc] = search(UF,UF[loc])
        return UF[loc]
print(0)
for i in range(2,n+1):
    if search(UF,2)[1]%2 == 1:
        print(1)
    else:
        print(0)

Submission status: Runtime Error

Solution code:

def spaceinput():
    return list(map(int,input().split(" ")))




def search(n):
    if visit[n]:
        return
    visit[n]=1
    for x in L[n]:
        if x[1]==0:
            col[x[0]]=col[n]
        else:
            col[x[0]]=(col[n]+1)%2
        search(x[0])


N=int(input())

col=[-1]*(N+1)
visit=[0]*(N+1)
L=[[] for i in range(N+1)]

for i in range(N-1):
    u,v,w=spaceinput()
    
    if w%2==0:
        L[u].append((v,0))
        L[v].append((u,0))
    else:
        L[u].append((v,1))
        L[v].append((u,1))

    

col[1]=0
search(1)
for sc in col[1:]:
    print(sc)

Submission status: Runtime Error

Solution code:
from operator import itemgetter

def dfs(n,team):
    li[n-1] = team
    for i in grp[n-1]:
        if(li[i[0]-1]==-1):
            dfs(i[0],(team+i[1])%2)



N = int(input())
li = [-1]*N
uvw = [[int(x) for x in input().split()]for _ in range(N-1)]
uvw.sort(key=itemgetter(0))
grp = [[]for _ in range(N)]
for i in uvw:
    grp[i[0]-1].append([i[1],i[2]])
    grp[i[1]-1].append([i[0],i[2]])
dfs(1,0)
for i in li:
    print(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())
    tree_dic[ui].append((vi, wi))
    tree_dic[vi].append((ui, wi))

distance_dic = {1:0}
def decide_color(distance_dic, current_point, tree_dic):
    for next_point, add_distance in tree_dic[current_point]:
        if next_point not in distance_dic:
            distance_dic[next_point] = add_distance + distance_dic[current_point]
            decide_color(distance_dic, next_point, tree_dic)
        elif add_distance + distance_dic[current_point] < distance_dic[next_point]:
            distance_dic[next_point] = add_distance + distance_dic[current_point]
            decide_color(distance_dic, next_point, tree_dic)

decide_color(distance_dic, 1, tree_dic)

for i in range(1, N+1):
    distance = distance_dic[i]
    if distance % 2 == 1:
        print(1)
    else:
        print(0)

Submission status: Runtime Error

Solution code:
N = int(input())
UV0 = [[] for _ in range(N)]
UV1 = [[] for _ in range(N)]
for i in range(N-1):
  uvw = list(map(int,input().split()))
  if uvw[2]%2 == 0:
    UV0[uvw[0]-1].append(uvw[1])
    UV0[uvw[1]-1].append(uvw[0])
  if uvw[2]%2 == 1:
    UV1[uvw[0]-1].append(uvw[1])
    UV1[uvw[1]-1].append(uvw[0])
WB = [0]*N
q = [i+1 for i in range(N)]
while q:
  a = q.pop(0)
  for i in UV1[a-1]:
    q.pop(q.index(i))
  for i in UV1[a-1]:
    WB[i-1] += 1
for j in range(N):
  print(WB[j]%2)

Submission status: Runtime Error

Solution code:
n=int(input())
aa={}
for _ in range(n-1):
    u,v,w=map(int,input().split())
    if w % 2:
        aa.setdefault(u, set()).add(v)
bb = [-1] * n
for u in aa:
    if bb[u-1] < 0:
        for v in aa[u]:
            if bb[v-1] >= 0:
                bb[u-1] = 1-bb[v-1]
                break
        else:
            bb[u-1] = 0
    for v in aa[u]:
        if bb[v-1] < 0:
            bb[v-1] = 1-bb[u-1]
        else:
            assert bb[v-1] == 1-bb[u-1]
for b in bb:
    print(1 if b == 1 else 0)

Submission status: Runtime Error

Solution code:
from sys import stdin
import math
import fractions
from collections import deque

WHITE = 0
BLACK = 1

N = int(stdin.readline().rstrip())
data = [list(map(int, stdin.readline().rstrip().split())) for _ in range(N-1)]

# 根から頂点までの距離
# 根は適当な頂点を選べば良いので、u_0とする
dist = [None] * (N+1)
dist[data[0][0]] = 0

# 根からの距離を算出
for u, v, w in data:
    # 木構造なので、どちらか一方はすでに求まっているはず
    if dist[u] != None:
        dist[v] = dist[u] + w
    else:
        dist[u] = dist[v] + w

# distが偶数の頂点には白で、奇数の頂点には黒で塗ることとする
for i in range(1, N+1):
    if dist[i] % 2 == 0:
        print(WHITE)
    else:
        print(BLACK)

Submission status: Runtime Error

Solution code:
class G:
    def __init__(self, i):
        self.graph = [i]
        self.id = i
        self.gid = -1


def concat(u, v):
    g1 = data[u].graph
    g2 = data[v].graph
    g = g1 + g2
    all_g.append(g)
    id = min(data[u].id, data[v].id)
    
    for elm in g:
        data[elm].graph = g
        data[elm].id = id

def make_revid(id):
    revid = id + 1 if id %2 == 0 else id - 1
    return revid


def sep_g(u, v):
    global gid_
    global all_gid

    gid0 = data[u].gid
    gid1 = data[v].gid
    cond1 = data[u].gid >= 0
    cond2 = data[v].gid >= 0

    if cond1 or cond2:
        if cond1 and cond2:
            if gid0 <= gid1:
                old_gid = data[v].gid
                new_gid = make_revid(gid0)
                data[v].gid = new_gid
            else:
                old_gid = data[u].gid
                new_gid = make_revid(gid1)
                data[u].gid = new_gid

        elif cond1 and not cond2:
            old_gid = data[v].gid
            new_gid = make_revid(gid0)
            data[v].gid = new_gid
        elif not cond1 and not cond2:
            old_gid = data[u].gid
            new_gid =  make_revid(gid1)
            data[u].gid = new_gid

        all_gid.remove(old_gid)
        all_gid.append(new_gid)

    else:
        data[u].gid = gid_
        data[v].gid = gid_ + 1
        all_gid += [gid_, gid_+1]
        gid_ += 2


gid_ = 0
N = int(input())

odd_pairs = []
all_g = []
all_gid = []

data = {}

for i in range(N):
    g = G(i)
    data[i] = g
    all_g.append(g)

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

    if w %2 == 1:
        odd_pairs.append([u, v, w])
        continue
    
    if v not in data[u].graph:
        concat(u, v)

for u, v, w in odd_pairs:
    sep_g(u, v)


for i in range(N):
    gid = data[i].gid
    if gid < 0:
        out = 0
    else:
        out = gid % 2
    print(out)

Submission status: Runtime Error

Solution code:
def sol(inp=input):
    n=int(inp())
    pots=[None for _ in range(n)]
    edges=[list(map(int,inp().split())) for _ in range(n-1)]
    adj=[{} for _ in range(n)]
    for e in edges:
        adj[e[0]-1][e[1]-1]=e[2]
        adj[e[1]-1][e[0]-1]=e[2]
    
    def dfs(node,pot):
        pots[node]=pot
        for v in adj[node]:
            if pots[v] is None:
                dfs(v,pots[node]+adj[node][v])
    dfs(0,0)
    return [str(p%2) for p in pots]
for c in sol():
  	print(c)

Submission status: Runtime Error

Solution code:
n = int(input())
ans = [0 for i in range (n)]
for i in range(n):
  a,b,c = map(int,input().split())
  if c % 2 == 1:
    if ans[a-1] == ans[b-1]:
      ans[b-1] = 1 - ans[b-1]
for i in range(n):
  print(ans[i])

Submission status: Runtime Error

Solution code:
n = int(input())
U = [[int(a) for a in input().split()] for _ in range(n-1)]
 
 
arr = [-1] * n
dic = {}
for u, v, w in U:
    if u in dic:
        dic[u].add((v, w))
    else:
        dic[u] = set([(v, w)])
 
    if v in dic:
        dic[v].add((u, w))
    else:
        dic[v] = set([(u, w)])
 
 
done = set()
stack = [0]
while len(done) < n:
    u = stack.pop()
    done.add(u)
    for v, w in dic[u]:
        if not v in done:
            arr[v-1] = (arr[u-1] + w) % 2
            stack.append(v)

 
for i in arr:
    print(i)

Submission status: Runtime Error

Solution code:
import numpy as np
N = int(input())
w = np.zeros(shape = (N,N))
flag = N-1
while flag:
    l = input().split()
    i = int(l[0])-1
    j = int(l[1])-1
    w[i][j] = int(l[2])
    flag -= 1
color = np.ones(shape = (N,))
for i in range(N-1):
    for j in range(i+1,N):
        weight = w[i][j]
        if weight % 2 == 0:
            color[j] = color[i]       
        else :
            color[j] = -color[i]
for i in color:
    if i == -1:
        print(0)
    else:
        print(1)

Submission status: Runtime Error

Solution code:
nnn = int(input())

a = [-2 for i in range(nnn)]
a[0] = 0

def m():
	return map(int,input().split())


def oon(x,n,nn,k):
	global a
	for i in range(len(x[n])):
		if x[n][i][0] != nn and a[nn] != -2:
			p = (k + x[n][i][1]) % 2
			if p == 0:
				a[x[n][i][0]] = 0
			else:
				a[x[n][i][0]] = 1
			oon(x,x[n][i][0],n,p)



b = [[] for i in range(nnn)]

for i in range(nnn-1):
	z,y,c = m();
	b[z-1].append([y-1,c])
	b[y-1].append([z-1,c])

oon(b,0,0,0)

for i in range(nnn):
	print(a[i])

Submission status: Runtime Error

Solution code:
N=int(input())
root=[-1]*N
color=[-1]*N
from collections import defaultdict
tree=dict()
branch=defaultdict(set)
for i in range(N):
    tree[i]={i}
def search(i):
    if root[i]>=0:
        root[i]=search(root[i])
        return root[i],cnt
    return i
def makecolor(u,v):
    if color[u]==color[v]==-1:
        color[u]=0
        color[v]=1
    elif color[u]==-1:
        color[v]=(color[u]+1)%2
    elif color[v]==-1:
        color[u]=(color[v]+1)%2
    else:
        if color[u]==color[v]:
            if len(tree[u])<=len(tree[v]):
                u,v=v,u
            for x in tree[v]:
                color[x]=(color[x]+1)%2
for i in range(N-1):
    u,v,w=map(int,input().split())
    if w%2==0:
        continue
    u-=1
    v-=1
    branch[u]|={v}
    branch[v]|={u}
    ru=search(u)
    rv=search(v)
    if ru==rv:
        continue
    
    if root[ru]<=root[rv]:
        root[rv]+=root[ru]
        root[ru]=rv
        makecolor(rv,ru)
        tree[rv]|=tree[ru]
    else:
        root[ru]+=root[rv]
        root[rv]=ru
        makecolor(ru,rv)
        tree[ru]|=tree[rv]
color=[i if i!=-1 else 1 for i in color]
for i in range(N):
    print(color[i])

Submission status: Runtime Error

Solution code:
nnn = int(input())

a = [-2 for i in range(nnn)]
a[0] = 0

def m():
	return map(int,input().split())


def oon(x,n,nn,k):
	global a
	for i in range(len(x[n])):
		if x[n][i][0] != nn and a[nn] != -2:
			p = (k + x[n][i][1]) % 2
			if p == 0:
				a[x[n][i][0]] = 0
			else:
				a[x[n][i][0]] = 1
			oon(x,x[n][i][0],n,p)



b = [[] for i in range(nnn)]

for i in range(nnn-1):
	z,x,c = m();
	b[z-1].append([x-1,c])
	b[x-1].append([z-1,c])

oon(b,0,0,0)

for i in range(nnn):
	print(a[i])

Submission status: Runtime Error

Solution code:
tree_list = []
tree_dict = {}
N = int(input())
for n in range(N):
  tree_list.append(input())
u,v,w = tree_list[0].split(" ")
if w % 2 == 0
  tree_dict[u] = 0
  tree_dict[v] = 0
else
  tree_dict[u] = 0
  tree_dict[v] = 1
for n in range(1,N):
  u,v,w = tree_list[n].split(" ")
  if w % 2 == 0:
    if u not in tree_dict.keys():
      tree_dict[u] = tree_dict[v]
    else:
      tree_dict[v] = tree_dict[u]
for i in list(tree_dict.value()):
  print(i)

Submission status: Runtime Error

Solution code:
from collections import deque


ans = {1:1}

def dfs(tree,nodes):
    for node in nodes:
        nexts = tree[node]
        for next,l in nexts.items():
            if l% 2 == 0 :
                ans[next] = ans[node]
            else:
                ans[next] = 1 - ans[node]
            tree[next].pop(node)

        dfs(tree,nexts)

    return 0




if __name__ == "__main__":
    tree= {}
    N = int(input())
    if N == 1:
        u, v, w = list(map(int, input().split(" ")))
        if w %2 == 1:
            print(1)
            print(0)
        else:
            print(0)
            print(0)
    else:
        for i in range(N-1):
            u,v,w = list(map(int,input().split(" ")))

            if u not in tree:
                tree[u] = {}
            tree[u][v] = w

            if v not in tree:
                tree[v] = {}
            tree[v][u] = w
        dfs(tree,[1])
        for i in range(1,N+1):
            print(ans[i])

Submission status: Runtime Error

Solution code:
# coding: utf-8
import re
import bisect
from datetime import datetime as dt
N = input()
color = [-1 for i in range(N)]

M = []
for i in range(N-1):
    M.append(map(int, raw_input().split()))
while len(M) != 0:
    for i, m in M:
        v = m[0]
        u = m[1]
        w = m[2]
        if w % 2 == 0:
            if color[u - 1] != -1:
                color[v - 1] = color[u - 1]
            elif color[v - 1] != -1:
                color[u - 1] = color[v - 1]
            else:
                color[u - 1] = 0
                color[v - 1] = 0
        else:
            if color[u - 1] != -1:
                color[v - 1] = (color[u - 1] + 1) % 2
            elif color[v - 1] != -1:
                color[u - 1] = (color[v - 1] + 1) % 2
        if color[v - 1] != -1 or color[u - 1] != -1:
            M.pop(i)

for i in color:
    print str(i)

Submission status: Runtime Error

Solution code:
n = int(input())
tree = []
k = n
for i in range(n-1):
     a = list(map(int,input().split()))
     if a[2]%2 == 1:
          f = 0
          for j in range(len(tree)):
               if a[0]-1 == tree[j][0]:
                    tree[j][1].append(a[1]-1)
                    f = 1
          if f == 0:
               tree.append([a[0]-1,[a[1]-1]])
def f(ans,tree_i,tree):
     if ans[tree_i[0]] == "#":
          ans[tree_i[0]] = 0
     for i in tree_i[1]:
          if ans[i] =="#":
               ans[i] = (ans[tree_i[0]]+1)%2
          for j in range(len(tree)):
               if tree[j][0] == i:
                    f(ans,tree[j],tree)
     tree.remove(tree_i)
     return ans


ans = ["#"]*n
while len(tree)>0:
     ans = f(ans,tree[0],tree)
          

for i in range(n):
     if ans[i] == "#":
          print(0)
     else:
          print(ans[i])

Submission status: Runtime Error

Solution code:
N = int(input())
M = [[-1 for i in range(N)] for i in range(N)]
for i in range(N-1):
  u,v,w = [int(item) for item in input().split()]
  if w % 2 != 0:
    M[u-1][v-1] = 1
  else:
    M[u-1][v-1] = 0

queue = [0]
fq = [0]
ans = []
 
while len(queue) > 0:
  i = queue.pop(0)
  f = fq.pop(0)
  ans.append(f)
  for j in range(N):
    if M[i][j] == 1:
      queue.append(j)
      fq.append(1-f)
      M[i][j] = -1
    elif M[i][j] == 0:
      queue.append(j)
      fq.append(f)
      M[i][j] = -1
    
for i in range(N):
  print (ans[i])

Submission status: Runtime Error

Solution code:
from sys import stdin

def check(edge, group, e):
    
    for c in edge[e]:
        if c not in group:
            group.add(c)
            check(edge, group, c)

    return group

def calc(n, g):

    edge = {x:set() for x in range(n)}

    for e in g:
        if e[2] % 2 == 0:
            edge[e[0]-1].add(e[1]-1)
            edge[e[1]-1].add(e[0]-1)
    s = -1
    for k,v in edge.items():
        if len(v) > 0:
            s = k
            break
    
    if s == -1:
        return n
    
    group = set()
    group = check(edge, group, s)

    ans = []
    for x in range(n):
        if x in group:
            ans.append(0)
        else:
            ans.append(1)
    return ans

def main():
    n = int(stdin.readline())
    g = []
    for x in range(n-1):
        g.append([int(x) for x in stdin.readline().split()])
    ans = calc(n, g)
    
    for a in ans:
        print(a)
    
if __name__=='__main__':
    main()

Submission status: Runtime Error

Solution code:
import numpy as np
N = int(input())
w = np.zeros(shape = (N,N))
flag = N-1
while flag:
    l = input().split()
    i = int(l[0])-1
    j = int(l[1])-1
    w[i][j] = int(l[2])
    flag -= 1
color = np.ones(shape = (N,))
for i in range(N//2 + 1):
    for j in range(i+1,N):
        weight = w[i][j]
        if weight!=0 and weight % 2 == 0:
            color[j] = color[i]       
        else:
            color[j] = -color[i]
for i in color:
    if i == -1:
        print(0)
    else:
        print(1)

Submission status: Runtime Error

Solution code:
N = int(input())
#dic = {}
order = "0"*N
#for i in range(N-1):
#	*key, val = input().split()
#	dic[key[0] + " " + key[1]] = int(val)

L = [list(map(int, input().split())) for i in range(N-1)]

print(L)
for i in range(N):
	for j in range(N)
		if L[j, 0] == i:
			if L[j, 2]%2 == 1:
				order[L[j,1]] = "1"
#	if key[0]==i+1:

Submission status: Runtime Error

Solution code:
import numpy as np

N = int(input())
col = [-1]*(N+1)
col[1]=0
dist = np.full((N+1,N+1),-1)

def paint(u):
    c = col[u]
    neigh = list(np.where(dist[u]>=0)[0])
    #print(neigh)
    if len(neigh)>0:
        for n in neigh:
            if col[n]<0:
                col[n] = (c+dist[u][n])%2
                paint(n)
    return 0



for i in range(N-1):
    u,v,w = list(map(lambda x: int(x),input().split()))
    dist[u][v] = w%2
    dist[v][u] = w%2

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

Submission status: Runtime Error

Solution code:
class Hen:
    def __init__(self, u, v, w):
        self.u = u
        self.v = v
        self.w = w

    def print(self):
        print(self.u, self.v, self.w)


N = int(input())
# u = [0 for _ in range(N)]
# v = [0 for _ in range(N)]
# w = [0 for _ in range(N)]

chouten = [0 for _ in range(N)]
hen = [None for _ in range(N-1)]

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

hen = sorted(hen, key=lambda h: h.u)


def findfirst(h, n):
    left = 0
    right = len(h)
    while left < right:
        mid = (left + right) // 2
        if h[mid].u == n:
            for i in range(len(h)):
                if mid-i < 0 or h[mid-i].u != n:
                    return mid-i+1
        elif n < h[mid].u:
            right = mid
        else:
            left = mid + 1
    return None


def rec(h, n):
    i = findfirst(h, n)
    if i == None:
        return
    while i < len(h) and h[i].u == n:
        if h[i].w % 2 == 0:
            chouten[h[i].v] = chouten[h[i].u]
        else:
            chouten[h[i].v] = 1 - chouten[h[i].u]
        rec(h, h[i].v)
        i += 1


rec(hen, hen[0].u)

for c in chouten:
    print(c)

Submission status: Runtime Error

Solution code:
n = int(input())
dist = []
for i in range(n-1):
    dist.append(list(map(int, input().split())))

branch = [0]*n

dist.sort()

for i in range(n):
    if dist[i][2] % 2 == 1:
        if branch[dist[i][0]-1] == 0:
            branch[dist[i][1]-1] == 1
        if branch[dist[i][0]-1] == 1:
            branch[dist[i][1]-1] == 0

for j in range(n):
    print(branch[j])

Submission status: Runtime Error

Solution code:
import numpy as np
N = int(input().strip())
edges = np.zeros((N,N))
distance = np.zeros(N)

def find(idx,l):
	route = edges[idx,:]
	for j, x in enumerate(route):
		if x != 0 and (j not in check):
			distance[j]+=(x+l)
			if j not in check:
				check.append(j)
				find(j,x+l)
				#print(j)
			check.append(j)


for i in np.arange(N-1):
	s, d, w = [ int(x) for x in input().strip().split(" ")]
	edges[s-1][d-1] = w
	edges[d-1][s-1] = w
#print(edges)

check = [0]

find(0,0)
#print(distance)
for x in distance:
	if x%2==0:
		print(0)
	else:
		print(1)

Submission status: Runtime Error

Solution code:
import queue

class tree:
    def __init__(self, first,second,dist):
        self.first = first
        self.second = second
        self.dist = True if dist % 2 == 0 else False
        self.check = 0

    def hasPoint(self,checkNum):
        if self.first == checkNum:
            self.check = checkNum
            return True
        elif self.second == checkNum:
            self.check = checkNum
            return True
        else:
            return False

    def getUnusedPoint(self):
        if self.check == 0:
            return False
        if self.check == self.first:
            return self.second
        else:
            return self.first

N = int(input())

treelist = []

anslist = [-1 for i in range(N)]

for i in range(N - 1):
    u,v,w = map(int,input().split())
    branch = tree(u,v,w)
    treelist.append(branch)

q = queue.Queue()
checkItem = treelist.pop(0)
checkItem.hasPoint(checkItem.first)

anslist[checkItem.getUnusedPoint() - 1] = 0

while len(treelist) > 0:
    nextPoint = checkItem.getUnusedPoint()
    poplist = []
    for i in range(len(treelist)):
        if treelist[i].hasPoint(nextPoint):
            poplist.append(i)
    for i in poplist:
        branch = treelist.pop(i)
        source = branch.check - 1
        target = branch.getUnusedPoint() - 1
        anslist[target] = anslist[source] if branch.dist else (anslist[source] + 1) % 2

for num in anslist:
    print(num)

Submission status: Runtime Error

Solution code:
from collections import deque
n=int(input())
color=[0]*n
cnt=[0]*n
edge=[ [] for _ in range(n)]

for i in range(n-1):
  ui, vi, wi = map(int, input().split())
  cnt[ui-1]+=1
  cnt[vi-1]+=1
  edge[ui-1].append([ui-1,[vi-1, wi]])
  edge[vi-1].append([vi-1,[ui-1, wi]])

queue=deque(edge[cnt.index(max(cnt))])
used=[0]*n
used[cnt.index(max(cnt))]=1
while queue:
  #print(queue)
  crt, ei = queue.popleft()
  if ei[1]%2==0: 
    color[ei[0]]=color[crt]
  else:
    color[ei[0]]=color[crt]^1
  
  for ej in edge[ei[0]]:
    if used[ej[0]]==0:
      queue.append(ej)
      edge[ej[1][0]].remove([ej[0], [crt, ei[1]]])
  used[ei[0]]=1

for c in color:
  print(c)

Submission status: Runtime Error

Solution code:
import random
n = int(input())
listA = []
listB = []
listN=[]
stockL=[]
index=0
while index < n-1:
    u, v, w = map(int, input().split())
    if w %2== 1:
        listA.append(u)
        listB.append(v)
        listN.append(u)
        listN.append(v)
    else:
        stockL.append([u, v])
    index+=1

flag=1
while flag:
    flag=0
    index=0
    while index < len(stockL):
        u = stockL[index][0]
        v = stockL[index][1]
        if u in listA:
            if v in listB:
                flag=1
                vI = listB.index(v)
                uI = listA.index(u)
                if random.random() > 0.5:
                    listA[vI], listB[vI] = listB[vI], listA[vI]
                else:
                    listA[uI], listB[uI] = listB[uI], listA[uI]
            else:
                if v in listA:
                    pass
                else:
                    listA.append(v)
                    listA.append(u)
        elif u in listB:
            if v in listA:
                flag=1
                vI = listA.index(v)
                uI = listB.index(u)
                if random.random() > 0.5:
                    listA[vI], listB[vI] = listB[vI], listA[vI]
                else:
                    listA[uI], listB[uI] = listB[uI], listA[uI]
            else:
                if v in listB:
                    pass
                else:
                    listB.append(v)
                    listB.append(u)
        else:
            if v in listB:
                listB.append(u)
                listB.append(v)
            elif v in listA:
                listA.append(u)
                listA.append(v)
            else:
                pass
        index+=1
index2=1
while index2 < n+1:
    if index2 in listA:
        print(0)
    elif index2 in listB:
        print(1)
    else:
        print(0)
    index2+=1

Submission status: Runtime Error

Solution code:
from collections import deque


ans = {1:1}

def dfs(tree,nodes):
    for node in nodes:
        nexts = tree[node]
        for next,l in nexts.items():
            if l% 2 == 0 :
                ans[next] = ans[node]
            else:
                ans[next] = 1 - ans[node]
            tree[next].pop(node)

        dfs(tree,nexts)

    return 0




if __name__ == "__main__":
    tree= {}
    N = int(input())
    if N == 1:
        u, v, w = list(map(int, input().split(" ")))
        if w %2 == 1:
            print(1)
            print(0)
        else:
            print(0)
            print(0)
    else:
        for i in range(N-1):
            u,v,w = list(map(int,input().split(" ")))

            if u not in tree:
                tree[u] = {}
            tree[u][v] = w

            if v not in tree:
                tree[v] = {}
            tree[v][u] = w
            dfs(tree,[1])
            for i in range(1,N+1):
                print(ans[i])

Submission status: Runtime Error

Solution code:
from sys import stdin
import numpy as np
# import math
# import random
# import fractions
# import sys
# sys.setrecursionlimit(100000)
# N = int(stdin.readline().rstrip().split()[0])
# A = [int(x) for x in stdin.readline().rstrip().split()]
# N, X = [int(x) for x in stdin.readline().rstrip().split()]
# S = stdin.readline().rstrip().split()[0]
N = int(stdin.readline().rstrip().split()[0])
mat = np.zeros((N+1,N+1))
for i in range(N-1):
  u,v,w = [int(x) for x in stdin.readline().rstrip().split()]
  if u > v:
    u = v
    v = u
  mat[u,v] = w
color_list = [-1]*(N+1)
def f(i, color):
  nodes = mat[i,:].nonzero()
  for node in nodes[0]:
    if mat[i, node]%2==0:
      color_list[node]=color
      f(node,color)
    else:
      color_list[node] = not color
      f(node,not color)
      
color_list[1]=True
f(1, True)
c_list = [(i+1)//2 for i in color_list]
for i in range(1,N+1):
  print(c_list[i])

Submission status: Runtime Error

Solution code:
N = int(input())
M = [[-1 for i in range(N)] for i in range(N)]
for i in range(N-1):
  u,v,w = [int(item) for item in input().split()]
  if w % 2 != 0:
    M[u-1][v-1] = 1
  else:
    M[u-1][v-1] = 0

queue = [0]
fq = [0]
ans = []

while len(queue) > 0:
  i = queue.pop(0)
  f = fq.pop(0)
  ans.append(f)
  for j in range(N):
    if M[i][j] == 1:
      queue.append(j)
      fq.append(1-f)
      M[i][j] = -1
    elif M[i][j] == 0:
      queue.append(j)
      fq.append(f)
      M[i][j] = -1
    
for i in range(N-1):
  print (ans[i])

Submission status: Runtime Error

Solution code:
n=int(input())
tree=[2]*n
u=[0]*n
v=[0]*n
w=[0]*n
x=[0]*n
for i in range(n-1):
    temp=list(map(int,input().split))
    u[i]=temp[0]
    v[i]=temp[1]
    w[i]=temp[2]
    x[i]=temp[2]%2
    if x[i]==0 and tree[u[i]]==0:
        tree[u[i]]=0
        tree[v[i]]=0
    elif x[i]==0 and tree[u[i]]==1:
        tree[u[i]]=1
        tree[v[i]]=1
    elif x[i]==1 and tree[u[i]]==1:
        tree[u[i]]=1
        tree[v[i]]=0
    elif x[i]==1 and tree[u[i]]==0:
        tree[u[i]]=0
        tree[v[i]]=1
    elif x[i]==0 and tree[u[i]]==2 and tree[v[i]]!=2:
        tree[u[i]]=tree[v[i]]
    elif x[i]==1 and tree[u[i]]==2 and tree[v[i]]!=2:
        tree[u[i]]=1-tree[v[i]]
for i in range(n):
    print(tree[i])

Submission status: Runtime Error

Solution code:
N = int(input())
tree = list()
for(i in range(N)):
  node = input().split(' ')
  tree.append(node)
  
print(tree)

Submission status: Runtime Error

Solution code:
import math
n=int(input())
vertex=[]
node=[]
for i in range(n-1):
    l=input().split()
    vertex.append([int(l[0])-1,int(l[1])-1,int(l[2])])
    
for i in range(n):
    node.append(None)

def toChild(nid,parent):
    if node[nid] is not None:
        return
    
    node[nid]=parent
    for i in range(n-1):
        next_nid=-1
        if vertex[i][0]==nid:
            next_nid=vertex[i][1]
        elif vertex[i][1]==nid:
            next_nid=vertex[i][0]
        if next_nid>=0:
            put=None
            if vertex[i][2]%2==0:
                put=parent
            else:
                put=not parent
            toChild(next_nid,put)
                

toChild(vertex[0][0],True)
ret=""
for x in range(len(node)):
    if node[x] is True:
        print("1")
    else:
        print("0")