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

Solution (Python):
import sys

input_methods=['clipboard','file','key']
using_method=0
input_method=input_methods[using_method]

IN=lambda : map(int, input().split())
mod=1000000007



def main():
	n = int(input())
	dd=[[] for i in range(n)]
	
	
	for i in range(n-1):
		na, nb , dist = IN()
		dd[na-1].append((nb-1, dist))
		dd[nb-1].append((na-1, dist))
	
	
	stock=[(0,0,0)]
	ret=[0]*n
	
	while len(stock)>0:
		(pn, cn, cc) = stock.pop()
		
		
		for next_n, dist in dd[cn]:
			if next_n==pn:
				continue
				
			paint_color = cc
			if dist % 2 == 1:
				paint_color = (cc + 1)%2
			ret[next_n] = paint_color
			stock.append((cn, next_n,paint_color))
			
	for color in ret:
		print(color)
	
	
	
	

isTest=False

def pa(v):
	if isTest:
		print(v)
		
def input_clipboard():
	import clipboard
	input_text=clipboard.get()
	input_l=input_text.splitlines()
	for l in input_l:
		yield l

if __name__ == "__main__":
	if sys.platform =='ios':
		if input_method==input_methods[0]:
			ic=input_clipboard()
			input = lambda : ic.__next__()
		elif input_method==input_methods[1]:
			sys.stdin=open('inputFile.txt')
		else:
			pass
		isTest=True
	else:
		pass
		
			
	ret = main()
	if ret is not None:
		print(ret)

Solution (Python):
inputs = open(0).readlines()
n = int(inputs[0])
uvw = [list(map(int, uvw.split())) for uvw in inputs[1:]]

def dfs(root, option):
    nodes, stack = {}, [(root, 0)]
    while stack:
        current_node, color = stack.pop()
        if current_node in nodes:
            continue
        nodes[current_node] = color
        for n, w in get_next_nodes(current_node):
            if n not in nodes:
                stack.append((n, (color + w) % 2))
    return nodes

def get_next_nodes(node):
    return lst[node].items()

lst = [{} for _ in range(n)]
for u, v, w in uvw:
    lst[u-1][v-1] = lst[v-1][u-1] = w

dct = dfs(0, get_next_nodes)
for i in range(max(dct)+1):
    print(dct[i])

Solution (Python):
n = int(input())
g =[[] for _ in range(n)]
for i 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))
distance = [-1]*n
distance[0] = 0
q = [0]
while q:
  p = q.pop()
  for a,b in g[p]:
    if distance[a] == -1:
      distance[a] = distance[p]+b
      q.append(a)
for i in range(n):
  print((distance[i])%2)

Solution (Python):
import sys
input = sys.stdin.readline
n = int(input())
d = {}
graph = {i:[] for i in range(n)}
for _ in range(n-1):
  u,v,w = map(int,input().split())
  d[(u-1,v-1)] = w
  graph[u-1].append(v-1)
  graph[v-1].append(u-1)
  
  
color = [-1 for i in range(n)] 
color[0] = 0
from collections import deque
queue =deque([0])

while queue:
  p = queue.popleft()
  color_p = color[p]
  for i in graph[p]:
    if color[i] != -1:
      continue
    else:
      if d[(min(i,p),max(i,p))] %2:
        color[i] = 1 - color_p
      else:
        color[i] = color_p
      queue.append(i)

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

Solution (Python):
import sys
input = sys.stdin.readline
n = int(input())
d = {}
graph = {i:[] for i in range(n)}
for _ in range(n-1):
  u,v,w = map(int,input().split())
  d[(u-1,v-1)] = w
  graph[u-1].append(v-1)
  graph[v-1].append(u-1)
  
  
color = [-1 for i in range(n)] 
color[0] = 0
from collections import deque
queue =deque([0])

while queue:
  p = queue.popleft()
  color_p = color[p]
  for i in graph[p]:
    if color[i] != -1:
      continue
    else:
      if d[(min(i,p),max(i,p))] %2:
        color[i] = 1 - color_p
      else:
        color[i] = color_p
      queue.append(i)

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

