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 defaultdict


class Solution:
    def main(self):
        N = int(input())
        self.hashmap = defaultdict(set)
        for i in range(N-1):
            u, v, w = map(int, input().split())
            self.hashmap[u-1].add((v-1, w))
            self.hashmap[v-1].add((u-1, w))
        
        self.colors = [None] * N
        for i in range(N):
            stack = [(i, 0)]
            while stack:
                idx, color = stack.pop()
                if self.colors[idx] == None:
                    self.colors[idx] = color
                    for node, weight in self.hashmap[idx]:
                        if weight % 2 == 0:
                            stack.append((node, color))
                        else:
                            stack.append((node, 1 ^ color))
        for i in range(N):
            print(self.colors[i])

    def dfs(self, i, color):
        if self.colors[i] is None:
            self.colors[i] = color
            for node, weight in self.hashmap[i]:
                if weight % 2 == 0:
                    self.dfs(node, color)
                else:
                    self.dfs(node, 1 ^ color)


if __name__ == '__main__':
    Solution().main()

Solution (Python):

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

res = [-1]*n
res[0] = 0
q = [0]
while len(q)>0:
    u = q.pop(0)
    if len(edge[u])==0:
        continue

    for v,w in edge[u]:
        if res[v]!=-1:
            continue
        if w%2==0:
            res[v] = res[u]
        else:
            res[v] = (res[u]+1)%2
        q.append(v)

for r in res:
    print(r)

Solution (Python):
from collections import deque

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

visited = [False]*N
q = deque([0])
dist = [0]*N
while q:
    cur = q.popleft()
    if visited[cur]:
        continue
    visited[cur] = True
    for nex, w in adj[cur]:
        if (not visited[nex]):
            q.append(nex)
            dist[nex] = dist[cur] + w

for d in dist:
    print(d%2)

Solution (Python):

import collections


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

connected = collections.defaultdict(list)
for (a, b, _) in triples:
    connected[a].append(b)
    connected[b].append(a)

dist = dict()
for (u, v, d) in triples:
    dist[u, v] = d
    dist[v, u] = d

ini, _, _ = triples[0]
stack = [ini]
color = dict()
color[ini] = False

while stack:
    state = stack.pop()
    for new_state in connected[state]:
        if new_state not in color:
            d = dist[state, new_state]
            color[new_state] = color[state] if d % 2 == 0 else (not color[state])
            stack.append(new_state)


for i in sorted(color):
    print(int(color[i]))

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

B = [[] for i in range(n+1)]

for i in range(len(A)):
    B[A[i][0]].append([A[i][1],A[i][2]])
    B[A[i][1]].append([A[i][0],A[i][2]])

root = 0
for i in range(len(B)):
    root = max(root, len(B[i]))

ANS = [-1 for i in range(n+1)]
ANS[root]=0

nurulist = [root]
t = 0
while t < len(nurulist):
    k = nurulist[t]
    col = ANS[k]
    for j in range(len(B[k])):
        if ANS[B[k][j][0]] == -1:
            ANS[B[k][j][0]] = (col + B[k][j][1])%2
            nurulist.append(B[k][j][0])
    t += 1




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

Solution (Python):


N = int(input())

 

l = [[] for i in range(N+1)]

def tuika(l,a,b):
    l[a].append(b)
    l[b].append(a)

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


colors = [0 for i in range(N+1)]

stack = [1]
colors[1] = 1
while stack:
    node = stack.pop()
    for next_node in guusuu[node]:
        if colors[next_node]==0:
            stack.append(next_node)
            colors[next_node] = colors[node]
            
    for next_node in kisuu[node]:
        if colors[next_node]==0:
            stack.append(next_node)
            colors[next_node] = - colors[node]
            
            







colors_modify = [1 if x ==1 else 0 for x in colors[1:] ]

for c in colors_modify:
    print(c)

Solution (Python):
import heapq

def dijkstra(v,s,path):
    inf = float('inf')

    
    d = [inf for i in range(v)]
    d[s] = 0

    
    q = [[0,s]]
    heapq.heapify(q)

    
    
    while q:
        p = heapq.heappop(q)

        
        if d[p[1]]<p[0]:
            continue

        
        for i in range(len(path[p[1]])):
            
            if d[path[p[1]][i][1]] > d[p[1]] + path[p[1]][i][0]:
                d[path[p[1]][i][1]] = d[p[1]]+path[p[1]][i][0]
                heapq.heappush(q,[d[path[p[1]][i][1]], path[p[1]][i][1]])
    return d


