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 sys import stdin
from collections import defaultdict,deque

N = int(stdin.readline().rstrip())
adj = defaultdict(set)

for i in range(N-1):
    u,v,w = [int(x) for x in stdin.readline().rstrip().split()]
    adj[u].add((v,w))
    adj[v].add((u,w))


ans = [0]*(N+1)
visit_p = deque()
visit_p.append((1,0))
visited = [False]*(N+1)
visited[1] = True


while visit_p:
    now_v,now_w = visit_p.popleft()
    for v,w in adj[now_v]:
        if visited[v]:
            continue
        ans[v] = w + now_w
        visited[v] = True
        visit_p.append((v,w+now_w))
for i in ans[1:]:
    if i % 2 == 0:
        print(0)
    else:
        print(1)

Solution (Python):
import sys
sys.setrecursionlimit(100000000)
N = int(input())
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]]

color = [-1]*N 
def dfs(v, c):
  color[v] = c
  for next_v, w in graph[v]:
    if color[next_v] == c and w % 2 != 0:
      return 
    if color[next_v] == -1 and w % 2 == 0 and dfs(next_v, c) == False:
      return False
    if color[next_v] == -1 and w % 2 != 0 and dfs(next_v, abs(1-c)) == False:
      return False
  return True

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

Solution (Python):
import sys
sys.setrecursionlimit(10**6)
def dfs(G,v,p):
    for nv,nw in G[v]:
        if(nv==p):
            continue
        if(nw%2==0):
            color[nv]=color[v]
        else:
            color[nv]=int(not color[v])
        dfs(G,nv,v)
N=int(input())
G=[[] for i in range(N)]
color=[-1]*N
for i in range(N-1):
    u,v,w=map(int,input().split())
    u,v=u-1,v-1
    G[u].append((v,w))
    G[v].append((u,w))
color[0]=0
dfs(G,0,-1)
print(*color,sep='\n')

Solution (Python):
N = int(input())
a = [0] * N
b = [[] for _ in range(N)]
for _ in range(N-1):
    x,y,z = map(int, input().split())
    x -= 1
    y -= 1
    b[x].append((y, z))
    b[y].append((x, z))


l = [(0, -1, 0)]
while l:
    x, s, t = l.pop()
    if t % 2 == 0:
        a[x] = 0
    else:
        a[x] = 1
    for v, w in b[x]:
        if v == s:
            continue
        l.append((v, x, t + w))

for x in a:
    print(x)

Solution (Python):
import sys

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


def main():
    N = int(input())
    en = [[] for _ in range(N)]
    on = [[] for _ in range(N)]
    for i in range(N - 1):
        u, v, w = map(int, input().split())
        if w % 2:
            on[u - 1].append(v - 1)
            on[v - 1].append(u - 1)
        else:
            en[u - 1].append(v - 1)
            en[v - 1].append(u - 1)

    color = [-1] * N
    stack = [(0, -1, 0)]
    while stack:
        node, parent, col = stack.pop()
        if color[node] >= 0:
            continue
        color[node] = col
        for k in en[node]:
            if k != parent:
                stack.append((k, node, col))
        for k in on[node]:
            if k != parent:
                stack.append((k, node, (col + 1) % 2))

    print(*color, sep="\n")


if __name__ == "__main__":
    main()

Solution (Python):
import sys

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


def main():
    N = int(input())
    en = [[] for _ in range(N)]
    on = [[] for _ in range(N)]
    for i in range(N - 1):
        u, v, w = map(int, input().split())
        if w % 2:
            on[u - 1].append(v - 1)
            on[v - 1].append(u - 1)
        else:
            en[u - 1].append(v - 1)
            en[v - 1].append(u - 1)

    color = [None] * N
    stack = [(0, -1, 0)]
    while stack:
        node, parent, col = stack.pop()
        if color[node] is not None:
            continue
        color[node] = col
        for k in en[node]:
            if k != parent:
                stack.append((k, node, col))
        for k in on[node]:
            if k != parent:
                stack.append((k, node, (col + 1) % 2))

    print(*color, sep="\n")


