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

Solution (Python):
from collections import deque

N = int(input())

graph = [[] for _ in range(N+1)]
cost = [[] for _ in range(N+1)]
ans = [-1] * (N+1)

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


que = deque()

ans[1] = 0
que.append(1)

while que:
    now = que.popleft()
    
    for index in range(len(graph[now])):
        nextg = graph[now][index]
        nextc = cost[now][index]
        
        if ans[nextg] != -1:
            
            continue
        que.append(nextg)

        
        if nextc == 1:
            ans[nextg] = (ans[now] + 1) % 2
        else:
            ans[nextg] = ans[now]
    
    



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

Solution (Python):
import sys
sys.setrecursionlimit(10**8)
N = int(input())
graph = [[] for _ in range(N)]

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

color = [0 for _ in range(N)]
visited = [False for _ in range(N)]

def dfs(now):

    for adj in graph[now]:
        v, dist = adj
        if visited[v]:
            continue
        visited[v] = True
        color[v] = color[now] + dist
        dfs(v)

    return


for start in range(N):
    if not visited[start]:
        color[start] = 0
        visited[start] = True
        dfs(start)

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

Solution (Python):
from collections import deque

N = int(input())
dist = {}
graph = [[] for i in range(N)]

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


q = deque()
q.append(0)

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

while q:
    now = q.popleft()

    for adj in graph[now]:
        if color[adj] == -1:
            if now < adj:
                color[adj] = color[now] + dist[(now, adj)]
            else:
                color[adj] = color[now] + dist[(adj, now)]

            q.append(adj)


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

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())
  g[u-1].append([v-1,w])
  g[v-1].append([u-1,w])
q = deque()

check = [0] * N
check[0] = 1
q.append(0)
ans = [-1] * N
ans[0] = 0
while len(q) > 0:
  e = q.popleft()
  for i,j in g[e]:
    if check[i] == 1:
      continue
    ans[i] = (ans[e] + j) %2
    check[i] = 1
    q.append(i)
for i in range(N):
  print(ans[i])

Solution (Python):
from collections import*
n=int(input())
l=[[]for i in range(n)]
ans=[-1 for i in range(n)]
visit=[False for i in range(n)]
ans[0]=0
for i in range(n-1):
    u,v,w=map(int,input().split())
    l[u-1].append((v-1,w))
    l[v-1].append((u-1,w))
      
q=deque()
q.append((0,0,-1))
while q:
    v,d,p=q.popleft()
    if d%2==0:
        ans[v]=0
    else:
        ans[v]=1
    for u,w in l[v]:
        if u==p:
            continue
        q.append((u,d+w,v))
print('\n'.join(map(str, ans)))

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

c=[0]*(N+1)
stack=[1]
c[1]=1
while stack:
    r=stack.pop()
    for nr,nw in G[r]:
        if c[nr]==0:
            stack.append(nr)
            if nw%2:
                c[nr]=-c[r]
            else:
                c[nr]=c[r]