Solution (Python):
from sys import stdin
from collections import deque
def main():
    
    readline=stdin.readline
    N=int(readline())
    g=[[] for _ in range(N)]
    for _ in range(N-1):
        u,v,w=map(int,readline().split())
        u-=1
        v-=1
        g[u].append((v,w))
        g[v].append((u,w))

    
    d=[0]*N
    is_searched=[False]*N
    is_searched[0]=True
    que=deque([0])
    while len(que)>=1:
        now=que.popleft()
        for x in g[now]:
            if is_searched[x[0]]==False:
                is_searched[x[0]]=True
                d[x[0]]=d[now]+x[1]
                que.append(x[0])

    
    for x in d:
        if x%2==0:
            print(0)
        else:
            print(1)

if __name__=="__main__":
    main()

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

def dfs(v,p,dist):
    for u,w in tree[v]:
        if u==p:
            continue
        else:
            dist[u]=dist[v]+w
            dfs(u,v,dist)
    
n =int(input())
tree = [[] for _ in range(n)]
for _ in range(n-1):
    u,v,w =map(int, input().split())
    tree[u-1].append((v-1,w))
    tree[v-1].append((u-1,w))
dist =[0]*n
dfs(0,-1,dist)

for num in dist:
    if num % 2==0:
        print("1")
    else:
        print("0")

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

def dfs(v, p, dist):
    for u, w in tree[v]:
        if u == p:
            continue
        else:
            dist[u] = dist[v] + w
            dfs(u, v, dist)
 
 
n = int(input())
tree = [[] for _ in range(n)]
for _ in range(n - 1):
    u, v, w = map(int, input().split())
    tree[u - 1].append((v - 1, w))
    tree[v - 1].append((u - 1, w))
 
dist = [0 for _ in range(n)]
dfs(0, -1, dist)
 
for i in dist:
    if i % 2 == 0:
        print(0)
    else:
        print(1)

Solution (Python):
import sys
from collections import deque

sys.setrecursionlimit(100000000)
n = int(input())
G = [[] for _ in range(n)]  
for i in range(n - 1):  
    u, v, w = map(int, input().split())
    u -= 1
    v -= 1
    G[u].append([v, w])
    G[v].append([u, w])
ans = [-1] * n
ans[0] = 0
que = deque([0])
while que:
    tmp = que.popleft()  
    for u, w in G[tmp]:
        if ans[u] != -1:  
            continue
        ans[u] = ans[tmp] + w  
        que.append(u)  

for c in ans:
    if c % 2 == 0:
        print(0)
    else:
        print(1)

Solution (Python):
import sys

sys.setrecursionlimit(100000000)


def dfs(u, c):  
    ans[u] = c  
    for v, w in G[u]:
        if ans[v] != -1:  
            continue
        if ans[v] != c and w % 2 == 0:  
            dfs(v, c)
        elif ans[v] != c and w % 2 != 0:  
            dfs(v, 1-c)


n = int(input())
G = [[] for _ in range(n)]  
for i in range(n-1):  
    u, v, w = map(int, input().split())
    u -= 1
    v -= 1
    G[u].append([v, w])
    G[v].append([u, w])
ans = [-1] * n
dfs(0, 0)
for a in ans:
    print(a)

Solution (Python):
from collections import deque
n = int(input())

mapping = [[] for i in range(n)]

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


already = [False]*n

depth = [0]*n

not_yet = deque(mapping[0])
already[0] = True

for u, v, w in mapping[0]:
    already[v] = True

while not_yet:
    key = not_yet.popleft()
    u, v, w = key[0], key[1], key[2]
    depth[v] = (depth[u]+w)%2  
    
    for key in mapping[v]:
        if already[key[1]]:
            continue
        not_yet.append(key)
        already[key[1]] = True
    
for i in range(n):
    print(depth[i])

Solution (Python):
N = int(input())
g = [[[]for i in range(2)] for j in range(N)]

for i in range(N-1):
    u,v,d = map(int,input().split())
    if d%2 == 0:
        g[u-1][0].append(v-1)
        g[v-1][0].append(u-1)
    else:
        g[u-1][1].append(v-1)
        g[v-1][1].append(u-1)

ans = [-1]*N
ans[0] = 0

stack = [0]
not_visit = [True for i in range(N)]
not_visit[0] = False

