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):
n=int(input())
uvw=[list(map(int,input().split())) for _ in range(n-1)]
uvw=[[u-1,v-1,w] for u,v,w in uvw]

z=[[] for _ in range(n)]
for u,v,w in uvw:
    z[u].append([u,v,w%2==0])
    z[v].append([v,u,w%2==0])
from collections import deque
que=deque([])
res=[-1 for _ in range(n)]
res[0]=0
for t in z[0]:
    que.append(t)

visited=[False for _ in range(n)]
visited[0]=True

while que:
    u,v,w=que.pop()
    if w:
        if res[u]>=0 and res[v]<0:
            res[v]=res[u]
        elif res[v]>=0 and res[u]<0:
            res[u]=res[v]
    else:
        if res[u]==0:
            res[v]=1
        elif res[u]==1:
            res[v]=0
        elif res[v]==0:
            res[u]=1
        elif res[v]==1:
            res[u]=1
    if visited[v]==False:
        visited[v]=True
        for t in z[v]:
            que.append(t)
for t in res:
    print(t)

Solution (Python):
from collections import deque

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

que = deque(tree[1])
dist = [-1]*(n+1)
dist[1] = 0
while len(que) > 0:
    u, v, w = que.popleft()
    dist[v] = dist[u]+w
    for un, vn, wn in tree[v]:
        if dist[vn] > 0:
            pass
        else:
            que.append((un, vn, wn))
            
for d in dist[1:]:
    print(0 if d%2 == 0 else 1)

Solution (Python):
class POTENTIAL_UNION_FIND(object):
    def __init__(self, n):
        self.parent = [-1 for i in range(n)]
        self.diff_p = [0 for i in range(n)]
 
    def root(self, x): 
        if self.parent[x] < 0:
            return x
        else:
            rx = self.root(self.parent[x]) 
            self.diff_p[x] += self.diff_p[self.parent[x]] 
            self.parent[x] = rx 
            return rx
 
    def size(self,x): 
        return -self.parent[self.root(x)]

    def merge(self, x, y, dxy): 
        rx = self.root(x) 
        ry = self.root(y) 
        dxy += self.diff_p[x] - self.diff_p[y] 
        x,y=rx,ry
        if x == y:
            return False
        if self.parent[x] > self.parent[y]: 
            x,y,dxy=y,x,-dxy
        self.parent[x] += self.parent[y] 
        self.parent[y] = x 
        self.diff_p[y] = dxy 
        return True
 
    def issame(self, x, y): 
        return self.root(x) == self.root(y)
        
    def diff(self,x,y): 
        if self.root(x) == self.root(y): 
            return self.diff_p[y] - self.diff_p[x]
        else:
            return None

n=int(input())
u=POTENTIAL_UNION_FIND(n)
for i in range(n-1):
    a,b,c=map(int,input().split())
    u.merge(a-1,b-1,c)
for i in range(n):
    print(u.diff(0,i)%2)

Solution (Python):
from heapq import heappush, heappop


N = int(input())
u, v, w = (
    zip(*(map(int, input().split()) for _ in range(N - 1))) if (N - 1) else
    ((), (), ())
)


G = [{} for _ in range(N + 1)]
for x, y, c in zip(u, v, w):
    G[x][y] = c
    G[y][x] = c
INF = 10**18


def dijkstra(G, s):
    dp = [INF for _ in range(len(G))]
    q = []
    heappush(q, (0, s))
    while q:
        c, i = heappop(q)
        if dp[i] == INF:
            dp[i] = c
            for j, w in G[i].items():
                heappush(q, (c + w, j))
    return dp


dp = dijkstra(G, 1)
ans = '\n'.join(
    str(dp[i] % 2)
    for i in range(1, N + 1)
)


print(ans)

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

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

def dist(x, prev, d):
    dp[x] = d
    for i, j in edge[x]:
        if i == prev:
            continue
        if dp[i] != -1:
            continue
        dist(i, x, d + j)
    return

