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())
V = [ list(map(int, input().split())) for _ in range(N-1)]

X = [[] for _ in range(N)]
for v in V:
    X[v[0]-1].append((v[0],v[1],v[2]))
    X[v[1]-1].append((v[1],v[0],v[2]))

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

que = deque()
que.append(1)

while len(que) > 0:
    v = que.popleft()
    for x in X[v-1]:

        b = x[1]
        dist = x[2]
        color_a = color[v-1]
        if  color[b-1] != -1:
            continue
        que.append(b)
        if dist % 2 == 0:
            color[b-1] = 0 if color_a == 0 else 1
        else:
            color[b-1] = 0 if color_a == 1 else 1

for c in color:
    print(c)

Solution (Python):
import queue

n = int(input())

connect = [ [] for _ in range(n)]
distances = dict()

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

    connect[u].append(v)
    connect[v].append(u)
    distances[(u, v)] = w
    distances[(v, u)] = w

colors = [-1] * n
colors[0] = 0
q = queue.Queue()
q.put(0)

while not q.empty():
    x = q.get()

    for y in connect[x]:
        if colors[y] != -1:
            continue
        colors[y] = (colors[x] + distances[(x, y)]) % 2
        q.put(y)

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

Solution (Python):
import queue

n = int(input())

connect = [ [] for _ in range(n)]
distances = dict()

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

    connect[u].append(v)
    connect[v].append(u)
    distances[(u, v)] = w
    distances[(v, u)] = w

colors = [-1] * n
colors[0] = 0
q = queue.Queue()
q.put(0)

while not q.empty():
    x = q.get()

    for y in connect[x]:
        if colors[y] != -1:
            continue
        colors[y] = (colors[x] + distances[(x, y)]) % 2
        q.put(y)

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

Solution (Python):