n = int(input())

a = [[] for i in range(n)]

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

d = dijkstra(n,0,a)

for i in range(n):
    print(d[i]%2)

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

mp={}
for _ in range(N-1):
    i,j,w=map(int,input().split())
    if not i in mp:
        mp[i] = []
    if not j in mp:
        mp[j] = []
    mp[i].append((j,w))
    mp[j].append((i,w))


res = [-1 for _ in range(N+1)]
que = deque([])

que.append((1,0))
res[1]=0
while que:
    i, dist = que.popleft()
    for j, dist2 in mp[i]:
        if res[j] == -1:
            bw = (dist + dist2) % 2
            res[j] = bw
            que.append((j,bw))

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

Solution (Python):
from collections import deque
from heapq import heappush,heappop
import re

def int_raw():
    return int(input())

def ss_raw():
    return input().split()

def ints_raw():
    return list(map(int, ss_raw()))

INF = 1<<29
N  = int_raw()
tree = [[] for _ in range(N)]
for _ in range(N-1):
    a,b,w = ints_raw()
    a = a-1
    b = b-1
    tree[a].append((b,w))
    tree[b].append((a,w))

def main():
    colors = [-1]*N
    colors[0]=1
    qu = deque()
    qu.append((0,0,-1))
    while len(qu)!=0:
        cur = qu.popleft()
        if cur[0]%2 == 0:
            colors[cur[1]]=0
        else:
            colors[cur[1]]=1
        for e in tree[cur[1]]:
            if e[0] ==cur[2]:
                continue
            qu.append([cur[0]+e[1],e[0],cur[1]])
    for c in colors:
        print (c)      
            
main()

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

N=int(input())

n=[[]for i in range(N+1)]

for i in range(N-1):
    u,v,w=map(int,input().split())
    n[u].append([v,w])
    n[v].append([u,w])
L=[-1 for i in range(N+1)]
L[1]=0
def dfs(x):
    for i in n[x]:
        if L[i[0]]==-1:
            L[i[0]]=L[x]+i[1]
            dfs(i[0])
dfs(1)


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

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

check_edge = [True for i in range(n)]
stack = []
stack.append(0)
check_edge[0] = False
ans = [0]*n
while stack:
    v = stack.pop()
    for j in ls[v]:
        u,w = j[0],j[1]
        if not check_edge[u]:continue
        if w % 2 == 0:
            ans[u] = ans[v]
        else:
            ans[u] = not ans[v]
        check_edge[u] = False
        stack.append(u)
for i in range(n):
    if ans[i] == True:
        print(1)
    else:
        print(0)

Solution (Python):

import itertools
from collections import Counter
from collections import defaultdict
import bisect

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

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

    que = [1]
    ans[1] = 0  

    while que:
        cursor = que.pop(0)
        for next, weight in vec[cursor]:
            if ans[next] == -1:
                if weight % 2 == 0:
                    ans[next] = ans[cursor]
                else:
                    ans[next] = 1 if ans[cursor] == 0 else 0
                que.append(next)
    for i in ans[1:]:
        print(i)


if __name__ == '__main__':
    main()

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

N = int(input())

v_to = [[] for i in range(N + 1)]
v_color = [-1 for i in range(N + 1)]

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

def unko(i, par):
  for to, w in v_to[i]:
    if to == par:
      continue
    if w % 2 == 1:
      v_color[to] = 1 - v_color[i]
    else:
      v_color[to] = v_color[i]
    unko(to, i)


v_color[1] = 0
unko(1, 1)

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

Solution (Python):
import sys
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()
from collections import defaultdict

def main():
    N = II()
    edges = [[] for _ in range(N)]
    for _ in range(N-1):
        u, v, w = LI()
        u, v = u - 1, v - 1
        w = w % 2
        edges[u].append([v, w])
        edges[v].append([u, w])
    ans = [-1] * N
    ans[0] = 0
    def solve(k):
        for e, w in edges[k]:
            if ans[e] == -1:
                ans[e] = ans[k] if w == 0 else 1 - ans[k]
                solve(e)
    solve(0)
    for a in ans:
        print(a)
    return

main()

