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

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

def dfs(v):
    check[v] = True
    for u, w in T[v]:
        if check[u]:
            continue
        dist[u] = dist[v] + w
        dfs(u)

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

dist = [0] * (N + 1)
check = [False] * (N + 1)
dfs(1)

print(*[d % 2 for d in dist[1:]], sep="\n")

Solution (Python):
from collections import deque
def main():
  N=int(input())
  G=[[] for i in range(N)]
  ans=[]
  for i in range(N-1):
    u,v,w=map(int,input().split())
    G[u-1].append([v-1,w%2])
    G[v-1].append([u-1,w%2])
  ans=[-1]*N
  finish=[0]*N
  q=deque([0])
  while q:
    now=q.pop()
    for i in G[now]:
      if finish[i[0]]==1:
        continue
      else:
        if i[1]%2==1:
          ans[i[0]]=-1*ans[now]
        else:
          ans[i[0]]=ans[now]
        finish[i[0]]=1
        q.append(i[0])
  for i in ans:
    print(i%2 if i == -1 else 0)
main()

Solution (Python):
import sys
sys.setrecursionlimit(100000000)
n=int(input())
es=[[]for i in range(n)]
for i in range(n-1):
    u,v,w=map(int,input().split())
    es[u-1].append([v-1,w])
    es[v-1].append([u-1,w])
color = [0 for i in range(n)] 
def dfs(v,c):
    color[v] = c
    for i in es[v]:
        if color[i[0]]==0:
            
            if i[1]%2==1:
                dfs(i[0],-c)
            else:
                dfs(i[0],c)
dfs(0,1)

for i in color:
    if i==-1:
        print(0)
    else:
        print(1)

Solution (Python):
from collections import deque,defaultdict
n=int(input())
routes=[tuple(map(int,input().split())) for i in range(n-1)]

edges=defaultdict(list)
for v1,v2,dist in routes:
  edges[v1-1].append([v2-1,dist])
  edges[v2-1].append([v1-1,dist])


ans=[0]*n
q=deque([0])
while q:
  v=q.popleft()
  
  if ans[v]==0:
    color=[1,0]
  else:
    color=[0,1]
  
  for edge in edges[v]:
    v2=edge[0]
    dist=edge[1]
    edges[v2].remove([v,dist])
    q.append(v2)
    if dist%2==1:
      ans[v2]=color[0]
    else:
      ans[v2]=color[1]
      
print(*ans,sep='\n')

Solution (Python):
import sys
input = sys.stdin.readline
n=int(input())
G=[[]for _ in range(n+1)]
for _ in range(n-1):
    u,v,w=map(int,input().split())
    w%=2
    G[u].append((v,w))
    G[v].append((u,w))
ans=[-1]*(n+1)

stack=[1]
ans[1]=1
while stack:
    t=stack.pop()
    color_t=ans[t]
    for w in G[t]:
        ten,kyori=w
        if ans[ten]==-1:
            if kyori==0:
                ans[ten]=color_t
            else:
                ans[ten]=color_t+1
                ans[ten]%=2
            stack.append(ten)
print(*ans[1::], sep='\n')

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

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

    go = [True for _ in range(N)]
    length = [0 for _ in range(N)]
    go[0] = False
    q = deque([0])
    while q:
        now = q.pop()
        for fol,d in dist[now]:
            if go[fol]:
                length[fol] = length[now]+d
                go[fol] = False
                q.append(fol)

    for i in length:
        print(i%2)
        
if __name__ == "__main__":
    main()

Solution (Python):
from collections import deque



def main():
    BLACK = 1
    WHITE = 0
    EDGE = 0
    WEIGHT = 1
    N = int(input())
    graph = [[] for i in range(N+1)]
    colors = [-1] * (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))

    q = deque()
    q.append(1)
    colors[1] = WHITE
    visited = [False] * (N + 1)
    visited[1] = True

    while len(q) != 0:
        n = q.popleft()

        for v, w in graph[n]:
            if visited[v]:
                continue

            if w % 2 == 0:
                colors[v] = colors[n]
            else:
                
                colors[v] = BLACK if colors[n] == WHITE else WHITE

            visited[v] = True
            q.append(v)

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


if __name__ == '__main__':
    main()

Solution (Python):

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

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

graph = [[] for _ in range(N+1)] 
for a,b,w in ABW:
    graph[a].append((b,w%2)) 
    graph[b].append((a,w%2))


