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())
Adj_dict = {x:[] for x in range(1, n+1)}
for _ in range(n-1):
    u, v, w = map(int, input().split())
    Adj_dict[u].append([v,w])
    Adj_dict[v].append([u,w])

dq = deque()
dq.append(1)
Visited = [-1 for _ in range(n+1)]
Visited[1] = 0

while dq:
    now = dq.popleft()
    Adjs = Adj_dict[now]
    for adj in Adjs:
        if Visited[adj[0]] != -1:
            continue
        else:
            dq.append(adj[0])
            Visited[adj[0]] = Visited[now] + adj[1]

for i in range(1,n+1):
    print(Visited[i]%2)

Solution (Python):
from collections import deque
n=int(input())
A=[[[] for j in range(2)] for i in range(n)]
for i in range(n-1):
  u,v,w=map(int,input().split())
  w=w%2
  A[u-1][0].append(v-1)
  A[u-1][1].append(w)
  A[v-1][0].append(u-1)
  A[v-1][1].append(w)
B=deque([0])
C=[0]*n
C[0]=1
ans=[0]*n
while len(B)>0:
  s=B[0]
  B.popleft()
  for i in range(len(A[s][0])):
    if C[A[s][0][i]]==0:
      B.append(A[s][0][i])
      C[A[s][0][i]]=1
      ans[A[s][0][i]]=(ans[s]+A[s][1][i])%2
for i in range(n):
  print(ans[i])

Solution (Python):
import sys
 
n = int(input())
links = [set() for _ in [0] * n]
for line in sys.stdin:
    u, v, w = map(int, line.split())
    u -= 1
    v -= 1
    links[u].add((v, w))
    links[v].add((u, w))
ans = [-1] * n
q = [(0, 0, -1)]
while q:
    v, d, p = q.pop()
    if d % 2 == 0:
        ans[v] = 0
    else:
        ans[v] = 1
    for u, w in links[v]:
        if u == p:
            continue
        q.append((u, d + w, v))
print('\n'.join(map(str, ans)))

Solution (Python):
import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 7)
N = int(input())
edge = [[] for _ in range(N + 1)]
for _ in range(N - 1):
    a, b, c = map(int, input().split())
    edge[a].append((b, c % 2))
    edge[b].append((a, c % 2))

root = 1
dist = [-1] * (N + 1)
dist[root] = 0
node = [root]

while node:
    s = node.pop()
    d = dist[s]
    for t, c in edge[s]:
        if dist[t] != -1:
            continue
        dist[t] = (d + c) % 2
        node.append(t)

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

Solution (Python):
from collections import deque

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

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

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

        if ans[u] != -1:
            continue
        ans[u] = (ans[v] + w) % 2
        q.append(u)
for i in range(n):
    print(ans[i])

Solution (Python):

import sys

class Node:
    def __init__(self):
        self.children = []
        self.color = -1
    
    def append(self,target,weight):
        self.children.append((target,weight))
        target.children.append((self,weight))
 
    def setColor(self,color):
        self.color = color
        for child in self.children:
            if child[0].color != -1:
                continue
            if child[1] % 2 == 0:
                child[0].setColor(self.color)
            else:
                child[0].setColor(0 if self.color == 1 else 1)

def solve(N: int, u: "List[int]", v: "List[int]", w: "List[int]"):
    nodes = [Node() for i in range(N)]
    
    for i in range(N-1):
        nodes[u[i]-1].append(nodes[v[i]-1],w[i])
    colorQueue = [(nodes[0],0)]
    while True:
        if len(colorQueue) == 0:
            break
        next = colorQueue.pop()
        next[0].color = next[1]
        for child in next[0].children:
            if child[0].color != -1:
                continue
            if child[1] % 2 == 0:
                colorQueue.append((child[0],next[0].color))
            else:
                colorQueue.append((child[0],0 if next[0].color == 1 else 1))

    for n in nodes:
        print(n.color)
    return



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

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

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

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

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

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

