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):
from collections import deque

N = int(input())
dic = {i:[] for i in range(1,N+1)}

for _ in range(N-1):
  u, v, w = map(int, input().split())
  dic[u].append((v,w))
  dic[v].append((u,w))
  
s1 = set([1])
s2 = set([])
h = deque([(1,0)])

while h:
  p = h.popleft()
  for t in dic[p[0]]:
    if t[0] == p[1]:
      continue
    if t[1]%2 == 0:
      if p[0] in s1:
        s1.add(t[0])
      else:
        s2.add(t[0])
    else:
      if p[0] in s1:
        s2.add(t[0])
      else:
        s1.add(t[0])
    h.append((t[0],p[0]))

for i in range(1,N+1):
  if i in s1:
    print(0)
  elif i in s2:
    print(1)

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

n = int(input())
uvw = [[] for _ in range(n)]
for _ in range(n - 1):
    u, v, w = map(int, input().split())
    u -= 1
    v -= 1
    uvw[u].append([v, w])
    uvw[v].append([u, w])
color = [-1 for _ in range(n)]
color[0] = 0
def dfs(before_pos, pos, w):
    color[pos] = w
    for next_pos, next_w in uvw[pos]:
        if next_pos == before_pos:
            continue
        dfs(pos, next_pos, (w + next_w) % 2)
    
dfs(-1, 0, 0)
for c in color:
    print(c)

Solution (Python):






import sys
input = sys.stdin.readline

import math

import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache





MOD = 10**9+7
INF = float('inf')
AZ = "abcdefghijklmnopqrstuvwxyz"






def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]


def P(arg): print(arg); return
def Y(): print("Yes"); return
def N(): print("No"); return
def E(): exit()
def PE(arg): print(arg); exit()
def YE(): print("Yes"); exit()
def NE(): print("No"); exit()


def DD(arg): return defaultdict(arg)


def inv(n): return pow(n, MOD-2, MOD)


kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n): return kaijo_memo[n]
  if(len(kaijo_memo) == 0): kaijo_memo.append(1)
  while(len(kaijo_memo) <= n): kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n): return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0): gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n): gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if n == r: return 1
  if n < r or r < 0: return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret


def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1: arr.append([temp, 1])
  if arr==[]: arr.append([n, 1])
  return arr


def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors


def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum


def gcd(a, b):
    while b: a, b = b, a % b
    return a


def lcm(a, b):
    return a * b // gcd (a, b)


def count_bit(n):
  count = 0
  while n:
    n &= n-1
    count += 1
  return count


def base_10_to_n(X, n):
  if X//n: return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

def base_10_to_n_without_0(X, n):
  X -= 1
  if X//n: return base_10_to_n_without_0(X//n, n)+[X%n]
  return [X%n]


def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count




N = I()
graph = [[] for i in range(N)]
for _ in range(N-1):
  u,v,w = IL()
  graph[u-1].append((v-1,w))
  graph[v-1].append((u-1,w))
  
color = [None for i in range(N)]
q = [0]
color[0] = 0

while q:
  u = q.pop()
  for v,w in graph[u]:
    if color[v]!=None:continue
    if w%2:
      color[v] = 1-color[u]
      q.append(v)
    else:
      color[v] = color[u]
      q.append(v)

for c in color:
  print(c)

Solution (Python):
from collections import deque

def bfs(start, g, visited):
    q = deque([start])
    visited[start] = 0
    while q:
        curr_node = q.popleft()
        for next_node, w in g[curr_node]:
            if visited[next_node] >= 0: continue
            visited[next_node] = (visited[curr_node] + w)%2
            q.append(next_node)


n = int(input())
gl = [ [] for _ in range(n+1)]
for _ in range(n-1):
    u,v,w = map(int, input().split())
    gl[u].append((v,w))
    gl[v].append((u,w))
visited = [-1] * (n+1)
bfs(1, gl, visited)

for v in visited[1:]:
    if v%2 == 0: print(0)
    else: print(1)

Solution (Python):

import numpy as np
from collections import deque
from collections import defaultdict
import heapq
import collections
import itertools
import bisect


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


def z():
    return int(input())


def S():
    return input()


def C(line):
    return [input() for _ in range(line)]