stack = [1]
parent = [0]*(N+1)
order = []
while stack:
    x = stack.pop()
    order.append(x)
    for i,j in graph[x]: 
        if i == parent[x]:
            continue
        parent[i] = x
        stack.append(i)



color = [-1]*(N+1)
color[1] = 0
for x in order: 
    c = 0 if color[x] == -1 or color[x] == 0 else 1
    for y,w in graph[x]: 
        if y == parent[x]: 
            continue
        if w == 0:
            color[y] = c
        else:
            color[y] = 1 - c


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

Solution (Python):
import sys

n = int(sys.stdin.readline().rstrip())
graph = [[] for _ in range(n)]
for _ in range(n-1):
    u, v, w = map(int, sys.stdin.readline().split())
    graph[u-1].append((v - 1, w))
    graph[v-1].append((u - 1, w))

def coloring_tree(g, size):
    par = [None] * size
    stack = [(0, 0)]
    color = [None] * size
    color[0] = 0
    while stack:
        u, d = stack.pop()
        color[u] = d & 1
        for v, w in g[u]:
            if par[u] == v:
                continue
            par[v] = u
            stack.append((v, d + w))
    return color

def main():
    return coloring_tree(graph, n)
    
if __name__ == '__main__':
    ans = main()
    print(*ans, sep='\n')

Solution (Python):
from math import ceil,log2

def main():
    N = int(input())
    UVW = [list(map(int,input().split())) for _ in range(N - 1)]
    edge = [[] for _ in range(N + 1)]
    dis = {}
    for u,v,w in UVW:
        edge[u].append(v)
        edge[v].append(u)
        dis[(u,v)] = w
        dis[(v,u)] = w
    cnt = 0
    queue = [1]
    gone = {1:0}
    while cnt < N:
        node = queue[cnt]
        for e in edge[node]:
            if e not in gone:
                if dis[(node,e)]%2 == 1:
                    gone[e] = (gone[node] + 1)%2
                else:
                    gone[e] = gone[node]
                queue.append(e)
        cnt += 1
    for i in range(1,N + 1):
        print(gone[i])
    return
if __name__ == "__main__":
    main()

Solution (Python):
from collections import deque
n=int(input())
edge=[[] for i in range(n)]
if n==1:
  print(0)
  exit()
col=[-1 for i in range(n)]
for i in range(n-1):
  u,v,w=map(int,input().split())
  u-=1
  v-=1
  edge[u].append((v,w))
  edge[v].append((u,w))
def dfs(edge,col):
  stack=deque([0])
  col[0]=0
  while stack:
    x=stack.pop()
    for i,j in edge[x]:
      newx=i
      if col[i]==-1:
        col[newx]=(col[x]+j)%2
        stack.append(newx)
  return col
for i in range(n):
  print(dfs(edge,col)[i])

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

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

def dfs(v, p=-1, c=0):
    for i in range(len(to[v])):
        u, w=to[v][i]
        if p==u:
            continue
        color[u]=(c+w)%2
        dfs(u, v, color[u])

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

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

def dfs(v, p=-1, c=0):
  for i in range(len(to[v])):
    u, w=to[v][i]
    if u==p:
      continue
    color[u]=(c+w)%2
    dfs(u, v, color[u])
    
N=int(input())
uvw=[list(map(int, input().split())) for _ in range(N-1)]
to=[[] for _ in range(N)]
color=[0 for _ in range(N)]
for i in range(N-1):
  u, v, w=uvw[i]
  u-=1
  v-=1
  to[u].append([v, w%2])
  to[v].append([u, w%2])

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

Solution (Python):

from collections import defaultdict
n = int(input())
e = defaultdict(lambda: [])

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

col = [-1]*n
q = [0]
col[0] = 0
while len(q)>0:
    v = q.pop()
    for u,w in e[v]:
        if col[u]<0:
            if w%2==1:
                col[u] = (col[v]+1)%2
            else:
                col[u] = col[v]
            q.append(u)

print(*col)

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

def search(tree, now, pre, t, ans):
  nex_li = tree[now]
  for nex, w in nex_li:
    if pre == nex:
      continue
    t1 = t+w
    if t1%2 == 0:
      ans[nex] = 0
    else:
      ans[nex] = 1
    ans = search(tree, nex, now, t1, ans)
  return ans

def run():
  N = int(input())
  tree = {}
  for n in range(N-1):
    u, v, w = map(int, input().split())
    tree.setdefault(u, []).append((v, w%2))
    tree.setdefault(v, []).append((u, w%2))
  ans = [0]*(N+1)
  ans = search(tree, 1, -1, 0, ans)
  for a in ans[1:]:
    print(a)
  
  
