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

input = sys.stdin.readline
N = int(input())
uvw = [list(map(int, input().split())) for _ in range(N - 1)]
g = [[] for _ in range(N)]
for a, b, w in uvw:
    g[a-1].append((b-1, w))
    g[b - 1].append((a - 1, w))

children = [[] for _ in range(N)]
colors = [None]*N
q = [(0, None, 0)]  
while len(q) > 0:
    v, p, c = q.pop()
    colors[v] = c
    for u, w in g[v]:
        if u != p:
            c_ = (c+(w%2))%2
            q.append((u, v, c_))
            children[v].append(u)
for c in colors:
    print(c)

Solution (Python):
from collections import deque

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

colors = [-1 for _ in range(N)]
stack = deque()
stack.append(0)
colors[0] = 0

while stack:
    n = stack.popleft()
    for _next, w in graph[n]:
        if colors[_next] != -1:
            continue
        colors[_next] = (colors[n] + w) % 2
        stack.append(_next)

for c in colors:
    print(c)

Solution (Python):
from collections import deque

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

q = deque([0])
while q:
    now = q.popleft()
    for nxt, w in ki[now]:
        if f[nxt]:
            continue
        if w&1:
            c[nxt] = c[now]^1
        else:
            c[nxt] = c[now]
        q.append(nxt)
        f[nxt] = True


for a in c:
    print(a)

Solution (Python):
import sys



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


def input_int():
    return int(input())


def input_int_list():
    return [int(i) for i in input().split()]


def main():
    from collections import defaultdict, deque
    n = input_int()
    G = defaultdict(dict)
    color = [None] * (n + 1)
    for _ in range(n - 1):
        u, v, w = input_int_list()
        G[u][v] = w
        G[v][u] = w

    
    color[1] = 0
    dq = deque()
    dq.append((1, 0))  
    while dq:
        u, cur = dq.popleft()
        for v, cost in G[u].items():
            if color[v] is None:
                if (cur + cost) % 2 == 0:
                    color[v] = 0
                else:
                    color[v] = 1
                dq.append((v, cur + cost))
    for c in color[1:]:
        print(c)

    return


if __name__ == "__main__":
    main()

Solution (Python):
n=int(input())
col=[-1]*n
e=[[[],[]]for i in range(n)]
for i in range(n-1):
    u,v,w=map(int,input().split())
    u-=1
    v-=1
    w%=2
    e[u][w].append(v)
    e[v][w].append(u)
col[0]=1
from collections import deque
dq=deque([])

dq.append(0)
while dq:
    a=dq.pop()
    b=col[a]
    for i in range(2):
        for ne in e[a][i]:
            if col[ne]==-1:
                col[ne]=b^i
                dq.appendleft(ne)
print(*col,sep='\n')

Solution (Python):

import sys


sysread = sys.stdin.buffer.readline
read = sys.stdin.buffer.read
printout = sys.stdout.write
sprint = sys.stdout.flush


sys.setrecursionlimit(10 ** 7)





from collections import deque



INF = 1 << 50
EPS = 1e-8
mod = 998244353


def intread():
    return int(sysread())
def mapline(t=int):
    return map(t, sysread().split())
def mapread(t=int):
    return map(t, read().split())

def dfs(c, num, to, cols):
    for n, nw in to[c]:
        if cols[n] == -1:
            y = (num + nw) % 2
            cols[n] = (num + nw) % 2
            dfs(n, y, to, cols)

def run():
    N = intread()
    to = [[] for _ in range(N+1)]
    for _ in range(N-1):
        u, v, w = mapline()
        to[u].append((v, w))
        to[v].append((u, w))
    cols = [-1] * (N+1)
    cols[1] = 0
    dfs(1, 0, to, cols)

    for x in cols[1:]:
        print(x)

if __name__ == "__main__":
    run()

