Problem:
 Score : 400 points    Problem Statement We have a tree with N vertices numbered 1 to N .
The i -th edge in the tree connects Vertex u_i and Vertex v_i , and its length is w_i .
Your objective is to paint each vertex in the tree white or black (it is fine to paint all vertices the same color) so that the following condition is satisfied:   For any two vertices painted in the same color, the distance between them is an even number.   Find a coloring of the vertices that satisfies the condition and print it. It can be proved that at least one such coloring exists under the constraints of this problem.      Constraints  All values in input are integers.  1 \leq N \leq 10^5  1 \leq u_i < v_i \leq N  1 \leq w_i \leq 10^9         Input Input is given from Standard Input in the following format:  N  u_1  v_1  w_1  u_2  v_2  w_2  .  .  .  u_{N - 1}  v_{N - 1}  w_{N - 1}       Output Print a coloring of the vertices that satisfies the condition, in N lines.
The i -th line should contain 0 if Vertex i is painted white and 1 if it is painted black.  If there are multiple colorings that satisfy the condition, any of them will be accepted.        Sample Input 1 3
1 2 2
2 3 1      Sample Output 1 0
0
1       Sample Input 2 5
2 5 2
2 3 10
1 3 8
3 4 2      Sample Output 2 1
0
1
0
1

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


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

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

def dfs(x,w,c):
    if w%2 !=0:
        c = 1-c
    S[x]=c
    for i in range(len(G[x])):
        x1 = G[x][i][0]-1
        if S[x1] != -1:
            continue
        w1 = G[x][i][1]
        dfs(x1,w1,c)

dfs(G[0][0][0]-1,G[0][0][1],0)
for i in range(N):
    print(S[i])

Solution (Python):
import sys
sys.setrecursionlimit(10 ** 5 + 10)
def input(): return sys.stdin.readline().strip()

def resolve():
    
    
    
    from heapq import heapify, heappop, heappush
    
    inf = 10 ** 17
    
    
    def dijkstra_heap(start, edge):
        
        d = [inf] * N
        used = [False] * N
        d[start] = 0
        used[start] = True
        edgelist = []
        
        for a, b in edge[start]:
            heappush(edgelist, a * (10 ** 6) + b)
    
        while len(edgelist):
            
            minedge = heappop(edgelist)
            if used[minedge % (10 ** 6)]:
                continue
            node = minedge % (10 ** 6)
            d[node] = minedge // (10 ** 6)
            used[node] = True
    
            for e in edge[node]:
                if not used[e[1]]:
                    heappush(edgelist, (e[0] + d[node]) * (10 ** 6) + e[1])
        return d
    
    
    
    N = int(input())
    W = N-1
    
    edge = [[] for i in range(N)]
    
    for _ in range(W):
        x, y, z = map(int, input().split())
        edge[x - 1].append((z, y - 1))
        edge[y - 1].append((z, x - 1))
    
    d = dijkstra_heap(0, edge)
    for i in d:
        print(i%2)
    
    
    
resolve()

Solution (Python):
import sys, re
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees
from collections import deque, defaultdict, Counter
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop, heapify
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7
 
N = INT()
uvw = [LIST() for _ in range(N-1)]

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

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



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

def DFS(node):
	for i, w in graph[node]:
		if color[i] == -1:
			if w%2:
				color[i] = color[node]^1
			else:
				color[i] = color[node]
			DFS(i)

DFS(0)



for x in color:
	print(x)

Solution (Python):
import sys, re
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees
from collections import deque, defaultdict, Counter
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop, heapify
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7
 
N = INT()
uvw = [LIST() for _ in range(N-1)]

graph = defaultdict(list)

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



colors=[0]*N
colors[0]=1

def DFS(node):
	for x, w in graph[node]:
		if not colors[x]:
			if w%2:
				colors[x] = colors[node]*(-1)
			else:
				colors[x] = colors[node]
			DFS(x)

DFS(0)



for x in colors:
	if x == 1:
		print(0)
	else:
		print(1)

Solution (Python):
import sys, re
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees
from collections import deque, defaultdict, Counter
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop, heapify
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7
 
N = INT()
uvw = [LIST() for _ in range(N-1)]

graph = defaultdict(list)

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



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