from heapq import heapify, heappush, heappop
def dijkstra(path, N, start):
    visited = [False] * N
    que = [(0, start)]
    heapify(que)  
    dist = [-1] * N  
    dist[start] = 0  
    while que:
        d, v = heappop(que)  
        visited[v] = True  
        
        for d, to in path[v]:
            cost = dist[v] + d
            if dist[to] < 0 or cost < dist[to]:
                dist[to] = cost
                if not visited[to]:
                    heappush(que, (cost, to))
    return dist
N = z()

path = [[] for _ in range(N)]
for i in range(N-1):
    u, v, w = zz()
    path[u-1].append((w, v-1))
    path[v-1].append((w, u-1))
dist = dijkstra(path, N, 0)

ans = [0] * N
for i, d in enumerate(dist):
    if (d % 2 == 0):
        ans[i] = 0 
    else:
        ans[i] = 1

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

Solution (Python):
import sys
readline = sys.stdin.readline
from heapq import heapify, heappush, heappop

def dijkstra(path, N, start):
    visited = [False] * N
    que = [(0, start)]
    heapify(que)  
    dist = [-1] * N  
    dist[start] = 0  
    while que:
        d, v = heappop(que)  
        visited[v] = True  
        
        for d, to in path[v]:
            cost = dist[v] + d
            if dist[to] < 0 or cost < dist[to]:
                dist[to] = cost
                if not visited[to]:
                    heappush(que, (cost, to))

    return dist

def main():
    N = int(readline())
    path = [[] for _ in range(N)]
    for _ in range(N-1):
        u, v, w = map(int, readline().rstrip().split())
        path[u-1].append((w, v-1))
        path[v-1].append((w, u-1))
    
    dist = dijkstra(path, N, 0)
    for d in dist:
        if d % 2 == 0:
            print(0)
        else:
            print(1)

if __name__ == '__main__':
    main()

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

N = int(input())
edge = [[] for _ in range(N)]

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

ans = [-1] * N
queue = deque([0])


ans[0] = 0

while queue:
    a = queue.popleft()
    for ve in edge[a]:
        if ans[ve[0]] == -1:
            if ve[1] == 0:
                ans[ve[0]] = ans[a]
            else:
                ans[ve[0]] = (ans[a]+1) % 2
            queue.append(ve[0])

for a in ans:
    print(a)

Solution (Python):
import sys
sys.setrecursionlimit(10**7) 
import math
from copy import copy, deepcopy
from copy import deepcopy as dcp
from operator import itemgetter
from bisect import bisect_left, bisect, bisect_right

from collections import deque


from collections import Counter

from itertools import accumulate,combinations,permutations

from heapq import heapify,heappop,heappush


from functools import lru_cache

from decimal import Decimal

def input(): 
    x=sys.stdin.readline()
    return x[:-1] if x[-1]=="\n" else x
def printl(li): _=print(*li, sep="\n") if li else None
def argsort(s, return_sorted=False): 
    inds=sorted(range(len(s)), key=lambda k: s[k])
    if return_sorted: return inds, [s[i] for i in inds]
    return inds
def alp2num(c,cap=False): return ord(c)-97 if not cap else ord(c)-65
def num2alp(i,cap=False): return chr(i+97) if not cap else chr(i+65)
def matmat(A,B):
    K,N,M=len(B),len(A),len(B[0])
    return [[sum([(A[i][k]*B[k][j]) for k in range(K)]) for j in range(M)] for i in range(N)]
def matvec(M,v):
    N,size=len(v),len(M)
    return [sum([M[i][j]*v[j] for j in range(N)]) for i in range(size)]
def T(M):
    n,m=len(M),len(M[0])
    return [[M[j][i] for j in range(n)] for i in range(m)]
def main():
    mod = 1000000007
    

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

    def dfs():
        q=deque([(0,0)])
        visited=[False]*N
        while len(q):
            e,w=q.pop()
            if visited[e]:continue
            visited[e]=1 if w%2==0 else 2
            for dw,ne in edge[e]:
                q.append((ne,w+dw))
        return visited
    x=dfs()
    for xi in x:
        if xi==1:
            print(0)
        else:
            print(1)



if __name__ == "__main__":
    main()

Solution (Python):
(n,),*t=[map(int,t.split())for t in open(0)]
*e,=eval('[],'*-~n)
q=[(1,0)]
f=[-1]*n
for v,w,c in t:e[v]+=(w,c),;e[w]+=(v,c),
for v,c in q:
 f[v-1]=c&1
 for w,d in e[v]:q+=[(w,c+d)]*(f[w-1]<0)
print(*f)