Solution (Python):
def abc126d():
    n = int(input())
    e = [list() for _ in range(n)]
    for _ in range(n-1):
        u, v, w = map(int, input().split())
        e[u - 1].append([v - 1, w])
        e[v - 1].append([u - 1, w])
    ans = [-1] * n
    ans[0] = 0
    q = e[0].copy()
    while len(q) > 0:
        v, w = q.pop()
        
        if ans[v] != -1: continue
        elif w % 2 == 0: ans[v] = 0
        else: ans[v] = 1
        for v1, w1 in e[v]:
            if ans[v1] != -1: continue
            q.append([v1, w+w1])
    for i in ans:
        print(i)
abc126d()

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

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

def dfs(graph, queue, color):
    is_bigraph = True
    while queue:
        current = queue.pop()
        current_color = color[current]

        for _next, dist in graph[current]:
            if color[_next] != - 1:
                if color[_next] != (color[current] + dist) % 2:
                    is_bigraph = False
            else:
                color[_next] = (color[current] + dist) % 2
                queue.append(_next)

    return is_bigraph

queue = [1]
color = [-1] + [-1] * n
color[1] = 0
if not dfs(graph, queue, color):
    print('Something wrong')
    sys.exit(1)

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

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

edges = [[] for _ in range(N)]
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))

q = deque()
q.append((0, 0))
color = {}
while q:
    node, dist = q.popleft()
    if node in color:
        continue
    if dist % 2 == 0:
        color[node] = 0
    else:
        color[node] = 1
    for n_node, n_dist in edges[node]:
        q.append((n_node, dist+n_dist))

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

Solution (Python):
import sys
sys.setrecursionlimit(500*500)
n = int(input())
a = [[] for _ in range(n)]; b = [-1]*n; b[0] = 0
for i 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 dfs(A, k):
    for i in A[k]:
        if b[i[0]] == -1:
            b[i[0]] = b[k]+i[1]
            dfs(A, i[0])
dfs(a, 0)
for i in b:
    print(0) if i%2 == 0 else print(1)

Solution (Python):
import sys
sys.setrecursionlimit(1<<30)

N = int(input())
def dfs(x):
    for y in Tree[x]:
        if Parent[x] != y:
            Parent[y] = x
            distance[y] += Web[min(x,y),max(x,y)]+distance[x]
            dfs(y)
Tree = [[] for i in range(N+1)]
Parent = [0]*(N+1)
Web = dict()
for i in range(N-1):
    a,b,w = map(int,input().split())
    Tree[a].append(b)
    Tree[b].append(a)
    Web[(min(a,b),max(a,b))] = w
distance = [0]*(N+1)
dfs(1)
for i in distance[1:]:
    if i%2 == 0:
        print(1)
    else:
        print(0)

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

color=[-1]*N
que=deque([0])
color[0]=0

while que:
	p=que.popleft()
	for q, W in G[p]:
		if color[q]==-1:
			color[q]=(color[p]+W)%2
			que.append(q)
print(*color, sep="\n")

Solution (Python):
from collections import deque

N = int(input())


vlist = [[] for _ in range(N)]

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

ans = [-1] * N
q = deque()

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

while q:
    new = q.popleft()
    for node, weight in vlist[new]:
        if ans[node] != -1:
            continue
        ans[node] = (ans[new] + weight) % 2
        q.append(node)
    
for i in ans:
    print(i)

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

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

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

    ans = [-1] * n
    ans[0] = 0
    todo = [0]
    while len(todo) > 0:
        parent = todo.pop(-1)
        color = ans[parent]

        for child, w in edges[parent]:
            if ans[child] == -1:
                if w == 0:
                    ans[child] = color
                else:
                    ans[child] = 1 - color
                todo.append(child)

    for i in ans:
        print(i)

main()

Solution (Python):
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))

from collections import deque

que = deque()
seen = [0] + [-1]*(n-1)
que.append(0)
while que:
    s = que.popleft()
    for v,w in g[s]:
        if seen[v] != -1:continue
        seen[v] = seen[s]^(w%2)
        que.append(v)
for i in seen:
    print(i)

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

for i in l:
    v = i[0]-1
    y = i[1]-1
    w = i[2]
    g[v].append([y,w])
    g[y].append([v,w])

seen = [0] + [-1] * (n-1)

def dfs(s):
    for k in g[s]:
        v,w = k[0],k[1]
        if seen[v]!=-1:continue
        seen[v] = seen[s]^(w%2)
        dfs(v)
        