if __name__ == '__main__':
    run()

Solution (Python):
from collections import deque

n = int(input())
ans = [0] * n
visited = [False] * n
G = [[] for _ in range(n)]

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

q = deque([])
q.append(0)
visited[0] = True

def dfs():
    while q:
        p = q.popleft()
        for u, w in G[p]:
            if visited[u]: continue
            else:
                ans[u] = (ans[p] + w) % 2
                visited[u] = True
                q.append(u)

dfs()

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

Solution (Python):
from collections import deque
 
n = int(input())
ans = [0] * n
visited = [False] * n
G = [[] for _ in range(n)]
 
for i in range(n-1):
    u, v, w = map(int, input().split())
    u -= 1
    v -= 1
    G[u].append([v, w])
    G[v].append([u, w])
 
q = deque([])
q.append(0)
visited[0] = True
 
def dfs():
    while q:
        p = q.pop()
        for u, w in G[p]:
            if visited[u]: continue
            else:
                ans[u] = (ans[p] + w) % 2
                visited[u] = True
                q.append(u)
 
dfs()
 
for i in range(n):
    print(ans[i])

Solution (Python):
from collections import deque

n = int(input())
ans = [0] * n
visited = [False] * n
G = [[] for _ in range(n)]

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

q = deque([])
q.append(0)
visited[0] = True

def dfs():
    while q:
        p = q.pop()
        for u, w in G[p]:
            if visited[u]: continue
            else:
                ans[u] = (ans[p] + w) % 2
                visited[u] = True
                q.append(u)

dfs()

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

Solution (Python):

import sys
sys.setrecursionlimit(10000000)
INF = 1<<32


def solve(N: int, u: "List[int]", v: "List[int]", w: "List[int]"):
    colors = [-1] *(N+1)
    g = [[] for i in range(N+1)]
    for i in range(N-1):
        g[u[i]].append([v[i], w[i]])
        g[v[i]].append([u[i], w[i]])

    

    from collections import deque
    d = deque()
    colors[1] = 0
    d.append(1)
    while len(d) > 0:
        
        n = d.popleft()
        for V, W in g[n]:
            if colors[V] != -1:
                continue
            d.append(V)
            if W%2 == 0:
                colors[V] = colors[n]
            else:
                colors[V] = int(not colors[n])
    
    for i in range(1, N+1):
        print(colors[i])
            

    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 numpy as np


def calDistance_dfs(aList, d, node):
    stack = [node]
    d[node] = 0
    while len(stack) != 0:
        current = stack.pop()
        for v in aList[current]:
            if d[v[0]] == -1:
                stack.append(v[0])
                d[v[0]] = d[current]+v[1]


n = int(input())
adjacencyList = [[] for i in range(n)]
d = [-1] * n

for i in range(n - 1):
    s = list(map(int, input().split()))
    adjacencyList[s[0] - 1].append((s[1] - 1, s[2]))
    adjacencyList[s[1] - 1].append((s[0] - 1, s[2]))


d[0] = 0
calDistance_dfs(adjacencyList, d, 0)
for i in d:
    print(i % 2)

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

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

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

visited = [0] * n
visited[0] = 1
ans = [0] * n
stack = [0]

while stack:
    v = stack.pop()
    for next, distance in edge[v]:
        if visited[next]: continue
        ans[next] = (ans[v] + distance) % 2
        visited[next] = 1
        stack.append(next)

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

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

n = int(input())
edges = [[] for _ in range(n+1)]
colors = [None] * (n+1)

for i in range(n-1):
    u, v, w = [int(x) for x in input().split()]
    if w & 1 == 0:
        edges[u].append((v, 0))
        edges[v].append((u, 0))
    else:
        edges[u].append((v, 1))
        edges[v].append((u, 1))

colors[1] = 0


def color(node, c):
    colors[node] = c
    for i, j in edges[node]:
        if colors[i] is None:
            new_color = (c + j)%2
            color(i, new_color)

color(1,1)

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

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

n = int(input())
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))

ans = [0 for _ in range(n)]

def journey(u, p, bit):
    ans[u] = bit
    for v, w in tree[u]:
        if v == p: continue
        if w % 2 == 0: journey(v, u, bit)
        else: journey(v, u, 1-bit)
    
journey(0, -1, 0)
[print(x) for x in ans]

Solution (Python):
import sys
N = int(input())
V = {}
if N == 1:
  print(0)
  exit(0)