Solution (Python):

import sys
sys.setrecursionlimit(500000)

n=int(input())
edges=[[] for _ in range(n)]
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))
visit=[False for _ in range(n)]
d=[0 for i in range(n)]

def dfs(i):
    visit[i]=True
    for v,w in edges[i]:
        if visit[v]==False:
            d[v]=(d[i]+w)%2
            dfs(v)
            
dfs(0)
print(*d,sep='\n')

Solution (Python):

import sys
sys.setrecursionlimit(500000)

n=int(input())
edges=[[] for _ in range(n)]
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))
visit=[False for _ in range(n)]
d=[0 for i in range(n)]

def dfs(i):
    visit[i]=True
    if all(visit[i] for i in range(n)):
        print(*d,sep='\n')
        exit()
    for v,w in edges[i]:
        if visit[v]==False:
            d[v]=(d[i]+w)%2
            dfs(v)
            
dfs(0)

Solution (Python):
from collections import deque

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

q = deque([1])
visit[1] = 0
while q:
    position = q.popleft()
    for i, cost in friends[position]:
        if visit[i] < 0:
            visit[i] = visit[position] + cost
            q.append(i)

for i in visit[1:]:
    print(i%2)

Solution (Python):
import sys
sys.setrecursionlimit(9**9)
n=int(input())
C=[0 for _ in range(n)]
L=[[] for _ in range(n)]
for j in range(n-1):
  u,v,w=map(int,input().split())
  u-=1
  v-=1
  L[u].append([v,w])
  L[v].append([u,w])
def a(n,v,d):
  for i in L[n]:
    if d%2==1:C[n]=1
    if v!=i[0]:a(i[0],n,d+i[1])
a(0,0,0)
for c in C:print(c)

Solution (Python):
import sys
from collections import defaultdict
sys.setrecursionlimit(10 ** 9)
def input(): return sys.stdin.readline().rstrip()

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

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

    depth = [-1] * (N)
    depth[0] = 0
    def dfs(x):
        for i, g in graph[x].items():
            if depth[i] > -1:
                continue
            depth[i] = depth[x] + g
            dfs(i)
    dfs(0)
    print("\n".join(['1' if d % 2 == 0 else '0' for d in depth]))

if __name__ == '__main__':
    main()

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

N=int(input())
A=[list(map(int,input().split())) for _ in range(N-1)]
C=[0]*N
D=[[] for i in range(N)]
for u,v,w in A:
  u-=1
  v-=1
  D[u].append((v,w))
  D[v].append((u,w))

def dfs(n,v,k):
  for i in D[n]:
    if k%2!=0:
      C[n]=1
    if v!=i[0]:
      dfs(i[0],n,k+i[1])       
        
dfs(0,0,0)

for i in C:
  print(i)

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

N = int(input())
visited = [False] * N
colors = [-1] * N
dist = [float('inf')] * N

def dfs(u):
    if visited[u]:
        return

    visited[u] = True
    for (v, w) in edges[u]:
        if visited[v]:
            continue
        if colors[v] != -1:
            continue

        dist[v] = dist[u] + w
        if dist[v] % 2 == 0:
            colors[v] = 0
        else:
            colors[v] = 1
        dfs(v)


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


colors[0] = 0
dist[0] = 0
dfs(0)
for c in colors:
    print(c)

Solution (Python):



from collections import defaultdict, deque

def main():
  tree = defaultdict(list)
  weights = dict()
  n = int(input())
  colors = dict()
  
  for _ in range(n-1):
    u, v, w = map(int, input().strip().split())
    tree[u].append(v)
    tree[v].append(u)
    weights[(u, v)] = weights[(v, u)] = w%2
  
  def bs(iroot=1):
    visited = set()
    dq = deque()
    dq.append((iroot, 0))
    colors[iroot] = 0
    while dq:
      inode, sw = dq.popleft()
      visited |= set([inode])
      
      for ichild in tree[inode]:
        if ichild in visited:
          continue
        colors[ichild] = (sw + weights[(inode, ichild)])%2
        dq.append((ichild, (sw + weights[(inode, ichild)]%2)))
    return colors
  
  colors = bs()
  for i in range(1, len(colors)+1):
    print(colors[i])