dfs(0)

for i in seen:
    print(i)

Solution (Python):


import sys 
from heapq import heappush, heappop
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
N = int(readline())

edges = [[] for _ in range(N+1)]
INF = 10**31
dist = [INF]*(N+1) 
prev=[None]*(N+1) 
for _ in range(N-1):
  x,y,t = map(int, readline().split())
  edges[x].append((y,t))
  edges[y].append((x,t))
  
q = [(0,1)]
dist[1] = 0 
while q:
  cost, v = heappop(q)
  if dist[v] < cost:
    continue
  for vert,_cost in edges[v]:
    newcost = cost+_cost
    if newcost < dist[vert]:
      prev[vert] = v
      dist[vert] = newcost 
      heappush(q,(newcost,vert))

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

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

ans=[None for i in range(n)]
ans[0]=0
s=[0]
while s:
  ns=[]
  for i in s:
    for j in e[i][0]:
      if ans[j]!=None:
        continue
      ns.append(j)
      ans[j]=ans[i]
    for j in e[i][1]:
      if ans[j]!=None:
        continue
      ns.append(j)
      ans[j]=1-ans[i]
  s=ns
print("\n".join(map(str,ans)))

Solution (Python):
n = int(input())
explored = set()
next = [[]for _ in range(n)]

from collections import deque
for i in range(n-1):
    u, v, w= map(int, input().split())
    next[u-1].append((v-1, w%2))
    next[v-1].append((u-1, w%2))
ans = [-1] * n
exploring = deque()
next_que = deque([0])
ans[0]=0
explored.add(0)
while next_que:
    i = next_que.popleft()
    exploring.extend(next[i])
    while exploring:
        a, b = exploring.popleft()
        ans[a] = (ans[i]+b)%2
        if a not in explored:
            next_que.append(a)
        explored.add(a)

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

Solution (Python):
n = int(input())
explored = set()
next = [[]for _ in range(n)]

from collections import deque
ls = []
for i in range(n-1):
    u, v, w= map(int, input().split())
    ls.append((u-1, v-1, w%2))
    next[u-1].append((v-1, w%2))
    next[v-1].append((u-1, w%2))

ans = [-1] * n

exploring = deque()
next_que = deque([0])
ans[0]=0
explored.add(0)
while next_que:
    i = next_que.popleft()
    exploring.extend(next[i])
    while exploring:
        a, b = exploring.popleft()
        ans[a] = (ans[i]+b)%2
        list = next[a]
        if a not in explored:
            next_que.append(a)
        explored.add(a)


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

Solution (Python):
n = int(input())
explored = set()
next = [[]for _ in range(n)]

from collections import deque
ls = []
for i in range(n-1):
    u, v, w= map(int, input().split())
    ls.append((u-1, v-1, w%2))
    next[u-1].append((v-1, w%2))
    next[v-1].append((u-1, w%2))

ans = [-1] * n

exploring = deque()
next_que = deque([0])
ans[0]=0
explored.add(0)
while next_que:
    i = next_que.popleft()
    exploring.extend(next[i])
    while exploring:
        a, b = exploring.popleft()
        ans[a] = (ans[i]+b)%2
        list = next[a]
        if a not in explored:
            next_que.append(a)
        explored.add(a)


for i in ans:
    print(i)

Solution (Python):
n = int(input())
explored = set()
next = [[]for _ in range(n)]

from collections import deque
ls = []
for i in range(n-1):
    u, v, w= map(int, input().split())
    ls.append((u-1, v-1, w%2))
    next[u-1].append((v-1, w%2))
    next[v-1].append((u-1, w%2))

ans = [-1] * n

exploring = deque()
next_que = deque([0])
ans[0]=0
explored.add(0)
while next_que:
    i = next_que.popleft()
    exploring.extend(next[i])
    while exploring:
        a, b = exploring.popleft()
        ans[a] = (ans[i]+b)%2
        list = next[a]
        if a not in explored:
            next_que.append(a)
        explored.add(a)


for i in ans:
    print(i)