sys.setrecursionlimit(N)


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

ANS = [-1] * N
visited = [False] * N

def dfs(pos):
  visited[pos] = True
  for x,w in V[pos]:
    if visited[x]:
      continue
    if w % 2 == 0:
      ANS[x] = ANS[pos]
    else:
      ANS[x] = 1 - ANS[pos]
    
    dfs(x)
  return

ANS[0] = 0
dfs(0)

for a in ANS:
  print(a)

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

n = int(input())
tree = [[] for _ in range(n)]
color = [0]*n
for _ in range(n-1):
  a,b,c = map(int,input().split())
  a -= 1
  b -= 1
  tree[a].append((b,c))
  tree[b].append((a,c))
  
  
def dfs(i,before,cost):
  if cost == 1:
    color[i] = 1
  for j in tree[i]:
    if j[0] == before:
      continue
    dfs(j[0],i,(cost + j[1])%2 )
    
dfs(0,-1,0)

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

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

colors = [-1] * n

conns = [set() for _ in [0] * n] 

for x in range(1, n):
  v1, v2, dis = map(int, input().split())
  
  conns[v1-1].add((v2-1, dis))
  conns[v2-1].add((v1-1, dis))


q = deque([(0, 0, -1)])

while q:
  v, dis, past = q.popleft()
  
  
  colors[v] = dis&1
  
  
  for edge, w in conns[v]:
    
    
    if edge == past:
      continue
    
    q.append((edge, dis + w, v))

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

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

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

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

def dfs(u, c):
    visited[u] = True   
    for vw in M[u]:
        v, w = vw       
        if visited[v] == False:
            if w%2 == 0:
                color[v] = c * 0b1
            else:
                color[v] = c ^ 0b1
            
            dfs(v, color[v])

dfs(u, 0)
for i in range(N):
    print(color[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 j 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):
n = int(input())
color = [-1] * n
edges = [[] for i 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))
q = [0]
color[0] = 0
while len(q) > 0:
    u = q.pop(0)
    for v, w in edges[u]:
        if color[v] < 0:
            q.append(v)
            color[v] = (color[u] + w) % 2
for i in range(n):
    print(color[i])

Solution (Python):
import os, sys, re, math, queue

N = int(input())
colors = [-1 for _ in range(N+1)]
nodes = {}

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

	if v in nodes:		
		nodes[v].append((u,w % 2))
	else:
		nodes[v] = [(u,w % 2)]

q = queue.Queue()
fst = list(nodes.keys())[0]
q.put((fst,0))

while not q.empty():
	pos, color = q.get()
	colors[pos] = color
	for cand in nodes[pos]:
		if colors[cand[0]] == -1:
			if cand[1] == 0:
				q.put((cand[0], color))
			else:
				q.put((cand[0], (color+1) % 2))

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

Solution (Python):

N = int(input())
flag = [None] * (N+1)
edges = [[] for j in range(N+1)]

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


def dfs(i, color):
  visited = set()
  distances = [float("inf")] * (N + 1)
  stack = [i]
  distances[i] = 0
  flag[i] = color

  while stack:
    u = stack.pop()
    visited.add(u)

    for (v, w) in edges[u]:
      if v not in visited:
        stack.append(v)
        distances[v] = distances[u] + w
        if distances[v] % 2 == 0:
          flag[v] = color

dfs(1, 0)
for u in range(1, N+1):
  if flag[u] == None:
    dfs(u, 1)
    break

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

Solution (Python):
from collections import deque
N = int(input())
uvw = [[]for i in range(N)]
for i in range(N-1):
    u,v,w = list(map(int,input().split()))
    uvw[u-1].append([v-1,w%2])
    uvw[v-1].append([u-1,w%2])    
color = [-1 for i in range(N)]
color[0] = 0
que = deque()
que.append(0)
while que:
    q = que.popleft()
    colorq = color[q]
    for i in uvw[q]:
        if color[i[0]] == -1:
            que.append(i[0])
            if i[1] == 0:
                color[i[0]] = colorq
            else:
                color[i[0]] = abs(colorq-1)
for i in color:
    print(i)

Solution (Python):

from bisect import *
from collections import *
from heapq import *



N=int(input())
VUW=[list(map(int,input().split())) for i in range(N-1)]
data=[[] for i in range(N+1)]
nagasa={}
for v,u,w in VUW:
    data[v].append(u)
    data[u].append(v)
    v,u=min(v,u),max(v,u)
    nagasa.update({str(v)+" "+str(u):w})