def DFS(node):
	for x, w in graph[node]:
		if colors[x] == -1:
			if w%2:
				colors[x] = colors[node]^1
			else:
				colors[x] = colors[node]
			DFS(x)

DFS(0)



for x in colors:
	print(x)

Solution (Python):
import sys, re
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees
from collections import deque, defaultdict, Counter
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop, heapify
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7
 
N = INT()
uvw = [LIST() for _ in range(N-1)]

graph = defaultdict(list)

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



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

def DFS(node):
	for x, w in graph[node]:
		if not color[x]:
			if w%2 == 0:
				color[x] = color[node] 
			else:
				color[x] = color[node]*(-1)
			DFS(x)

DFS(0)

for x in color:
	if x == 1:
		print(0)
	elif x == -1:
		print(1)
	else:
		print("HOGE")

Solution (Python):
import sys, re
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees
from collections import deque, defaultdict, Counter
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop, heapify
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7
 
N = INT()
uvw = [LIST() for _ in range(N-1)]

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

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



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

def DFS(n):
	for x, w in graph[n]:
		
		if step[x] == -1:
			if (w+step[n])%2:
				step[x] = 1
			else:
				step[x] = 0
			
			DFS(x)

DFS(0)

for ans in step:
	print(ans)

Solution (Python):
import sys, re
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees
from collections import deque, defaultdict, Counter
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop, heapify
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7
 
N = INT()
uvw = [LIST() for _ in range(N-1)]

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

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



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

def DFS(n):
	for x, w in graph[n]:
		
		if step[x] == -1:
			if (w+step[n])%2:
				step[x] = 1
			else:
				step[x] = 0
			
			DFS(x)

DFS(0)

for ans in step:
	print(ans)

Solution (Python):
import sys
import collections
def input():
    return sys.stdin.readline()[:-1]
sys.setrecursionlimit(10000000)

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])
lis = [-1 for i in range(n)]
def dfs(i,j,color):
    for nec,leng in g[i]:
        if nec==j:continue
        if leng%2==0:
            lis[nec] = color
            dfs(nec,i,color)
        else:
            lis[nec] = 1-color
            dfs(nec,i,1-color)
lis[0]=0
dfs(0,-1,0)

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

Solution (Python):


import sys
sys.setrecursionlimit(10 ** 6)


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


N = int(input())
UVW = [LI() for _ in range(N - 1)]



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


def dfs(ans, x):
    for y, w in link[x]:
        if ans[y] is None:
            if w % 2 == 0:
                ans[y] = ans[x]
            else:
                ans[y] = 0 if ans[x] else 1
            dfs(ans, y)


def main():
    ans = [None] * N
    ans[0] = 0
    dfs(ans, 0)
    for a in ans:
        print(a)


if __name__ == "__main__":
    main()

Solution (Python):


import sys
input= lambda: sys.stdin.readline().rstrip()
sys.setrecursionlimit(10**9)
def pin(type=int):return map(type,input().split())
def tupin(t=int):return tuple(pin(t))
def lispin(t=int):return list(pin(t))

def resolve():
    N,=pin()
    graph={i+1:dict() for i in range(N)}
    
    for i in range(N-1):
        u,v,w=pin()
        graph[u][v]=w%2
        graph[v][u]=w%2
    

    ans={i+1:0 for i in range(N)}
    seen={i+1:0 for i in range(N)}
    
    stack=[(1,0)]
    while (stack!=[]):
        p,c=stack.pop()
        if seen[p]==1:continue

        seen[p]=1
        ans[p]=c
        for k,v in graph[p].items():
            stack.append((k,(c+v)%2))
    
    print(*ans.values(),sep="\n")
resolve()

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

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

def func(x, w, c):
    if w % 2 != 0:
        c = 1 - c
    S[x] = c
    for i in range(len(G[x])):
        x1 = G[x][i][0] - 1
        if S[x1] != -1:
            continue
        w1 = G[x][i][1]
        func(x1, w1, c)

func(G[0][0][0] - 1, G[0][0][1], 0)
for i in range(N):
    print(S[i])

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

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

res = [None] * N
visited = [False] * (N+1)
def dfs(node, c, w):
  res[node-1] = c
  visited[node] = True

  for nei, nw, in adj_list[node]:
    if not visited[nei]:
      if (w+nw)%2 == 0:
        dfs(nei, 0, w+nw)
      else:
        dfs(nei, 1, w+nw)