Solution (Python):
import sys
from sys import exit
from collections import deque
from copy import deepcopy
from bisect import bisect_left, bisect_right, insort_left, insort_right
from heapq import heapify, heappop, heappush
from itertools import product, permutations, combinations, combinations_with_replacement
from functools import reduce
from math import gcd, sin, cos, tan, asin, acos, atan, degrees, radians

sys.setrecursionlimit(10**6)
INF = 10**20
eps = 1.0e-20
MOD = 10**9+7

def lcm(x,y):
    return x*y//gcd(x,y)
def lgcd(l):
    return reduce(gcd,l)
def llcm(l):
    return reduce(lcm,l)
def powmod(n,i,mod=MOD):
    return pow(n,mod-1+i,mod) if i<0 else pow(n,i,mod)
def div2(x):
    return x.bit_length()
def div10(x):
    return len(str(x))-(x==0)
def intput():
    return int(input())
def mint():
    return map(int,input().split())
def lint():
    return list(map(int,input().split()))
def ilint():
    return int(input()), list(map(int,input().split()))
def judge(x, l=['Yes', 'No']):
    print(l[0] if x else l[1])
def lprint(l, sep='\n'):
    for x in l:
        print(x, end=sep)
def ston(c, c0='a'):
    return ord(c)-ord(c0)
def ntos(x, c0='a'):
    return chr(x+ord(c0))
class counter(dict):
    def __init__(self, *args):
        super().__init__(args)
    def add(self,x,d=1):
        self.setdefault(x,0)
        self[x] += d
    def list(self):
        l = []
        for k in self:
            l.extend([k]*self[k])
        return l