kakutei=set([i for i in range(1,N+1)])
iro=[0 for i in range(N+1)]


itta=set()
st=1
stack=deque([[st,0,st]])
while stack:
    v,m,st=stack.popleft()
    for u in data[v]:
        if not u in itta:
            itta.add(u)
            a,b=min(v,u),max(v,u)
            w=nagasa[str(a)+" "+str(b)]
            M=m+w

            if M%2==1:
                iro[u]=1
            stack.append([u,M,st])

for i in range(1,N+1):
    print(iro[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):
from collections import defaultdict
N=int(input())
E=defaultdict(list)
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))
ans=[-1]*N

stack=[0]
ans[0]=0
while stack:
    node=stack.pop()
    for to,w in E[node]:
        if ans[to]!=-1: continue
        ans[to]=ans[node]^(w&1)
        stack.append(to)

for c in ans:
    print(c)

Solution (Python):
import queue

import sys
input = sys.stdin.readline

N=int(input())
adj=[[] for _ in range(N)]

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

q=queue.Queue()
ans=[0]*N
q.put((0,-1,0))

while not q.empty():
    v,p,c=q.get()
    for i in range(len(adj[v])):
        n_v=adj[v][i][0]
        if n_v!=p:
            n_c=(c+adj[v][i][1])%2
            ans[n_v]=n_c
            q.put((n_v,v,n_c))
            
[print(ans[i]) for i in range(N)]

Solution (Python):
import collections

def dfs(s_node):
    q = collections.deque()
    used = set()
    q.append(s_node)
    used.add(s_node)
    while len(q) > 0:
        prv_node = q.pop()
        for node, cost in g[prv_node]:
            if node in used:
                continue
            else:
                if cost % 2 == 0:
                    cols[node] = cols[prv_node]
                else:
                    cols[node] = -cols[prv_node]
                q.append(node)
                used.add(node)


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

cols = [-1 for _ in range(N)]
dfs(0)

[print(1) if cols[i] == 1 else print(0) for i in range(N)]

Solution (Python):
from collections import deque

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

D = deque([0])
ans = [None] * N
ans[0] = 0
while D:
    x = D.popleft()
    for v, w in tree[x]:
        if ans[v] is None:
            ans[v] = (ans[x] + w) % 2
            D.append(v)

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

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


colors = [-1]*N


def dfs(v, color):
    if colors[v] != -1: 
        return
    colors[v] = color
    for adjacent_v in adjacent_list[v]:
        if adjacent_v[1] % 2 == 0:
            dfs(adjacent_v[0], color)
        else:
            dfs(adjacent_v[0], 1-color)

dfs(0,0)


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

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


colors = [-1]*N


def dfs(v, color):
    if colors[v] != -1:
        return
    colors[v] = color
    for adjacent_v in adjacent_list[v]:
        if adjacent_v[1] % 2 == 0:
            dfs(adjacent_v[0], color)
        else:
            dfs(adjacent_v[0], 1-color)

dfs(0,0)


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

Solution (Python):


from collections import deque


test = ""

"""
3
1 2 2
2 3 1
ans:
0
0
1
"""

"""
5
2 5 2
2 3 10
1 3 8
3 4 2
ans:
1
0
1
0
1
"""

test = list(reversed(test.strip().splitlines()))
if test:
    def input2():
        return test.pop()
else:
    def input2():
        return input()

        
n = int(input2())
edges = [0] * (n-1)
for i in range(n-1):
    edges[i] = tuple(map(int, input2().split()))

adjacency_list = [[] for i in range(n+1)]
for edge in edges:
    adjacency_list[edge[0]].append((edge[1], edge[2]))
    adjacency_list[edge[1]].append((edge[0], edge[2]))

nodeL = [None] * (n+1)
nodeL[1] = 0
nodeQ = deque([[1]])
while nodeQ:
    tmp = nodeQ.popleft()
    tmp = tmp[0]
    
    nodes = adjacency_list[tmp]
    for nd in nodes:
        if nodeL[nd[0]] == None:
            nodeL[nd[0]] = nodeL[tmp] ^ nd[1]%2
            nodeQ.append([nd[0]])

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

Solution (Python):
import sys
sys.setrecursionlimit(10**7)
N = int(input())
L = [-1 for i in range(N)]
flg = [0 for i in range(N)]
M = [[] for i in range(N)]
for i in range(N-1):
  u, v, w = map(int, input().split())
  M[u-1].append([v-1, w%2])
  M[v-1].append([u-1, w%2])