while stack:
    now = stack.pop()
    for h in range(2):
        if h == 0: 
            for i in range(len(g[now][h])):
                if not_visit[g[now][h][i]]:
                    not_visit[g[now][h][i]] = False
                    ans[g[now][h][i]] = ans[now]
                    stack.append(g[now][h][i])
        if h == 1: 
            for i in range(len(g[now][h])):
                if not_visit[g[now][h][i]]:
                    not_visit[g[now][h][i]] = False
                    ans[g[now][h][i]] = (ans[now] + 1)%2
                    stack.append(g[now][h][i])

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

Solution (Python):

import sys
sys.setrecursionlimit(100000000)
n = int(input())
graph = [[] for _ in range(n)]
for _ in range(n-1):
  u, v, w = map(int, input().split())
  u -= 1
  v -= 1
  graph[u] += [[v, w]] 
  graph[v] += [[u, w]] 

color = [-1]*n 
def dfs(u, c):
  color[u] = c 
  for v, w in graph[u]:
    if color[v] != -1:
      continue
    if color[v] != c and w % 2 == 0:
      dfs(v, c)
    elif color[v] != c and w % 2 != 0:
      dfs(v, abs(1-c))

  return

dfs(0, 0)
for c in color:
  print(c)

Solution (Python):



import sys


sys.setrecursionlimit(10**5)

def input():
    return sys.stdin.readline().rstrip('\n')

N = int(input())

childsof = [[] for _ in range(N+1)]

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

distances = [-1]*(N+1)
distances[1] = 0

def dfs(i):
    childs = childsof[i]

    for c in childs:
        j = c[0]
        if distances[j] == -1:
            distances[j] = distances[i] + c[1]
            dfs(j)

dfs(1)

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

Solution (Python):
N = int(input())

checked = [False]*(N+1)
edges = [[] for i in range(N+1)]
ans = [0]*(N+1)
for i in range(N-1):
    u,v,w = list(map(int,input().split()))
    edges[u].append((v,w))
    edges[v].append((u,w))

stack = [(1,0)]
while stack:
    p = stack.pop()
    checked[p[0]] = True
    for np in edges[p[0]]:
        if not checked[np[0]]:
            stack.append((np[0],p[1]+np[1]))
            if (p[1]+np[1])%2:
                ans[np[0]] = 1

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

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


def dfs(v, p, dist):
    for u, w in tree[v]:
        if u == p:
            continue
        else:
            dist[u] = dist[v] + w
            dfs(u, v, dist)


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

dist = [0 for _ in range(n)]
dfs(0, -1, dist)

for i in dist:
    if i % 2 == 0:
        print(0)
    else:
        print(1)

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

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

for _ in range(N-1):
    a,b,c=map(int,input().split())
    a-=1
    b-=1
    Graph[a].append((b,c))
    Graph[b].append((a,c))

def dfs(Graph,v,cur=0):
    global color
    color[v]=cur
    for next_v_t in Graph[v]:
        next_v=next_v_t[0]
        w=next_v_t[1]
        if color[next_v]!=-1:
            continue
        ncur=cur
        if w%2==1:
            ncur=1-cur
        dfs(Graph,next_v,ncur)


for v in range(N):
    if color[v]==-1:
        dfs(Graph,v)
for i in color:
    print(i)

Solution (Python):
from collections import deque

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

que = deque([1])
seen = [-1]*(N+1)
seen[1] = 0
cnt = 1
while cnt < N:
    cur = que.pop()
    for item in data[cur]:
        if seen[item[0]] == -1:
            seen[item[0]] = (seen[cur]+item[1]%2)%2
            cnt += 1
            que.append(item[0])

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

Solution (Python):
from collections import deque

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

que = deque([1])
seen = [-1]*(N+1)
seen[1] = 0
cnt = 1
while cnt < N:
    cur = que.popleft()
    for item in data[cur]:
        if seen[item[0]] == -1:
            seen[item[0]] = (seen[cur]+item[1]%2)%2
            cnt += 1
            que.append(item[0])

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

Solution (Python):
import sys
sys.setrecursionlimit(10 ** 7)
n=int(input())
E=[[] for _ in range(n+1)]
for _ in range(n-1):
    u,v,w=map(int,input().split())
    E[u].append((v,w))
    E[v].append((u,w))
color=[-1]*(n+1)