Solution (Python):
from collections import deque
def sol():
    n=int(input())
    d=[-1]*n
    l=deque([])
    for i in range(n-1):
        u,v,w=map(int,input().split())
        u,v=min(u,v),max(u,v)
        l.append((u-1,v-1,w))
    f=0
    while len(l):
        x=l.popleft()
        if f:
            if x[2]%2 and d[x[0]]==0:
                d[x[1]]=1
            elif x[2]%2 and d[x[0]]==1:
                d[x[1]]=0
            elif x[2]%2==0 and d[x[0]]==1:
                d[x[1]]=1
            elif x[2]%2==0 and d[x[0]]==0:
                d[x[1]]=0
            elif x[2]%2 and d[x[1]]==0:
                d[x[0]]=1
            elif x[2]%2 and d[x[1]]==1:
                d[x[0]]=0
            elif x[2]%2==0 and d[x[1]]==1:
                d[x[0]]=1
            elif x[2]%2==0 and d[x[1]]==0:
                d[x[0]]=0
            else:
                l.append(x)
        else:
            f=1
            if x[2]%2:
                d[x[0]]=0
                d[x[1]]=1
            else:
                d[x[0]]=0
                d[x[1]]=0
    for i in d:
        print(i)

if __name__=="__main__":
    sol()

Solution (Python):


import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

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

ans=[-1]*N
def rec(cur, color):
    if ans[cur]!=-1:
        return
    ans[cur]=color
    for node in nodes[cur]:
        nxt,w=node
        if w%2==0:
            rec(nxt, color)
        else:
            rec(nxt, 1-color)
    return

rec(0, 0)

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

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

E = [[] for _ in range(N)]
Color = [None] * N

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


for i in range(N):
	if Color[i] is not None:
		continue
	stack = [(i, 0)]
	
	while stack:
		u, color = stack.pop()
		Color[u] = color
		for v, w in E[u]:
			if Color[v] is not None:
				continue
			stack.append((v, color if w == 0 else 1 - color))

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

Solution (Python):

def main():
    buf = input()
    N = int(buf)
    edge = dict()
    for i in range(N):
        edge[i] = [] 
    for i in range(N-1):
        buf = input()
        buflist = list(buf.split())
        u = int(buflist[0])-1 
        v = int(buflist[1])-1 
        w = int(buflist[2])
        edge[u].append((w, v))
        edge[v].append((w, u))
    vertex_color = []
    for i in range(N):
        vertex_color.append(None)
    stack = [(0, 0)] 
    while stack:
        current = stack.pop()
        if current[0] % 2 == 0:
            vertex_color[current[1]] = 1
        else:
            vertex_color[current[1]] = 0
        for e in edge[current[1]]:
            if vertex_color[e[1]] == None:
                stack.append((current[0]+e[0], e[1]))
    for x in vertex_color:
        print(x)

if __name__ == '__main__':
    main()

Solution (Python):
n = int(input())
links = {u: {} for u in range(1, n + 1)}
for i in range(n - 1):
	x, y, z = map(int, input().split())
	links[x][y] = z
	links[y][x] = z
vis = [0] * (n + 1)
col = [0] * (n + 1)

now = 0
q = [(1, 0)]
while now < len(q):
	u = q[now][0]
	c = q[now][1]
	now += 1
	vis[u] = 1
	col[u] = c
	for v, l in links[u].items():
		if vis[v] == 0:
			if l & 1:
				q.append((v, c ^ 1))
			else:
				q.append((v, c))

for u in range(1, n + 1):
	print(col[u])

Solution (Python):
from sys import stdin
input = stdin.readline
n=int(input())
b=[]
for i in range(n-1):b.append(list(map(int,input().split())))
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
a=BFS(0,b,n)
for i in a:print(0 if i%2==0 else 1)

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

N = int(input())

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


for _ in range(N-1):
  v1,v2,w = [int(x) for x in input().split()]
  if w&1:
    edge[v1].append((v2,-1))
    edge[v2].append((v1,-1))
  else:
    edge[v1].append((v2,1))
    edge[v2].append((v1,1))

color = [None] * (N+1)

def set_color(v,c):
  color[v] = c
  for x,sgn in edge[v]:
    if color[x] is None:
      set_color(x,sgn*c)
      
set_color(1,1)