Solution (Python):
import sys
import copy
sys.setrecursionlimit(10**7)
def dfs(graph,v,dist_mod):
    color[v] = dist_mod
    for next_v,dist in graph[v]:
        if color[next_v] != -1:
            continue
        dfs(graph,next_v,(dist_mod+dist)%2)
n = int(input())
uvw = [list(map(int,input().split())) for _ in range(n-1)]
g = [[] for _ in range(n)]
color = [-1]*n
for i in range(n-1):
    g[uvw[i][0]-1].append([uvw[i][1]-1,uvw[i][2]])
    g[uvw[i][1]-1].append([uvw[i][0]-1,uvw[i][2]])
dfs(g,0,0)
for i in range(n):
    print(color[i])

Solution (Python):
"""bfs"""

import sys
sys.setrecursionlimit(10**6)

n = int(input())

to = [[] for _ in range(n)]
cost = [[] for _ in range(n)]

for i in range(n-1):
    a,b,w = map(int, input().split())
    a -= 1; b -= 1
    to[a].append(b); cost[a].append(w)
    to[b].append(a); cost[b].append(w)

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

import queue

q = queue.Queue()
q.put(0)

while not q.empty():
    v = q.get()
    for i in range(len(to[v])):
        u = to[v][i]
        w = cost[v][i]
        if ans[u] != -1: continue
        ans[u] = (ans[v]+w)%2
        q.put(u)
        
print(*ans)

Solution (Python):
"""dfs"""

import sys
sys.setrecursionlimit(10**6)

n = int(input())
 
G = {}
for i in range(n):
    G.update({i:[]})

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

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

def dfs(graph, v, c):
    color[v] = c
    
    for next_v in graph[v]:
        if color[next_v[0]] != -1: continue
        dist = next_v[1]
        if dist == 0:
            next_c = c
        elif dist == 1:
            next_c = 1 - c
        
        dfs(graph, next_v[0], next_c)

dfs(G, 0, 0)

print(*color)

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

n = int(input())
 
G = {}
for i in range(n):
    G.update({i: []})
 
for i 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 = [-1 for i in range(n)]
 
def dfs(graph, v, c):
    color[v] = c
    
    for next_v in graph[v]:
        dis = next_v[1]
        if color[next_v[0]] != -1:
            continue
        
        if dis == 0:
            n_c = c
        elif dis == 1:
            n_c = 1 - c
        
        dfs(graph, next_v[0], n_c)
 
dfs(G, 0, 0)
[print(i) for i in color]

Solution (Python):




import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil,pi,factorial
from operator import itemgetter
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
def SI(): return input().rstrip()
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
inf = 10**17
mod = 10**9 + 7

n=I()
tree=[[] for i in range(n)]
for i in range(n-1):
    u,v,w=MI()
    u-=1
    v-=1
    tree[u].append([v,w])
    tree[v].append([u,w])
q=deque([[0,0]])
al=[-1 for i in range(n)]

col=[0 for i in range(n)]
def dfs(a,b):
    al[a]=0
    col[a]=b
    for x,y in tree[a]:
        if al[x]<0:
            dfs(x,(y+b)%2)
dfs(0,0)

for i in range(n):
    print(str(col[i]))

Solution (Python):




import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil,pi,factorial
from operator import itemgetter
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
def SI(): return input().rstrip()
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
inf = 10**17
mod = 10**9 + 7

n=I()
tree=[[] for i in range(n)]
for i in range(n-1):
    u,v,w=MI()
    u-=1
    v-=1
    tree[u].append([v,w])
    tree[v].append([u,w])
q=deque([[0,0]])
al=[-1 for i in range(n)]

col=[0 for i in range(n)]
def dfs(a,b):
    al[a]=0
    col[a]=b
    for x,y in tree[a]:
        if al[x]<0:
            dfs(x,(y+b)%2)
dfs(0,0)

for i in range(n):
    print(str(col[i]))

Solution (Python):




import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil,pi,factorial
from operator import itemgetter
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
def SI(): return input().rstrip()
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
inf = 10**17
mod = 10**9 + 7

n=I()
tree=[[] for i in range(n)]
for i in range(n-1):
    u,v,w=MI()
    u-=1
    v-=1
    tree[u].append([v,w])
    tree[v].append([u,w])