dist(0, -1, 0)
for i in range(n):
    if dp[i] % 2 == 0:
        print(0)
    else:
        print(1)

Solution (Python):
N = int(input())
us = []
vs = []
ws = []

for i in range(N-1):
    u,v,w = map(int, input().strip().split(" "))
    us.append(u)
    vs.append(v)
    ws.append(w)

class Node:
    def __init__(self, i):
        self.id = i
        self.friends = []
        self.color = -1
nodes = [Node(i) for i in range(N+1)]
nodes[0] = None
for u,v,w in zip(us, vs, ws):
    nodes[u].friends.append((v,w))
    nodes[v].friends.append((u,w))

nodes[1].color = 0

stack = [(1,-1)]
while len(stack):
    node_id, parent_id = stack.pop()
    node = nodes[node_id]
    node_color = node.color
    children = [(f,w) for f,w in node.friends if f != parent_id]
    for child_id, w in children:
        child_node = nodes[child_id]
        child_node.color = (node_color + w) % 2
        stack.append((child_id, node_id))

for n in nodes[1:]:
    print(n.color)

Solution (Python):
n = int(input())
li = [[] for _ in range(n+1)]
q = [(1,0)]
ans = [-1]*n

while n>1:
  s,g,c = map(int,input().split())
  li[s] += [(g,c)]
  li[g] += [(s,c)]
  n -= 1


while q:
  s,c = q.pop()
  ans[s-1] = c%2 
  for g, d in li[s]:
    q += [(g, c+d)] * (ans[g-1]<0)
print(*ans)

Solution (Python):
N = int(input())
lis = [[] for _ in range(N + 1)]
for _ in range(N - 1):
    u, v, w = map(int, input().split())
    lis[u] += [v * [-1, 1][w % 2]]
    lis[v] += [u * [-1, 1][w % 2]]
colors = [-1 for _ in range(N + 1)]

q = [1]
colors[1] = 0
while q:
    start = abs(q.pop(0))
    nodes = lis[start]
    for node in nodes:
        if colors[abs(node)] < 0:
            if node < 0:
                colors[abs(node)] = colors[start]
            else:
                colors[abs(node)] = int(colors[start] == 0)
            q.append(abs(node))

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

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

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


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

def dfs(frm):
	for ne in edges[frm]:
		if bw[ne[0]] >= 0:
			continue
		else:
			bw[ne[0]] = abs(bw[frm] - ne[1])
			dfs(ne[0])

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

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

n = int(input())
edges = [list(map(int, input().split())) for _ in range(n - 1)]
bw = [-1 for i in range(n + 1)]
bw[1] = 0

new_edges = [[] for _ in range(n + 1)]

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

def dfs(frm, now):
	for ne in new_edges[now]:
		if ne[0] == frm:
			continue
		else:
			if ne[1] % 2 == 0:
				bw[ne[0]] = bw[now]
			else:
				bw[ne[0]] = abs(1 - bw[now])
			dfs(now, ne[0])

dfs(0, 1)

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

Solution (Python):
import queue
N = int(input())
t = [[]for i in range(N)]
for _ in range(N-1):
  u,v,w = map(int,input().split())
  u,v,w = u-1,v-1,w%2
  t[u].append([v,w])
  t[v].append([u,w])
q = queue.Queue()
ans = [-1 for i in range(N)]
ans[0] = 0
q.put(0)
while not q.empty():
  v = q.get()
  for vuw in t[v]:
    u = vuw[0]
    w = vuw[1]
    if ans[u]!=-1:
      continue
    else:
      ans[u]=(ans[v]+w)%2
      q.put(u)
for a in ans:
  print(a)

Solution (Python):
from queue import Queue as queue
import numpy as np
n = int(input())
e = [[] for i in range(n + 1)]
for i in range(n - 1):
    u, v, w = map(int, input().split())
    e[u].append([v, w])
    e[v].append([u, w])