def dfs(i,j):
    color[i] = j
    for w,l in E[i]:
        if color[w] == -1:
            tj = j
            if l % 2 != 0:
                tj = int(not tj)
            dfs(w,tj)

dfs(1,0)
[print(color[i]) for i in range(1,n+1)]

Solution (Python):
import math
import fractions
import bisect
import collections
import itertools
import heapq
import string
import sys
import copy
from collections import deque
sys.setrecursionlimit(10**7)
MOD = 10**9+7
INF = float('inf') 
def gcd(a,b):return fractions.gcd(a,b) 
def lcm(a,b):return (a*b) // fractions.gcd(a,b) 
def iin(): return int(sys.stdin.readline()) 
def ifn(): return float(sys.stdin.readline()) 
def isn(): return sys.stdin.readline().split() 
def imn(): return map(int, sys.stdin.readline().split()) 
def imnn(): return map(lambda x:int(x)-1, sys.stdin.readline().split()) 
def fmn(): return map(float, sys.stdin.readline().split()) 
def iln(): return list(map(int, sys.stdin.readline().split())) 
def iln_s(): return sorted(iln()) 
def iln_r(): return sorted(iln(), reverse=True) 
def fln(): return list(map(float, sys.stdin.readline().split())) 
def join(l, s=''): return s.join(l) 
def perm(l, n): return itertools.permutations(l, n) 
def perm_count(n, r): return math.factorial(n) // math.factorial(n-r) 
def comb(l, n): return itertools.combinations(l, n) 
def comb_count(n, r): return math.factorial(n) // (math.factorial(n-r) * math.factorial(r)) 
def two_distance(a, b, c, d): return ((c-a)**2 + (d-b)**2)**.5 
def m_add(a,b): return (a+b) % MOD

def sieves_of_e(n):
    is_prime = [True] * (n+1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5)+1):
        if not is_prime[i]: continue
        for j in range(i * 2, n+1, i): is_prime[j] = False
    return is_prime

N = iin()

edges = [[] for _ in range(N)]

for _ in range(N-1):
    u,v,w = imn()
    u -= 1
    v -= 1
    edges[u].append((v,w))
    edges[v].append((u,w))

colors = [None] * (N)

def set_color(vertex, color):
    colors[vertex] = color
    for v, w in edges[vertex]:
        if colors[v] == None:
            next_color = color
            if w % 2 == 1:
                next_color = (next_color+1)%2
            set_color(v, next_color)
set_color(0, 0)

for c in colors:
    print(c)

Solution (Python):
from collections import deque
n = int(input())
l = [-1]*n
dis = [[] for i in range(n)]
for i in range(n-1):
    a,b,c = map(int,input().split())
    dis[a-1].append([b-1,c])
    dis[b-1].append([a-1,c])

q = deque([])
l[0] = 0
q.append((0,0))
while q:
    bef,di = q.popleft()
    for i,j in dis[bef]:
        if l[i] == -1:
            if (di+j)%2==0:
                l[i] = 0
            else:
                l[i] = 1
            q.append((i,(di+j)%2))
for i in l:
    print(i)

Solution (Python):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7


N = INT()
e = [[] for _ in range(N)]

for _ in range(N-1):
    t = LIST()
    e[t[0]-1].append([t[1]-1, t[2]%2])
    e[t[1]-1].append([t[0]-1, t[2]%2])

a = [0] * N
f = [0] * N

"""
for edge in G:
    if edge[2]%2 == 1:
        a[edge[1]-1] = 1 - a[edge[0]-1]
    else:
        a[edge[1]-1] = a[edge[0]-1]
"""
def r(n):
    f[n] = 1
    for nn in e[n]:
        if f[nn[0]] == 0:
            if nn[1] == 0:
                a[nn[0]] = a[n]
                r(nn[0])
            else:
                a[nn[0]] = 1 - a[n]
                r(nn[0])

r(0)
for item in a:
    print(item)

Solution (Python):
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
 
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
 
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N = INT()

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

color = [0] * N
color[0] = 1

graph = defaultdict(list)

for u, v, w in L:
    graph[u-1].append((v-1, w))
    graph[v-1].append((u-1, w))




def dfs(n):
    q = [n]
    while q:
        n = q.pop()
        for node, w in graph[n]:
            if color[node] == 0:
                if w % 2 == 0:
                    color[node] = color[n]
                else:
                    color[node] = color[n] * (-1)
                q.append(node)