dfs(1, 0, 0)
for r in res: print(r)

Solution (Python):
import sys
sys.setrecursionlimit(10 ** 6)
N = int(input())
uvw = [list(map(int, input().split())) for i in range(N - 1)]
R = [-1] * N
Q = [[] for i in range(N)]
for i in range(N - 1):
    Q[uvw[i][0] - 1].append([uvw[i][1], uvw[i][2]])
    Q[uvw[i][1] - 1].append([uvw[i][0], uvw[i][2]])

def func(i, s, d, l):
    
    if R[i] != -1:
        return

    if R[i] == -1:
        if l %2 == 0:
            R[i] = s
        else:
            R[i] = d
            tmp = s
            s = d
            d = tmp
    for j in range(len(Q[i])):
        func(Q[i][j][0] - 1, s, d, Q[i][j][1])

func(uvw[0][0] - 1, 0, 1, 0)
for i in range(len(R)):
    print(R[i])

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

n = int(input())
t = [[] for _ in range(n)]
color = [None for _ in range(n)]
visited = [False for _ in range(n)]


def dfs(n_num):
    visited[n_num] = True
    for i in t[n_num]:
        if visited[i[0]]:
            continue
        if i[1] % 2 == 0:
            color[i[0]] = color[n_num]
        else:
            color[i[0]] = abs(color[n_num] - 1)
        dfs(i[0])


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

color[0] = 0
dfs(0)
for i in color:
    print(i)

Solution (Python):
from queue import Queue
N = int(input())
G = [[] for _ in range(N)]
C = [[] for _ in range(N)]
for _ in range(N-1):
    a, b, w = map(int, input().split())
    a -= 1
    b -= 1
    G[a].append(b)
    C[a].append(w)
    G[b].append(a)
    C[b].append(w)
ans = [-1] * N
ans[0] = 0
que = Queue()
que.put(0)
while not que.empty():
    v = que.get()
    l = len(G[v])
    for i in range(l):
        u = G[v][i]
        w = C[v][i]
        if ans[u] != -1:
            continue
        ans[u] = (ans[v] + w) % 2
        que.put(u)
print(*ans, sep='\n')

Solution (Python):
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
from itertools import accumulate
from itertools import permutations
from itertools import combinations
from collections import defaultdict
from collections import Counter
import fractions
import math
from collections import deque
from bisect import bisect_left
from bisect import insort_left
import itertools
from heapq import heapify
from heapq import heappop
from heapq import heappush
import heapq
import numpy as np
INF = float("inf")











N = int(input())
tree = [[] for _ in range(N)]
for _ in range(N-1):
    u,v,w = map(int,(input().split()))
    tree[u-1].append((v-1,w))
    tree[v-1].append((u-1,w))
color = [-1]*N
black = 0
white = 1
color[0] = white
def dfs(cur,parent):
    li = tree[cur]
    for chi,dis in li:
        if chi == parent:
            continue
        if dis % 2 == 0:
            color[chi] = color[cur]
            dfs(chi,cur)
        else:
            if color[cur] == black:
                color[chi] = white
            else:
                color[chi] = black
            dfs(chi,cur)
dfs(0,-1)
for i in color:
    print(i)

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

N = int(input())
color = [-1]*N
graph = [[] for _ in range(N)]
for _ in range(N-1):
  u, v, w = map(int, input().split())
  u -= 1
  v -= 1
  graph[u] += [[v, w]]
  graph[v] += [[u, w]]

def dfs(u, c):
  color[u] = c
  for v, w in graph[u]:
    if color[v] == -1:
      if w % 2 == 0:
        dfs(v, c)
      else:
        dfs(v, abs(1-c))
  return

dfs(0, 0)
color = list(map(str, color))
print(*color)

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

def dfs(node,w):
  weight = w
  for l in tree[node]:
    if color[l[0]] > -1:
      continue
    color[l[0]] = int (not ((l[1]%2==0) ^ color[node]))
    
    dfs(l[0],l[1])
    


N = int(input())
tree = {}
color = [-1]*(N+1)

for i in range(1,N+1):
  tree[i] = []