q=deque([[0,0]])
al=[-1 for i in range(n)]
al[0]=0
col=[0 for i in range(n)]
while q:
    a,b=q.popleft()
    
    for x,y in tree[a]:
        if (b+y)%2==1:
            col[x]=1
            if al[x]==-1:
                q.append([x,1])
                al[x]=0
        else:
            if al[x]==-1:
                q.append([x,0])
                al[x]=0

for i in range(n):
    print(str(col[i]))

Solution (Python):




import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil,pi,factorial
from operator import itemgetter
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
def SI(): return input().rstrip()
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
inf = 10**17
mod = 10**9 + 7

n=I()
tree=[[] for i in range(n)]
for i in range(n-1):
    u,v,w=MI()
    u-=1
    v-=1
    tree[u].append([v,w])
    tree[v].append([u,w])
q=deque([[0,0]])
al=[-1 for i in range(n)]
al[0]=0
col=[0 for i in range(n)]
while q:
    a,b=q.popleft()
    
    for x,y in tree[a]:
        if (b+y)%2==1:
            col[x]=1
            if al[x]==-1:
                q.append([x,1])
                al[x]=0
        else:
            if al[x]==-1:
                q.append([x,0])
                al[x]=0

for i in range(n):
    print(str(col[i]))

Solution (Python):
import networkx as nx

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

G = nx.Graph()

color = [0 for _ in range(N)]

for u, v, w in UVW:
    G.add_edge(u - 1, v - 1, weight=w)

color[0] = -1

pred, dist = nx.dijkstra_predecessor_and_distance(G, 0)

c = [dist[i] for i in range(N)]
ans = [1 if i % 2 == 0 else 0 for i in c]
print(*ans)

Solution (Python):
import collections

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

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

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

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

Ans = [-1]*N
P = deque([0])
Ans[0] = 0
while(len(P) > 0):
    a = P.popleft()
    for i in T[a]:
        if Ans[i[0]] == -1:
            if i[1] == 0:
                Ans[i[0]] = Ans[a]
            else:
                Ans[i[0]] = (Ans[a] + 1) % 2
            P.append(i[0])
for i in Ans:
    print(i)

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

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



kaisuu = 0
settansaku = set([])
setmada = {0}
kouho = 1
guuki = [0 for _ in range(n)]

while kouho != 0:
	kaisuu += 1
	for i in list(setmada):
		settansaku.add(i)
		setmada.remove(i)
		kouho -= 1
		for k, leng in ikeru[i]:
			if not k in setmada:
				if not k in settansaku:
					setmada.add(k)
					guuki[k] = (guuki[i] + leng) % 2
					kouho += 1
					
					

print("\n".join([str(guuki[i]) for i in range(n)]))

Solution (Python):
N = int(input())
D = {i: [] for i in range(N)}
distD = {}
for i in range(N-1):
    u, v, w = map(int, input().split())
    u -= 1
    v -= 1
    D[u].append(v)
    D[v].append(u)
    distD[u*N+v], distD[v*N+u] = w, w
clr = [-1 for _ in range(N)]
clr[0] = 0
s = [0]
pnt = 0
cnt = 1
while pnt < cnt:
    n = cnt
    for i in range(pnt, cnt):
        L = D[s[i]]
        for j in L:
            if clr[j] == -1:
                clr[j] = (clr[s[i]] + distD[s[i]*N+j]) % 2
                s.append(j)
                cnt += 1
    pnt = n
for i in range(N):
    print(clr[i])

Solution (Python):
def INT():
    return int(input())

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

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

from collections import deque

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

for _ in range(N - 1):
    u, v, w = MI()
    Tree[u - 1].append((v - 1, w))
    Tree[v - 1].append((u - 1, w))
    
color = [0] * N
queue = deque([0])
visited = [False] * N

while queue:
    q = queue.popleft()
    visited[q] = True
    
    for t in Tree[q]:
        if not visited[t[0]]:
            if t[1] % 2 == 0:
                color[t[0]] = color[q]
                
            else:
                if color[q] == 0:
                    color[t[0]] = 1
                else:
                    color[t[0]] = 0
            
            queue.append(t[0])
        
for c in color:
    print(c)

Solution (Python):
from collections import deque

n = int(input())
a = [[] for _ in range(n)]
for _ in range(n - 1):
    u, v, w = map(int, input().split())
    a[u - 1].append((v - 1, w))
    a[v - 1].append((u - 1, w))