q = queue()
donelist = [0 for i in range(n + 1)]

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

for i in e[1]:
    q.put([i, False])
    donelist[1] = 1

while not q.empty():
    nx = q.get()
    donelist[nx[0][0]] = 1
    if not nx[0][1] % 2:
        ans[nx[0][0]] = nx[1]
    else:
        ans[nx[0][0]] = not nx[1]
    for i in e[nx[0][0]]:
        if donelist[i[0]]:
            continue
        q.put([i, ans[nx[0][0]]])

del ans[0]

for i in ans:
    if i:
        print(0)
    else:
        print(1)

Solution (Python):
n=int(input());e=[[]for _ in[0]*-~n];q=[(1,0)];f=[-1]*n
while n>1:v,w,c=map(int,input().split());e[v]+=(w,c),;e[w]+=(v,c),;n-=1
while q:
 v,c=q.pop();f[v-1]=c%2
 for w,d in e[v]:
  if f[w-1]<0:q+=(w,c+d),
print(*f)

Solution (Python):
import collections
n=int(input())
way=[[] for i in range(n)]
for i in range(n-1):
  u,v,w=list(map(int,input().split()))
  u-=1
  v-=1
  way[u].append((v,w))
  way[v].append((u,w))
visited=[False]*n
ans=[0]*n

q=collections.deque()
q.append(0)
while len(q)>0:
  c=q.popleft()
  visited[c]=True
  for next in way[c]:
    if not visited[next[0]]:
      ans[next[0]]=(ans[c]+next[1])%2
      q.append(next[0])
for i in ans:
  print(i)

Solution (Python):
import sys
sys.setrecursionlimit(10**6)
n = int(input())
edge = [[] for i in range(n)]
colors = [0] * n
for i in range(n-1):
    u, v, w = [int(item) for item in input().split()] 
    u -= 1
    v -= 1
    edge[u].append([v, w%2])
    edge[v].append([u, w%2])

def dfs(frm, n, d):
    for tv, tw in edge[n]:
        if tv == frm:
            continue
        else:
            td = (d + tw) % 2
            if td == 1:
                colors[tv] = 1 
            else:
                colors[tv] = 0 
            dfs(n, tv, td)
    return True

colors[0] = 0
dfs(0, 0, 0)
for item in colors:
    print(item)

Solution (Python):
from collections import deque

N = int(input())

colors = [-1] * N
trees = [{} for _ in range(N)]
for _ in range(N-1):
    u, v, w = list(map(int, input().split()))
    trees[u-1][v-1] = (w % 2 == 0)
    trees[v-1][u-1] = (w % 2 == 0)

targets = deque([0])
colors[0] = 0
while len(targets) > 0:
    target = targets.popleft()
    next_targets = trees[target]
    for next_target, is_even in next_targets.items():
        if colors[next_target] != -1:
            continue
        if is_even:
            colors[next_target] = colors[target]
        else:
            colors[next_target] = 1 - colors[target]
        targets.append(next_target)

for c in colors:
    print(c)

Solution (Python):
from collections import deque
n = int(input())
q = deque(maxlen=n-1)

for i in range(n - 1):
    a, b, c = map(int, input().split())
    q.append([a-1, b-1, c % 2])

cllist = [-1] * n
a, b, c = q.popleft()
cllist[a] = 0
cllist[b] = c
while q:
    a, b, c = q.popleft()
    if cllist[a] != -1:
        cllist[b] = (cllist[a] + c) % 2
    elif cllist[b] != -1:
        cllist[a] = (cllist[b] + c) % 2
    else:
        q.append([a, b, c])
print(*cllist)

Solution (Python):
import sys

sys.setrecursionlimit(100000)


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



ans=[]
for i in range(0,n+1):
	ans.append(-1)

_neighbors=[]
for i in range(0,n+1):
	_neighbors.append([])

for i in range(0,n-1):
	_neighbors[u[i]].append([v[i], w[i]])
	_neighbors[v[i]].append([u[i], w[i]])


