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):
N=int(input())
from collections import defaultdict
branch=defaultdict(dict)
for i in range(N-1):
    u,v,w=map(int,input().split())
    u-=1
    v-=1
    branch[u][v]=w
    branch[v][u]=w
dist=[float('inf')]*N
dist[0]=0
check={0}
while len(check)>0:
    now=check.pop()
    for nex,d in branch[now].items():
        if dist[nex]>dist[now]+d:
            dist[nex]=dist[now]+d
            check|={nex}
for i in range(N):
    print(dist[i]%2)

Solution (Python):



""" convenient functions




"""

import sys
sys.setrecursionlimit(10**7)
from itertools import accumulate, combinations, permutations, product 

from math import factorial, ceil, floor
def factorize(n):
    """return the factors of the Arg and count of each factor
    
    Args:
        n (long): number to be resolved into factors
    
    Returns:
        list of tuples: factorize(220) returns [(2, 2), (5, 1), (11, 1)]
    """
    fct = []  
    b, e = 2, 0  
    while b * b <= n:
        while n % b == 0:
            n = n // b
            e = e + 1
        if e > 0:
            fct.append((b, e))
        b, e = b + 1, 0
    if n > 1:
        fct.append((n, 1))
    return fct
def combinations_count(n, r):
    """Return the number of selecting r pieces of items from n kinds of items.
    
    Args:
        n (long): number
        r (long): number
    
    Raises:
        Exception: not defined when n or r is negative
    
    Returns:
        long: number
    """
    
    if n < 0 or r < 0:
        raise Exception('combinations_count(n, r) not defined when n or r is negative')
    if n - r < r: r = n - r
    if r < 0: return 0
    if r == 0: return 1
    if r == 1: return n
    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]
    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot
    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])
    return result
def combinations_with_replacement_count(n, r):
    """Return the number of selecting r pieces of items from n kinds of items allowing individual elements to be repeated more than once.
    
    Args:
        n (long): number
        r (long): number
    
    Raises:
        Exception: not defined when n or r is negative
    
    Returns:
        long: number
    """
    if n < 0 or r < 0:
        raise Exception('combinations_with_replacement_count(n, r) not defined when n or r is negative')
    elif n == 0:
        return 1
    else:
        return combinations_count(n + r - 1, r)
from bisect import bisect_left, bisect_right
from collections import deque, Counter, defaultdict 
from heapq import heapify, heappop, heappush, heappushpop, heapreplace,nlargest,nsmallest 
from copy import deepcopy, copy 
from operator import itemgetter


from functools import reduce
def chmin(x, y):
    """change minimum
    if x > y, x = y and return (x, True).
    convenient when solving problems of dp[i]
    
    Args:
        x (long): current minimum value
        y (long): potential minimum value
    
    Returns:
        (x, bool): (x, True) when updated, else (x, False)
    """
    if x > y:
        x = y
        return (x, True)
    else:
        return (x, False)
def chmax(x, y):
    """change maximum
    if x < y, x = y and return (x, True).
    convenient when solving problems of dp[i]
    
    Args:
        x (long): current maximum value
        y (long): potential maximum value
    
    Returns:
        (x, bool): (x, True) when updated, else (x, False)
    """
    if x < y:
        x = y
        return (x, True)
    else:
        return (x, False)

from fractions import gcd 
def gcds(numbers):
    return reduce(gcd, numbers)
def lcm(x, y):
    return (x * y) // gcd(x, y)
def lcms(numbers):
    return reduce(lcm, numbers, 1)



INF = 10 ** 18
MOD = 10 ** 9 + 7
modpow = lambda a, n, p = MOD: pow(a, n, p) 
def modinv(a, p = MOD):
    
    
    return modpow(a, p-2, p)
def modinv_list(n, p = MOD):
    if n <= 1:
        return [0,1][:n+1]
    else:
        inv_t = [0,1]
        for i in range(2, n+1):
            inv_t += [inv_t[p % i] * (p - int(p / i)) % p]
        return inv_t
def modfactorial_list(n, p = MOD):
    if n == 0:
        return [1]
    else:
        l = [0] * (n+1)
        tmp = 1
        for i in range(1, n+1):
            tmp = tmp * i % p
            l[i] = tmp
        return l