if __name__=='__main__':
  main()

Solution (Python):
import heapq
import sys

N = int(input())
a = [[] for i in range(N)]
for i in range(N - 1):
	u, v, w = map(int, input().split())
	a[u - 1].append((v - 1, w))
	a[v - 1].append((u - 1, w))
b = [(0, 0)]
c = [False] * N
d = [sys.maxsize] * N
d[0] = 0
while len(b) != 0:
	e = heapq.heappop(b)
	c[e[1]] = True
	for i in a[e[1]]:
		if c[i[0]]:
			continue
		if d[e[1]] + i[1] < d[i[0]]:
			d[i[0]] = d[e[1]] + i[1]
			heapq.heappush(b, (d[i[0]], i[0]))
for i in d:
	print(i % 2)

Solution (Python):
from collections import deque
n=int(input())
edges=[[] for _ in range(n)]
visited=[-1 for _ in range(n)]
for i 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))
def dfs(edges,visited):
  stack=deque([0])
  visited[0]=0
  while stack:
    x=stack.pop()
    for newx,w in edges[x]:
      if visited[newx]==-1:
        if w%2:
          visited[newx]=1-visited[x]
        else:
          visited[newx]=visited[x]
        stack.append(newx)
  return visited
for i in dfs(edges,visited):
  print(i)

Solution (Python):
import math
import copy
from copy import deepcopy
import sys
import fractions
import numpy as np
from functools import reduce

import heapq
sys.setrecursionlimit(100001)






def getInputInt():
    inputNum = int(input())
    return inputNum


def getInputListInt():
    outputData = []
    inputData = input().split()
    outputData = [int(n) for n in inputData]

    return outputData


def getSomeInputInt(n):
    outputDataList = []
    for i in range(n):
        inputData = int(input())
        outputDataList.append(inputData)

    return outputDataList


def getSomeInputListInt(n):
    inputDataList = []
    outputDataList = []
    for i in range(n):
        inputData = input().split()
        inputDataList = [int(n) for n in inputData]
        outputDataList.append(inputDataList)

    return outputDataList




n = int(input())


ans = [-1]*n

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])
ans = [-1]*n
def dfs(x,y):
    for i,j in g[x]:
        if ans[i] == -1:
            ans[i] = (y+j)%2
            dfs(i,y+j)
dfs(0,0)
for i in ans:
    print(i)

Solution (Python):
from collections import deque

def bfs(colors, links):
    q = deque([(0, 0)])
    
    while q:
        v, current = q.popleft()

        for next_v, distance in links[v]:
            if colors[next_v] != -1: continue
        
            if (current+distance) % 2 == 0:
                colors[next_v] = 0
            else:
                colors[next_v] = 1

            q.append((next_v, current + distance))
        
def solve():
    N = int(input())
    A = [list(map(int, input().split())) for _ in range(N-1)]
    cs = [-1] * N
    cs[0] = 0

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

    bfs(cs, links)

    print('\n'.join(map(str, cs)))

solve()

Solution (Python):
from collections import deque

def bfs(colors, links):
    q = deque([(0, 0)])
    
    while q:
        v, current = q.popleft()

        if current % 2 == 0:
            colors[v] = 0
        else:
            colors[v] = 1

        for next_v, distance in links[v]:
            if colors[next_v] != -1: continue

            q.append((next_v, current + distance))
        
def solve():
    N = int(input())
    A = [list(map(int, input().split())) for _ in range(N-1)]
    cs = [-1] * N
    cs[0] = 0

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

    bfs(cs, links)

    print('\n'.join(map(str, cs)))