dfs(0)

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

Solution (Python):
N = int(input())

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

distance = [-1] * N
distance[0] = 0
q = [0]
while q:
    p = q.pop()
    for n, w in links[p]:
        if distance[n] == -1:
            distance[n] = distance[p] + w
            q.append(n)

for i in distance:
    print(i % 2)

Solution (Python):
import math
import fractions
import bisect
import collections
import itertools
import heapq
import string
import sys
import copy
from collections import deque
sys.setrecursionlimit(10**7)
MOD = 10**9+7
INF = float('inf') 
def gcd(a,b):return fractions.gcd(a,b) 
def lcm(a,b):return (a*b) // fractions.gcd(a,b) 
def iin(): return int(sys.stdin.readline()) 
def ifn(): return float(sys.stdin.readline()) 
def isn(): return sys.stdin.readline().split() 
def imn(): return map(int, sys.stdin.readline().split()) 
def imnn(): return map(lambda x:int(x)-1, sys.stdin.readline().split()) 
def fmn(): return map(float, sys.stdin.readline().split()) 
def iln(): return list(map(int, sys.stdin.readline().split())) 
def iln_s(): return sorted(iln()) 
def iln_r(): return sorted(iln(), reverse=True) 
def fln(): return list(map(float, sys.stdin.readline().split())) 
def join(l, s=''): return s.join(l) 
def perm(l, n): return itertools.permutations(l, n) 
def perm_count(n, r): return math.factorial(n) // math.factorial(n-r) 
def comb(l, n): return itertools.combinations(l, n) 
def comb_count(n, r): return math.factorial(n) // (math.factorial(n-r) * math.factorial(r)) 
def two_distance(a, b, c, d): return ((c-a)**2 + (d-b)**2)**.5 
def m_add(a,b): return (a+b) % MOD

def sieves_of_e(n):
    is_prime = [True] * (n+1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5)+1):
        if not is_prime[i]: continue
        for j in range(i * 2, n+1, i): is_prime[j] = False
    return is_prime

N = iin()

edges = [[] for _ in range(N)]

for _ in range(N-1):
    u,v,w = imn()
    u -= 1
    v -= 1
    edges[u].append((v,w))
    edges[v].append((u,w))

colors = [None] * (N)

def set_color(vertex, color):
    colors[vertex] = color
    for v, w in edges[vertex]:
        if colors[v] == None:
            next_color = color
            if w % 2 == 1:
                next_color = (next_color+1)%2
            set_color(v, next_color)
set_color(0, 0)

for c in colors:
    print(c)

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

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N = int(readline())

E = [[] for _ in range(N + 1)]

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

COLOR = [None] * (N + 1)


def setColor(v, c):
    COLOR[v] = c
    for w, l in E[v]:
        if COLOR[w] == None:
            nc = c
            if l % 2 != 0:
                nc = int(not nc)
            setColor(w, nc)


setColor(1, 0)

print("\n".join(map(str, COLOR[1:])))

Solution (Python):
from collections import deque

n=int(input())

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

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

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

dq=deque()
dq.append(0)

while dq:
  x=dq.popleft()
  for vv,ww in tree[x]:
    if dist[vv]==-1:
      dq.append(vv)
      dist[vv]=dist[x]+ww
      if dist[vv]%2==0:
        ans[vv]=0
      else:
        ans[vv]=1

for i in ans:
  print(i)

Solution (Python):
from sys import stdin
from collections import deque
nii=lambda:map(int,stdin.readline().split())

n=int(input())

tree=[[] for i in range(n)]
for i in range(n-1):
  u,v,w=nii()
  u-=1
  v-=1
  tree[u].append([v,w])
  tree[v].append([u,w])

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

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

dq=deque()
dq.append(0)

while dq:
  x=dq.popleft()
  for vv,ww in tree[x]:
    if dist[vv]==-1:
      dq.append(vv)
      dist[vv]=dist[x]+ww
      if dist[vv]%2==0:
        ans[vv]=0
      else:
        ans[vv]=1

for i in ans:
  print(i)

Solution (Python):