for i in range(N-1):
  u,v,w = map(int,input().split())
  tree[u].append([v,w])
  tree[v].append([u,w])
  
color[1] = 0
dfs(1,0)
print('\n'.join(map(str,color[1:])))

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

def dfs(node,w):
  weight = w
  for l in tree[node]:
    if color[l[0]] > -1:
      continue
    if l[1]%2 == 0:
      color[l[0]] = color[node]
    else:
      color[l[0]] = int(not color[node])
    dfs(l[0],l[1])
    


N = int(input())
tree = {}
color = [-1]*(N+1)

for i in range(1,N+1):
  tree[i] = []
for i in range(N-1):
  u,v,w = map(int,input().split())
  tree[u].append([v,w])
  tree[v].append([u,w])
  
color[1] = 0
dfs(1,0)
color = [c  if c>-1 else 0 for c in color]
print('\n'.join(map(str,color[1:])))

Solution (Python):
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(2000000)


    N = int(input())
    edges = [[]for _ in range(N+1)]
    for _ in range(N-1):
        u,v,w = map(int,input().split())
        edges[u].append((v,w%2))
        edges[v].append((u,w%2))
    colors = [0]*(N+1)
    def dfs(n,p,c):
        colors[n] = c
        for nx,w in edges[n]:
            if nx != p:
                if w%2 == 0:
                    dfs(nx,n,c)
                else:
                    dfs(nx,n,(c+1)%2)

    dfs(1,0,0)
    for i in range(1,N+1):
        print(colors[i])

main()

Solution (Python):
n = int(input())
g = [[]for i in range(n)]
def swap(n):
    if n == 1:
        return 0
    else:
        return 1
for i in range(n-1):
    u,v,w = map(int,input().split())
    u = u-1
    v = v-1
    w = w%2
    g[u].append([v,w])
    g[v].append([u,w])
ans = [-1 for i in range(n)]
from collections import deque
d = deque([[0,0]]) 
while d:
    p,q = d.pop()
    ans[p] = q
    for j,w in g[p]:
        if ans[j] != -1:
            continue
        else:
            if w == 1:
                d.append([j,swap(q)])
            else:
                d.append([j,q])
for i in range(n):
    print(ans[i])

Solution (Python):
n = int(input())
g = [[]for i in range(n)]
def swap(n):
    if n == 1:
        return 0
    else:
        return 1
for i in range(n-1):
    u,v,w = map(int,input().split())
    u = u-1
    v = v-1
    w = w%2
    g[u].append([v,w])
    g[v].append([u,w])
ans = [-1 for i in range(n)]
from collections import deque
d = deque([[0,0]]) 
while d:
    p,q = d.popleft()
    ans[p] = q
    for j,w in g[p]:
        if ans[j] != -1:
            continue
        else:
            if w == 1:
                d.append([j,swap(q)])
            else:
                d.append([j,q])
for i in range(n):
    print(ans[i])

Solution (Python):

from collections import deque
import sys
try:
    from typing import List
except ImportError:
    pass


def solve(N: int, u: "List[int]", v: "List[int]", w: "List[int]"):
    G = [[] for _ in range(N)]
    for ui, vi, wi in zip(u, v, w):
        ui -= 1
        vi -= 1
        G[ui].append((vi, wi))
        G[vi].append((ui, wi))
    color = [-1] * N
    color[0] = 0
    q = deque([0])
    while q:
        s = q.popleft()
        for t, wi in G[s]:
            if color[t] >= 0:
                continue
            color[t] = (color[s] + wi) % 2
            q.append(t)
    for colori in color:
        print(colori)


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))
    solve(N, u, v, w)


if __name__ == '__main__':
    main()

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

start=0
node =[None]*N
node[start] =0
dq =deque()
dq.append(start)


while dq:
    sarch =dq.popleft()
    for nv,w in connection[sarch]:
        if node[nv] is None:
            node[nv] = (node[sarch] +w) %2
            dq.append(nv)   
print(*node,sep="\n")

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())
    T[u-1].append([v-1,w%2])
    T[v-1].append([u-1,w%2])