for x in color[1:]:
  print((x+1)//2)

Solution (Python):
import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline

n = int(input())

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

memo = [-1] * n

def dfs(v, memo, color):
    memo[v] = color
    for (nv, dist) in graph[v]:
        if memo[nv] != -1:
            continue
        if dist == 0:
            dfs(nv, memo, color)
        else:
            dfs(nv, memo, (color + 1)%2)

dfs(0, memo, 0)

for i in memo:
    print(i)

Solution (Python):
N=int(input())
S=[]
ans=[-1 for x in range(N+1)]
con=[[] for x in range(N+1)]
for i in range(N-1):
    u,v,w=[int(x) for x in input().split()]
    con[u].append([v,w])
    con[v].append([u,w])
K=[]
ans[1]=0
focus=[[1,0]]
M=1
while(M<N):
    newfocus=[]
    for f in focus:
        s=f[0]
        c=f[1]
        for A in con[s]:
            d,w=A
            if ans[d]==-1:
                nc =c
                if w%2:
                    nc=not(c)
                ans[d]=nc
                newfocus.append([d,nc])
                M+=1
        focus=newfocus[:]
for i in range(1,N+1):
    print(int(ans[i]))

Solution (Python):
n=int(input())
l=[list(map(int,input().split())) for i in range(n-1)]
r=[[] for i in range(n+1)]
ans=[-1 for i in range(n+1)]
for i in l:
  u,v,w=i
  r[u].append((v,w))
  r[v].append((u,w))
q=[1]
ans[1]=0
while(len(q)>0):
  t=q.pop()
  for i in r[t]:
    V,W=i
    if(ans[V]!=-1):
      continue
    q.append(V)
    c=ans[t]
    if(W%2==0):
      ans[V]=c
    else:
      ans[V]=c^1
for i in ans[1:]:
  print(i)

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

Solution (Python):
n = int(input())
graph = dict()
for i in range(1,n+1):
    graph[i] = []

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

arrival = [-1 for i in range(n+1)]
q = [1]
r = []
while not(len(q) == 0 and len(r) == 0): 
    while len(q) != 0:
        arrival[q[0]] = 0
        for i in range(len(graph[q[0]])):
            if arrival[graph[q[0]][i][0]] == -1 and graph[q[0]][i][1] % 2 == 0:
                arrival[graph[q[0]][i][0]] = 0
                q.append(graph[q[0]][i][0])
            elif arrival[graph[q[0]][i][0]] == -1 and graph[q[0]][i][1] % 2 == 1:
                r.append(graph[q[0]][i][0])
        q.pop(0)

    while len(r) != 0:
        arrival[r[0]] = 1
        for i in range(len(graph[r[0]])):
            if arrival[graph[r[0]][i][0]] == -1 and graph[r[0]][i][1] % 2 == 0:
                arrival[graph[r[0]][i][0]] = 1
                r.append(graph[r[0]][i][0])
            elif arrival[graph[r[0]][i][0]] == -1 and graph[r[0]][i][1] % 2 == 1:
                q.append(graph[r[0]][i][0])
        r.pop(0)


for i in range(1,n+1):
    if arrival[i] != 0:
        print("1")
    else:
        print("0")

Solution (Python):
from collections import deque, defaultdict


def read_input():
    n = int(input())
    edges = []

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

    return n, edges



def search_graph(nodes, edges):
    edge_table = {n:[] for n in nodes}

    for e in edges:
        edge_table[e[0]].append((e[1], e[2]))
        edge_table[e[1]].append((e[0], e[2]))

    
    q = deque()
    
    q.appendleft((nodes[0], 0))

    even = []
    odd = []
    searched = defaultdict(int)

    while len(q) > 0:
        cnode, cdist = q.pop()
        searched[cnode] = 1

        if cdist % 2:
            odd.append(cnode)
        else:
            even.append(cnode)

        next_nodes = edge_table[cnode]
        for nn in next_nodes:
            if searched[nn[0]] == 0:
                q.appendleft((nn[0], cdist + nn[1]))

    return set(even), set(odd)


def submit():
    n, edges = read_input()
    nodes = [i for i in range(1, n + 1)]
    even, odd = search_graph(nodes, edges)

    for n in nodes:
        if n in even:
            print(0)
        else:
            print(1)



if __name__ == '__main__':
    submit()

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

R = {}

for u, v, w in uvw:
  U = u - 1
  V = v - 1
  if U not in R:
    R[U] = [[U, V, w]]
  else:
    R[U].append([U, V, w])
  if V not in R:
    R[V] = [[V, U, w]]
  else:
    R[V].append([V, U, w])

S = [0]
L = [-1] * N
L[0] = 0
while S != []:
  t = []
  for j in S:
    for i in R[j]: 
      if L[i[1]] == -1:
        if i[2] % 2 == 0:
          L[i[1]] = L[i[0]]
        else:
          L[i[1]] = 1 - L[i[0]]
        t.append(i[1])
  S = t

for i in L:
  print(i)

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

def main():
    input = sys.stdin.readline
    N = int(input())
    d = defaultdict(list)
    for _ in range(N-1):
        u, v, w = map(int, input().split())
        d[u-1].append((v-1, w))
        d[v-1].append((u-1, w))

    dist = [0] * N
    q = deque()
    q.append((0, 0))
    visited = set()

    while len(q) > 0:
        q_ = deque()
        while len(q) > 0:
            node1, cost1 = q.popleft()

            dist[node1] = cost1
            visited.add(node1)

            for node2, cost2 in d[node1]:
                if node2 in visited:
                    continue

                q_.append((node2, cost1 + cost2))

        q = q_

    for d in dist:
        print(d % 2)


if __name__ == '__main__':
    main()

Solution (Python):
from collections import defaultdict

n = int(input())
edges = {}
connected_nodes = defaultdict(list)

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




color = {}
color[1] = 0

visiting = [1]

while edges:
  node = visiting.pop()
  
  
  for nn in connected_nodes[node]:
    edge = (node, nn) if node < nn else (nn, node)
    if edge in edges:
      w = edges[edge]
      del edges[edge]
      visiting.append(nn)
      if w % 2 == 0:
        color[nn] = color[node]
      else:
        color[nn] = 1 - color[node]

for node in sorted(color.keys()):
  print(color[node])

Solution (Python):
n=int(input())
path=[[] for i in range(n)]
for i in range(n-1):
    a,b,c=map(int, input().split())
    path[a-1].append([b-1,c%2])
    path[b-1].append([a-1,c%2])
ans=[-1]*n
ans[0]=0
q=[0]
while q:
    nq=[]
    for k in q:
        for i,j in path[k]:
            if ans[i]==-1:
                ans[i]=(ans[k]+j)%2
                nq.append(i)
    q=nq[:]
for i in ans:print(str(i))

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

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


visited = [False] * N
visited[0] = True


def dfs(n):
    visited = [False] * N
    stack = [[n, 0]]
    longest = [-1, -1]

    while stack:
        node, weight = stack.pop()
        if visited[node]:
            continue
        visited[node] = True
        if longest[1] < weight:
            longest = [node, weight]

        for n, w in T[node]:
            if not visited[n]:
                stack.append([n, w + weight])

    return longest


start, xw = dfs(0)


color = [None] * N


def dfs(n):
    for to, weight in T[n]:
        if color[to] is None:
            if weight % 2 == 0:
                color[to] = color[n]
                dfs(to)
            else:
                color[to] = color[n] ^ 1
                dfs(to)


color[start] = 0
dfs(start)
print(*color, sep='\n')

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

visited = set([0])
Col = [-1]*N
Col[0] = 1
stack = [0]
while stack:
    vn = stack.pop()
    for vf, wf in Edge[vn]:
        if vf in visited:
            continue
        if wf % 2 == 0:
            c = Col[vn]
        else:
            c = 1 - Col[vn]
        visited.add(vf)
        Col[vf] = c
        stack.append(vf)
for c in Col:
    print(c)

Solution (Python):
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time
sys.setrecursionlimit(10**7)
inf = 10**20

N = int(input())
edges = [[] for _ in range(N)]
for _ in range(N-1):
    u,v,w = map(int,input().split())
    w = w%2
    edges[u-1].append((v-1,w));
    edges[v-1].append((u-1,w));
from collections import deque
queue = deque()
ans = [-1 for _ in range(N)]
queue.append(0)
ans[0] = 1
while len(queue) > 0:
    v = queue.popleft()
    for w,d in edges[v]:
        if ans[w] != -1:
            continue
        
        ans[w] = (ans[v] + d) % 2
        
        queue.append(w)
for i in range(N):
    print(ans[i])

Solution (Python):
from collections import deque

N=int(input())

node_list = [[] for i in range(N)]

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

Q=deque([0])

color_list[0] = 0

while len(Q)>0:
    v1 = Q.pop()
    current_color=color_list[v1]
    for v2 in node_list[v1]:
        if color_list[v2[0]]==-1:
            if v2[1]==0:
                color_list[v2[0]]=current_color
            else:
                color_list[v2[0]]=1-current_color
            Q.appendleft(v2[0])

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

Solution (Python):
N = int(input())
E = [[] for x in range(N)]
D = [0]*N
L = [0]*N
for i in range(N-1):
    u,v,w = map(int,input().split(" "))
    u -= 1
    v -= 1
    E[u].append([v,w])
    E[v].append([u,w])

q = [[-1,0,0]]
while len(q):
    root,to,dis = q.pop()
    L[to] = 1
    if root != -1:
        D[to] = D[root] + dis
    for t,d in E[to]:
        if L[t]:
            continue
        q.append([to,t,d])

for d in D:
    print(d%2)

Solution (Python):
import heapq
import sys


class UnionFind:
    """
    sizeによる実装
    """

    def __init__(self, N):
        self.parent = [i for i in range(N)]
        self.size = [1 for _ in range(N)]

    def find(self, x):
        if self.parent[x] == x:
            return x
        else:
            return self.find(self.parent[x])

    def union(self, x, y):
        px = self.find(x)
        py = self.find(y)
        if px == py:
            return
        if self.size[px] < self.size[py]:
            self.parent[px] = py
            self.size[py] += self.size[px]
        else:
            self.parent[py] = px
            self.size[px] += self.size[py]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def connectedNum(self, x):
        return self.size[self.find[x]]



sys.setrecursionlimit(10**9)
input = sys.stdin.readline

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

dist = [0]*N


Un = UnionFind(N)
Q = [0]
while Q:
    current = Q.pop()
    for nex, wei in adj[current]:
        if Un.same(nex, current):
            continue
        else:
            Un.union(nex, current)
            dist[nex] = dist[current]+wei
            Q.append(nex)

dist = list(map(lambda x: x % 2, dist))
print("\n".join(map(str, dist)))

Solution (Python):
import sys
sys.setrecursionlimit(10 ** 5)
n = int(input())
color = [-1] * n
neighbor = [[] for _ in range(n)]
for _ in range(n - 1):
    u, v, w = tuple(map(int, input().split()))
    neighbor[u - 1].append((v-1, w))
    neighbor[v - 1].append((u-1, w))
def col(u, c):
    color[u] = c
    for v, w in neighbor[u]:
        if color[v] < 0:
            col(v, (c + w) % 2)
col(0, 0)
for i in range(n):
    print(color[i])

Solution (Python):
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))