def modcomb(n, k, fac_list = [], p = MOD):
    
    
    from math import factorial
    if n < 0 or k < 0 or n < k: return 0
    if n == 0 or k == 0: return 1
    if len(fac_list) <= n:
        a = factorial(n) % p
        b = factorial(k) % p
        c = factorial(n-k) % p
    else:
        a = fac_list[n]
        b = fac_list[k]
        c = fac_list[n-k]
    return (a * modpow(b, p-2, p) * modpow(c, p-2, p)) % p
def modadd(a, b, p = MOD):
    return (a + b) % MOD
def modsub(a, b, p = MOD):
    return (a - b) % p
def modmul(a, b, p = MOD):
    return ((a % p) * (b % p)) % p
def moddiv(a, b, p = MOD):
    return modmul(a, modpow(b, p-2, p))

""" initialize variables and set inputs

    
    

    
    
    
    
    

    
    
    
    

    
    
"""


r = lambda: sys.stdin.readline().strip()
r_int = lambda: int(r())
R = lambda: list(map(int, r().split()))
Rfloat = lambda: list(map(float, r().split()))
Rtuple = lambda: tuple(map(int, r().split()))
Rmap = lambda: map(int, r().split())

""" how to treat input







"""


N = int(r())
Dic = defaultdict(list)
ans = [-1] * N
task = []
for _ in range(N-1):
    u, v, w = R()
    Dic[u-1].append((v-1,w))
    Dic[v-1].append((u-1,w))

task.append(0)
ans[0] = 0

while task:
    s = task.pop()
    zeroone = ans[s]
    for (v, w) in Dic[s]:
        if ans[v] >= 0:
            continue
        elif w % 2 == 0:
            ans[v] = zeroone
        else:
            ans[v] = abs(zeroone-1)
        task.append(v)

for i in ans:
    print(i)

"""memo: how to use defaultdict of list

Dic = defaultdict(list)

Dic[x].append(y)

for k, v in Dic.items():
"""