from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
import itertools
sys.setrecursionlimit(10**5)
stdin = sys.stdin
bisect_left = bisect.bisect_left
bisect_right = bisect.bisect_right
def LI(): return list(map(int, stdin.readline().split()))
def LF(): return list(map(float, stdin.readline().split()))
def LI_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def II(): return int(stdin.readline())
def IF(): return float(stdin.readline())
def LS(): return list(map(list, stdin.readline().split()))
def S(): return list(stdin.readline().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')


def A():
    n, k = LI()
    s = S()
    s[k-1] = s[k-1].lower()
    print("".join(s))

    return


def B():
    s = S()
    a = int("".join(s[:2]))
    b = int("".join(s[2:]))
    if 0 < a <= 12:
        if 0 < b <= 12:
            print("AMBIGUOUS")
        else:
            print("MMYY")
    elif a == 0:
        if 0 < b <= 12:
            print("YYMM")
        else:
            print("NA")
    else:
        if 0 < b <= 12:
            print("YYMM")
        else:
            print("NA")
    return


def C():
    n, k = LI()
    ans = 0
    if k == 1:
        print(1)
        return
    nibuiti = [None for i in range(int(math.log2(k) + 1))]
    for num in range(int(math.log2(k) + 1)):
        if num == 0:
            nibuiti[num] = 1 / 2
            continue
        nibuiti[num] = nibuiti[num-1]/2
        
    for i in range(1, n + 1):
        if i >= k:
            ans += 1
            continue
        b = nibuiti[int(math.log2((k - 1) // i))]
        ans += b
    print(ans/n)
    return


def D():
    n = II()
    color = [0 for i in range(n)]
    edge = [[] for i in range(n)]
    for i in range(n - 1):
        v, u, w = LI_()
        edge[v].append((u,w+1))
        edge[u].append((v,w+1))
    check = [True for i in range(n)]
    for i in range(n):
        q = deque()
        q.append(i)
        
        while q:
            a = q.pop()
            if check:
                check[a] = False
                for k,w in edge[a]:
                    if check[k]:
                        q.append(k)
                        if w % 2:
                            color[k] = color[a] ^ 1
                        else:
                            color[k] = color[a]
    for c in color:
        print(c)
    return


def E():
    return


def F():
    return


def G():
    return


def H():
    return


if __name__ == '__main__':
    D()

Solution (Python):
import sys
sys.setrecursionlimit(10**6)
n=int(input())
G=[[]for i in range(n+1)]
for i in range(n-1):
    a, b, c = map(int,input().split())
    G[a] += (b,c),
    G[b] += (a,c),
    
d = [0]*(n+1) 
def f(v,p,u): 
    d[v] = u
    for t, c in G[v]:
        if p != t:
            f(t,v,u+c)
f(1,0,0)
for i in range(n):
    if d[i+1] % 2 == 0:
        print(1)
    else:
        print(0)

Solution (Python):

from math import *

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


colors = [None for i in range(N)]

q = [0]
colors[0]=0
while len(q)!=0:
    u = q.pop()
    for v,w in tonaris[u]:
        tonaris[v].remove((u,w))
        colors[v] = colors[u] ^ w
        q.append(v)

for color in colors:
    print(color)

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

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

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

for u, v, w in uvw :
    path[u].append((v, w))
    path[v].append((u, w))

paint = [0] * (N + 1)

queue = [1]
visited = [False] * (N + 1)

while queue :
    current = queue.pop(0)
    w = paint[current]

    for destination, w_ in path[current] :
        if not visited[destination] :
            paint[destination] = (w + w_) & 1
            queue.append(destination)
            visited[destination] = True

for i in paint[1:] :
    print(i)

Solution (Python):
from collections import deque

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

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

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

q = deque()
q.append(0)

while q:
    x = q.popleft()
    for y, w in v[x]:
        if bfs_map[y]:
            if w%2 :
                ans[y] = ans[x] ^ 1
            else:
                ans[y] = ans[x]
            bfs_map[y] = 0
            q.append(y)
    
for i in ans:
    print(i)

Solution (Python):
from queue import Queue

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

isChecked = [False for i in range(N)]
ans = [0 for i in range(N)]
q = Queue()

q.put([1, 0])
while not q.empty():
    v, l = q.get()
    if isChecked[v-1]:
        continue
    ans[v-1] = 0 if l%2 == 0 else 1
    isChecked[v-1] = True
    for u, w in d[v]:
        q.put([u, l+w])

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

Solution (Python):


n = int(input())

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

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


while(len(que)!=0): 
    node = que.pop()
    for next_node,w in tree[node]:
        if color[next_node]==-1:
            
            color[next_node]=(color[node]+w)%2
            que.append(next_node)
            
for i in range(1,len(color)):
    print(color[i])

Solution (Python):
import sys
from collections import defaultdict
import heapq

class Dijkstra():
    def __init__(self):
        self.edges = defaultdict(list)
    
    def add_edge(self, a, b, cost, directed=False):
        self.edges[a].append((b,cost))
        if not directed:
            self.edges[b].append((a,cost))
        
    def delete_edge(self, a, b):
        self.edges[a] = [item for item in self.edges[a] if item[0] != b]
        self.edges[b] = [item for item in self.edges[a] if item[0] != a]

    def Dijkstra_search(self, start=0):
        '''
        Returns min distances to every node from start node(input).
        '''

        
        distances = defaultdict(lambda: float('inf'))
        distances[start] = 0 

        
        q = []
        heapq.heappush(q, (0, start))

        
        if_visited = defaultdict(bool)

        while q:
            
            cost_current, node_current = heapq.heappop(q)
            
            
            if if_visited[node_current]:
                continue
            
            else:
                if_visited[node_current] = True

                
                for node_visiting, cost_visiting in self.edges[node_current]:

                    if if_visited[node_visiting]: 
                        continue
                    
                    cost_cumulative = cost_current + cost_visiting

                    if cost_cumulative < distances[node_visiting]: 
                        distances[node_visiting] = cost_cumulative
                        heapq.heappush(q, (cost_cumulative, node_visiting))

        return distances


input = sys.stdin.readline
N = int(input())
g = Dijkstra()

while True:
    s = input()
    if s == '':
        break
    
    a, b, c = map(int, s.rstrip().split())
    a -= 1
    b -= 1
    g.add_edge(a,b,c)

distance = g.Dijkstra_search()

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

Solution (Python):

n = int(input())
g = [[] for i in range(n)]
c = [-1 for i 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])


q = [0]
while (len(q) > 0):
    v = q.pop()
    for u, w in g[v]:
        if c[u] != -1:
            continue
        q.append(u)
        c[u] = (c[v] + w) % 2

for v in c:
    print(v)

Solution (Python):
import sys


def visit(current, v, dist, color):
    for ele in v[current]:
        if color[ele] != -1:
            continue
        if dist[(ele, current)] % 2 == 0:
            color[ele] = color[current]
        else:
            if color[current] == 0:
                color[ele] = 1
            else:
                color[ele] = 0
        visit(ele, v, dist, color)

def main():
    sys.setrecursionlimit(100100)
    num = int(input())

    v = [[] for i in range(num + 1)]

    dist = {}

    for i in range(1, num):
        a, b, d = map(int, input().split())
        v[a].append(b)
        v[b].append(a)
        dist[(a, b)] = d
        dist[(b, a)] = d

    color = [-1 for i in range(num + 1)]
    color[1] = 0
    visit(1, v, dist, color)

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

if __name__ == '__main__':
    main()

Solution (Python):

import sys
sys.setrecursionlimit(20000000)

n = int(input())
g = [[] for i in range(n)]
c = [-1 for i in range(n)]

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


def dfs(p, d):
    if c[p] == -1:
        c[p] = d
        for x, w in g[p]:
            dfs(x, d ^ w)


dfs(0, 0)

for i in range(len(c)):
    print(c[i])

Solution (Python):

import sys
sys.setrecursionlimit(100100)

n = int(input())
g = [[] for i in range(n)]
c = [-1 for i in range(n)]

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


def dfs(p, d):
    if c[p] == -1:
        c[p] = d
        for x, w in g[p]:
            dfs(x, d ^ w)


dfs(0, 0)

for i in range(len(c)):
    print(c[i])

Solution (Python):


import sys
sys.setrecursionlimit(100000)

def dfs(graph, color, visit, idx):
    visit[idx] = True
    if len(graph[idx]) == 0:
        return
    for i, w in graph[idx]:
        if visit[i] is True:
            continue
        if w%2 == 0:    
            color[i] = color[idx]
        else:   
            color[i] = 1 - color[idx]   
        dfs(graph, color, visit, i)


N = int(input())
L = N-1
graph = [[] for _ in range(N)]
color = [-1 for _ in range(N)]
visit = [False for _ in range(N)]

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

color[0] = 0    
dfs(graph, color, visit, 0)

for c in color:
    print(c)

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

N=int(input())
G=[[] for i in range(N)]
for i in range(N-1):
    u,v,w=map(int,input().split())
    u,v=u-1,v-1
    G[u].append((v,w))
    G[v].append((u,w))
res=[-1]*N
def dfs(v,p,c):
    res[v]=c
    for nv,w in G[v]:
        if res[nv]>=0:
            continue
        dfs(nv,v,(c+w)%2)
        """
        if w&1:
            dfs(nv,v,1-c)
        else:
            dfs(nv,v,c)
        """
dfs(0,-1,0)
for i in res:
    print(i)

Solution (Python):
import sys
import math 
ni = lambda: int(ns())
na = lambda: list(map(int, input().split()))
ns = lambda: input()

N=ni()
G=[dict() for i in range(N)]
for i in range(N-1):
    u,v,w=na()
    G[u-1][v-1]=w
    G[v-1][u-1]=w

dist=[-1 for i in range(N)]
color=[0 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
        else:
            dist[p]=dist[r]+G[r][p]
            q.append(p)
for i in range(N):
    if(dist[i]%2==0):
        color[i]=1

for ans in color:
    print(ans)

Solution (Python):


from collections import deque

N = int(input())
L = N-1
graph = [[] for _ in range(N)]
color = [-1 for _ in range(N)]
visit = [False for _ in range(N)]

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

que = deque([0])    
color[0] = 0    
while len(que) > 0:
    idx = que.popleft()
    visit[idx] = True
    for i, w in graph[idx]:
        if visit[i] is True:
            continue
        if w%2 == 0:    
            color[i] = color[idx]
            que.append(i)
        else:   
            color[i] = 1 - color[idx]   
            que.append(i)

for c in color:
    print(c)

Solution (Python):
N=int(input())
G=[[] for i in range(N)]
for i in range(N-1):
    u,v,w=map(int,input().split())
    u,v=u-1,v-1
    G[u].append((v,w))
    G[v].append((u,w))
reached=[0]*N
stack=[0]
reached[0]=[1]
res=[-1]*N
res[0]=0
while(stack):
    v=stack.pop()
    for nv,w in G[v]:
        if reached[nv]:
            continue
        if w & 1:
            res[nv]=1-res[v]
        else:
            res[nv]=res[v]
        stack.append(nv)
        reached[nv]=1
for i in res:
    print(i)

Solution (Python):
import sys
sys.setrecursionlimit(100100)
n=int(input())
route=[[] for i in range(n)]
for i in range(n-1):
	u,v,w=map(int,input().split())
	route[u-1].append((v-1,w))
	route[v-1].append((u-1,w))
ans=[-1]*n
def dfs(p,d):
	ans[p]=d
	for i,j in route[p]:
		if ans[i]<0:dfs(i,(d+j)%2)
dfs(0,0)
for i in range(n):
	print(ans[i])

Solution (Python):
from collections import deque

n = int(input())

node = [-1 for _ in range(n)]
que = deque()
neighbors = [[] for _ in range(n)]

for _ in range(n - 1):
    v1, v2, w = map(int, input().split())
    v1, v2 = v1 - 1, v2 - 1
    neighbors[v1].append((v2, w))
    neighbors[v2].append((v1, w))

que.append(0)
node[0] = 0
while len(que) > 0:
    p = que.popleft()
    for neighbor in neighbors[p]:
        v, w = neighbor
        if node[v] == -1:
            if w % 2 == 0:
                node[v] = node[p]
            else:
                if node[p] == 1:
                    node[v] = 0
                else:
                    node[v] = 1
            que.append(v)

for ni in node:
    print(ni)

Solution (Python):
import sys
sys.setrecursionlimit(10**7)
 
*D, = open(0)
n = int(D[0])
 
v = [[] for _ in range(n+1)]
 
dist = {}
 
for i in range(1, n):
    a, b, d = map(int, D[i].split())
    v[a].append(b)
    v[b].append(a)
    dist[(a,b)]=d
    dist[(b,a)]=d
 
def visit(current, v, dist, color):
   
    for it in v[current]:
        if color[it] != None:
            continue
        if dist[(it, current)]%2 == 0:
            color[it] = color[current]
        else:
            color[it] = not color[current]
        visit(it, v, dist, color)
        
color = [None for _ in range(n+1)]
color[1]=True
visit(1, v, dist, color)
 
for i in range(1, n+1):
    if color[i]:
        print('0')
    else:
        print('1')

Solution (Python):
import numpy as np

n=int(input())
E=[]
node_l=np.zeros(n)
node_l[0]=1
for i in range(n-1):
    u,v,w=map(int,input().split())
    
    E.append((u,v,w))


def bfs(node,l):
    root=[[] for i in range(n)]
    for a,b,c in l:
        root[a-1]+=[(b-1,c)]
        root[b-1]+=[(a-1,c)]
    stack=[]
    stack.append(node-1)
    
    dist=[-1]*n
    dist[node-1]=0
    while stack:
        
        buf=stack.pop(-1)
        for v,weight in root[buf]:
            if dist[v]==-1:
                dist[v]=dist[buf]+weight
                stack.append(v)
    return dist

for i in bfs(1,E):
    print(i%2,end='\n')

Solution (Python):

def main():
    import sys
    from collections import deque
    input = sys.stdin.readline
    N = int(input())
    color = [-1] * N
    color[0] = 0
    uvw = []
    edge = [[]for _ in range(N)]
    
    for i in range(N-1):
        ui, vi, wi = map(int, input().split())
        ui -= 1
        vi -= 1
        edge[ui].append((vi, wi))
        edge[vi].append((ui, wi))
    stack = [0]
    for i in range(N):
        tmp = deque()
        while stack:
            i = stack.pop()
            for e, w in edge[i]:
                if color[e] == -1:
                    stack.append(e)
                    if color[i] == 0:
                        if w % 2 == 0:
                            color[e] = 0
                        else:
                            color[e] = 1
                    else:
                        if w % 2 == 0:
                            color[e] = 1
                        else:
                            color[e] = 0
                
                
                else:
                    if (color[i] == color[e]) != (w % 2 == 0):
                        print(-1)
                        exit()
                
        
        stack = tmp
    print(*color, sep="\n")


if __name__ == '__main__':
    main()

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





def BFS(K,edges,N): 
  roots=[ [] for i in range(N)]
  for a,b,c in edges:
    roots[a-1]+=[(b-1,c)]
    roots[b-1]+=[(a-1,c)]
  dist=[-1]*N
  stack=[]
  stack.append(K)
  dist[K]=0
  while stack:
    label=stack.pop(-1)
    for i,c in roots[label]:
      if dist[i]==-1:
        dist[i]=dist[label]+c
        stack+=[i]
  return dist
 

edges=[]
N = int(input())
for i in range(N-1):
  edges += [list(map(int,input().split()))]
distance = BFS(0,edges,N)
for i in range(N):
  print(distance[i] % 2)

Solution (Python):
import sys
sys.setrecursionlimit(10**5-10)

n = int(input())
if n==1:
  print(0)
  exit()
from collections import defaultdict
edge = defaultdict(list)
for i in range(n-1):
  u, v, w = list(map(int, input().split()))
  edge[u].append((v, w))
  edge[v].append((u, w))
graph = [-1 for i in range(n+1)]

def dfs(x, c):
  nexts = edge.get(x)
  if nexts is None:
    return
  if graph[x]!=-1:
    return
  else:
    graph[x] = c
  for y, w in nexts:
    if w%2:
      dfs(y, not c)
    else:
      dfs(y, c)

dfs(1, 0)
for i in range(1, n+1):
  print(int(graph[i]))

Solution (Python):
import sys
sys.setrecursionlimit(10**5-1)

n = int(input())
if n==1:
  print(0)
  exit()
from collections import defaultdict
edge = defaultdict(list)
for i in range(n-1):
  u, v, w = list(map(int, input().split()))
  edge[u].append((v, w))
  edge[v].append((u, w))
graph = [-1 for i in range(n+1)]

def dfs(x, c):
  nexts = edge.get(x)
  if nexts is None:
    return
  if graph[x]!=-1:
    return
  else:
    graph[x] = c
  for y, w in nexts:
    if w%2:
      dfs(y, not c)
    else:
      dfs(y, c)

dfs(1, 0)
for i in range(1, n+1):
  print(int(graph[i]))

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

n = int(input())
if n==1:
  print(0)
  exit()
from collections import defaultdict
edge = defaultdict(list)
for i in range(n-1):
  u, v, w = list(map(int, input().split()))
  edge[u].append((v, w))
  edge[v].append((u, w))
graph = [-1 for i in range(n+1)]

def dfs(x, c):
  nexts = edge.get(x)
  if nexts is None:
    return
  if graph[x]!=-1:
    return
  else:
    graph[x] = c
  for y, w in nexts:
    if w%2:
      dfs(y, not c)
    else:
      dfs(y, c)

dfs(1, 0)
for i in range(1, n+1):
  print(int(graph[i]))

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

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

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

COLOR_WHITE = 0
COLOR_BLACK = 1
COLOR_NONE = 2

colors = [COLOR_NONE for _ in range(N)]
colors[0] = COLOR_WHITE

stack = [(0, 0)]

while stack:
    root, abs_distance = stack.pop()
    for node, distance in connections[root]:
        if colors[node] == COLOR_NONE:
            new_distance = abs_distance+distance
            colors[node] = COLOR_WHITE if (new_distance) % 2 == 0 else COLOR_BLACK
            stack += [(node, new_distance)]

for c in colors:
    print(c)

Solution (Python):
N = int(input())
graph = {}
root = -1
for n in range(N-1):
    u, v, w = map(int, input().split())
    u -= 1
    v -= 1

    if root == -1:
        root = u
    if u not in graph:
        graph[u] = {}
    if v not in graph:
        graph[v] = {}
    graph[u][v] = w
    graph[v][u] = w    

answer = [-1] * N
queue = [[root, 0]]
counter = -1
while counter < N - 1:
    counter += 1
    node = queue[counter][0]
    depth = queue[counter][1]
    answer[node] = depth
    for n in graph[node]:
        if answer[n] == -1:
            queue.append([n, depth + graph[node][n]])

for a in answer:
   print('0' if a % 2 else '1')

Solution (Python):
def solve(string):
    n, *uvw = map(int, string.split())
    g = [[] for _ in range(n + 1)]
    for u, v, w in zip(uvw[::3], uvw[1::3], uvw[2::3]):
        g[u].append((v, w))
        g[v].append((u, w))
    s = [(1, 0)]
    w = [-1] * (n + 1)
    while s:
        _s, _w = s.pop()
        w[_s] = _w % 2
        for _t, _w_ in g[_s]:
            if w[_t] == -1:
                s.append((_t, _w + _w_))
    return "\n".join(str(_w) for _w in w[1:])


if __name__ == '__main__':
    n = int(input())
    print(solve('{}\n'.format(n) + '\n'.join([input() for _ in range(n - 1)])))

Solution (Python):
def solve(string):
    n, *uvw = map(int, string.split())
    p = [[] for _ in range(n + 1)]
    for u, v, w in zip(uvw[::3], uvw[1::3], uvw[2::3]):
        p[u].append((v, w))
        p[v].append((u, w))
    s = [(1, 0)]
    l = [-1] * (n + 1)
    while s:
        _s, w = s.pop()
        l[_s] = w % 2
        for _t, _w in p[_s]:
            if l[_t] == -1:
                s.append((_t, w + _w))
    return "\n".join(str(_w) for _w in l[1:])


if __name__ == '__main__':
    n = int(input())
    print(solve('{}\n'.format(n) + '\n'.join([input() for _ in range(n - 1)])))

Solution (Python):
def solve(string):
    n, *uvw = map(int, string.split())
    p = [[] for _ in range(n + 1)]
    for u, v, w in zip(uvw[::3], uvw[1::3], uvw[2::3]):
        p[u].append((v, w))
        p[v].append((u, w))
    s = [(1, 0)]
    l = [-1] * n
    while s:
        a, w = s.pop()
        l[a - 1] = w % 2
        for b, c in p[a]:
            if l[b - 1] == -1:
                s.append((b, w + c))
    return "\n".join(str(c) for c in l)


if __name__ == '__main__':
    n = int(input())
    print(solve('{}\n'.format(n) + '\n'.join([input() for _ in range(n - 1)])))

Solution (Python):
N=int(input());p=[[]for _ in range(N+1)]
for _ in range(N-1):u,v,w=map(int,input().split());p[u].append((v,w));p[v].append((u,w))
s=[(1,0)];l=[-1]*N
while s:
 a,w=s.pop()
 l[a-1]=w%2
 for b,c in p[a]:
  if l[b-1]==-1:s.append((b,w+c))
for i in l:print(i)

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

to_cost = [[] for i in range(n + 1)]
for _ in range(n-1):
    u, v, w = map(int, input().split())
    to_cost[u].append([v, w % 2])
    to_cost[v].append([u, w % 2])
ans = [-1] * (n + 1)
stack = [(1,1)]
while stack:
    a, w = stack.pop()
    ans[a] = w
    for to, cost in to_cost[a]:
        if ans[to] < 0:
            stack.append((to, w ^ cost))

for a in ans[1:]:
    print(a)

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

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

ans = [-1] * N
P = [set() for _ in range(N)]
for l in L:
    u, v, w = l
    P[u - 1].add(((v - 1), w))
    P[v - 1].add(((u - 1), w))

ans[0] = 0
F = [0] * (N + 1)
it = 0
po = 1
already = {0}
for _ in range(N + 1):
    if it > po:
        break
    u = F[it]
    it += 1
    for (v, w) in P[u]:
        if v in already:
            continue
        ans[v] = ans[u] if w % 2 == 0 else 1 - ans[u]
        F[po] = v
        already.add(v)
        po += 1

res = ""
for a in ans:
    res += "{}\n".format(a)
print(res)

Solution (Python):
from queue import Queue

N = int(input())
X = [list(map(int, input().split())) for _ in range(N-1)]
X = list(map(lambda x: (x[0]-1, x[1]-1, x[2]), X))




node = [[] for i in range(N)]
for x in X:
    u, v, w = x
    node[u].append((v, w))
    node[v].append((u, w))


color = [-1] * N



q = Queue()
color[0] = 0
q.put((0, color[0]))
while not q.empty():
    q0 = q.get()

    n = q0[0]
    c = q0[1]
    neighbors = node[n]
    for p in neighbors:
        if color[p[0]] == -1:
            color[p[0]] = (c + p[1]) % 2
            q.put((p[0], color[p[0]]))

for c in color:
    print(c)

Solution (Python):
N = int(input())
adj = [[] for _ in range(N)]
 
for i in range(N-1):
    u,v,w = map(int,input().split())
    u,v = u-1, v-1
    w %= 2
    adj[u].append((v,w))
    adj[v].append((u,w))
 
color = [None]*N
color[0] = False
stack = [0]
 
while stack:
    u = stack.pop()
    for v,w in adj[u]:
        if color[v] is None:
            color[v] = (w%2) ^ color[u]
            stack += [v]
 
for c in color:
    print(1 if c else 0)

Solution (Python):
def sub():
    N = int(input())
    edges = []
    for _ in range(N-1):
        ed = [int(e) for e in input().split(" ")]
        edges.append(ed)
    
    d_neighbor = {i: [] for i in range(1, N+1)} 
    d_weight = {}
    for ed in edges:
        h, t, w = ed
        d_neighbor[h].append(t)
        d_neighbor[t].append(h)
        d_weight[(h,t)] = w
    
    d_color = {i: None for i in range(1, N+1)}
    for i in range(1, N+1):
        if d_color[i] is not None:
            continue
        
        s_visit = set()
        position = i
        
        stack = [position]
        d_color[position] = False
        while len(stack) > 0:
            position = stack.pop()
            s_visit.add(position)
            nn = d_neighbor[position]
            nn_uv = [n for n in nn if n not in s_visit]
            cTmp = d_color[position]
            for n in nn_uv:
                t = (position, n)
                if position > n:
                    t = (n, position)
                w = d_weight[t]
                if w % 2 == 0:
                    d_color[n] = cTmp
                else:
                    d_color[n] = not cTmp
            stack.extend(nn_uv)
    
    for i in range(1, N+1):
        print(int(d_color[i]))

sub()

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

N = int(input())
G = [[] for i 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])

color = [-1] * N


def dfs(x, y):
    for i, w in G[x]:
        if color[i] == -1:
            color[i] = (y+w) % 2
            dfs(i, y+w)


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

Solution (Python):
class UNION_FIND(object):
    def __init__(self,n):
        self.parent=[-1 for i in range(n)]
        
    def root(self,x):
        if self.parent[x]<0:
            return x
        else:
            self.parent[x]=self.root(self.parent[x])
            return self.parent[x]
 
    def size(self,x):
        return -self.parent[self.root(x)]
    def union(self,x,y):
        x=self.root(x)
        y=self.root(y)
        if x==y:
            return False
        if self.size(x)<self.size(y):
            x,y=y,x
        self.parent[x]+=self.parent[y]  
        self.parent[y]=x   
        return True

n=int(input())
u=UNION_FIND(2*n)
for i in range(n-1):
    a,b,c=map(int,input().split())
    if c%2==0:
        u.union(a-1,b-1)
        u.union(a-1+n,b-1+n)
    else:
        u.union(a-1+n,b-1)
        u.union(a-1,b-1+n)

for i in range(n):
    if u.root(i)<n:
        print(1)
    else:
        print(0)

Solution (Python):
import sys
from collections import deque
sys.setrecursionlimit(200000)
 
readline = sys.stdin.readline
 
N = int(readline())
 
nodes = [deque() for i in range(N)]
node_colors = [-1 for i in range(N)]
 
for i in range(N - 1):
    u,v,w = map(int, readline().split())
    u, v = u - 1, v - 1
    nodes[u].append([v, w])
    nodes[v].append([u, w])
 
 
node_colors[0] = 0
 
def process(u, parent, w): 
    p_color = node_colors[parent]
    node_colors[u] = p_color if w % 2 == 0 else 1 - p_color
    
    for v, w in nodes[u]:
        if v == parent:
            continue
        process(v, u, w)
 
for v, w in nodes[0]:
    process(v, 0, w)
 
for c in node_colors:
    print(c)

Solution (Python):
N=int(input());p=[[]for _ in range(N+1)]
for _ in range(N-1):u,v,w=map(int,input().split());p[u].append((v,w));p[v].append((u,w))
s=[(1,0)];l=[-1]*N
while s:
 a,w=s.pop()
 l[a-1]=w%2
 for b,c in p[a]:
  if l[b-1]==-1:s.append((b,w+c))
for i in l:print(i)

Solution (Python):
N=int(input())
p=[[]for _ in range(N+1)]
for _ in range(N-1):
 u,v,w=map(int,input().split())
 p[u].append((v,w))
 p[v].append((u,w))
s=[(1,0)]
l=[-1]*N
while s:
 a,w=s.pop()
 l[a-1]=w%2
 for b,c in p[a]:
  if l[b-1]==-1:
   s.append((b,w+c))
for i in l:
 print(i)

Solution (Python):
N=int(input())
p=[[]for _ in range(N+1)]
for _ in range(N-1):
  u,v,w=map(int,input().split())
  p[u].append((v,w))
  p[v].append((u,w))
s=[(1,0)]
l=[-1]*N
while s:
  a,w=s.pop()
  l[a-1]=w%2
  for b,c in p[a]:
    if l[b-1]==-1:
      s.append((b,w+c))
for i in l:
	print(i)