L[0] = 0
def dist(m, d):
  L[m] = d % 2
  for i in M[m]:
    if L[i[0]] == -1:
      dist(i[0], i[1] + d)
dist(0, 0)
for i in range(N):
  print(L[i])

Solution (Python):
import math
import sys
import numpy as np
sys.setrecursionlimit(10 ** 7)

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

n = int(input())

G = [[] for _ in range(n + 5)]
for i in range(n - 1):
    u, v, w = int_input()
    u -= 1
    v -= 1
    G[u].append([v, w])
    G[v].append([u, w])

ans = [-1] * (n + 5)

def dfs(k, dist):
    ans[k] = dist % 2
    for i in G[k]:
        if ans[i[0]] == -1:
            dfs(i[0], dist + i[1])
    
dfs(0, 0)

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

Solution (Python):
import sys
sys.setrecursionlimit(10**7)
N = int(input())
a = [[] for _ in range(N)]
ans = [0]*N
for _ 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])
def calc(u, b):
  for v, w in a[u]:
    if not b == v:
      ans[v]=(ans[u] + w)%2
      calc(v, u)
calc(0, -1)
for i in ans:
  if i % 2 == 0:
    print(0)
  else:
    print(1)

Solution (Python):
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,pprint,fractions
sys.setrecursionlimit(10**8)
mod = 10**9+7
mod2 = 998244353
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpln(n): return list(int(sys.stdin.readline()) for i in range(n))

n = inp()
g = [[] for i in range(n)]
for i in range(n-1):
    a,b,c = inpl()
    g[a-1].append((b-1,c))
    g[b-1].append((a-1,c))
color = [-1] * n 
color[0] = 0
def dfs(node):
    for v,c in g[node]:
        if color[v] != -1:
            continue
        if (c) % 2:
            color[v] = 0 if color[node] else 1
        else: color[v] = 1 if color[node] else 0
        dfs(v)
dfs(0)

for i in color:
    print(i)

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

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

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

ans = [0] * n
def dfs(v,p,c):
  ans[v] = c
  for i in g[v]:
    if i[0] != p:
      if i[1] % 2 == 0:
        dfs(i[0], v, c)
      else:
        dfs(i[0], v, 1-c)
        
dfs(0,-1,0)

for i in ans:
  print(i)

Solution (Python):
import sys
sys.setrecursionlimit(20000000)
def prepare(n,arr):
    nodeArr = [[] for i in range(n)]
    for ar in arr:
        nodeArr[ar[0]-1].append([ar[1]-1,ar[2]])
        nodeArr[ar[1]-1].append([ar[0]-1,ar[2]])
    return nodeArr

def dfs(currentNode,distance):
    res[currentNode] = distance
    for next in nodeArr[currentNode]:
        nextNode = next[0]
        nextNodeDistance = next[1]
        if res[nextNode] == -1:
            dfs(nextNode,distance + nextNodeDistance)




n = int(input())

arr = []

for i in range(n-1):
    arr.append([int(s) for s in input().split(" ")])

nodeArr = prepare(n, arr)


if n == 1:
    print(1)
else:
    res = [-1 for i in range(n)]

    dfs(0,0)

    result = [(re % 2) for re in res]

    for re in res:
        print(re % 2)

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


n = int(input())
COLORS = [True] * (n + 1)

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

def dfs(now, prev):
    for vertex in TREE[now]:
        if vertex == prev:
            continue
        else:
            next = vertex
        u, v = min(now, next), max(now, next)
        if LENGTHS[(u, v)] % 2 == 0:
            COLORS[next] = COLORS[now]
        else:
            COLORS[next] = not COLORS[now]
        dfs(next, now)
dfs(1, 0)

for i in range(1, n + 1):
    ans = int(COLORS[i])
    print(ans)

Solution (Python):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline

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

dic = {}
color = [0]*N
dist = {}
root = [0]*N

for i in range(N):
    dic[i+1] = []
for n in range(N-1):
    i = uvw[n][0]
    j = uvw[n][1]
    dic[i].append(j)
    dic[j].append(i)
    root[i-1] += 1
    root[j-1] += 1
    
    dist[(i,j)] = uvw[n][2]
    dist[(j,i)] = uvw[n][2]
root_node = root.index(1)+1

def rec(now_node, now_dist):
    if now_dist%2==1:
        color[now_node-1] = 1
    tg_list = dic[now_node][:]
    for elem in tg_list:
        dic[elem].remove(now_node)
        rec(elem, now_dist + dist[(elem,now_node)])
rec(root_node,0)

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