class comb():
    def __init__(self, n, mod=None):
        self.l = [1]
        self.n = n
        self.mod = mod
    def get(self,k):
        l,n,mod = self.l, self.n, self.mod
        k = n-k if k>n//2 else k
        while len(l)<=k:
            i = len(l)
            l.append(l[i-1]*(n+1-i)//i if mod==None else (l[i-1]*(n+1-i)*powmod(i,-1,mod))%mod)
        return l[k]
def pf(x,mode='counter'):
    C = counter()
    p = 2
    while x>1:
        k = 0
        while x%p==0:
            x //= p
            k += 1
        if k>0:
            C.add(p,k)
        p = p+2-(p==2) if p*p<x else x
    if mode=='counter':
        return C
    S = set([1])
    for k in C:
        T = deepcopy(S)
        for x in T:
            for i in range(1,C[k]+1):
                S.add(x*(k**i))
    if mode=='set':
        return S
    if mode=='list':
        return sorted(list(S))



N=intput()
if N==1:
    print(0)
    exit()
color=[-1]*(N+1)
cost=[-1]*(N+1)
node=[list() for _ in range(N+1)]
for _ in range(N-1):
    u,v,w=mint()
    node[u].append([v,w])
    node[v].append([u,w])
color[1]=0
cost[1]=0
q=deque([1])
while q:
    u=q.popleft()
    for v,w in node[u]:
        if color[v]<0:
            cost[v]=cost[u]+w
            color[v]=cost[v]%2
            q.append(v)
lprint(color[1:])

Solution (Python):
from collections import deque

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

q = deque()
l[0] = 0
q.append(0)
while (q):
    u = q.pop()
    for v, w in e[u]:
        if l[v] >= 0:
            continue
        if w % 2 == 0:
            l[v] = l[u]
        else:
            l[v] = 1 - l[u]
        q.append(v)

for col in l:
    print(col)

Solution (Python):
import sys, math
from collections import defaultdict, deque, Counter
from bisect import bisect_left, bisect_right
from itertools import combinations, permutations, product
from heapq import heappush, heappop
from functools import lru_cache
input = sys.stdin.readline
rs = lambda: input().strip()
ri = lambda: int(input())
rl = lambda: list(map(int, input().split()))
mat = lambda x, y, v: [[v]*y for _ in range(x)]
ten = lambda x, y, z, v: [mat(y, z, v) for _ in range(x)]
mod = 1000000007
sys.setrecursionlimit(1000000)

N = ri()
edges = defaultdict(list)
for i in range(N-1):
	u, v, w = rl()
	u, v = u-1, v-1
	edges[u].append((v,w))
	edges[v].append((u,w))

visited = {}
colors = [None] * N
colors[0] = 0
def dfs(node, prev=-1):
	if node in visited: return
	visited[node] = 1
	color = colors[node]
	for next_node, dist in edges[node]:
		if next_node == prev: continue
		if dist % 2 == 0:
			colors[next_node] = colors[node]
		else:
			colors[next_node] = int(not colors[node])
		dfs(next_node, node)
dfs(0)
for c in colors:
	print(c)

Solution (Python):
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

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

for _ in range(N-1):
    u, v, w = mapint()
    graph[u-1][v-1] = w%2
    graph[v-1][u-1] = w%2

from collections import deque
stack = deque([0])

colors = [-1]*N
colors[0] = 0
while stack:
    v = stack.pop()
    for nx in graph[v].keys():
        if colors[nx]==-1:
            w = graph[v][nx]
            colors[nx] = (colors[v]+w)%2
            stack.append(nx)

for a in colors:
    print(a)

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

N = int(readline())
G = [[] for i in range(N)]

for i in range(N - 1):
  u,v,w = map(int,readline().split())
  G[u - 1].append((v - 1, w))
  G[v - 1].append((u - 1, w))
  
color = [-1] * N
stack = []
stack.append([0, -1, 0])
while stack:
  v,parent,cost = stack.pop()
  color[v] = cost
  for child in G[v]:
    if child[0] == parent:
      continue
    stack.append([child[0], v, (cost + child[1]) % 2])

for c in color:
  print(c)

Solution (Python):
from collections import deque

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

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

ans = [0] * n
parents = [-1] * n
q = deque([0])
while q:
    a = q.pop()
    for i, j in l[a]:
        if i == parents[a]:
            continue
        parents[i] = a
        q.append(i)
        ans[i] = ans[a] if j%2 == 0 else (ans[a]+1) % 2
for i in ans:
    print(i)

Solution (Python):
import sys
from collections import deque
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

def dfs(start,n,g):
    visited = [-1]*(n+1)
    visited[start] = 0
    stack = deque([start])
    while stack:
        c_node = stack.pop()
        for neib, dist in g[c_node]:
            if visited[neib] != -1: continue
            visited[neib] = visited[c_node] + dist
            stack.append(neib)
    return visited
    

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

visited = dfs(1,N,g)
for p in visited[1:]:
    print(p%2)

Solution (Python):

icase=0
if icase==0:
    n=int(input())
    g=[[] for i in range(n)]
    for i in range(n-1):
        ui,vi,wi=map(int,input().split())
        wi=wi%2
        g[ui-1].append((vi-1,wi))
        g[vi-1].append((ui-1,wi))
elif icase==1:
    vv,e,r=4,5,0
    g = [[] for _ in range(vv)]
    g[0]=[(1,1),(2,4)]
    g[1]=[(2,2),(3,5)]
    g[2]=[(3,1)]
    n=3
    g=[[(1, 0)], [(0, 0), (2, 1)], [(1, 1)]]
elif icase==2:
    n=5
    g=[[(2, 0)], [(4, 0), (2, 0)], [(1, 0), (0, 0), (3, 0)], [(2, 0)], [(1, 0)]]

from heapq import heappop,heappush

q=[]
heappush(q,(0,0)) 

inf=float("INF")
dist=[inf]*(n)
dist[0]=0
while len(q)>0:
    dd,state = heappop(q)

    for v,dv in g[state]:

        if dist[v]>dist[state]+dv:
            dist[v]=dist[state]+dv
            heappush(q,(dist[v],v))


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

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

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

while q:
  x,y = q.pop()
  ans[x-1] = y%2 
  for g,d in G[x]:
    q+=[(g,y+d)]*(ans[g-1]<0)

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

Solution (Python):
import collections
n=int(input())
d=[2]*n
w=collections.deque()
for i in range(n-1):
    a,b,c=map(int,input().split())
    if i==0:
        d[a-1]=0
        d[b-1]=c%2
    elif d[a-1]!=2:
        d[b-1]=(d[a-1]+c%2)%2
    elif d[b-1]!=2:
        d[a-1]=(d[b-1]+c%2)%2
    else:
        w.append((a,b,c))

while len(w):
    a,b,c=w.pop()
    if d[a-1]!=2:
        d[b-1]=(d[a-1]+c%2)%2
    elif d[b-1]!=2:
        d[a-1]=(d[b-1]+c%2)%2
    else:
        w.appendleft((a,b,c))
for i in d:
    print(i)

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

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

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

color = [-1] * (n+1)
color[1] = 0
stack = [1]

while stack:
    node = stack.pop()
    for vertex, weight in tree[node]:
        if color[vertex] != -1:
            continue
        color[vertex] = (color[node] + weight) % 2
        stack.append(vertex)

print("\n".join(map(str, color[1:])))

Solution (Python):
import sys
from heapq import heappush, heappop

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N, *UVW = map(int, read().split())
    G = [[] for _ in range(N)]
    for u, v, w in zip(*[iter(UVW)] * 3):
        G[u - 1].append((v - 1, w))
        G[v - 1].append((u - 1, w))

    dist = [INF] * N
    dist[0] = 0
    hq = [(0, 0)]

    while hq:
        d, v = heappop(hq)
        if d > dist[v]:
            continue
        for nv, cost in G[v]:
            if dist[nv] > dist[v] + cost:
                dist[nv] = dist[v] + cost
                heappush(hq, (dist[nv], nv))

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

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


if __name__ == '__main__':
    main()

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

def search(nodes, searched, labels, v):
  searched[v] = 1
  label = labels[v]
  for l in nodes[v]:
    x, w = l
    if not searched[x]:
      if w %2 == 0:
        labels[x] = label
      else:
        labels[x] = (label + 1) % 2
      search(nodes, searched, labels, x)

def solve(n, nodes):
  searched = [0]*n
  labels = [None]*n
  labels[0] = 0
  search(nodes, searched, labels, 0)
  return labels

def main():
  n = int(input())
  nodes = [[] for _ in range(n)]
  for _ in range(n-1):
    v, u, w = map(int, input().split(' '))
    nodes[v-1].append((u-1,w))
    nodes[u-1].append((v-1,w))
  ans = solve(n, nodes)
  for r in ans:
    print(r)
  

if __name__=='__main__':
  main()

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


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

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


def dfs(v, color):
    for nv, w in to[v]:
        if color[nv] == -1:
            color[nv] = color[v] ^ (w % 2)
            dfs(nv, color)


def main():
    color = [-1] * N
    color[0] = 0
    dfs(0, color)
    print(*color, sep='\n')


if __name__ == "__main__":
    main()

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


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

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


def dfs(v, color):
    for nv, w in to[v]:
        if color[nv] == -1:
            if w % 2:
                color[nv] = color[v] ^ 1
            else:
                color[nv] = color[v]
            dfs(nv, color)


def main():
    color = [-1] * N
    color[0] = 0
    dfs(0, color)
    print(*color, sep='\n')


if __name__ == "__main__":
    main()

Solution (Python):


from collections import deque

INT = lambda: int(input())
INTM = lambda: map(int,input().split())
STRM = lambda: map(str,input().split())
STR = lambda: str(input())
LIST = lambda: list(map(int,input().split()))
LISTS = lambda: list(map(str,input().split()))

class Graph():
    def __init__(self, v):
        self.v = v
        self.graph = [[] for _ in range(v)]
        self.INF = 10 ** 9
    
    def addEdge(self, start, end, dist):
        self.graph[start].append((end, dist))
        self.graph[end].append((start, dist))

def do():
    n=INT()
    g=Graph(n)
    for i in range(n-1):
        u,v,d=INTM()
        u-=1
        v-=1
        g.addEdge(u,v,d)

    que=deque()
    check=[True]*n
    dists=[-1]*n
    check[0]=False
    dists[0]=0
    que.append([0,0])
    while que:
        now,dist_f=que.popleft()
        for next,dist in g.graph[now]:
            if check[next]:
                check[next]=False
                temp=dist_f+dist
                dists[next]=temp
                que.append([next,temp])

    for i in dists:
        if i%2==0:
            print(0)
        else:
            print(1)
    
if __name__=='__main__':
    do()

Solution (Python):
from collections import deque

n = int(input())

distance = [-1] * n

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

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

D = deque([0])
distance[0] = 0

while D:
    now = D.popleft()
    for i in edge[now]:
        if distance[i] == -1:
            distance[i] = (distance[now] + edge[now][i]) % 2
            D.append(i)

for i in distance:
    print(i)

Solution (Python):
from collections import deque

def bfs(s):
    global color
    q = deque()
    q.append(s)
    color[s] = 0
    while q:
        i = q.popleft()
        for g in G[i]:
            if color[g[0]] == -1:
                if g[1] % 2 == 0:
                    color[g[0]] = color[i]
                else:
                    color[g[0]] = 1 - color[i]
                q.append(g[0])
    return

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

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

for i in range(n-1):
    a, b, w = map(int, input().split())
    trees[a-1].append([b-1, w])
    trees[b-1].append([a-1, w])

color = [0 for _ in range(n)]
visited = set()

next = deque()
next.append(0)
visited.add(0)
color[0] = 1

while len(next):
    i = next.popleft()
    for j, d in trees[i]:
        if j in visited:
           continue
        if d % 2 == 0:
            color[j] = color[i]
        else:
            color[j] = color[i] * -1
        next.append(j)
        visited.add(j)

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

Solution (Python):
import heapq as hq
N = int(input())
L = [set() for _ in range(N)]
for _ in range(N-1):
    u, v, w = list(map(int, input().split()))
    u -= 1
    v -= 1
    L[u].add((w, v))
    L[v].add((w, u))


INF = float('inf')
D = [INF]*N
D[0] = 0
task = []
hq.heapify(task)
for w, v in L[0]:
    hq.heappush(task, (w, v))
while task:
    w, v = hq.heappop(task)
    
    if D[v] <= w:
        continue
    D[v] = w
    for y, x in L[v]:
        hq.heappush(task, (w+y, x))


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

Solution (Python):
from collections import deque

N = int(input())
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, w])
    conn[v].append([u, w])