d = [-1] * n
todo = deque([(0, 0)])
seen = set()
while todo:
    p, e = todo.popleft()
    if p in seen:
        continue
    seen.add(p)
    d[p] = e
    for pi, ei in a[p]:
        todo.append((pi, e + ei))
for di in d:
    print(di % 2)

Solution (Python):
from heapq import heappop, heappush

n = int(input())
a = [[] for _ in range(n)]
for _ in range(n - 1):
    u, v, w = map(int, input().split())
    a[u - 1].append((v - 1, w))
    a[v - 1].append((u - 1, w))
d = [-1] * n
todo = [(0, 0)]
seen = set()
while todo:
    e, p = heappop(todo)
    if p in seen:
        continue
    seen.add(p)
    d[p] = e
    for pi, ei in a[p]:
        heappush(todo, (e + ei, pi))
for di in d:
    print(di % 2)

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


def mi(): return map(int,input().split())
def ii(): return int(input())
def isp(): return input().split()

def main():
    N = ii()

    u = 0
    graph = [[] for _ in range(10**5+10)]
    for i in range(N-1):
        u,v,w=mi()
        graph[u].append((v,w))
        graph[v].append((u,w))

    seen = set()
    stack = deque([u])

    ans=[[] for _ in range(N+1)]
    ans[u] = 0
    while stack:
        current = stack.popleft()

        for next, w in graph[current]:
            if next in seen: continue
            if w%2==0:
                ans[next] = ans[current]
            else:
                ans[next] = 0 if ans[current] == 1 else 1

            seen.add(next)
            stack.append(next)



    print(*ans[1:],sep='\n')




if __name__ == "__main__":
  main()

Solution (Python):
import sys
readline = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7

INF = 10**18
eps = 10**-7

N = int(readline())

nodes = [{} for i in range(N+1)]

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

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

def dfs(start,to,dist):
    ver = nodes[start][to]
    ans[to] = (dist + ver)%2
    for k in nodes[to].keys():
        if k != start:
            dfs(to,k,dist+ver)

for k in nodes[1].keys():
    dfs(1,k,0)

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

Solution (Python):

import sys
sys.setrecursionlimit(200_000)

def solve(N: int, u: "List[int]", v: "List[int]", w: "List[int]"):
    from collections import namedtuple
    Edge = namedtuple("Edge", "to cost")
    edges = [[] for _ in range(N)]
    for uu, vv, ww in zip(u, v, w):
        edges[uu-1].append(Edge(vv-1, ww))
        edges[vv-1].append(Edge(uu-1, ww))
    colors = [None] * N
    def dfs(n, c):
        if colors[n] is not None:
            return
        colors[n] = c
        for nn, w in edges[n]:
            dfs(nn, (c+w)%2)
    dfs(0, 0)
    return colors



def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  
    u = [int()] * (N - 1)  
    v = [int()] * (N - 1)  
    w = [int()] * (N - 1)  
    for i in range(N - 1):
        u[i] = int(next(tokens))
        v[i] = int(next(tokens))
        w[i] = int(next(tokens))
    print(*solve(N, u, v, w), sep="\n")

def test():
    import doctest
    doctest.testmod()

if __name__ == '__main__':
    
    main()

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

ans = [[] for i in range(n)]
ans[0].append(0)
q = [0]

while q:
    x = q.pop()
    for u,w in d[x]:
        if not ans[u]:
            buf = ans[x][0]
            if w%2==1:
                buf = (buf+1)%2
            ans[u].append(buf)
            q.append(u)

for i in ans:
    print(*i)

Solution (Python):
n=int(input())
a=[-1 for i in range(n)]
d=[[] for i in range(n)]
for i in range(n-1):
    u,v,w=map(int,input().split())
    u-=1
    v-=1
    d[u].append([v,w])
    d[v].append([u,w])
e=0
a[0]=0
l=[]
for i,j in d[0]:
    a[i]=(a[0]+j)%2
    l.append(i)
while len(l)>0:
    b=l.pop()
    for i,j in d[b]:
        if a[i]==-1:
            a[i]=(a[b]+j)%2
            l.append(i)
print(*a,sep='\n')

Solution (Python):
import sys
sys.setrecursionlimit(500*500)

graph = []
distance = []

def dfs(G, v, dist = 0):
    
    distance[v-1] = dist

    for i in range(0,len(G[v-1]),2):
        
        if distance[G[v-1][i]-1] != -1:
            continue
        dist += G[v-1][i+1]
        
        dfs(G, G[v-1][i], dist)
        dist -= G[v-1][i+1]