from collections import deque

n = getN()
paths = [[] for i in range(n)]
for i in range(n-1):
    a,b,c = getList()
    paths[a-1].append((b-1,c))
    paths[b-1].append((a-1,c))

def findroot(tree):
    for i, v in enumerate(tree):
        if len(v) == 1:
            return i

root = findroot(paths)


def getdist(tree, root):
    d = deque([root])
    dist = [-1 for i in range(len(tree))]
    dist[root] = 0
    while(d):
        
        nxt = d.pop()
        tmp = dist[nxt]
        for edge in tree[nxt]:
            v, c = edge
            if dist[v] == -1:
                d.append(v)
                dist[v] = tmp + c

    return dist

distlist = getdist(paths, root)
for i in distlist:
    print(i % 2)

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

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

def dfs(vNow):
    useds[vNow] = True
    ans = anss[vNow]
    for v2, wt in adjL[vNow]:
        if useds[v2]: continue
        if wt % 2:  
            anss[v2] = 1-ans
        else:
            anss[v2] = ans
        dfs(v2)

useds = [False] * N
anss = [0] * N
anss[0] = 0
dfs(0)

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

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 9)


class UnionFind:
    def __init__(self, n):
        self.v = [-1 for _ in range(n)]  

    def find(self, x):  
        if self.v[x] < 0:  
            return x
        else:  
            self.v[x] = self.find(self.v[x])  
            return self.v[x]

    def unite(self, x, y):  
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if -self.v[x] < -self.v[y]:  
            x, y = y, x  
        self.v[x] += self.v[y]  
        self.v[y] = x  

    def root(self, x):
        return self.v[x] < 0  

    def same(self, x, y):
        return self.find(x) == self.find(y)  

    def size(self, x):
        return -self.v[self.find(x)]  


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

    uf.same(u, v)



root = uf.find(0)


ans = [None] * N
ans[root] = 0




def rec(vv):
    for nv, w in e[vv]:
        if ans[nv] is not None: continue
        ans[nv] = (ans[vv] + w) % 2
        rec(nv)


rec(root)

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