def bfs(u,c):
	if ans[u] != -1:
		return

	ans[u] = c

	for vw in _neighbors[u]:
		if vw[1] == 0:
			bfs(vw[0],c)
		else:
			bfs(vw[0],1-c)

bfs(1,0)

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

Solution (Python):


from collections import deque,defaultdict


N = int(input())

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

visiting = set([0])
colors[0] = 0
while len(visiting) > 0:
  p = visiting.pop()
  for q in tree[p]:
    if colors[q] < 0:
      colors[q] = (tree[p][q]+colors[p]) % 2
      visiting.add(q)

for c in colors:
  print(c)

Solution (Python):


from collections import deque,defaultdict


N = int(input())

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

visiting = deque([0])
colors[0] = 0
while len(visiting) > 0:
  p = visiting.popleft()
  for q in tree[p]:
    if colors[q] < 0:
      colors[q] = (tree[p][q]+colors[p]) % 2
      visiting.append(q)

for c in colors:
  print(c)

Solution (Python):
import sys
import Queue

n = int(raw_input())

graph = dict()
color = [-1 for i in range(0, n)]
for i in range(0, n - 1):
    u, v, w = map(int, raw_input().split(" "))
    if (u - 1) in graph:
        graph[u - 1].append((v-1, w))
    else:
        graph[u - 1] = [(v-1, w)]

    if (v - 1) in graph:
        graph[v - 1].append((u - 1, w))
    else:
        graph[v - 1] = [(u - 1, w)]





queue = Queue.Queue()
sum = 0
next_check = 0

while sum < n:

    for i in range(next_check, n):
        if color[i] < 0:
            queue.put(i)
            color[i] = 0
            sum += 1
            next_check = i
            break

    while not queue.empty():
        current_node = queue.get()
        if current_node in graph:
            for end, weight in graph[current_node]:
                if color[end] < 0:
                    color[end] = (color[current_node] + weight % 2) % 2
                    queue.put(end)
                    sum += 1

for node in range(0, n):
    print(color[node])

Solution (Python):
from collections import deque

N = int(input())

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

visiting = deque([0])
colors[0] = 0
while len(visiting) > 0:
  n = visiting.popleft()
  neighbors = tree[n]
  for m in neighbors:
    if colors[m] < 0:
      colors[m] = colors[n] if neighbors[m] else 1 - colors[n]
      visiting.append(m)

for color in colors:
  print(color)

Solution (Python):
from collections import deque

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


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

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

dq = deque()
dq.append(0)
while dq:
    v = dq.popleft()
    for nv, cost in es[v]:
        if visited[nv] != -1: continue
        visited[nv] = (visited[v] + cost) % 2
        dq.append(nv)
print(*visited, sep='\n')

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


d = [0]+[-1 for i in range(N-1)]
stack = []
stack.append(0)
while len(stack) != 0:
    
    s = stack.pop()
    
    for x,w in connect_list[s]:
        
        if d[x] == -1:
            d[x] = d[s] + w
            stack.append(x)
        
for i in range(N):
    print(d[i]%2)

Solution (Python):

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



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


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

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

for a in ans:
    print(a)

Solution (Python):
n=int(input());e=[[]for _ in[0]*-~n];q=[(1,0)];f=[-1]*n
while n>1:v,w,c=map(int,input().split());e[v]+=(w,c),;e[w]+=(v,c),;n-=1
while q:
 v,c=q.pop();f[v-1]=c%2
 for w,d in e[v]:q+=[(w,c+d)]*(f[w-1]<0)
print(*f)

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

st = deque()
push, pop = st.appendleft, st.pop
push(0)
dist = [0]*N
cnt = [0]*N
cnt[0] = 1

while st:
    u = pop()
    for v,w in G[u]:
        if cnt[v] == 1:
            continue
        dist[v] = dist[u] + w
        push(v)
        cnt[v] = 1

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