if __name__ == "__main__":
    main()

Solution (Python):
import sys

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

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

color = [None] * N
stack = [(0, -1, 0)]
while stack:
    node, parent, col = stack.pop()
    if color[node] is not None:
        continue
    color[node] = col
    for k in en[node]:
        if k != parent:
            stack.append((k, node, col))
    for k in on[node]:
        if k != parent:
            stack.append((k, node, (col + 1) % 2))

print(*color, sep="\n")

Solution (Python):
import sys

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

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

color = [None] * N


def dfs(node, parent, col):
    if color[node] is not None:
        return
    color[node] = col
    for k in en[node]:
        if k != parent:
            dfs(k, node, col)
    for k in on[node]:
        if k != parent:
            dfs(k, node, (col + 1) % 2)


dfs(0, -1, 0)
print(*color, sep="\n")

Solution (Python):
N=int(input())
tree=[set() for _ in range(N)]
for i in range(1,N):
    u,v,w=map(int,input().split())
    u=u-1
    v=v-1
    tree[u].add((v,w))
    tree[v].add((u,w))
ans=[-1]*N
q=[(0,0,-1)]
while q:
    now, ndis, priv = q.pop()
    if ndis % 2 == 0:
        ans[now] = 0
    else:
        ans[now] = 1
    for nex, dis in tree[now]:
        if nex == priv:
            continue
        q.append((nex, ndis + dis, now))
for i in ans:
    print(i)

Solution (Python):
n = int(input())
d = [[] for i in range(n)]
for i 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])
ans = [-1]*n
ans[0]=0
q = [0]
cnt = 0

while q:
    u = q.pop()
    for v,w in d[u]:
        if ans[v]==-1:
            if w%2==0:
                ans[v]=ans[u]
            else:
                ans[v]=(ans[u]+1)%2
            q.append(v)
for i in ans:
    print(i)

Solution (Python):
from collections import deque

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


color = [-1 for i in range(N)]

q = deque([0])
color[0] = 0
flag = 1
while len(q) != 0:
    u = q.popleft()
    for v, w in G[u]:
        if color[v] != -1: 
            if w % 2 == 1 and color[v] == color[u]:
                flag = 0
            continue
        if w % 2 == 0:
            color[v] = color[u]
            q.append(v)
        else:
            color[v] = 1 - color[u]
            q.append(v)

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

Solution (Python):


from collections import deque

n = int(input())


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

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



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

q = deque()
q.append(0)

while len(q)>0:
    node = q.popleft()
    for i, j in alist[node]:
        if dlist[i]<0:
            q.append(i)
            dlist[i] = (dlist[node] + j)%2
        else:
            continue

'''
def dfs(node, par, dist):
    dlist[node] = dist%2
    for i, j in alist[node]:
        if i==par:
            continue
        else:
            dfs(i, node, dist+j)
dfs(0,0,0)
'''

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

Solution (Python):


from collections import deque

data = int(input())
g = tuple(set() for _ in range(data))
for _ in range(data - 1):
    u, v, w = map(int, input().split())
    u -= 1
    v -= 1
    g[u].add((v, w))
    g[v].add((u, w))

d = [-1] * data
d[0] = 0

q = deque()
q.append(0)

while q:
    v = q.popleft()
    for u, w in g[v]:
        if d[u] != -1:
            continue
        d[u] = (d[v] + w) % 2
        q.append(u)

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

Solution (Python):
from collections import deque
n = int(input())
g = [[] for _ in range(n)]
ln = []

for _ in range(n - 1):
    a, b, l = map(int, input().split())
    a, b = a - 1, b - 1
    g[a].append(b)
    g[b].append(a)
    ln.append((a, b, l))

q = deque([0])
par = [0] * n
order = []

while q:
    x = q.pop()
    order.append(x)
    for y in g[x]:
        if y == par[x]:
            continue
        par[y] = x
        q.append(y)