ans = [0]*N
used_1 = [0]*N
used_2 = [0]*N
for i in range(N):
    if used_1[i] == 0:
        used_1[i] = 1
        u = i
        P = deque([])
        for j in range(len(T[i])):
            v = T[u][j][0]
            w = T[u][j][1]
            P.append(v)
            if used_2[v] == 1:
                k = ans[v]
                if k == 1:
                    if w == 1:
                        ans[u] = 0
                    else:
                        ans[u] = 1
                else:
                    if w == 1:
                        ans[u] = 1
                    else:
                        ans[u] = 0
                used_2[u] = 1
            elif used_2[u] == 1:
                k = ans[u]
                if k == 1:
                    if w == 1:
                        ans[v] = 0
                    else:
                        ans[v] = 1
                else:
                    if w == 1:
                        ans[v] = 1
                    else:
                        ans[v] = 0
                used_2[v] = 1
            else:
                if w == 1:
                    ans[v] = 1
                else:
                    pass
                used_2[u] = 1
                used_2[v] = 1
        while(True):
            i = P.popleft()
            if used_1[i] == 0:
                used_1[i] = 1
                u = i
                for j in range(len(T[i])):
                    v = T[u][j][0]
                    w = T[u][j][1]
                    P.append(v)
                    if used_2[v] == 1:
                        k = ans[v]
                        if k == 1:
                            if w == 1:
                                ans[u] = 0
                            else:
                                ans[u] = 1
                        else:
                            if w == 1:
                                ans[u] = 1
                            else:
                                ans[u] = 0
                        used_2[u] = 1
                    elif used_2[u] == 1:
                        k = ans[u]
                        if k == 1:
                            if w == 1:
                                ans[v] = 0
                            else:
                                ans[v] = 1
                        else:
                            if w == 1:
                                ans[v] = 1
                            else:
                                ans[v] = 0
                        used_2[v] = 1
                    else:
                        if w == 1:
                            ans[v] = 1
                        else:
                            pass
                        used_2[u] = 1
                        used_2[v] = 1
            if len(P) == 0:
                break

for i in ans:
    print(i)

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

def dijkstra_heap(s):
    
    d = [float("inf")] * n
    used = [True] * n 
    d[s] = 0
    used[s] = False
    edgelist = []
    for e in edge[s]:
        heapq.heappush(edgelist,e)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        
        if not used[minedge[1]]:
            continue
        v = minedge[1]
        d[v] = minedge[0]
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,[e[0]+d[v],e[1]])
    return d

Path_from_0 = dijkstra_heap(0)
for i in range(n):
    print(Path_from_0[i] % 2)

Solution (Python):
import numpy as np
from scipy.sparse.csgraph import shortest_path
import heapq
n = int(input())
edge = [[] for i in range(n)]
for i in range(n-1):
    u, v, w = map(int, input().split())
    u -= 1
    v -= 1
    edge[u].append([w, v])
    edge[v].append([w, u])

def dijkstra_heap(s):
    
    d = [float("inf")] * n
    used = [True] * n 
    d[s] = 0
    used[s] = False
    edgelist = []
    for e in edge[s]:
        heapq.heappush(edgelist,e)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        
        if not used[minedge[1]]:
            continue
        v = minedge[1]
        d[v] = minedge[0]
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,[e[0]+d[v],e[1]])
    return d

Path_from_0 = dijkstra_heap(0)
for i in range(n):
    print(Path_from_0[i] % 2)

Solution (Python):
from collections import defaultdict
import sys
sys.setrecursionlimit(1000000)

class edge:
    def __init__(self, to, cost):
        self.to, self.cost = to, cost

def main():
    N = int(input())
    g = defaultdict(list)
    for i in range(N-1):
        u, v, w = (int(_) for _ in input().split())
        g[u].append(edge(v, w))
        g[v].append(edge(u, w))

    color = [0] * (N+1)

    def dfs(ver):
        for e in g[ver]:
            if color[e.to] == 0 and e.cost%2 == 0:
                color[e.to] = color[ver]
                dfs(e.to)
            elif color[e.to] == 0 and e.cost%2 == 1:
                color[e.to] = (-1) * color[ver]
                dfs(e.to)
    color[1] = 1
    dfs(1)
    for i in range(1, N+1):
        if color[i] == -1: color[i] = 0
    print(*color[1:], sep='\n')
    return

if __name__ == '__main__':
    main()