Solution (Python):

"""
Created on Mon May 20 23:18:56 2019

@author: Yamazaki Kenichi
"""

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

import sys
sys.setrecursionlimit(10**6)

class UnionFind(object):

    def __init__(self, size):
        self.table = [-1 for _ in range(size)]

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

    def union(self, x, y):
        s1 = self.find(x)
        s2 = self.find(y)
        if s1 != s2:
            if self.table[s1] <= self.table[s2]:
                self.table[s1] += self.table[s2]
                self.table[s2] = s1
            else:
                self.table[s2] += self.table[s1]
                self.table[s1] = s2
            return True
        else:
            return False

uf = UnionFind(N*2 + 1)

for c in uvw:
    if c[2] % 2 == 0:
        uf.union(c[0],c[1])
        uf.union(c[0]+N, c[1]+N)
    else:
        uf.union(c[0]+N, c[1])
        uf.union(c[0], c[1]+N)
for i in range(N*2+1):
    uf.find(i)
tmp1,tmp2 = 0, 0
for i in range(1,N+1):
    if uf.table[i] == tmp1 or i == tmp1:
        print(1)
    elif uf.table[i] == tmp2 or i == tmp2:
        print(0)
    elif tmp1 == 0:
        tmp1 = max(uf.table[i],i)
        print(1)
    else:
        tmp2 = max(uf.table[i],i)
        print(0)

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

d = [0]+[-1 for i in range(N-1)]
stack = []
stack.append(0)
while len(stack) != 0:
    s = stack.pop()
    for x,w in connect_list[s]:
        if d[x] == -1:
            d[x] = d[s] + w
            stack.append(x)

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

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

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))
 
visited = [False]*N
def dfs(num, kyori): 
    if not visited[num]:
        visited[num] = '1' if kyori%2 == 1 else '0'
        for hen in g[num]:
            dfs(hen[0], kyori+hen[1])
    return visited
 
print('\n'.join(dfs(0,0)))

Solution (Python):
from collections import deque

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

que = deque(tree[1])
dist = [-1]*(n+1)
dist[1] = 0
while len(que) > 0:
    u, v, w = que.popleft()
    dist[v] = dist[u]+w
    for un, vn, wn in tree[v]:
        if dist[vn] > 0:
            pass
        else:
            que.append((un, vn, wn))
            
for d in dist[1:]:
    print(0 if d%2 == 0 else 1)