chr_l = [0] * n
for a, b, l in ln:
    if par[a] == b:
        chr_l[a] = l
    else:
        chr_l[b] = l




color = [-1] * n
color[0] = 0
org = [0, 1]

for x in order:
    for y in g[x]:
        if y == par[x]:
            continue
        if chr_l[y] % 2 == 0:
            color[y] = color[x]
        else:
            color[y] = color[x] ^ 1
print("\n".join(map(str, color)))

Solution (Python):
import sys
from io import StringIO
import unittest

sys.setrecursionlimit(100**3)

def coloring(v, p, vs, cs, color):
	cs[v] = color
	for e in vs[v]:
		if e[0] == p:
			continue
		nc = color if e[1] % 2 == 0 else 1 - color
		coloring(e[0], v, vs, cs, nc)

def resolve():
	n = int(input())
	vs = [[] for _ in range(n)]
	cs = [None]*n
	for i in range(n-1):
		u, v, w = map(int, input().split())
		vs[u-1].append([v-1, w])
		vs[v-1].append([u-1, w])
	coloring(0, None, vs, cs, 1)
	for i in cs:
		print(i)
resolve()

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

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

for _ in range(N-1):
    u,v,w=[int(x) for x in input().split()]
    if w&1:
        edge[u].append((v,-1))
        edge[v].append((u,-1))
    else:
        edge[u].append((v,1))
        edge[v].append((u,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(1000000000)
N = int(input())

color = [-1 for i in range(N)]

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

def dfs(u, c):
    color[u] = c
    for v, w in G[u]:
        if color[v] != -1:
            if color[v] == c and w % 2 != 0:
                return False
        else:
            if w % 2 == 0:
                dfs(v, c)
            else:
                dfs(v, 1-c)
    return True

if dfs(0, 0):
    for i in range(N):
        print(color[i])

Solution (Python):


import queue

def main():
    N = int(input())
    UV = [[] for _ in range(N)]

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

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

    que = queue.Queue()
    que.put(0)
    while not(que.empty()):
        mm = que.get()
        for uv in UV[mm]:
            que.put(uv[0])
            if uv[1]%2==0:
                ans[uv[0]] = ans[mm]
            else:
                ans[uv[0]] = (ans[mm]+1)%2
        UV[mm] = []

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

if __name__ == '__main__':
    main()

Solution (Python):
from collections import deque
n = int(input())
d = [0]*(n+1)
tree = [[] for _ in range(n+1)]
for i in range(n-1):
  u,v,w = map(int,input().split())
  tree[u].append([v,w])
  tree[v].append([u,w])
q = deque([1])
done = [0]*(n+1)
done[1] = 1
while q:
  now = q.popleft()
  for l in tree[now]:
    if not done[l[0]]:
      q.append(l[0])
      done[l[0]] = 1
      d[l[0]] = d[now] + l[1]
for i in range(1,n+1):
  print(d[i]%2)

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

Dist = [[] for j in range(N)]
Seen = [-1] * N

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

que = [0]
Seen[0] = 0
flag = True
while -1 in Seen:
    now = que.pop()
    for next, distance in Dist[now]:
        if Seen[next] == -1:
            que.insert(0, next)
            if distance % 2 == 0:
                Seen[next] = Seen[now]
            else:
                Seen[next] = 1 - Seen[now]
for i in range(N):
    print(Seen[i])

Solution (Python):
from collections import deque

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

dist=[-1]*(N+1)
q=deque()
color=[-1]*(N+1)

dist[1]=0
q.append(1)
color[1]=0
while q:
    now=q.popleft()
    for next in L[now]:
        if dist[next[0]]==-1:
            q.append(next[0])
            dist[next[0]]=dist[now]+next[1]
            if dist[next[0]]%2==0:
                color[next[0]]=0
            else:
                 color[next[0]]=1

for b in range(1,N+1):
    print(color[b])

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

stack = [(0, -1, 0)]
while stack:
    v, par, dist = stack.pop()
    if dist % 2 == 0:
        ans[v] = 0
    else:
        ans[v] = 1
    for child, child_dist in tree[v]:
        if child == par:
            continue
        stack.append((child, v, dist + child_dist))

for x in ans:
    print(x)

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

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

colors = [0] * N
def dfs(vNow, vPar):
    color = colors[vNow]
    for v2, wt in adjL[vNow]:
        if v2 == vPar: continue
        if wt%2:
            colors[v2] = 1-color
        else:
            colors[v2] = color
        dfs(v2, vNow)

dfs(0, -1)

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

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


N = int(input())
graph = [[] for _ in range(N)]
for _ in range(N-1):
    a, b, w = map(int, input().split())
    graph[a-1].append((b-1, w))
    graph[b-1].append((a-1, w))

def dfs(s):
    stack = [s]
    Color = [-1]*N
    Color[s] = 0
    while stack:
        p = stack.pop()
        for np, w in graph[p]:
            if Color[np] == -1:
                Color[np] = Color[p]^(w%2)
                stack.append(np)
    return Color

if __name__ == "__main__":
    Color = dfs(0)
    print(*Color, sep="\n")

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


N = int(input())
graph = [[] for _ in range(N)]
for _ in range(N-1):
    a, b, w = map(int, input().split())
    graph[a-1].append((b-1, w))
    graph[b-1].append((a-1, w))

def dfs(s):
    Ind = [0]*N
    stack = [s]
    Color = [0]*N
    while stack:
        p = stack[-1]
        if Ind[p] == len(graph[p]):
            stack.pop()
        elif len(stack) > 1 and stack[-2] == graph[p][Ind[p]][0]:
            Ind[p] += 1
        else:
            ch, w = graph[p][Ind[p]]
            Ind[p] += 1
            stack.append(ch)
            Color[ch] = Color[p]^(w%2)
    return Color

Color = dfs(0)
print(*Color, sep="\n")

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


N = int(input())
graph = [[] for _ in range(N)]
for _ in range(N-1):
    a, b, w = map(int, input().split())
    graph[a-1].append((b-1, w))
    graph[b-1].append((a-1, w))

def dfs(s):
    Ind = [0]*N
    stack = [s]
    Color = [0]*N
    while stack:
        p = stack[-1]
        if Ind[p] == len(graph[p]):
            stack.pop()
        elif len(stack) > 1 and stack[-2] == graph[p][Ind[p]][0]:
            Ind[p] += 1
        else:
            ch, w = graph[p][Ind[p]]
            Ind[p] += 1
            stack.append(ch)
            Color[ch] = Color[p]^(w%2)
    return Color

Color = dfs(0)
print(*Color, sep="\n")

Solution (Python):
from collections import deque

n = int(input())

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

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

checked = [False] * (n+1)
colors = [0] * (n+1)

d = deque([1])
while len(d) > 0:
    u = d.pop()
    checked[u] = True

    for v, w in neighbors[u]:
        if checked[v]:
            continue

        if (colors[u] == 0 and w % 2 == 1) or (colors[u] == 1 and w % 2 == 0):
            colors[v] = 1

        d.append(v)

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

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

n=int(input())
l=[-1]*n
p=[[] for _ in range(n)]
for i in range(n-1):
    ui,vi,wi=map(int,input().split())
    p[ui-1].append([vi,wi])
    p[vi-1].append([ui,wi])

def tr1(x,y):
    
    
    
    if l[x-1]!=-1:
        return
    l[x-1]=y
    for i in range(len(p[x-1])):
        tr1(p[x-1][i][0],(y+p[x-1][i][1])%2)
tr1(1,0)
for j in range(n):
    print(l[j])

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

d = defaultdict(lambda: defaultdict(int))
for i in range(N-1):
    u, v, w = list(map(int, input().split()))
    d[u-1][v-1] = w
    d[v-1][u-1] = w
for i in range(N):
    if len(d[i]) == 1:
        start = i
        break

visited = [False for _ in range(N)]
visited[start] = True
all_length =  [0 for _  in range(N)]
q = queue.Queue()
q.put(start)
while not q.empty():
    i = q.get()
    for v, w in d[i].items():
        if not visited[v]:
            q.put(v)
            visited[v] = True
            all_length[v] = all_length[i] + w
for length in all_length:
    print(length % 2)

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

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

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

w = [u_v_w[i][2] for i in range(N-1)]

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

for i in range(N-1):
    u = u_v_w[i][0]
    v = u_v_w[i][1]
    tree[u-1].append((v,w[i]))
    tree[v-1].append((u,w[i]))

ans = [0] * N
ans[0] = 1
def dfs(now):
    global ans
    for next in tree[now-1]:
        if ans[next[0]-1]:
            continue
        if next[1] % 2 == 0:
            ans[next[0]-1] = ans[now-1]
        else:
            ans[next[0]-1] = ans[now-1] * (-1)
        dfs(next[0])

dfs(1)
for i in range(len(ans)):
    if ans[i] == 1:
        print(0)
    else:
        print(1)

Solution (Python):
from collections import deque
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])
color = [-1]*n
que = deque([[0, -1, 0]])
while que:
    u, v, c = que.popleft()
    color[u] = c
    for i, j in edge[u]:
        if i == v: continue
        que.append([i, u, (c+j)%2])