from collections import deque
def main():
    n = int(input()) 
    
    
    to = [[] for _ in range(n)]
    cost = [[] for _ in range(n)]
    for _ in range(n-1):
        v, u, w  = map(int, input().split())
        v -= 1
        u -= 1
        to[v].append(u)
        cost[v].append(w)
        to[u].append(v)
        cost[u].append(w)

    
    
    dist = [-1 for _ in range(n)]
    dist[0] = 0
    q = deque()
    q.append(0)
    while len(q) != 0:
        
        val = q.popleft()
        
        for i in range(len(to[val])):
            wal = to[val][i]
            cos = cost[val][i]
            if dist[wal] != -1:
                continue
            dist[wal] = (dist[val] + cos)%2 
            q.append(wal)
    
    for i in range(n):
        print(dist[i])
main()

Solution (Python):
import sys
input = sys.stdin.readline

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

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

for i in range(n-1):
    b[a[i][0]-1].append((a[i][1]-1,a[i][2]))
    b[a[i][1]-1].append((a[i][0]-1,a[i][2]))

import collections
from collections import deque

INF = -10 ** 9
dis = [INF for i in range(n)]
ans = [-1]*n
def bfs(s):
    d = deque()
    d.append(s)
    dis[s]=0
    ans[s]=0
    flag = True

    while len(d):
        x = d.popleft()

        for i in range(len(b[x])):
            y=b[x][i][0]
            if dis[y] == INF:
                d.append(y)
                dis[y]=dis[x]+b[x][i][1]
                if dis[y]%2==0:
                    ans[y]=0
                else:
                    ans[y]=1
    return ans
z=bfs(0)

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

Solution (Python):

from collections import Counter, defaultdict, deque







import sys



ipti = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)

class Node:
    def __init__(self, node_id):
        self.color = -1
        self.id = node_id
        self.next = []

def main():
    n = int(input())
    nodes = [0] * (n+1)

    for i in range(1, n+1):
        nodes[i] = Node(i)

    for i in range(n-1):
        u, v, w = list(map(int,ipti().split()))
        nodes[u].next.append((v, w))
        nodes[v].next.append((u, w))

    que = deque()
    que.append((1,0))
    idx = 0

    while que:
        current_id, current_color = que.popleft()
        current_node = nodes[current_id]
        nodes[current_id].color = current_color

        while current_node.next:
            next_id, next_dist = current_node.next.pop()
            if nodes[next_id].color == -1:
                if next_dist % 2 == 0:
                    next_color = current_color
                else:
                    next_color = (current_color+1) % 2
                que.append((next_id, next_color))

    for i in range(1, n+1):
        print(nodes[i].color)

if __name__ == '__main__':
    main()

Solution (Python):
import sys
from collections import namedtuple


sys.setrecursionlimit(10**5)

Edge = namedtuple('Edge', 'to cost')

N = int(input())


colors = [0] * (N + 1)
vertexes = [[] for _ in range(N + 1)]

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


def dfs(id, color):
  colors[id] = color
  for edge in vertexes[id]:
    if edge.cost % 2 != 0:
      if colors[edge.to] == color:
        return False
      if colors[edge.to] == 0 and not dfs(edge.to, -color):
        return False
    elif colors[edge.to] == 0:
      dfs(edge.to, color)
  return True

if dfs(1, 1):
  for color in colors[1:]:
    print(1 if color == 1 else 0)

Solution (Python):
import sys
from collections import deque

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

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

for i in range(n-1):
    u,v,w=list(map(int,sys.stdin.readline().strip().split()))
    w%=2

    edge[u].append([v,w])
    edge[v].append([u,w])

q=deque([1])
color[1]=0

while len(q)>0:
    parent=q.popleft()
    pw=color[parent]

    for child,ew in edge[parent]:
        if color[child]!=-1:
            continue
        cw=(pw+ew)%2
        color[child]=cw
        q.append(child)

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

Solution (Python):
import sys
input = sys.stdin.readline

N = int(input())

ans = [-1] * N

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

for _ in range(N - 1):
    u, v, w = [int(x) for x in input().split()]
    if w % 2 == 0:
        G[u - 1][0].append(v - 1)
        G[v - 1][0].append(u - 1)
    else:
        G[u - 1][1].append(v - 1)
        G[v - 1][1].append(u - 1)