Solution (Python):
from collections import Counter
from collections import deque
from functools import reduce
from pprint import pprint
import bisect
import copy
import fractions
import itertools
import math
import queue
import random
import sys
import time
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def MI(): return map(int, sys.stdin.readline().split())
def II(): return int(sys.stdin.readline())
def IS(): return input()
def C(x): return Counter(x)
def GCD_LIST(numbers): return reduce(fractions.gcd, numbers)
def LCM_LIST(numbers): return reduce(LCM, numbers)
def LCM(m, n): return (m * n // fractions.gcd(m, n))


def f(v, c):
    for next_v, w in graph[v]:
        if seen[next_v] == -1:
            seen[next_v] = (c + w) & 1
            f(next_v, c + w)


n = II()
node = [LI() for _ in range(n - 1)]
graph = [[] for _ in range(n)]
seen = [-1] * n
for u, v, w in node:
    graph[u - 1].append((v - 1, w))
    graph[v - 1].append((u - 1, w))

seen[0] = 0
f(0, 0)
for i in seen:
    print(i)

Solution (Python):
from collections import deque
import sys

sys.setrecursionlimit(50000000)


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

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

N = int(input())
A = [[] for i in range(N)]

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

H = deque()
H.append(a)
visited = [-1]*(N)
visited[a] = 0

while H:
  x = H.popleft()
  for y, z in A[x]:
    if visited[y] == -1:
      visited[y] = (visited[x] + z%2)%2
      H.append(y)
for i in visited:
  print(i)

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


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


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

for i in uvw:
    Graph[i[0]-1].append([i[1]-1, i[2]])
    Graph[i[1]-1].append([i[0]-1, i[2]])

dfs(0, 0)

for i in color:
    print(i)

Solution (Python):
from collections import defaultdict
N = int(input())
dic = defaultdict(list)

for i in range(N-1):
    inf = input().split()
    u = int(inf[0])
    v = int(inf[1])
    w = int(inf[2])
    dic[u-1] += [(v-1,w)]
    dic[v-1] += [(u-1,w)]


dist = [-1]*N
stack = []
dist[0] = 0

stack += [0]

while stack:
    u = stack.pop(-1)
    for i, w in dic[u]:
        if dist[i]==-1:
            dist[i] = dist[u]+w
            stack.append(i)

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

Solution (Python):
import sys

input = sys.stdin.readline
N = int(input().strip())

ans = [0] * (N+1)
path = [[] for _ in range(N+1)]

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

is_visit = [False] * (N+1)
search_list = [(1, 0)]

while len(search_list) > 0:
    now, color = search_list.pop()
    ans[now] = color
    is_visit[now] = True

    for node, distance in path[now]:
        if not is_visit[node]:
            search_list.append((node, (distance+color) % 2))
for color in ans[1:]:
    print(color)

Solution (Python):
import sys

input = sys.stdin.readline
N = int(input().strip())

ans = [0] * (N+1)
path = [[] for _ in range(N+1)]

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

is_visit = [False] * (N+1)
search_list = [(1, 0)]

while len(search_list) > 0:
    now, color = search_list.pop()
    ans[now] = color
    is_visit[now] = True

    for node, distance in path[now]:
        if not is_visit[node]:
            search_list.append((node, (distance+color) % 2))
for color in ans[1:]:
    print(color)

Solution (Python):
import sys
sys.setrecursionlimit(1000000)
 
N = int(input())
X = [[] for _ in range(N)]
for _ in range(N-1):
    u, v, w = map(int, input().split())
    X[u-1].append((v-1, w%2))
    X[v-1].append((u-1, w%2))
 

D = [-1] * N
def calc(i, c):
    D[i] = c
    for j, w in X[i]:
        if D[j] < 0:
            calc(j, D[i]^w)
 
calc(0, 0)
for d in D:
    print(d)

Solution (Python):
N = int(input())
G = [dict() for i in range(N)]

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

dist[0]=0
q=[0]
while(len(q)>0):
    r=q.pop()
    for p in G[r]:
        if dist[p]!=-1:
            continue
        dist[p]=dist[r]+G[r][p]
        q.append(p)

for i in range(N):
    print(dist[i]%2)

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

dic = [[] for i in range(N)]
for i in range(N-1):
  inf = input().split()
  u = int(inf[0])
  v = int(inf[1])
  w = int(inf[2])
  dic[u-1] +=[(v-1, w)]
  dic[v-1] +=[(u-1, w)]

dist = [-1]*N
stack = []
stack.append(0)
dist[0] = 0

while stack:
  label = stack.pop(-1)
  for i, c in dic[label]:
    if dist[i] == -1:
      dist[i] = dist[label]+c
      stack += [i]

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

Solution (Python):
import sys
sys.setrecursionlimit(10**5+1)
N = int(input())
es = [[] for i in range(N+1)]
for i in range(N-1):
    u, v, w = map(int, input().split())
    es[u].append([v,w])
    es[v].append([u,w])
dfs_map = [1 for i in range(N+1)]
col = [None] * (N+1)
def dfs(v, c):
    col[v] = c
    for e in es[v]:
        if dfs_map[e[0]]:
            dfs_map[e[0]] = 0
            if e[1] % 2:
                dfs(e[0], c^1)
            else:
                dfs(e[0], c)
dfs_map[1] = 0
dfs(1, 0)
for i in range(1, N+1):
    print(col[i])

Solution (Python):
n = int(input())
dic = [[] for i in range(n)] 
for i in range(n-1):
    inf = input().split()
    u = int(inf[0])
    v = int(inf[1])
    w = int(inf[2])
    dic[u-1] += [(v-1, w)]
    dic[v-1] += [(u-1, w)] 
    
dist = [-1]*n
stack = []
stack.append(0)
dist[0] = 0 

while stack:
    label = stack.pop(-1) 
    
    for i, c in dic[label]: 
        if dist[i] == -1: 
            dist[i] = dist[label]+c
            stack += [i]
            
print(0)
for i in range(1,n):
    if dist[i]%2==0:
        print(0)
    else:
        print(1)

Solution (Python):

import bisect
from collections import defaultdict
import math

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

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

    colors = [None]*N
    colors[0] = 0
    colored = [(0, 0)]
    while colored:
        new_colored = []
        for n, d in colored:
            nodes = edges[n]
            for m, w in nodes:
                if colors[m] is None:
                    dist = d + w
                    if dist % 2 == 0:
                        colors[m] = 0
                    else:
                        colors[m] = 1
                    new_colored.append((m, dist))
        colored = new_colored

    for n in range(N):
        print(colors[n])

if __name__ == '__main__':
    main()

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

dic = [[] for i in range(N)]
for i in range(N-1):
  inf = input().split()
  u = int(inf[0])
  v = int(inf[1])
  w = int(inf[2])
  dic[u-1] +=[(v-1, w)]
  dic[v-1] +=[(u-1, w)]

dist = [-1]*N
stack = []
stack.append(0)
dist[0] = 0

while stack:
  label = stack.pop(-1)
  for i, c in dic[label]:
    if dist[i] == -1:
      dist[i] = dist[label]+c
      stack += [i]

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

Solution (Python):
import sys
input = sys.stdin.readline
from collections import deque
N = int(input())
table = [[] for i in range(N)]
for i in range(N-1):
  u, v, w = map(int, input().split())
  u, v = u-1, v-1
  table[u].append((v, w))
  table[v].append((u, w))
H = deque()
H.append(0)
visit = [-1]*N
visit[0] = 0
while H:
  x = H.popleft()
  for y, w in table[x]:
    if visit[y] == -1:
      visit[y] = (visit[x]+w)%2
      H.append(y)
for i in range(N):
  print(visit[i])

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

N = int(input())
tree = [[] for _ in range(N)]
for i 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 = [None]*N
dist[0] = 0
comp = [0]*N
next_ptr = [0]
for ptr in next_ptr:
    comp[ptr] = 1
    edges = tree[ptr]
    for edge in edges:
        if comp[edge[0]] == 0:
            dist[edge[0]] = dist[ptr] + edge[1]
            next_ptr.append(edge[0])

for item in dist:
    print(item%2)

Solution (Python):
import sys

N=int(input())
sys.setrecursionlimit(100000)
u = [0]*(N-1)
v = [0]*(N-1)
w = [0]*(N-1)
for i in range(N-1):
    u[i], v[i], w[i] = map(int, input().split())
    u[i] -= 1
    v[i] -= 1

class Path:
    def __init__(self, next_node, length, num):
        self.next=next_node
        self.len=length
        self.num=num

class Node:
    def __init__(self, index):
        self.index = index
        self.paths = []

    def append(self, next_node, length, num):
        self.paths.append(Path(next_node, length, num))

nodes = [Node(i) for i in range(N)]
for i in range(N-1):
    nodes[u[i]].append(v[i], w[i], i)
    nodes[v[i]].append(u[i], w[i], i)

past_paths = [0]*(N-1)
paints = [-1]*N

def rec(pos, color):
    if paints[pos] == -1:
        paints[pos] = color
    for path in nodes[pos].paths:
        
        if past_paths[path.num] == 0:
            past_paths[path.num] = 1
            rec(path.next, (color + path.len) % 2)
        

rec(0, 0)

for i in paints:
    print(i)

Solution (Python):

import sys
def input(): return sys.stdin.readline().rstrip()
def mi(): return map(int, input().split())


N = int(input())

adj = [set() for _ in range(N)] 
for _ in range(N-1):
  u, v, w = mi()
  
  u -= 1
  v -= 1
  adj[u].add((v, w%2))
  adj[v].add((u, w%2))

from collections import deque
q = deque([])

seen = [-1] * N 



q.append(0)
seen[0] = 0


while q:
  nownode = q.popleft()
  nowcolor = seen[nownode]

  
  for adjidx, w in adj[nownode]:
    if seen[adjidx]==-1:
      q.append(adjidx)
      seen[adjidx]=(nowcolor+w)%2

for color in seen:
  print(color)

Solution (Python):

import sys
def input(): return sys.stdin.readline().rstrip()
def mi(): return map(int, input().split())

import sys
sys.setrecursionlimit(10000000)

N = int(input())

adj = [set() for _ in range(N)] 
for _ in range(N-1):
  u, v, w = mi()
  
  u -= 1
  v -= 1
  adj[u].add((v, w%2))
  adj[v].add((u, w%2))

from collections import deque
q = deque([])

seen = [0] * N
bw = [0] * N



q.append(0)
bw[0] = 0 
seen[0] = 1


def solve(): 
  try: nownode = q.popleft()
  except: return
  nowcolor = bw[nownode]

  
  for adjidx, w in adj[nownode]:
    if seen[adjidx]!=1:
      q.append(adjidx)
      seen[adjidx]=1
      bw[adjidx] = (nowcolor+w)%2

  solve()

solve()

for color in bw:
  print(color)

Solution (Python):
from collections import deque


n = int(input())
es = [[] for _ in range(n)]
for _ in range(n-1):
    u, v, w = map(int, input().split())
    u -= 1
    v -= 1
    es[u].append((v, w))
    es[v].append((u, w))
clr = [None]*n
clr[0] = 0
dq = deque()
dq.append(0)
while dq:
    v = dq.popleft()
    for nv, w in es[v]:
        if clr[nv] is not None:
            continue
        clr[nv] = (clr[v] + w)%2
        dq.append(nv)
print(*clr, sep='\n')

Solution (Python):


import sys
import collections
import numpy as np

def main():
    N = int(sys.stdin.readline())
    UVW = [[] for _ in range(N)]
    for _ in range(N-1):
        u, v, w = list(map(int, sys.stdin.readline().split()))
        UVW[u-1].append([v,w])
        UVW[v-1].append([u,w])
    answerList = [0] + [-1]*(N-1)
    edge = collections.deque([(1,0)])

    while edge:
        u, w1 = edge.pop()
        for v, w2 in UVW[u-1]:
            if answerList[v-1] == -1:
                answerList[v-1] = (w1 + w2) % 2
                edge.append((v,w1+w2))

    for answer in answerList:
        print(answer)



if __name__ == "__main__":
    main()

Solution (Python):
from collections import deque

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

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

clr = [None] * N
clr[0] = 0

dq = deque()
dq.append(0)

while dq:
    v = dq.popleft()
    for nv, w in es[v]:
        if clr[nv] is not None:
            continue
        clr[nv] = (clr[v] + w) % 2
        dq.append(nv)
print(*clr, sep='\n')

Solution (Python):
N = int(input())
color = [ [] for i in range(N)]

def updateColor( color, i, from_i, c):
    if len(color[i]) == 1 and color[i][0][0] == from_i:
        color[i] = c
    else:
        for l in color[i]:
            if l[0] != from_i:
                if l[1] == 'Same':
                    updateColor( color, l[0], i, c)
                else:
                    updateColor( color, l[0], i, 1-c)
        color[i] = c
                    

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

            for l in color[v]:
                if l[1] == "Same":
                    updateColor( color, l[0], v, temp )
                else:
                    updateColor( color, l[0], v, 1-temp )
            color[v] = temp

        elif color[v] in (0,1):
            if w%2 == 0:
                temp = color[v]
            else:
                temp = 1-color[v]
                
            for l in color[u]:
                if l[1] == "Same":
                    updateColor( color, l[0], u, temp )
                else:
                    updateColor( color, l[0], u, 1-temp )
            color[u] = temp

        else:
            if w%2 == 0:
                color[u].append([v, "Same"])
                color[v].append([u, "Same"])
            else:
                color[u].append([v, "Diff"])
                color[v].append([u, "Diff"])
                    
for c in color:
    print(c)

Solution (Python):

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

stack = [(e,0) for e in edge[0]]
ans[0] = 0

while len(stack) > 0:
    e,c = stack.pop()
    n,w = e[0],e[1]
    if ans[n] >= 0:
        continue
    ans[n] = (c + w) % 2
    stack += [(e,ans[n]) for e in edge[n]]

for a in ans:
    print(a)

Solution (Python):
from collections import defaultdict
import queue


class Graph:
    def __init__(self):
        self.graph = defaultdict(list)

    def __len__(self):
        return len(self.graph)

    def add_edge(self, src, dst, weight):
        self.graph[src].append((dst, weight))

    def get_nodes(self):
        return self.graph.keys()


N = int(input())
g = Graph()
q = queue.Queue()
ans = [-1] * N
ans[0] = 0  
q.put(0)

for i in range(N-1):
    src, dst, weight = map(int, input().split())
    src -= 1
    dst -= 1
    g.add_edge(src, dst, weight % 2)
    g.add_edge(dst, src, weight % 2)

while not q.empty():
    v = q.get()
    for i in range(len(g.graph[v])):
        u, w = g.graph[v][i]

        
        if ans[u] != -1:
            continue

        ans[u] = (ans[v] + w) % 2  
        q.put(u)

for a in ans:
    if a < 0:
        a = 0
    print(a)

Solution (Python):
import sys
from collections import deque


def bfs(s):
    color_list[s] = 0
    flag_list[s] = 1
    q.append(s)
    while len(q) > 0:
        u = q.popleft()
        for v, w in m_list[u]:
            if flag_list[v] == 0:
                flag_list[v] = 1
                if w%2 == 0:
                    color_list[v] = color_list[u]
                else:
                    color_list[v] = (color_list[u]+1)%2
                q.append(v)
        flag_list[u] = 2


if __name__ == "__main__":
    input = sys.stdin.readline
    n = int(input())
    m_list = [[]*n for _ in range(n)]
    color_list = [0]*n
    flag_list = [0]*n
    q = deque([])
    for _ in range(n-1):
        u, v, w = map(int, input().split())
        m_list[u-1].append([v-1, w])
        m_list[v-1].append([u-1, w])
    bfs(0)
    for color in color_list:
        print(color)

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


rl = lambda: map(int,input().split())
rr = lambda N: [list(l) for l in zip(*[rl() for _ in range(N)])]
YN = lambda b: print('YES') if b else print('NO')
yn = lambda b: print('Yes') if b else print('No')
OE = lambda x: print('Odd') if x%2 else print('Even')
INF = 10**18
MOD = 10**9+7

N = ri()
coler = [0]*N
ME = [None]*N
MO = [None]*N
UVW=[]
for i in range(N-1):
    u,v,w = rl()
    u -= 1
    v -= 1
    if w%2 == 1:
        if MO[u] == None:
            MO[u] = [v]
        else:
            MO[u].append(v)
        if MO[v] == None:
            MO[v] = [u]
        else:
            MO[v].append(u)
    else:
        if ME[u] == None:
            ME[u] = [v]
        else:
            ME[u].append(v)
        if ME[v] == None:
            ME[v] = [u]
        else:
            ME[v].append(u)

from collections import deque
q = deque([0])
visited = [False]*N
while len(q)>0:
    n = q.popleft()
    if visited[n] == True:
        continue
    else:
        visited[n] = True
    v = coler[n]
    e = ME[n]
    if not e is None:
        q.extend(e)
        for en in e:
            coler[en] = v
    o = MO[n]
    if not o is None:
        v += 1
        q.extend(o)
        for on in o:
            coler[on] = v

for c in coler:
    print(c%2)

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

rel = {x:{} for x in range(1, N + 1)}
for u, v, w in UVW:
	rel[u][v] = w
	rel[v][u] = w

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



route = [x for x in range(N, 0, -1)]
while route:
	
	current = route.pop()
	for k, v in rel[current].items():
		if -1 == visited[k]:
			route += [k]
		if not v % 2:
			visited[k] = visited[current]
		else:
			visited[k] = (visited[current] + 1) % 2
	

for node in visited[1:]:
	print(node)

Solution (Python):




from queue import Queue


n = int(input())

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

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

    
    
    u-=1
    v-=1


    to[u].append(v)
    cost[u].append(w)

    to[v].append(u)
    cost[v].append(w)    





q = Queue()

ans = [-1] * n
q.put(0)

while not q.empty():
    u = q.get()
    
    for i in range(len(to[u])):
        v = to[u][i]
        w = cost[u][i]

        if (ans[v] != -1): continue

        ans[v] = (ans[u] + w) % 2
        q.put(v)
        

for a in ans:
    print(a)

Solution (Python):


N = int(input())
edge = [[] for i in range(N)]
color = [-1 for i in range(N)]
for i in range(N-1):
    u,v,w = map(int,input().split())
    u -= 1
    v -= 1
    w %= 2
    edge[u].append((v,w))
    edge[v].append((u,w))
search = [(e, 0) for e in edge[0]]
color[0] = 0
while len(search) > 0:
    e,c = search.pop()
    n,w = e[0],e[1]
    if color[n] >= 0:
        continue
    color[n] = (c + w) % 2
    search += [(e,color[n]) for e in edge[n]]

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

Solution (Python):
n=int(input())
l=[]
for i in range(n-1):
    a=[int(j) for j in input().split()]
    l.append(a)

from collections import defaultdict
from heapq import heappop, heappush


class Graph(object):
    """
    隣接リストによる有向グラフ
    """

    def __init__(self):
        self.graph = defaultdict(list)

    def __len__(self):
        return len(self.graph)

    def add_edge(self, src, dst, weight=1):
        self.graph[src].append((dst, weight))

    def get_nodes(self):
        return self.graph.keys()


class Dijkstra(object):
    """
    ダイクストラ法（二分ヒープ）による最短経路探索
    計算量: O((E+V)logV)
    """

    def __init__(self, graph, start):
        self.g = graph.graph

        
        
        self.dist = defaultdict(lambda: float('inf'))
        self.dist[start] = 0

        
        self.prev = defaultdict(lambda: None)

        
        self.Q = []
        heappush(self.Q, (self.dist[start], start))

        while self.Q:
            
            dist_u, u = heappop(self.Q)
            if self.dist[u] < dist_u:
                continue
            for v, weight in self.g[u]:
                alt = dist_u + weight
                if self.dist[v] > alt:
                    self.dist[v] = alt
                    self.prev[v] = u
                    heappush(self.Q, (alt, v))

    def shortest_distance(self, goal):
        """
        startノードからgoalノードまでの最短距離
        """
        return self.dist[goal]

    def shortest_path(self, goal):
        """
        startノードからgoalノードまでの最短経路
        """
        path = []
        node = goal
        while node is not None:
            path.append(node)
            node = self.prev[node]
        return path[::-1]
        

g = Graph()
for src, dst, weight in l:
    g.add_edge(src, dst, weight)
    g.add_edge(dst, src, weight)

d = Dijkstra(g, 1)  
for i in range(n):
    if d.shortest_distance(i+1)%2==0:
        print(0)
    else:
        print(1)

Solution (Python):
N = int(input())
tree = []
for i in range(0, N):
	tree.append([])
for i in range(0, N-1):
	u, v, w = map(int, input().split())
	tree[u-1].append([v-1, w])
	tree[v-1].append([u-1, w])
oddeven = []
for i in range(0, N):
	oddeven.append(-1)
stack = [[0, 0]]
while stack != []:
	now = stack.pop(-1)
	oddeven[now[0]] = now[1]%2
	for i in range(0, len(tree[now[0]])):
		if oddeven[tree[now[0]][i][0]] == -1:
			stack.append([tree[now[0]][i][0], now[1]+tree[now[0]][i][1]])
for i in range(0, N):
	print(oddeven[i])

Solution (Python):
import numpy as np
N=int(input())
G=[[] for n in range(N+1)]
for n in range(N-1):
    [u,v,w]=[int(_) for _ in input().split()]
    G[u].append(v*((-1)**w))
    G[v].append(u*((-1)**w))
D=[-1 for n in range(N+1)]
V=[0,1]
while V!=[0]:
    now=V[1]
    for nex in G[now]:
        if D[abs(nex)]==-1:
            if np.sign(nex)==1:
                D[abs(nex)]=D[now]%2
            else:
                D[abs(nex)]=(D[now]+1)%2
            V.append(abs(nex))
    V.pop(1)
for n in range(1,N+1):
    print(D[n])

Solution (Python):

import sys
input = sys.stdin.readline

n = int(input())

connect_list = [ [] for i in range(n) ]
distance_list = [ -1 for i in range(n) ]
color_list = [ "Gray" for i in range(n) ]
distance_list[0] = 0

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

search_list = [0]

t = 0
stop = 0
while t < len(search_list):
	s = search_list[t]
	stop = 0
	for i in connect_list[s]:
		if distance_list[i[0]] == -1:
			distance_list[i[0]] = (distance_list[s] + i[1]) % 2
			search_list.append(i[0])
	t += 1


for i in distance_list:
	print(i)