print(*color, sep="\n")

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


def input():
    return sys.stdin.readline()


n = int(input())
e = [[] for _ in range(n)]
for _ in range(n - 1):
    a, b, c = [int(i) - 1 for i in input().split()]
    c += 1
    e[a].append([b, c])
    e[b].append([a, c])

c = [0] * n


def dfs(i=0, r=-1, co=0):
    c[i] = co
    for j, k in e[i]:
        if j != r:
            dfs(j, i, (co+k) % 2)


dfs()
print("\n".join(map(str, c)))

Solution (Python):
import collections, math, bisect

local = False
if local:
    file = open("input.txt", "r")
    import time

def inp():
    if local:
        return file.readline().rstrip()
    else:
        return input().rstrip()

def ints():
    return [int(_) for _ in inp().split()]


if local:
    start=time.time()

N = int(inp())

connection = [dict() for i in range(N)]

for i in range(1, N):
    u,v,w = ints()

    connection[u-1][v-1] = w
    connection[v-1][u-1] = w

colors = ["0"]*N
visited = set()

stck = [(0,0)]
visited.add(0)

while len(stck)>0:
    vertex, cur_dist = stck.pop(-1)

    if cur_dist%2==0:
        colors[vertex] = "0"
    else:
        colors[vertex] = "1"

    for nextVertex in connection[vertex]:
        if nextVertex not in visited:
            visited.add(nextVertex)
            stck.append((nextVertex, cur_dist+connection[vertex][nextVertex]))