for i in c[1:]:
    print((i+1)//2)

Solution (Python):
class Graph():
	def __init__(self):
		self.adjacency_dict = {}
		self.weight = []

	def add_vartex(self, v):
		self.adjacency_dict[v] = []
		self.weight.append([])

	def add_edge(self, v1, v2, w):
		self.adjacency_dict[v1].append(v2)
		self.adjacency_dict[v2].append(v1)
		self.weight[v1].append(w)
		self.weight[v2].append(w)

	def get_vartexes(self):
		return self.adjacency_dict.keys()

	def get_edges(self, v):
		return self.adjacency_dict[v], self.weight[v]

	def printgraph(self):
		return print(self.adjacency_dict)

n = int(input())

res = []
g = Graph()
for i in range(n):
	res.append(-1)
	g.add_vartex(i)

for i in range(n-1):
	u, v, w = map(int, input().strip().split())
	g.add_edge(u - 1, v - 1, w % 2)


q = []
res[0] = 0
q.append(0)
while(len(q) > 0):
	v = q.pop()
	u_l, w_l = g.get_edges(v)
	for u, w in zip(u_l, w_l):
		if res[u] != -1:
			continue
		res[u] = (res[v] + w) % 2
		q.append(u)

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

Solution (Python):
from collections import deque

N = int(input())

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

q = deque([1])
dist = [-1] * (N + 1)
dist[1] = 0
while q:
    u = q.popleft()
    for v in conn[u]:
        if dist[v] == -1:
            if u < v:
                dist[v] = dist[u] + length[(u, v)]
            else:
                dist[v] = dist[u] + length[(v, u)]
            q.append(v)

for i in range(1, N + 1):
    print(dist[i] % 2)

Solution (Python):
from sys import stdin
import sys
import math
from functools import reduce
import functools
import itertools
from collections import deque,Counter,defaultdict
from operator import mul
import copy


import heapq
sys.setrecursionlimit(10**6)

INF = 10**18
import bisect
import statistics
mod = 10**9+7


N = int(input())

al = [[] for i in range(N+1)]
for i in range(N-1):
    a, b, c = map(int, input().split())
    al[a].append((b,c))
    al[b].append((a,c))


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

def bfs(u):
    stack = deque([u])
    seen[u] = 1
    ans[u] = 0

    while len(stack) > 0:
        v = stack.popleft()

        for w in al[v]:
            if seen[w[0]] == 0:
                stack.append(w[0])
                if w[1] % 2 == 0:
                    ans[w[0]] = ans[v]
                else:
                    ans[w[0]] = 1 - ans[v]
                seen[w[0]] = 1

bfs(1)

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

Solution (Python):

import sys
import copy

sys.setrecursionlimit(10 ** 9)


def dfs(seen, graph, i):
    for v, w in graph[i]: 
        if seen[v-1] != -1:
            continue
        seen[v-1] = abs((w % 2) - seen[i])
        dfs(seen, graph, v-1)
    

def main():
    n = int(input())
    graph = [[] for _ in range(n)]
    for _ in range(n-1):
        ui, vi, wi = map(int, input().split())
        graph[ui-1].append((vi, wi))
        graph[vi-1].append((ui, wi))
    
    seen = [-1 for _ in range(n)]
    seen[0] = 0
    for i in range(n-1):
        dfs(seen, graph, i)
        
    print(*seen, sep='\n')
        
main()

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

stack = [0]
color = [-1]*N
color[0] = 0
while stack:
    v = stack.pop()
    for child, w in adj[v]:
        if color[child] < 0:
            color[child] = (color[v] + w) % 2
            stack.append(child)

for i in color:
    print(i)

Solution (Python):
class UnionFind():
  def __init__(self, n=10**6):
    self.n = n
    self.root = [-1]*(n+1)
    self.rnk = [0]*(n+1)
  def find(self, x):
    if(self.root[x] < 0):
      return x
    else:
      self.root[x] = self.find(self.root[x])
      return self.root[x]
  def unite(self, x, y):
    x = self.find(x)
    y = self.find(y)
    if(x == y):return 
    elif(self.rnk[x] > self.rnk[y]):
      self.root[x] += self.root[y]
      self.root[y] = x
    else:
      self.root[y] += self.root[x]
      self.root[x] = y
      if(self.rnk[x] == self.rnk[y]):
        self.rnk[y] += 1
  def same(self, x, y):
    return self.find(x) == self.find(y)
  def count(self, x):
    return -self.root[self.find(x)]
uf=UnionFind()
n=int(input())
for _ in range(n-1):
  u,v,w=map(int,input().split())
  if w%2:
    uf.unite(2*u,2*v-1)
    uf.unite(2*u-1,2*v)
  else:
    uf.unite(2*u,2*v)
    uf.unite(2*u-1,2*v-1)
f=uf.find(2*1)
for i in range(1,n+1):
  print(int(uf.find(2*i)==f))

Solution (Python):
import sys,math,collections,itertools
input = sys.stdin.readline

N=int(input())
road=[[] for i in range(N+1)]
for _ in range(N-1):
    u,v,w=list(map(int,input().split()))
    road[u].append((v,w))
    road[v].append((u,w))
dist = [float('inf')for i in range(N+1)]
ans = [0]*(N+1)

q = collections.deque([])
q.append(1)
dist[1]=0
while q:
    now = q.popleft()
    for goto,cost in road[now]:
        if dist[goto]>dist[now]+cost:
            dist[goto]=dist[now]+cost
            q.append(goto)

for a in dist[1:]:
    print(a%2)

Solution (Python):
from collections import deque

n=int(input())
ch=0
g=[[] for _ in range(n)]
k=[[] for _ in range(n)]
for i in range(n-1):
  u,v,w=map(int,input().split())
  if w%2==0:
    g[u-1].append(v-1)
    g[v-1].append(u-1)
  else:
    k[u-1].append(v-1)
    k[v-1].append(u-1)
    ch1=u-1
    ch2=v-1
    ch=1


ans=[-1 for _ in range(n)]

if ch>0:
  ans[ch1]=0
  d=[ch1]
  qu=deque(d)
  while qu:
    p=qu.popleft()
    
    for gr in g[p]:
      if ans[gr]==-1:
        if ans[p]==0:
          ans[gr]=0
          qu.append(gr)
        else:
          ans[gr]=1
          qu.append(gr)
      
    for kr in k[p]:
      if ans[kr]==-1:
        if ans[p]==0:
          ans[kr]=1
          qu.append(kr)
        else:
          ans[kr]=0
          qu.append(kr)   
    
          
  for j in range(n):
    print(ans[j])
    
else:
  for j in range(n):
    print(0)

Solution (Python):
class UnionFindTree:
    def __init__(self, n):
        self.nodes = [-1] * n 
    def find(self, i):
        if self.nodes[i] < 0: 
            return i
        else:
            self.nodes[i] = self.find(self.nodes[i]) 
            return self.nodes[i]

    def union(self, i, j):
        i = self.find(i)
        j = self.find(j)
        if i == j:
            return
        if self.nodes[i] > self.nodes[j]: 
            i, j = j, i
        self.nodes[i] += self.nodes[j] 
        self.nodes[j] = i 
    
    def size(self, i): 
        i = self.find(i)
        return -self.nodes[i]

n = int(input())
uft = UnionFindTree(2 * n)
for _ in range(n-1):
    u, v, w = map(int, input().split())
    u -= 1
    v -= 1
    if w % 2 == 0:
        uft.union(u, v)
        uft.union(u + n, v + n)
    else:
        uft.union(u + n, v)
        uft.union(u, v + n)

x = uft.find(0)
for i in range(n):
    print(0 if uft.find(i) == x else 1)

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

stack = [0]
color = [-1] * n
color[0] = 0
while stack:
    v = stack.pop()
    for child, w in tree[v]:
        if color[child] < 0:
            color[child] = (color[v] + w) % 2
            stack.append(child)
for i in color:
    print(i)

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

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

while q:
    v = q.popleft()
    for child, w in tree[v]:
        if color[child] < 0:
            color[child] = (color[v] + w) % 2
            q.append(child)

for i in color:
    print(i)

Solution (Python):
import sys
mod=10**9+7 ; inf=float("inf")
from math import sqrt, ceil
from collections import deque, Counter, defaultdict 
input=lambda: sys.stdin.readline().strip()
sys.setrecursionlimit(11451419)
from decimal import ROUND_HALF_UP,Decimal  
  
from functools import lru_cache
from bisect import bisect_left as bileft, bisect_right as biright






n=int(input())
G=[[] for i in range(n)]
for i in range(n-1):
    a,b,w=map(int,input().split())
    a-=1;b-=1
    G[a].append((b,w))
    G[b].append((a,w))
C=[-1]*n 
C[0]=0
def dfs(x):
    for v,w in G[x]:
        if C[v]==-1:
            C[v]=1-C[x] if w%2==1 else C[x]
            dfs(v)

dfs(0)

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

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


n = int(input())
nodes = [list(map(int,input().split())) for _ in range(n-1)]
a = [[] for _ in range(n+1)]

for node in nodes:
    a[node[0]].append([node[1],node[2]])
    a[node[1]].append([node[0],node[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**7)
N = int(input())

Graph = [[] for _ in range(N+1)]
dist  = [1000000000000]*(N+1)

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


def func(fromE,now,length):
	dist[now] = length
	for i in range(len(Graph[now])):
		target = Graph[now][i][0]
		lengt  = Graph[now][i][1]

		if target == fromE:
			continue

		func(now,target,dist[now]+lengt)

func(-1,0,0)

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

Solution (Python):
import sys
sys.setrecursionlimit(10**7)
N = int(input())

Graph = [[] for _ in range(N+10)]
dist  = [10000000000000]*(N+10)

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

dist[0] = 0

def func(fromE,now,length):
	if fromE != -1:
		dist[now] = dist[fromE]+length
	for i in range(len(Graph[now])):
		target = Graph[now][i][0]
		lengt  = Graph[now][i][1]

		if target == fromE:
			continue

		func(now,target,lengt)

func(-1,0,0)

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

Solution (Python):
from collections import deque

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

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

while len(q) != 0:
  v = q.popleft()
  for next_v, next_w in graph[v]:
    if dist[next_v] != -1:
      continue
    dist[next_v] = dist[v] + next_w
    q.append(next_v)

for d in dist:
  if d%2 == 0:
    print(0)
  else:
    print(1)

Solution (Python):
import sys
from collections import deque
input=sys.stdin.readline
N=int(input())
tree=[[] for _ in range(N)]
for _ in range(N-1):
  u,v,w=map(int,input().split())
  tree[u-1].append((v-1,w))
  tree[v-1].append((u-1,w))
ans=[-1]*N
ans[0]=0
d=deque([0])
while d:
  p=deque.popleft(d)
  color=ans[p]
  for v,w in tree[p]:
    if ans[v]==-1:
      deque.append(d,v)
      ans[v]=color^(w%2)
print(*ans,sep='\n')

Solution (Python):
from collections import deque
import sys
sys.setrecursionlimit(10**7)
n = int(input())
ad_ls = [[] for _ in range(n)]
for _ in range(n-1):
    a,b,w = map(int,input().split())
    ad_ls[a-1].append([b-1,w])
    ad_ls[b-1].append([a-1,w])

cost_ls = [0] * n
done_ls = [0] * n
def dfs(v,c):
    for new,cost in ad_ls[v]:
        if not done_ls[new]:
            cost_ls[new] = c+cost
            done_ls[new] = 1
            dfs(new,c+cost)

dfs(0,0)

color_ls = [0] * n
for i in range(n):
    color_ls[i] = cost_ls[i] % 2

for color in color_ls:
    print(color)

Solution (Python):
from collections import deque
n = int(input())
ad_ls = [[] for _ in range(n)]
for _ in range(n-1):
    a,b,w = map(int,input().split())
    ad_ls[a-1].append([b-1,w])
    ad_ls[b-1].append([a-1,w])

cost_ls = [0] * n
done_ls = [0] * n
done_ls[0] = 1
q = deque()
q.append(0)

while q:
    now = q.pop()
    for new in ad_ls[now]:
        nex,cost = new[0],new[1]
        if not done_ls[nex]:
            cost_ls[nex] = cost + cost_ls[now]
            done_ls[nex] = 1
            q.append(nex)

color_ls = [0] * n
for i in range(n):
    color_ls[i] = cost_ls[i] % 2

for color in color_ls:
    print(color)

Solution (Python):
from collections import deque

n = int(input())

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

for i 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))

"""
根から各頂点への距離をd_iとする
2頂点u,vについて、その最小共通祖先をwとすると
uとvの距離=d_u+d_v-2d_w
第3項は常に偶数
d_uとd_vの偶奇が等しければ全体は偶数、偶奇が異なれば全体は奇数
例えば、d_iが偶数なら白に、奇数なら黒に塗るとすれば条件を満たす
"""

dq = deque([0])



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


while dq:
    now = dq.popleft()
    
    for info in g[now]:
        next = info[0]
        d = info[1]
        if dist_list[next] == -1:
            
            dist_list[next] = dist_list[now] + d
            dq.append(next)


for i in dist_list:
    if i % 2 == 0:
        print(0)
    else:
        print(1)

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

visited = [-1]*n
stack = [0]
visited[0]=0
while stack:
    z = stack.pop()
    for v,w in e[z]:
        if visited[v-1]==-1:
            stack.append(v-1)
            if w%2==0:
                visited[v-1]=visited[z]
            else:
                visited[v-1]=1-visited[z]
        else:
            continue
print(*visited,sep="\n")

Solution (Python):
from collections import deque
N=int(input())
E={i:{} for i in range(1,N+1)}

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

inf=float("inf")
Dist=[inf]*(N+1)
Q=deque([1])
Dist[1]=0
while Q:
    u=Q.popleft()
    for v in E[u]:
        if Dist[v]==inf:
            Q.append(v)
            Dist[v]=Dist[u]^E[u][v]
print("\n".join(map(str,Dist[1:])))

Solution (Python):

from collections import deque

n = int(input())
g = [list() for _ in range(n)]
visited = [True] * n
coler = [0] * n
for _ in range(1, n):
    v1, v2, w = map(int, input().split())
    v1 -= 1
    v2 -= 1
    w %= 2
    g[v1].append((v2, w))
    g[v2].append((v1, w))

q = deque([0])
visited[0] = False
while q:
    a = q.pop()
    for v, w in g[a]:
        if visited[v]:
            visited[v] = False
            coler[v] = (coler[a] + w) % 2
            q.append(v)

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

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

def f(x):
  for tmp in links[x]:
    if c[tmp[0]]<0:
      if tmp[1]%2==0:
        c[tmp[0]]=c[x]+0
      else:
        c[tmp[0]]=1-c[x]
      f(tmp[0])

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

print(*c[1:], sep='\n')

Solution (Python):
import sys
input = sys.stdin.readline
from collections import deque
N = int(input())
lis = [[] for i in range(N)]
for i in range(N-1):
    a,b,w = map(int,input().split())
    lis[a-1].append((b-1,w%2))
    lis[b-1].append((a-1,w%2))

flg = [True] * N
ans = [-1] * N
que = deque([ (0,0) ])

ans[0] = 0
flg[0] = False
while len(que) != 0:
    p = que.popleft()
    
    for i in lis[p[0]]:
        if flg[i[0]] == True:
            que.append(i)
            flg[i[0]] = False
            if i[1] == 0:
                ans[i[0]] = ans[p[0]]
            else:
                if ans[p[0]] == 1:
                    ans[i[0]] = 0
                else:
                    ans[i[0]] = 1
for i in ans:
    print(i)

Solution (Python):





class Graph():

    def __init__(self):
        self.adjacency_dict = {}
        self.weight = []
    
    def add_vertex(self, v):
        self.adjacency_dict[v] = []
        self.weight.append([])

    def add_edge(self, v1, v2, w):
        self.adjacency_dict[v1].append(v2)
        self.adjacency_dict[v2].append(v1)
        self.weight[v1].append(w)
        self.weight[v2].append(w)

    def get_vertexes(self):
        return self.adjacency_dict.keys()

    def get_edges(self, v):
        return self.adjacency_dict[v], self.weight[v]

    def print_graph(self):
        print(self.adjacency_dict)

n = int(input())

res = []
g = Graph()
for i in range(n):
    res.append(-1)
    g.add_vertex(i)

for i in range(n-1):
    u, v, w = map(int, input().strip().split())
    g.add_edge(u-1, v-1, w % 2)

q = []
res[0] = 0
q.append(0)
while(len(q) > 0):
    v = q.pop()
    u_l, w_l = g.get_edges(v)
    for u, w in zip(u_l, w_l):
        if res[u] != -1:
            continue
        res[u] = (res[v] + w) % 2
        q.append(u)

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

Solution (Python):
from collections import defaultdict, deque

N = int(input())
dic = defaultdict(list)
color = [-1]*N

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

queue = deque()
color[0]=0
for i in dic[1]:
    queue.append(i)

while queue:
    u, v, w =map(int, queue.popleft())
    if (color[u-1]+w)%2==0:
        color[v-1]=0
    else:
        color[v-1]=1
    for i in dic[v]:
        if color[i[1]-1]==-1:
            queue.append(i)
print(*color)

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


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



import sys
sys.setrecursionlimit(10**7)


colors=[0 for i in range(n)]
def search(v,color):
  colors[v]=color
  
  for to in es[v]:
    if colors[to[0]]==0 and to[1]%2==0:
      search(to[0],color)
    elif colors[to[0]]==0 and to[1]%2==1:
      search(to[0],-color)
  return colors

search(0,1)
for i in colors:
  if i==-1:
    print(0)
  else:
    print(1)

Solution (Python):
from collections import deque
n = int(input())
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])
used = [0]*n
used[0] = 1
parity = [-1]*n
parity[0] = 0
que = deque()
que.append(0)
while que:
    
    v = que.popleft()
    for nv, w in g[v]:
        if used[nv]:
            continue
        parity[nv] = (parity[v] + w)%2
        used[nv] = 1
        que.append(nv)