Solution (Python):
from functools import reduce
from fractions import gcd
import math
import bisect
import itertools
import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline
INF = float("inf")
MOD = 1000000007


class Edge:
    def __init__(self, to, cost):
        self.to = to
        self.cost = cost


visited = []
vertex = []
def dfs(G, v, d):
    visited[v] = True
    if d % 2 == 0:
        vertex[v] = 0
    else:
        vertex[v] = 1

    for edge in G[v]:
        nv = edge.to
        if visited[nv]:
            continue
        nd = d + edge.cost
        dfs(G, nv, nd)


def main():
    N = int(input())
    G = [[] for _ in range(N)]
    for _ in range(N-1):
        a, b, cost = map(int, input().split())
        a -= 1; b -= 1
        G[a].append(Edge(b, cost))
        G[b].append(Edge(a, cost))

    for _ in range(N):
        visited.append(False)
        vertex.append(0)
    
    dfs(G, 0, 0)

    for v in vertex:
        print(v)


if __name__ == '__main__':
    main()

Solution (Python):
import sys
def input(): return sys.stdin.readline().rstrip()
from collections import deque
def main():
    n=int(input())
    graph=[[]for _ in range(n)]
    for _ in range(n-1):
        u,v,w=map(int,input().split())
        graph[u-1].append((v-1,w))
        graph[v-1].append((u-1,w))
    D=[-1]*n
    D[0]=0
    que=deque([0])
    while que:
        q=que.popleft()
        qw=D[q]
        for nn,w in graph[q]:
            if D[nn]==-1:
                D[nn]=qw+w
                que.append(nn)
    for d in D:
        if d%2==0:
            print(0)
        else:
            print(1)


if __name__=='__main__':
    main()

Solution (Python):
import sys
def input(): return sys.stdin.readline().rstrip()
from collections import deque
def main():
    n=int(input())
    graph=[[]for _ in range(n)]
    for _ in range(n-1):
        u,v,w=map(int,input().split())
        graph[u-1].append((v-1,w))
        graph[v-1].append((u-1,w))
    D=[-1]*n
    D[0]=0
    que=deque([0])
    while que:
        q=que.popleft()
        qw=D[q]
        for nn,w in graph[q]:
            if D[nn]==-1:
                D[nn]=qw+w
                que.append(nn)
    for d in D:
        if d%2==0:
            print(0)
        else:
            print(1)


if __name__=='__main__':
    main()

Solution (Python):
import sys
def input(): return sys.stdin.readline().rstrip()
from collections import deque
def main():
    n=int(input())
    graph=[[]for _ in range(n)]
    for _ in range(n-1):
        u,v,w=map(int,input().split())
        graph[u-1].append((v-1,w))
        graph[v-1].append((u-1,w))
    D=[-1]*n
    D[0]=0
    que=deque([0])
    while que:
        q=que.popleft()
        qw=D[q]
        for nn,w in graph[q]:
            if D[nn]==-1:
                D[nn]=qw+w
                que.append(nn)
    for d in D:
        if d%2==0:
            print(0)
        else:
            print(1)


if __name__=='__main__':
    main()

Solution (Python):
n = int(input())
tree = [[] for i in range(n)]
d_list = [0]*n

stack = []
for i in range(n-1):
  u,v,w = map(int,input().split())
  tree[u-1].append((u-1,v-1,w))
  tree[v-1].append((v-1,u-1,w))
while len(tree[0]) > 0:
  e = tree[0].pop()
  stack.append(e)

while len(stack) > 0:
  u,v, w = stack.pop()
  if d_list[v] == 0:
    d_list[v] = d_list[u]+w
  while len(tree[v]) > 0:
    e = tree[v].pop()
    stack.append(e)
  
for v in d_list:
  if v % 2 == 0:
    print(0)
  else:
    print(1)

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



n=int(input())

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

result=[-1]*n

def DEF(x,dis):
    
    global tree, uvw,result
    for nextNode in tree[x]:
        if result[nextNode]==-1:
            nextDis=dis+uvw[(min(x,nextNode),max(x,nextNode))]
            if (nextDis)%2==0:
                result[nextNode]=0
                DEF(nextNode,nextDis)
            else:
                result[nextNode]=1
                DEF(nextNode,nextDis)
result[0]=0
DEF(0,0)

for item in result:
    print(item)