for c in colors:
    print(c)


if local:
    fin = (time.time()-start)*1000
    print("{:.2f}".format(fin) + "ms")

Solution (Python):
import sys
sys.setrecursionlimit(500*500)
N = int(input())
edges = [list(map(int,input().split())) for _ in range(N-1)]
A = [[] for _ in range(N+1)]
 
for edge in edges:
  A[edge[0]].append([edge[1],edge[2]])
  A[edge[1]].append([edge[0],edge[2]])
  
depth = [-1] * (N+1)
depth[1] = 0
 
def dfs(A,s):
  for v in A[s]:
    if depth[v[0]] == -1:
      depth[v[0]] = depth[s] + v[1]
      dfs(A,v[0])    
dfs(A,1)
for d in depth[1:]:
  if d % 2 == 0:
    print(0)
  else:
    print(1)

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)]
color = [0] * N
color[0] = 1
graph = defaultdict(list)
for u, v, w in L:
    graph[u-1].append((v-1, w))
    graph[v-1].append((u-1, w))

q = [0]

while q:
    a = q.pop()
    for node, w in graph[a]:
        if color[node] == 0:
            if w % 2 == 0:
                color[node] = color[a]
            else:
                color[node] = -1 * color[a]
            q.append(node)
for c in color:
    print(1 if c == -1 else 0)