def dfs(x):
    ans[x] = 0
    stack = [x]
    while stack:
        y = stack.pop()
        for i in G[y][0]:
            if ans[i] < 0:
                ans[i] = ans[y]
                stack.append(i)
        for j in G[y][1]:
            if ans[j] < 0:
                ans[j] = int(not ans[y])
                stack.append(j)
    return ans

ans = dfs(0)

for i in ans:
    print(i)

Solution (Python):
import sys
sys.setrecursionlimit(10**7)
N=int(input())
G=[[] for i in range(N)]
for _ in range(N-1):
    u,v,w=map(int,input().split())
    G[u-1].append([v-1,w%2])
    G[v-1].append([u-1,w%2])
color=[0 for i in range(N)]
seen=[False for i in range(N)]
color[0]=1
def dps(i):
    seen[i]=True
    for g in G[i]:
        if seen[g[0]]:
            continue
        else:
            if g[1]==0:
                color[g[0]]=color[i]
            else:
                color[g[0]]=color[i]*-1
            dps(g[0])
dps(0)
for i in range(N):
    print(1 if color[i]==1 else 0)

Solution (Python):
N = int(input())

edge = [ [] for _ in range(N) ]
for _ in range(N-1):
  U, V, W = map(int, input().split())
  edge[U-1].append([V-1, W])
  edge[V-1].append([U-1, W])

dist = [-1] * N
dist[0] = 0
q = [0]
while q:
  temp = q.pop()
  for u, v in edge[temp]:
    if dist[u] != -1:
      continue
    dist[u] = dist[temp] + v
    q.append(u)
  
for ans in dist:
  if ans % 2 == 0:
    print(1)
  else:
    print(0)

Solution (Python):
import sys
sys.setrecursionlimit(4100000)

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

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

def dfs(index):
    if ans[index]==-1:
        ans[index] = 0
    for i in root[index]:
        if ans[i[0]] == -1:
            ans[i[0]] = (ans[index]+i[1])%2
            dfs(i[0])

for i in range(N):
    dfs(i)

for i in ans:
    print(i)

Solution (Python):
from collections import deque

n = int(input())
color = [-1] * n
g = [[] for _ in range(n)]
l = [[] for _ in range(n)]

que = deque()
que.append(0)
color[0] = 1

for i in range(n-1):
    u,v,w = map(int,input().split()) 
    g[u-1].append(v-1)
    g[v-1].append(u-1)
    l[u-1].append(w)
    l[v-1].append(w)
    
while que:
    s = que.pop()
    for i in range(len(g[s])):
        x = g[s][i]
        y = l[s][i]
        
        if color[x] != -1:
            continue
        elif y % 2 == 0:
            color[x] = color[s]
        else:
            color[x] = (color[s]+1) % 2
            
        que.append(g[s][i])
        
for i in range(n):
    print(color[i])

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

color=[-1]*N 
color[0]=0
now=0
nex=[0]
from copy import deepcopy
while nex:
    now=nex.pop()
    stack=deepcopy(uvw[now])
    uvw[now]=[]
    while stack:
        a=stack.pop()
        if a[1]%2==0:
            color[a[0]]=color[now]
        else:
            color[a[0]]=color[now]^1
        nex.append(a[0])
for c in color:
    print(c)

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

color=[-1]*N 
color[0]=0
now=0
nex=[0]
from copy import deepcopy
while nex:
    now=nex.pop()
    stack=deepcopy(uvw[now])
    uvw[now]=[]
    while stack:
        a=stack.pop()
        if a[1]%2==0:
            color[a[0]]=color[now]
        else:
            color[a[0]]=color[now]^1
        nex.append(a[0])
for c in color:
    print(c)

Solution (Python):
import sys
input = sys.stdin.readline

def main():
    n=int(input())
    l=[[] for _ in range(n+1)]
    for _ in range(n-1):
        u,v,w=map(int,input().split())
        u-=1
        v-=1
        l[u].append([v,w])
        l[v].append([u,w])
    ans=[-1]*n
    chk=[(0,0,-1)]
    while chk:
        v,d,p=chk.pop()
        if d%2==0:
            ans[v]=0
        else:
            ans[v]=1
        for u,w in l[v]:
            if u==p:
                continue
            chk.append((u,d+w,v))
    [print(i) for i in ans]

if __name__ == '__main__':
    main()