solve()

Solution (Python):
import sys
from collections import deque
sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline
N = int(input())
L = [deque([]) for _ in range(N)]
ans = [-1] * N

for n in range(N-1):
    u, v, w = [int(x) for x in input().strip().split()]
    L[u-1].append((v, w))
    L[v-1].append((u, w))

def dfs(x, w):
    if ans[x-1] >= 0:
        return
    ans[x-1] = w % 2
    for nx, w_ in L[x-1]:
        dfs(nx, (w + w_) % 2)
    return

dfs(1, 0)

for a in ans:
    print(a)

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

N = int(input())
d = [[] for _ in range(N)]
iro = [0] * (N)

def dfs(n, v, k):
    for i in d[n]:
        if k % 2 != 0:
            iro[n] = 1
        if v == i[0]:
            continue
        dfs(i[0], n, k + i[1])

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

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

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

N = int(input())

G = []
for i in range(N):
    G.append([])

color = [None] * N

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




def dfs(v, c):
    color[v] = c

    
    for p, d in G[v]:
        
        if color[p] is not None:
            continue
        if d % 2 == 0:
            dfs(p, c)
        else:
            dfs(p, c ^ 1)  


dfs(0, 0)


for col in color:
    print(col)

Solution (Python):


import sys
 
sys.setrecursionlimit(10**7)

def dfs(num,hiyo):
    ans[num]=hiyo
    for to,cos in way[num]:
        if ans[to]==-1:
            dfs(to,hiyo+cos)
    
    return 

N=int(input())

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

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



dfs(0,0)

for item in ans:
    print(item%2)

Solution (Python):
import copy ; import sys ; sys.setrecursionlimit(11451419)
n=int(input())
color=[-1 for i in range(n)]
color[0]=1
G=[[] for i in range(n)]
for i in range(n-1):
  a,b,d=map(int,input().split())
  G[a-1].append([b-1,d])
  G[b-1].append([a-1,d])
  
def dfs(x):
  
  for i,dis in G[x]:
    
    if color[i] != -1: continue
    if dis %2==1:
      color[i]=1-color[x]
    else:
      color[i]=color[x]
    dfs(i)
dfs(0)
for i in range(n):
  print(color[i])

Solution (Python):
from collections import defaultdict, deque

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
que = deque([0])

while que:
    u = que.popleft()
    for v, w in edges[u]:
        if colors[v] != None:
            continue
        if edges[v] != []:
            que.append(v)

        if w % 2 == 0:
            colors[v] = colors[u]
        else:
            colors[v] = 1 ^ colors[u]

for c in colors:
    print(c)

Solution (Python):
n=int(input())
cost = [[] for _ in range(n)]
for _ in range(n-1):
    a, b, c = (int(x) for x in input().split())
    cost[a-1].append([b-1, c])
    cost[b-1].append([a-1, c])

dp = [0]*n

move = [0]
check = [-1]*n
check[0] = 0

while len(move):
    v = move.pop(0)
    for i, j in cost[v]:
        if check[i] == -1:
            dp[i] = dp[v] + j
            check[i] = 1
            move.append(i)
for i in dp:
    print(i%2)

Solution (Python):
import heapq as h

N=int(input())
u=[0 for i in range(0,N-1)]
v=[0 for i in range(0,N-1)]
w=[0 for i in range(0,N-1)]
for i in range(0,N-1):
    u[i],v[i],w[i]=map(int,input().split())
w=[w[i]%2 for i in range(0,N-1)]
hen=[[] for i in range(0,N+1)]
for i in range(0,N-1):
    hen[u[i]].append([v[i],w[i]])
    hen[v[i]].append([u[i],w[i]])