Solution (Python):
import sys
sys.setrecursionlimit(100**4)

class Edge():
	def __init__(self, v, w):
		self._v = v
		self._w = w
	def v(self):
		return self._v
	def w(self):
		return self._w

def dfs(v, g, colors, color = 0):
	colors[v] = color
	if not len(g[v]):
		return
	for nv in g[v]:
		if colors[nv.v()] != -1:
			continue
		nc = color if nv.w() % 2 == 0 else 1 - color
		dfs(nv.v(), g, colors, nc)

def resolve():
	n = int(input())
	colors = [-1]*n
	g = [list() for _ in range(n)]
	for _ in range(n-1):
		u, v, w = map(int, input().split())
		g[v-1].append(Edge(u-1, w))
		g[u-1].append(Edge(v-1, w))
	for i in range(n):
		if colors[i] != -1:
			continue
		dfs(i, g, colors)
	for c in colors:
		print(c)
resolve()

Solution (Python):
from collections import deque
from heapq import heapify,heappop,heappush,heappushpop
from copy import copy,deepcopy
from itertools import permutations,combinations
from collections import defaultdict,Counter
from pprint import pprint

def myinput():
    return map(int,input().split())

def mycol(data,col):
    return [ row[col] for row in data ]

def mysort(data,col):
    data.sort(key=lambda x:x[col],reverse=False)
    return data

def mymax(data):
    M = -1*float("inf")
    for i in range(len(data)):
        m = max(data[i])
        M = max(M,m)
    return M

def mymin(data):
    m = float("inf")
    for i in range(len(data)):
        M = min(data[i])
        m = min(m,M)
    return m

n = int(input())
uvw = [ list(myinput()) for _ in range(n-1) ]

g = [ [] for _ in range(n) ]
for i in range(n-1):
    u = uvw[i][0] - 1
    v = uvw[i][1] - 1
    w = uvw[i][2]
    g[u].append([v,w])
    g[v].append([u,w])


def bfs(g):
    ls_ans = [-1] * n
    ls_ans[0] = 0
    q = deque()
    q.append(0)
    while q:
        node = q.popleft()
        ls = g[node]
        
        for i in range(len(ls)):
            child = ls[i][0]
            weight = ls[i][1]
            if ls_ans[child]!=-1:
                pass
            elif ls_ans[node]==0 and weight%2==0:
                ls_ans[child] = 0
                q.append(child)
            elif ls_ans[node]==0 and weight%2==1:
                ls_ans[child] = 1
                q.append(child)
            elif ls_ans[node]==1 and weight%2==0:
                ls_ans[child] = 1
                q.append(child)
            elif ls_ans[node]==1 and weight%2==1:
                ls_ans[child] = 0
                q.append(child)
            else:
                print("error")
        
    return ls_ans

ls_ans = bfs(g)


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

Solution (Python):
import sys
stdin = sys.stdin
sys.setrecursionlimit(10**6)
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()

n = ni()
g = [[] for i in range(n)]

for i in range(n-1):
    u,v,w = na()
    g[u-1].append((v-1,w))
    g[v-1].append((u-1,w))

dp = [0]*n

def f(a,b,c):
    dp[b] = c
    for i,j in g[b]:
        if i != a:
            f(b,i,c+j)

f(0,0,0)

for k in dp:
    print(k%2)

Solution (Python):
from collections import deque
n = int(input())
path = [{} for _ in range(n)]
for _ in range(n-1):
  u,v,w = map(int,input().split())
  u -= 1
  v -= 1
  path[u][v] = w
  path[v][u] = w

q = deque([(0,0)])
reached = [True] + [False]*(n-1)
ans = [0]*n
while q:
  p,c = q.popleft()
  for i,d in path[p].items():
    if reached[i]:continue
    if d&1:
      ans[i] = 1 - c
    else:
      ans[i] = c
    reached[i] = True
    q.append((i,ans[i]))