for i in range(n):
    print(parity[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 = [[] for i in range(n)]
ans[0].append(0)
q = [0]

while q:
  x = q.pop()
  for u, w in d[x]:
    if not ans[u]:
      buf = ans[x][0]
      if w%2==1:
        buf = (buf+1)%2
      ans[u].append(buf)
      q.append(u)
    
for i in ans:
  print(*i)

Solution (Python):
import bisect, collections, copy, heapq, itertools, math, string, sys
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = float('inf')
def I(): return int(input())
def F(): return float(input())
def SS(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LSS(): return input().split()

def resolve():
    N = I()
    G = [[] for _ in range(N)]
    for _ in range(N - 1):
        u, v, w = LI()
        G[u-1].append((v - 1, w))
        G[v-1].append((u - 1, w))

    

    ans = [-1] * N
    ans[0] = 0
    visited = [False] * N

    def dfs(c):
        visited[c] = True
        for n, w in G[c]:
            if not visited[n]:
                if w % 2 == 0:
                    ans[n] = ans[c]
                else:
                    ans[n] = 1 - ans[c]
                dfs(n)

    dfs(0)

    for i in ans:
        print(i)

if __name__ == '__main__':
    resolve()

Solution (Python):


import sys
sys.setrecursionlimit(500*500)


N = int(input())
















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

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



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

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

dfs(tree, 1)



for l in depth[1:]:
    if l % 2 == 0:
        print(1)
    else:
        print(0)

Solution (Python):
N = int(input())
data = [[] for _ in range(N)]
for _ in range(N-1):
    p, q, w = map(int, input().split())
    p -= 1
    q -= 1
    data[p].append((q,w))
    data[q].append((p,w))

colors = [0]*N
visited = [0]*N
start = 0
next_set = [start]
while next_set:
    p = next_set.pop()
    visited[p] = 1
    color = colors[p]
    for q, w in data[p]:
        if visited[q]:
            continue
        colors[q] = (color + w%2)%2
        next_set.append(q)
print(*colors, sep="\n")

Solution (Python):
import heapq
inf=float("inf")


def prim():
    color=["white" for _ in range(n+1)]
    D=[inf for _ in range(n+1)]
    M=[[] for _ in range(n+1)]

    for u,v,w in UVW:
        M[u].append([w,v])
        M[v].append([w,u])

    queue=[[0,1]]
    heapq.heapify(queue)
    color[1]="gray"
    D[1]=1

    while len(queue)>0:
        num=heapq.heappop(queue)[1]
        if color[num]=="black":continue
        color[num]="black"

        for i,j in M[num]:
            if D[j]>i and color[j]!="black":
                if i%2==0:D[j]=D[num]
                else:D[j]=-D[num]
                color[j]="gray"
                heapq.heappush(queue,[i,j])

    return D[1:]


n=int(input())
UVW=[list(map(int,input().split())) for _ in range(n-1)]
for i in prim():
    if i==1:print(i)
    else:print(0)

Solution (Python):
import _heapq
inf=float("inf")


def prim():
    color=["white" for _ in range(n+1)]
    D=[inf for _ in range(n+1)]
    M=[[] for _ in range(n+1)]

    for u,v,w in UVW:
        M[u].append([w,v])
        M[v].append([w,u])

    queue=[[0,1]]
    _heapq.heapify(queue)
    color[1]="gray"
    D[1]=1

    while len(queue)>0:
        num=_heapq.heappop(queue)[1]
        if color[num]=="black":continue
        color[num]="black"

        for i,j in M[num]:
            if D[j]>i and color[j]!="black":
                if i%2==0:D[j]=D[num]
                else:D[j]=-D[num]
                color[j]="gray"
                _heapq.heappush(queue,[i,j])

    return D[1:]


n=int(input())
UVW=[list(map(int,input().split())) for _ in range(n-1)]
for i in prim():
    if i==1:print(i)
    else:print(0)

Solution (Python):


"""
Created on Sat Aug 15 08:50:44 2020

@author: naoki
"""
from collections import deque

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

routes = [[] for _ in range(N)]
for uvw in uvws:
    u = uvw[0]-1
    v = uvw[1]-1
    w = uvw[2]
    
    routes[u].append([v,w])
    routes[v].append([u,w])
    
    
colors = [-1 for _ in range(N)]
todo = deque()
todo.append(0)
colors[0] = 0


while len(todo)>0:
    checking = todo.pop()
    for route in routes[checking]:
        destination = route[0]
        weight = route[1]
        
        if colors[destination] == -1:
            if weight%2 == 0:
                colors[destination] = colors[checking]
            else:
                colors[destination] = 1 - colors[checking]
            todo.append(destination)

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

Solution (Python):
N=int(input())
tree=[[] for i in range(N)]
for i 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))
h=[]
h.append(0)
distance=[-1 for i in range(N)]
distance[0]=0
while h:
  k=h.pop(0)
  for v in tree[k]:
    x=v[0]
    y=v[1]
    if distance[x]==-1:
      distance[x]=distance[k]+y
      h.append(x)
for i in range(N):
  if distance[i]%2==0:
    print(0)
  else:
    print(1)

Solution (Python):
def main():
    N = int(input())
    G = [[] for _ in range(N)]
    for _ in range(N-1):
        a, b, c = (int(i) for i in input().split())
        G[a-1].append((b-1, c % 2))
        G[b-1].append((a-1, c % 2))

    color = [-1]*N

    def dfs(s):
        seen = [False]*N
        stack = [s]
        seen[s] = True
        color[0] = 0
        while stack:
            v = stack.pop()
            for u, dist in G[v]:
                if seen[u]:
                    continue
                if dist == 1:
                    color[u] = color[v] ^ 1
                else:
                    color[u] = color[v]
                stack.append(u)
                seen[u] = True

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


if __name__ == '__main__':
    main()

Solution (Python):
import sys
def input(): return sys.stdin.readline().rstrip()
def ii(): return int(input())
def mi(): return map(int, input().split())
def li(): return list(mi())

from collections import deque
def main():
    n = ii()
    edge = [[] for _ in range(n)]
    for i in range(n-1):
        u, v, w = mi()
        u -= 1
        v -= 1
        edge[u].append((v, w))
        edge[v].append((u, w))
    dist = [0]*n
    parent = [-1]*n
    que = deque([0])
    while que:
        v = que.pop()
        for nv, nx in edge[v]:
            if parent[v] == nv:
                continue
            parent[nv] = v
            dist[nv] = dist[v]+nx%2
            dist[nv]%= 2
            que.append(nv)
    print(*dist, sep='\n')
    


if __name__ == '__main__':
    main()

Solution (Python):
import sys
from collections import deque

input = sys.stdin.readline


def main():
    N = int(input())
    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))

    ans = [-1] * N
    ans[0] = 0
    stack = deque([(-1, 0)])
    while stack:
        p, u = stack.pop()
        for v, w in G[u]:
            if v == p:
                continue
            if w % 2 == 0:
                ans[v] = ans[u]
            else:
                ans[v] = (ans[u] + 1) % 2
            stack.append((u, v))

    print("\n".join(map(str, ans)))


if __name__ == "__main__":
    main()

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

def bfs():
    q = deque([0])
    dist = [-1]*N
    dist[0] = 0
    
    while q:
        v = q.popleft()
        
        for nv, w in G[v]:
            if dist[nv]==-1:
                dist[nv] = dist[v]+w
                q.append(nv)
        
    return dist

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))

dist = bfs()
ans = [0]*N

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

for ans_i in ans:
    print(ans_i)