ans=[[0,0] for i in range(0,N+1)]
ans[1]=[0,1]
q=[]
q.append(1)
h.heapify(q)
sub=[]
h.heapify(sub)
while q!=[]:
    while q!=[]:
        x=h.heappop(q)
        if ans[x][0]==0:
            for p in hen[x]:
                s=p[0]
                t=p[1]
                if ans[s][1]==0:
                    if p[1]==0:
                        ans[s][0]=0
                    else:
                        ans[s][0]=1
                    h.heappush(sub,s)
                    ans[s][1]=1
        else:
            for p in  hen[x]:
                s=p[0]
                t=p[1]
                if ans[s][1]==0:
                    if p[1]==0:
                        ans[s][0]=1
                    else:
                        ans[s][0]=0
                    h.heappush(sub,s)
                    ans[s][1]=1
        if q==[]:
            q=sub
            sub=[]
            h.heapify(sub)
            break
ans[0]=100
ans.remove(100)
for i in range(0,N):
    print(ans[i][0])

Solution (Python):
from collections import defaultdict
from queue import deque
N = int(input())
colors = [None]*N
edges = defaultdict(list)
for i 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[0] = 0
q = deque([0])
while q:
    u = q.popleft()
    for v,w in edges[u]:
        if colors[v] != None:
            continue
        if edges[v] != []:
            q.append(v)
        if w % 2 == 0:
            colors[v] = colors[u]
        else:
            colors[v] = 1 ^ colors[u]
for c in colors:
    print(c)

Solution (Python):
import sys
def input():
    return sys.stdin.readline()[:-1]
sys.setrecursionlimit(200000)
N=int(input())
s=[[]for i in range(N)]
c=[None]*N
for i in range(N-1):
    u,v,w=map(int,input().split())
    s[v-1].append((u,w%2))
    s[u-1].append((v,w%2))
def mu(n,l,co):
    for i in l:
        if c[i[0]-1]==None:
            if co==i[1]%2:
                c[i[0]-1]=0
                mu(i,s[i[0]-1],0)
            else:
                c[i[0]-1]=1
                mu(i,s[i[0]-1],1)
mu(1,s[0],0)
print(*c,sep="\n")

Solution (Python):
import sys
def input():
    return sys.stdin.readline()[:-1]
sys.setrecursionlimit(200000)
N=int(input())
s=[[]for i in range(N)]
c=[None]*N
for i in range(N-1):
    u,v,w=map(int,input().split())
    s[v-1].append((u,w%2))
    s[u-1].append((v,w%2))
def mu(n,l,co):
    for i in l:
        if c[i[0]-1]==None:
            if co==i[1]%2:
                c[i[0]-1]=0
                mu(i,s[i[0]-1],0)
            else:
                c[i[0]-1]=1
                mu(i,s[i[0]-1],1)
mu(1,s[0],0)
print(*c,sep="\n")

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



q = []
q.append([0,0])
used[0] = 0

while q:
    
    e,c = q.pop()
    for i,d in M[e]:
        if used[i]==-1:
            C = (c+d)%2
            used[i] = C
            q.append([i,C])  
for i in used[:-1]:
    print(i)

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

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



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

while q:
    
    e = q.pop()
    for i,d in M[e]:
        if used[i]==-1:
            C = (used[e]+d)%2
            used[i] = C
            q.append(i)  
for i in used[:-1]:
    print(i)

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

d = defaultdict(list)
cost = defaultdict(int)
N = int(input())

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

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

def dfs(x):
    visited[x]=True
    for y in d[x]:
        if visited[y]:continue
        c = cost[(x, y) if x<y else (y, x)]
        color[y] = color[x]^1 if c%2 else color[x]  
        dfs(y)

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

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

d = defaultdict(list)
cost = defaultdict(int)
N = int(input())

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

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

def dfs(x):
    visited[x]=True
    for y in d[x]:
        if visited[y]:continue
        c = cost[(x, y) if x<y else (y, x)]
        color[y] = color[x]^1 if c%2 else color[x]  
        dfs(y)

dfs(1)
for i in color[1:]:
    print(i)

Solution (Python):
from collections import defaultdict
import sys