for i in ans:
  print(i)

Solution (Python):
from collections import deque

N = int(input())
tree =   [[] for _ in range(N)]
color = [-1] * N
color[0] = 0
for n 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])

q = deque()
q.append((0,-1))

while q:
  index, parent = q.pop()
  for target, d in tree[index]:
    if target == parent: continue
    if d%2 == 0:
      color[target] = color[index]
    else:
      color[target] = (color[index] + 1)%2
    q.append((target,index))
print(*color, sep="\n")

Solution (Python):
import sys
input = sys.stdin.readline
import sys
sys.setrecursionlimit(1000000)
n = int(input())

g = [[] * n 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))

chk = [0]*n
chk[0] = 1

def dfs(now, prev):
    global chk
    
    for next in g[now]:
        if next[0] != prev:
          if next[1]%2 == 0:
            chk[next[0]] = chk[now]
          elif next[1]%2 == 1:
            chk[next[0]] = (chk[now]*-1)
          
          dfs(next[0], now)
        
dfs(0,-1)
chk = tuple(chk)
for i in chk:
  if i == 1:
    print(1)
  else:
    print(0)

Solution (Python):
import sys, copy, math, heapq, bisect
from itertools import accumulate
from collections import deque, defaultdict, Counter
input = sys.stdin.readline 
sys.setrecursionlimit(500000)

N = int(input())
T = [defaultdict(int) for i in range(N)]
for i in range(N-1):
    u,v,w = map(int,input().split())
    T[u-1][v-1] = w
    T[v-1][u-1] = w
visited = [0]*N
ans = [0]*N
def dfs(now,col):
    visited[now] = 1
    for i in T[now].keys():
        if visited[i] == 1:
            continue
        if T[now][i]%2==1:
            ans[i] = col^1
            next = col^1
        else:
            ans[i] = col
            next = col
        dfs(i,next)
dfs(0,0)
for i in range(N):
    print(ans[i])

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

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


def dfs(u, c):
    color[u] = c
    for v, w in g[u]:
        if color[v] != -1:
            continue
        if w % 2 == 0:
            nc = c
        else:
            nc = 1 - c
        dfs(v, nc)


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

Solution (Python):
def bfs(n, g):
    from collections import deque
    color = [-1] * n
    q = deque([0])
    while q:
        tmp = q.popleft()
        for u, w in g[tmp]:
            if color[u] != -1:
                continue
            color[u] = color[tmp] + w
            q.append(u)
    for c in color:
        if c % 2 == 0:
            print(1)
        else:
            print(0)


def main():
    n = int(input())
    g = [[] for _ in range(n)]
    for _ 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])
    bfs(n, g)


if __name__ == "__main__":
    main()

Solution (Python):
from collections import deque

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

q = deque([1])
while q:
  x = q.popleft()
  for y, w in graph[x]:
    if(y == parent[x]):
      continue
    parent[y] = x
    ans[y] = ans[x]^(w&1)
    q.append(y)
      
for i in range(1, n+1):
  print(ans[i])

Solution (Python):
import sys
sys.setrecursionlimit(500*500)

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

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

for edge in edges:
    A[edge[0]].append([edge[1], edge[2]])
    A[edge[1]].append([edge[0], edge[2]])

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

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

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

Solution (Python):
import sys
sys.setrecursionlimit(10**5)
n = int(input())
uvw = [list(map(int, input().split())) for _ in range(n-1)]

edges = [[] for _ in range(n)]
for u, v, w in uvw:
    u-=1
    v-=1
    edges[u].append([v, w%2])
    edges[v].append([u, w%2])

res = [[] for _ in range(n)]
def dfs(v, p, c):
    res[v] = c
    for e in edges[v]:
        if e[0] == p: continue
        if e[1]%2==1: dfs(e[0], v, 1-c%2)
        else: dfs(e[0], v, c)

dfs(0, -1, 1)
print('\n'.join(list(map(str, res))))