Solution (Python):
import sys
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def II(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def SI(): return input()
YN = lambda b: print('YES') if b else print('NO')
yn = lambda b: print('Yes') if b else print('No')


N = II()
u_li = []
v_li = []
w_li = []
for i in range(N-1):
    u, v, w = LI()
    u_li.append(u)
    v_li.append(v)
    w_li.append(w)


max_node = max(max(u_li), max(v_li))
neighbor = [[] for i in range(max_node+1)]
for i in range(N-1):
    neighbor[u_li[i]].append((v_li[i], w_li[i]))
    neighbor[v_li[i]].append((u_li[i], w_li[i]))


from collections import deque
def depth_first(neighbor, start):
    visited, stack = [False]*(N+1), deque()
    stack.append(start)
    result = [None, 0] + [None]*(N-1)
    while len(stack) > 0:
        next_node = stack.pop()
        if visited[next_node]: continue
        visited[next_node] = True
        for nei in neighbor[next_node]:
            if result[nei[0]] is not None: continue
            if nei[1]%2 == 0:
                result[nei[0]] = result[next_node]
            else:
                result[nei[0]] = (result[next_node]+1)%2
            stack.append(nei[0])
    return result

colors = depth_first(neighbor, 1)

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

Solution (Python):
from collections import deque

N = int(input())

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

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

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

q = deque([0])

while q :
    a = q.popleft()
    
    for b,w in L[a] :
        if ans[b] != -1 :
            continue
        
        ans[b] = (ans[a] + w) % 2
        q.append(b)

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

Solution (Python):
from collections import deque

N = int(input())

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

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

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

q = deque()
q.append(0)

while q :
    a = q.popleft()
    
    for b,w in L[a] :
        if ans[b] == -1 :
            ans[b] = (ans[a] + w) % 2
            q.append(b)

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

Solution (Python):
def main():
    N = int(input())
    distance = [-1 for _ in range(N)]
    edges = [[] for _ in range(N)]
    nodes = [0]
    for _ in range(N-1):
        u, v, w = map(int, input().split())
        edges[u-1].append((v-1, w))
        edges[v-1].append((u-1, w))
    distance[0] = 0
    while any(d < 0 for d in distance):
        n = nodes.pop(0)
        for edge in edges[n]:
            m, d = edge[0], edge[1]
            if distance[m] == -1:
                distance[m] = distance[n] + d
                nodes.append(m)
    for d in distance:
        print(0 if d % 2 == 0 else 1)


if __name__ == '__main__':
    main()

Solution (Python):
n=int(input());e=[[]for _ in[0]*-~n];q=[(1,0)];f=[-1]*n
while n>1:v,w,c=map(int,input().split());e[v]+=(w,c),;e[w]+=(v,c),;n-=1
while q:
 v,c=q.pop();f[v-1]=c%2
 for w,d in e[v]:q+=[(w,c+d)]*(f[w-1]<0)
print(*f)

Solution (Python):
from collections import defaultdict, deque
def inpl(): return list(map(int, input().split()))

N = int(input())
D = defaultdict(list)

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

color = [-1]*(N+1)
Q = deque()
color[1] = 0
Q.append(1)

while Q:
    u = Q.pop()
    c = color[u]
    for v, w in D[u]:
        if color[v] == -1:
            if w % 2:
                color[v] = int(not c)
            else:
                color[v] = c
            Q.append(v)

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

Solution (Python):
n=int(input());e=[[]for _ in[0]*-~n];q=[(1,0)];f=[-1]*n
while n>1:v,w,c=map(int,input().split());e[v]+=(w,c),;e[w]+=(v,c),;n-=1
while q:
 v,c=q.pop();f[v-1]=c%2
 for w,d in e[v]:
  if f[w-1]<0:q+=(w,c+d),
print(*f)

Solution (Python):
n=int(input());e=[[]for _ in[0]*-~n];q=[(1,0)];f=[-1]*n
for _ in[0]*~-n:v,w,c=map(int,input().split());e[v]+=(w,c),;e[w]+=(v,c),
while q:
 v,c=q.pop();f[v-1]=c%2
 for w,d in e[v]:
  if f[w-1]<0:q+=(w,c+d),
print(*f)

Solution (Python):
n=int(input());e=[[]for _ in[0]*-~n];q=[1];f=[0]+[-1]*~-n
for _ in[0]*~-n:v,w,c=map(int,input().split());e[v]+=(w,c),;e[w]+=(v,c),
while q:
 v=q.pop()
 for w,c in e[v]:
  if f[w-1]<0:f[w-1]=(f[v-1]+c)%2;q+=w,
print(*f)

Solution (Python):
n,*t=map(int,open(0).read().split());e=[[]for _ in[0]*n];q=[0];f=[0]+[-1]*~-n
for v,w,c in zip(t[::3],t[1::3],t[2::3]):e[v-1]+=(w-1,c),;e[w-1]+=(v-1,c),
while q:
 v=q.pop()
 for w,c in e[v]:
  if f[w]<0:f[w]=(c+f[v])%2;q+=w,
print(*f)

Solution (Python):
n,*t=map(int,open(0).read().split());e=[[]for _ in[0]*n];q=[0];f=[0]+[-1]*~-n
for v,w,c in zip(t[::3],t[1::3],t[2::3]):e[v-1]+=(w-1,c),;e[w-1]+=(v-1,c),
while q:
 v=q.pop()
 for w,c in e[v]:
  if f[w]<0:f[w]=(c+f[v])%2;q+=w,
print(*f)

Solution (Python):
n,*t=map(int,open(0).read().split())
e=[[]for _ in[0]*n]
for v,w,c in zip(t[::3],t[1::3],t[2::3]):
  e[v-1]+=(w-1,c),
  e[w-1]+=(v-1,c),
q=[0]
f=[0]+[-1]*~-n
while q:
  v=q.pop()
  for w,c in e[v]:
    if-1<f[w]:continue
    f[w]=(c+f[v])%2
    q+=w,
print(*f)

Solution (Python):
n,*t=map(int,open(0).read().split())
e=[[]for _ in range(n)]
for v,w,c in zip(t[::3],t[1::3],t[2::3]):
  e[v-1]+=(w-1,c),
  e[w-1]+=(v-1,c),
q=[(0,0)]
f=[0]+[-1]*~-n
while q:
  v,c=q.pop()
  for w,d in e[v]:
    if-1<f[w]:continue
    d=(c+d)%2
    f[w]=d
    q+=(w,d),
print(*f)

Solution (Python):
n,*t=map(int,open(0).read().split())
e=[[]for _ in range(n)]
for v,w,c in zip(t[::3],t[1::3],t[2::3]):
  e[v-1].append((w-1,c))
  e[w-1].append((v-1,c))
q=[(0,0)]
f=[0]+[-1]*~-n
while q:
  v,c=q.pop()
  for w,d in e[v]:
    if-1<f[w]:continue
    d=(c+d)%2
    f[w]=d
    q+=[(w,d)]
print(*f)

Solution (Python):
from collections import*
n,*t=map(int,open(0).read().split())
e=[[]for _ in range(n)]
for v,w,c in zip(t[::3],t[1::3],t[2::3]):
  e[v-1].append((w-1,c))
  e[w-1].append((v-1,c))
q=deque([(0,0)])
f=[0]+[-1]*~-n
while q:
  v,c=q.pop()
  for w,d in e[v]:
    if-1<f[w]:continue
    d=(c+d)%2
    f[w]=d
    q.append((w,d))
print(*f,sep='\n')

Solution (Python):
from collections import*
n,*t=map(int,open(0).read().split())
e=[[]for _ in range(n)]
for v,w,c in zip(t[::3],t[1::3],t[2::3]):
  e[v-1].append((w-1,c))
  e[w-1].append((v-1,c))
q=deque([(0,0)])
f=[0]+[-1]*~-n
while q:
  v,c=q.pop()
  for w,d in e[v]:
    if-1<f[w]:continue
    d=(c+d)%2
    f[w]=d
    q.append((w,d))
print(*f)

Solution (Python):
from collections import deque

N = int(input())
edges = {i: [] for i in range(N)}
for _ in range(N-1):
    x, y, z = map(int, input().split())
    edges[x-1].append((y-1, z%2))
    edges[y-1].append((x-1, z%2))
color = [None]*N

q = deque([(0, 0)])
while q:
    v, c = q.popleft()
    color[v] = c
    for u, w in edges[v]:
        if color[u] is None:
            if w == 0:
                q.append((u, c))
            else:
                q.append((u, c^1))
print(*color, sep='\n')

Solution (Python):
from collections import deque

N = int(input())
vw = [[] for _ in range(N)]
for i in range(N-1):
    a, b, w = map(int, input().split())
    vw[a-1].append((b-1, w))
    vw[b-1].append((a-1, w))
ans = [-1] * N
q = deque([(0, 0)])
while q:
    a, w = q.popleft()
    ans[a] = w % 2
    for b, c in vw[a]:
        if ans[b] == -1:
            q.append((b, w + c))
print("\n".join(map(str, ans)))

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

def func(num,pr):
  global l,ans

  if len(l[num])!=0:
    for z in l[num]:
      if z[0]==pr:
        continue

      if pr==-1:
        ans[z[0]]=z[1]
      else:
        ans[z[0]]=ans[num]+z[1]
      func(z[0],num)

N=int(input())
l=[ [] for z in range(N)]
ans=[0]*N


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

func(0,-1)





for z in ans:
  if z%2==0:
    print(1)
  else:
    print(0)

Solution (Python):
def main():
    n = int(input().rstrip())
    from collections import defaultdict
    
    edges = defaultdict(dict)
    for i in range(n - 1):
        a, b, distance = [int(x) for x in input().rstrip().split(" ")]
        edges[a][b] = distance
        edges[b][a] = distance

    passed = {1: 0}

    distances = {1: 0}
    candidates = [(1, 0)]
    total_distance = 0
    while candidates:
        a, total_distance = candidates.pop(0)
        for b, distance in edges[a].items():
            if not b in passed:
                distances[b] = total_distance + distance
                passed[b] = 1
                candidates.append((b, total_distance + distance))
    for number in range(1, n + 1):
        print(distances[number] % 2)


if __name__ == '__main__':
    main()

Solution (Python):
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))
ans = [-1] * (n + 1)
q = [(1, 0, 0)]
while q:
    v, d, p = q.pop()
    ans[v] = d
    for u, w in links[v]:
        if u == p:
            continue
        q.append((u, d + w, v))