sys.setrecursionlimit(1000000)

d = defaultdict(list)
cost = defaultdict(int)
N = int(input())

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

visited = [False]*(N+1)
color = [-1]*(N+1)

def dfs(x):
    visited[x]=True
    if color[x]==-1:
        color[x] = 0

    for y in d[x]:
        if visited[y]:
            continue
        
        c = cost[(x, y) if x<y else (y, x)]
        if c%2==0:
            color[y] = 0 if color[x]==0 else 1
        else:
            color[y] = 1 if color[x]==0 else 0
        dfs(y)

dfs(1)
for i in color[1:]:
    print(i)

Solution (Python):
from collections import deque

n = int(input())
edges = [{} for i in range(n+1)]

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

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

d = deque()
d.append(1)
colors[1] = 0

while(len(d) > 0):
    now = d.pop()
    for key,val in edges[now].items():
        if(colors[key] == -1):
            colors[key] = (val + colors[now])%2
            d.append(key)

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

Solution (Python):
n = int(input())
l=[]
for i in range(n-1):
    tmp = list(map(int,input().split()))
    l.append(tmp)
l.sort()

link = [[] for _ in range(n)]

for tmp in l:
    link[tmp[0]-1].append([tmp[1]-1,tmp[2]])
    link[tmp[1]-1].append([tmp[0]-1,tmp[2]])

from collections import deque
Q = deque()
Q.append(0)

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

while Q:
    num=Q.popleft()
    for tmp in link[num]:
        if dis[tmp[0]] == -1:
            dis[tmp[0]] = dis[num]+tmp[1]
            Q.append(tmp[0])

for a in dis:
    print(a%2)

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


class Tree:
    WHITE = 0
    GRAY = 1
    BLACK = 2

    def __init__(self, adj):
        n = len(adj)
        self.adj = adj
        self.colors = [self.WHITE] * n
        self.depths = [-1] * n
        self.depth = 0

    def dfs(self, u):
        if self.colors[u] == self.BLACK:
            return

        self.colors[u] = self.GRAY
        self.depths[u] = self.depth

        for v, w in self.adj[u]:
            if self.colors[v] == self.WHITE:
                self.depth += w
                self.dfs(v)
                self.depth -= w

        self.colors[u] = self.BLACK


if __name__ == "__main__":
    n = int(input())
    uvw = [list(map(int, input().split())) for _ in range(n - 1)]

    g = [[] for _ in range(n)]

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

    tree = Tree(g)
    tree.dfs(0)
    ans = [x % 2 for x in tree.depths]
    print(*ans, sep="\n")

Solution (Python):
N = int(input())
 
link = [[] for _ in range(N)]
for _ in range(N - 1):
    u, v, w = map(int, input().split())
    link[u - 1].append((v - 1, w))
    link[v - 1].append((u - 1, w))
 
d = [-1] * N
d[0] = 0
q = [0]
while q:
  i = q.pop(0)
  for n, w in link[i]:
    if d[n] == -1:
      d[n] = d[i] + w
      q.append(n)
 
for i in d:
  print(i % 2)

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

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

q = deque([1])
visited = {1}
while len(q) > 0:
    now = q.popleft()
    visited.add(now)
    for v, w in tree[now]:
        if v in visited:
            pass
        else:
            q.append(v)
            if w % 2 == 0:
                color1[v] = color1[now]
                color2[v] = color2[now]
            else:
                color1[v] = int(not color1[now])
                color2[v] = int(not color2[now])

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

Solution (Python):
from collections import deque

N = int(input())

u = [None] * (N - 1)
v = [None] * (N - 1)
w = [None] * (N - 1)
for i in range(N - 1):
    uvw = input().split()
    u[i], v[i], w[i] = int(uvw[0]) - 1, int(uvw[1]) - 1, int(uvw[2])



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

for i in range(N - 1):
    AL[u[i]].append((v[i], w[i] % 2))
    AL[v[i]].append((u[i], w[i] % 2))