N = int(input())

for i in range(N):
    graph.append([])
    distance.append(-1)

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





dfs(graph, 1)

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

Solution (Python):
import sys
N = int(input())
G = [{} for _ in range(N)]
for _ in range(N - 1):
    u, v, w = map(int, sys.stdin.readline().split())
    u -= 1
    v -= 1
    G[u][v] = w
    G[v][u] = w

ans = [0] * N
todo = [(0, 0)]
done = set()
while todo:
    p, d = todo.pop()
    for np, dd in G[p].items():
        if not np in done:
            nd = d + dd
            ans[np] = nd % 2
            todo.append((np, nd))
    done.add(p)

for x in ans:
    print(x)

Solution (Python):
import sys
sys.setrecursionlimit(10**9)
def dfs(parent,current,distance):
  global m
  m[current]=distance
  for child in graph[current]:
    if child[0]==parent:
      continue
    dfs(current,child[0],distance+child[1])
n=int(input())
graph=[]
for i in range(n+1):
  graph.append([])
m=[0]*(n+1)
for i in range(n-1):
  a,b,c=map(int,input().split())
  graph[a].append([b,c])
  graph[b].append([a,c])
dfs(1,1,0)
for i in range(1,n+1):
  if m[i]%2==0:
    print(1)
  else:
    print(0)

Solution (Python):
N = int(input())
graph = [[] for  _ in range(N)]
now = 0
for _ in range(N-1):
    x,y,w = map(int,input().split())
    x -= 1
    y -= 1
    graph[x].append((y,w))
    graph[y].append((x,w))
    now = x
    
vis = [0 for _ in range(N)]

even = set()
odd = set()
import sys
sys.setrecursionlimit(10000000)


def dfs(now):
    
    for nv in graph[now]:
        if vis[nv[0]]: continue
        if nv[1] % 2 == 0:
            if now in even:
                even.add(nv[0])
            else:
                odd.add(nv[0])
        else:
            if now in even:
                odd.add(nv[0])
            else:
                even.add(nv[0])
        vis[nv[0]] = 1
        dfs(nv[0])
vis[x] = 1
even.add(x)
dfs(x)

for i in range(N):
    if i in even:
        print(1)
    else:
        print(0)

Solution (Python):
from collections import deque

def dfs(start):
  stack = deque([[start, 0]])
  while stack:
    p, c = stack.popleft()
    for next, distance in graph[p]:
      if visited[next] == -1:
        if distance % 2 == 0:
          visited[next] = int(c)
        else:
          visited[next] = int(not c)
        stack.append([next, visited[next]])

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

visited = [-1] * n
visited[0] = 0
dfs(0)
for v in visited:
    print(v)

Solution (Python):
from collections import deque
from collections import defaultdict

n = int(input())

graph = defaultdict(set)
visited = [1] * 2 + [0] * (n - 1)
ans = [0] * (n + 1)

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

q = deque([1])

while q:
    curr = q.popleft()
    visited[curr] = 1
    for v, w in graph[curr]:
        if not visited[v]:
            ans[v] = (ans[curr] + w) % 2
            q.append(v)
        else:
            continue

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

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

res = [-1]*n
res[0] = 0
q = [0]
while len(q):
    v = q.pop()
    for u,w in e[v]:
        if res[u]>=0:
            continue
        res[u] = res[v]+w
        q.append(u)

for r in res:
    print(r%2)

Solution (Python):
from collections import deque


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

    if v not in e:
        e[v] = [[u,w]]
    else:
        e[v].append([u,w])


que = deque()
que.append([1,0,0])
ans = [-1 for i in range(n)]
ans[0] = 0
no_one = True
flag = True
while True:
    if len(que) == 0:
        break
    top = que.popleft()
    st = top[0]
    for edge in e[st]:
        ecos = edge[1]
        nex = edge[0]
        if ans[nex-1] == -1:
            cos0 = top[1]+ecos
            cos1 = top[2]+ecos

            if cos0 %2 == 0:
                que.append([nex,0,cos1])
                ans[nex-1] = 0
            elif cos1 %2 == 0:
                que.append([nex,cos0,0])
                ans[nex-1] = 1
            else:
                if no_one:
                    que.append([nex, cos0, 0])
                    ans[nex - 1] = 1
                else:
                    flag = False
                    break

    if not flag:
        break
    

for a in ans:
    print(a)