print('\n'.join(map(lambda x: str(x % 2), ans[1:])))

Solution (Python):
n = int(input())
x,ans,q = [[] for i in range(n+1)],[-1]*(n+1),[]
for i in range(n-1):
    u,v,w = (int(i) for i in input().split())
    x[u].append((v,w%2))
    x[v].append((u,w%2))
for i,j in x[1]: q.append((i,1,j))
ans[1] = 0
while q:
    i,p,d = q.pop()
    ans[i] = abs(d-ans[p])
    for j,k in x[i]:
        if ans[j]==-1: q.append((j,i,k))
for i in ans[1:]: print(i)

Solution (Python):
n = int(input())
v = [list(map(int,input().split())) for _ in range(n-1)]
g = {}
for a,b,w in v:
    if a not in g:
        g[a] = []
    if b not in g:
        g[b] = []
    g[a].append([b,w])
    g[b].append([a,w])
from collections import deque
queue = deque([[1,0]])
b = [-1]*n
b[0] = 0
while queue:
    q,d = queue.popleft()
    if d%2==1:
        b[q-1] = 0
    else:
        b[q-1] = 1
    for new_q in g[q]:
        v_,d_ = new_q
        if b[v_-1]==-1:
            queue.appendleft([v_,d+d_])
for i in b:
    print(i)

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

n = int(input())
uvw = [tuple(int(x) for x in input().split()) for _ in range(n-1)]

c = [-1] * n

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

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


def f(p):
    count = 0
    for x, w in r[p]:
        if c[x] == -1:
            if w % 2 == 0:
                c[x] = c[p]
                f(x)
            else:
                c[x] = (c[p] + 1) % 2
                f(x)
            count += 1


c[0] = 0
f(0)

for x in c:
    print(x)

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

n = int(input())
uvw = [tuple(int(x) for x in input().split()) for _ in range(n-1)]

c = [-1] * n

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

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

def f(p):
    count = 0
    for x, w in r[p]:
        if c[x] == -1:
            if w % 2 == 0:
                c[x] = c[p]
                f(x)
            else:
                c[x] = (c[p] + 1) % 2
                f(x)
            count += 1
    

c[0] = 0
f(0)

for x in c:
    print(x)

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


used = [0] * N
que = deque([0])
ans = [False] * N
while que:
    
    u = que.popleft()
    for v,w in G[u]:
        if used[v]:
            
            continue
        else:
            
            
            if w%2 == 0:
                ans[v] = ans[u]
            else:
                ans[v] = not ans[u]
            
            que.append(v)
            used[u] = True
for a in ans:
    print(int(a))