color = [0] + [-1] * (N - 1) 
visited = [False] * N      
que = deque()   
que.append(0) 

while(len(que) > 0):
    current = que.popleft()
    visited[current] = True
    for next, dist in AL[current]:
        if not visited[next]:
            que.append(next)
            color[next] = (color[current] + dist) % 2

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

Solution (Python):
from collections import deque

N = int(input())

u = [None] * (N - 1)
v = [None] * (N - 1)
w = [None] * (N - 1)
for i in range(N - 1):
    uvw = input().split()
    u[i], v[i], w[i] = int(uvw[0]) - 1, int(uvw[1]) - 1, int(uvw[2])



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

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

color = [0] + [-1] * (N - 1) 
visited = [False] * N      
que = deque()   
que.append(0) 

while(len(que) > 0):
    current = que.popleft()
    visited[current] = True
    for next, dist in AL[current]:
        if not visited[next]:
            que.append(next)
            if dist % 2 == 0:  
                color[next] = color[current]
            else:
                color[next] = 1 - color[current]

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

Solution (Python):

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



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


def dfs(edge, s):
    for v in edge[s]:
        if depth[v[0]] == -1:  
            depth[v[0]] = depth[s] + v[1]
            dfs(edge, v[0])


dfs(edge, 0)
for d in depth:
    if d % 2 == 0:
        print(0)
    else:
        print(1)

Solution (Python):
from collections import deque
N = int(input())
graph = [[] * N for _ in range(N)]

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

dist = [-1 for _ in range(N)]
que = deque()
dist[0] = 0
que.append(0)

while que:
    v = que[0]
    que.popleft()
    for i in range(len(graph[v])):
        nv = graph[v][i][0]
        d = graph[v][i][1]
        if dist[nv] != -1:
            continue
        dist[nv] = dist[v] + d
        que.append(nv)

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

Solution (Python):
import sys
sys.setrecursionlimit(10**6)
def main():
    N = int(input())
    V = [[] for _ in range(N)]
    for _ in range(N - 1):
        u, v, w = list(map(int, input().split()))
        V[u - 1].append((v - 1, w))
        V[v - 1].append((u - 1, w))

    R = [0] * N
    def color(n, c, f):
        R[n] = c
        for u, w in V[n]:
            if u == f:
                continue
            color(u, (c + w) & 1, n)
    color(0, 0, 0)
    print("\n".join(str(i) for i in R))

main()

Solution (Python):
n = int(input())
adj = [[] for _ in range(n)]
for _ in range(n-1):
  u, v, w = map(int, input().split())
  adj[u-1].append((w, v-1))
  adj[v-1].append((w, u-1))
paint = [None] * n
paint[0] = 0
stack = [0]
while stack:
  u = stack.pop()
  for w, v in adj[u]:
    if paint[v] is None:
      stack.append(v)
      paint[v] = (paint[u] + w) % 2
for p in paint:
  print(p)

Solution (Python):
def main():
    ii = lambda : int(input())
    mi = lambda : map(int,input().split())
    li = lambda : list(map(int,input().split()))
    n = ii()
    v = [[] for _ in range(n)]
    for i in range(n-1):
        u,vv,w = mi()
        v[u-1].append([vv -1,w % 2])
        v[vv-1].append([u -1,w % 2])
    flag = [0] * n
    flag[0] = 1
    ans = [-1] * n
    from collections import deque
    q = deque()
    q.append((0,0))
    ans[0] = 0
    while q:
        ima,ima_col = q.popleft()
        for lis in v[ima]:
            if flag[lis[0]] :continue
            flag[lis[0]] = 1
            if lis[1]:
                ans[lis[0]] = lis[1] - ima_col
                q.append((lis[0],lis[1] - ima_col))
            else:
                ans[lis[0]] = ima_col
                q.append((lis[0],ima_col))
    for i in range(n):
        print(ans[i])
main()