q = deque([1])
d = [-1]* (N + 1)
d[1] = 0
while q:
    u = q.popleft()
    for e in conn[u]:
        v, w = e[0], e[1]
        if d[v] == -1:
            d[v] = d[u] + w
            q.append(v)

for v in range(1, N + 1):
    print(d[v] % 2)

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

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

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

color=[-1]*N
def even(v=0,col=0):
    color[v]=col
    for i in range(len(graph[v])):
        nv,nw=map(int,graph[v][i])
        if color[nv]!=-1: continue
        if nw%2==0:
            even(nv,col)
        else:
            even(nv,1-col)

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

Solution (Python):
import collections

n = int(input())
graph = [[] for i in range(n + 1)]
flag = [False for i in range(n + 1)]
for i in range(n - 1):
    u, v, w = map(int, input().split())
    graph[u].append([v, w])
    graph[v].append([u, w])
color = [None for i in range(n + 1)]
color[1] = 0
queue = collections.deque([1])
while queue:
    test = queue.popleft()
    flag[test] = True
    for i in graph[test]:
        if flag[i[0]] == True:
            continue
        queue.append(i[0])
        color[i[0]] = i[1] % 2 ^ color[test]
for i in range(n):
    print(color[i + 1])

Solution (Python):
from collections import deque
N=int(input())
visited=[-1]*N
l=[[] for i in range(N)]
for i in range(N-1):
   a,b,c=map(int,input().split())
   a-=1;b-=1
   l[a].append((b,c%2))
   l[b].append((a,c%2))
def ans(node,dis):
   visited[node]=0
   que=deque(l[node])
   while que:
      node,dis=que.popleft()
      visited[node]=dis
      for i,j in l[node]:
         if visited[i]==-1:
            visited[i]=(dis+j)%2
            que.append((i,(dis+j)%2))
ans(0,0)
for i in visited:
   print(i)