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):
"""
dfs活用問題
- 2部グラフ作成
- https://atcoder.jp/contests/abc126/tasks/abc126_d
"""
from collections import deque
import sys
sys.setrecursionlimit(10 ** 9)

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


def dfs_recursive(n, graph):
    def dfs(graph, colors, cur, depth):
        colors[cur] = depth % 2
        for child in graph[cur]:
            child_index = child[0]
            if -1 != colors[child_index]:
                continue
            dfs(graph, colors, child_index, depth + child[1])
    colors = [-1 for _ in range(n)]
    dfs(graph, colors, 0, 0)
    for i in colors:
        print(i)


def dfs_with_queue(n, grpah):
    q = deque()
    ans = [-1 for _ in range(n)]
    q.append(0)
    ans[0] = 0
    while 0 != len(q):
        v = q.popleft()
        for neigbhor in graph[v]:
            u = neigbhor[0]
            w = neigbhor[1]
            if -1 != ans[u]:
                continue
            ans[u] = (ans[v] + w) % 2
            q.append(u)
        for i in ans:
            print(i)


dfs_recursive(n, graph)

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


q = deque()
ans = [-1 for _ in range(n)]
q.append(0)
ans[0] = 0
while 0 != len(q):
    v = q.popleft()
    for neigbhor in graph[v]:
        u = neigbhor[0]
        w = neigbhor[1]
        if -1 != ans[u]:
            continue
        ans[u] = (ans[v] + w) % 2
        q.append(u)

for i in ans:
    print(i)

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

input = sys.stdin.readline

def main():
    INF = float('inf')
    N = int(input())
    dist = [INF] * N
    visited = [False] * N
    
    E = [[] for i in range(N)]
    V = None
    
    for i 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))
        
        if V is None: V = u-1
    
    q = E[V]
    heapify(q)
    dist[V] = 0
    visited[V] = True
    
    while q:
        v, w = heappop(q)
    
        if visited[v]: continue
    
        visited[v] = True
        dist[v] = w
        
        for u, c in E[v]:
            if visited[u] or dist[u] <= w+c: continue
            heappush(q, (u, w+c))
            
    for d in dist:
        if d % 2: print(0)
        else: print(1)

if __name__ == '__main__':
    main()

Solution (Python):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
from bisect import bisect_left
import heapq

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N = INT()
uvw = [LIST() for _ in range(N-1)]

graph = defaultdict(list)
for u, v, w in uvw:
	graph[u-1].append((v-1, w))
	graph[v-1].append((u-1, w))


color = [0] *  N
color[0] = 1
def DFS(node):
	for i, w in graph[node]:
		if not color[i]:
			if w % 2 == 0:
				color[i] = color[node]
			else:
				color[i] = color[node] * (-1)
			DFS(i)

DFS(0)
for c in color:
	if c == 1:
		print(0)
	elif c == -1:
		print(1)
	else:
		print("HOGE")

Solution (Python):
n = int(input())
T = [[] for _ in range(n+1)]
todo = []
seen = [-1 for _ in range(n+1)]
for i in range(n-1):
    u, v, w = [int(_) for _ in input().split()]
    T[u].append((v, w))
    T[v].append((u, w))
seen[1] = 1
todo.append(1)
while len(todo) != 0:
    t = todo.pop()
    for j in T[t]:
        v = j[0]
        w = j[1]
        color = seen[t]
        if seen[v] == -1:
            todo.append(v)
            if w % 2 == 0:
                seen[v] = color
            else:
                seen[v] = (color + 1) % 2
        else:
            continue
for i in range(1, n+1):
    print(seen[i])

Solution (Python):

import sys
sys.setrecursionlimit(20000000)

def dfs(node,distance):
    for next_node,edge_distangce in G[node]:
        if ans[next_node]==-1:
            ans[next_node] = (distance+edge_distangce)%2
            dfs(next_node,distance+edge_distangce)

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

ans = [-1]*N
dfs(0,0)
print(*ans,sep='\n')

Solution (Python):
N = int(input())
keirolist = [tuple(map(int, input().split())) for i in range(N-1)]

graph = [[] for _ in range(N+1)]
for (u, v, w) in keirolist:
  graph[u].append([v, w])
  graph[v].append([u, w])

root = 1
dist = [-1 for _ in range(N+1)]
dist[root] = 0

stack = [root]
while stack:
  idx = stack.pop()
  for i, w in graph[idx]:
    if dist[i] == -1:
      dist[i] = dist[idx] + w
      stack.append(i)

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

Solution (Python):
N = int(input())
graph = [[] for _ in range(N)]
for i 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])


root = 0
distances = [-1 for _ in range(N)]
distances[0] = 0

stack = [root]

while len(stack) != 0:
    src = stack.pop()
    for dst, w in graph[src]:
        if distances[dst] == -1:
            distances[dst] = distances[src] + w
            stack.append(dst)


root_color = 0
another_color = 1

for d in distances:
    if d%2==0: print(root_color)
    else: print(another_color)

Solution (Python):
import sys
import collections


def solve():
    readline = sys.stdin.buffer.readline
    mod = 10 ** 9 + 7
    tmd = collections.defaultdict(list)
    n = int(readline())
    start = -1
    cql = collections.defaultdict(int)
    for i in range(n-1):
        tma, tmb, tmc = list(map(int, input().rstrip('\n').split()))
        tmd[tma-1] += [tmb-1]
        cql[tma-1, tmb-1] = tmc
        tmd[tmb-1] += [tma-1]
        cql[tmb-1, tma-1] = tmc
        if start == -1:
            start = tma - 1

    ql = [[0, start]]
    ql = collections.deque(ql)
    fq = collections.defaultdict(int)
    fq[start]
    while True:
        if len(ql) != 0:
            cost, tmp = ql.popleft()
            for tmv in tmd[tmp]:
                if tmv not in fq:
                    ql.append([cost + cql[tmv, tmp], tmv])
                    fq[tmv] = (cost + cql[tmv, tmp]) % 2
        else:
            break
    for i in range(n):
        print(fq[i])


if __name__ == '__main__':
    solve()

Solution (Python):



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

root = 0
distances = [-1 for _ in range(N)]
distances[root] = 0

stack = [root]
while len(stack) != 0:
    src = stack.pop()
    for dst, w in graph[src]:
        if distances[dst] == -1:
            distances[dst] = distances[src] + w
            stack.append(dst)



root_color = 0
another_color = 1
for d in distances:
    if d % 2 == 0:
        print(root_color)
    else:
        print(another_color)

Solution (Python):
import math

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    
    return divisors







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


queue = []    
for i in range(n+1):
    if(len(nlist[i])==1):
        queue.append([-1,i])
        break
        

searched = 0
color=[-1 for i in range(n+1)]
nowcol=0


color[queue[0][1]]=nowcol
queue.append([queue[0][1],nlist[queue[0][1]][0][0]])
if(nlist[queue[0][1]][0][1]%2==0):
    color[nlist[queue[0][1]][0][0]]=nowcol
else:
    nowcol=1-nowcol
    color[nlist[queue[0][1]][0][0]]=nowcol
searched+=1
    
while(True):
    nowpos = queue[searched][1]
    
    
    for k in nlist[nowpos]:
        if(k[0]!=queue[searched][0]):
            queue.append([nowpos,k[0]])
            
            if(k[1]%2==0):
                color[k[0]]=color[nowpos]
                
            else:
                color[k[0]]=1-color[nowpos]
                
    searched+=1
    if(len(queue)==searched):
        break
print()
for i in range(n):
    print(color[i+1])

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

def dfs(node, distance):
    for next_node, edge_size in G[node]:
        if ans[next_node] == -1:
            ans[next_node] = ((distance + edge_size) % 2)
            dfs(next_node, distance + edge_size)

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

ans = [-1] * N
dfs(0, 0)
print(*ans, sep='\n')

Solution (Python):
from collections import deque

n = int(input())
uvw = [list(map(int, input().split())) for i in range(n-1)]
tree = [list() for i in range(n)]
queue = deque([0])
ans = [0] + [-1] * (n-1)
for u,v,w in uvw:
  u -= 1
  v -= 1
  w %= 2
  tree[u].append((v,w))
  tree[v].append((u,w))
while len(queue):
  i = queue.popleft()
  for NEXT,w in tree[i]:
    if ans[NEXT] == -1:
      if w % 2:
        ans[NEXT] = 1 if ans[i] == 0 else 0
      else:
        ans[NEXT] = ans[i]
      queue.append(NEXT)
print(*ans, sep="\n")

Solution (Python):
from collections import deque


def main():
    
    WHITE = 0
    EDGE = 0
    WEIGHT = 1
    N = int(input())
    graph = [[] for i in range(N+1)]
    colors = [-1] * (N + 1)

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

    q = deque()
    q.append(1)
    colors[1] = WHITE
    visited = [False] * (N + 1)
    while len(q) != 0:
        parentIdx = q.popleft()
        parent = graph[parentIdx]
        
        for v, e in enumerate(parent):
            if not visited[e[EDGE]]:
                q.append(e[EDGE])
                visited[e[EDGE]] = True
                if e[WEIGHT] % 2 == 0:
                    colors[e[EDGE]] = colors[parentIdx]
                else:
                    colors[e[EDGE]] = 1 - colors[parentIdx]
                

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


if __name__ == '__main__':
    main()

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

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

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

    es[u-1].append((v-1,w))
    es[v-1].append((u-1,w))

ans = [-1] * N

ans[0] = 0

queue = [0]

while len(queue) > 0:
    next_queue = []
    for curr in queue:
        for next,w in es[curr]:
            if ans[next] == -1:
                    next_queue.append(next)
                    if w % 2 == 0:
                        ans[next] = ans[curr]
                    else:
                        ans[next] = 1 if ans[curr] == 0 else 0

    if len(next_queue) > 0:
        queue = next_queue
    else:
        queue = []

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

Solution (Python):
from collections import deque

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

fromzero = [0]*n

res = [0]*n
q = deque([0])
visited = [0]*n; visited[0] = 1
while q :
    now = q.popleft()
    for nxt, c in g[now] :
        if visited[nxt] : continue
        visited[nxt] = 1
        fromzero[nxt] = fromzero[now] + c
        d = fromzero[nxt]
        res[nxt] = (d % 2)
        q.append(nxt)

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

Solution (Python):
from collections import Counter,defaultdict,deque
import sys,bisect,math,itertools,string,queue,copy
from heapq import heappop, heappush
input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7

def inp(): 
    return int(input())
def inpm(): 
    return map(int,input().split())
def inpl(): 
    return list(map(int, input().split()))
def inpls(): 
    return list(input().split())
def inplm(n): 
    return list(int(input()) for _ in range(n))
def inpll(n): 
    return sorted([list(map(int, input().split())) for _ in range(n)])
def sortx(x,n,k):
    if k == 0:x.sort(key=lambda y:y[1,n])
    else:x.sort(reversed=True, key=lambda y:y[1,n])
def graph():
    n,m=inpm()
    g=[[] for _ in range(n)]
    for _ in range(n-1):
        a,b=inpm()
        a-=1
        b-=1
        g[a].append(b)
        g[b].append(a)
    return n,m,g

def graphm():
    n=inp()
    g=[[] for _ in range(n)]
    for _ in range(n-1):
        a,b,w=inpm()
        a-=1
        b-=1
        g[a].append((b,w))
        g[b].append((a,w))
    return n,g

def main():
    n,g=graphm()
    que=[0]
    ans=[-1 for _ in range(n)]
    ans[0]=0
    while len(que)>0:
        x=que.pop(0)
        for i in range(len(g[x])):
            go=g[x][i][0]
            if ans[go]==-1:
                que.append(go)
                if g[x][i][1]%2==0:
                    ans[go]=ans[x]
                else:
                    ans[go]=1-ans[x]
    print(*ans)

if __name__ == "__main__":
    main()

Solution (Python):
from collections import Counter,defaultdict,deque
import sys,bisect,math,itertools,string,queue,copy
from heapq import heappop, heappush
input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7

def inp(): 
    return int(input())
def inpm(): 
    return map(int,input().split())
def inpl(): 
    return list(map(int, input().split()))
def inpls(): 
    return list(input().split())
def inplm(n): 
    return list(int(input()) for _ in range(n))
def inpll(n): 
    return sorted([list(map(int, input().split())) for _ in range(n)])
def sortx(x,n,k):
    if k == 0:x.sort(key=lambda y:y[1,n])
    else:x.sort(reversed=True, key=lambda y:y[1,n])
def graph():
    n,m=inpm()
    g=[[] for _ in range(n)]
    for _ in range(n-1):
        a,b=inpm()
        a-=1
        b-=1
        g[a].append(b)
        g[b].append(a)
    return n,m,g

def graphm():
    n=inp()
    g=[[] for _ in range(n)]
    for _ in range(n-1):
        a,b,w=inpm()
        a-=1
        b-=1
        g[a].append([b,w])
        g[b].append([a,w])
    return n,g

def main():
    n,g=graphm()
    que=[0]
    ans=[-1 for _ in range(n)]
    ans[0]=0
    while len(que)>0:
        x=que.pop(0)
        for i in range(len(g[x])):
            go=g[x][i][0]
            if ans[go]==-1:
                que.append(go)
                if g[x][i][1]%2==0:
                    ans[go]=ans[x]
                else:
                    ans[go]=1-ans[x]
    print(*ans)

if __name__ == "__main__":
    main()

Solution (Python):
N = int(input())
G = [[] for i in range(N)]

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

while len(stack) > 0:
    x = stack.pop()
    p = ans[x-1]
    g = len(G[x-1])
    for i in range(g):
        y = G[x-1][i][0]
        z = G[x-1][i][1]
        a = ans[y-1]
        if a == -1:
            stack.append(y)
            if z == 0:
                ans[y-1] = p
            else:
                ans[y-1] = 1-p
for i in range(N):
    print(ans[i])

Solution (Python):
import sys
sys.setrecursionlimit(10**7)
n=int(input())
t=[[] for i in range(n)]
for i in range(n-1):
    a,b,l=map(int,input().split())
    t[a-1].append([b-1,l % 2])
    t[b-1].append([a-1,l % 2])

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

def dfs(s,l,c):
    global flag
    global t
    if l == 1:
        if c == 0:c = 1
        else:c = 0
    flag[s] = c
    for g in t[s]:
        if flag[g[0]] == -1:
            dfs(g[0],g[1],c)

dfs(0,0,0)

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

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

n = int(input())
G = [[] for _ in range(n+1)]
seen = [-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])

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

dfs(1, 0)
for i in seen[1:]:
  print(i)

Solution (Python):
from collections import deque

N = int(input())
dic = {i + 1:[] for i in range(N)}
color = [-1 for i in range(N + 1)]

for i in range(N - 1):
    f, t, d = map(int, input().split())
    dic[f].append((t, d & 1)) 
    dic[t].append((f, d & 1))

q = deque()
q.append(1)
color[1] = 0
while len(q) > 0:
    v = q.popleft()
    for t in dic[v]:
        if not color[t[0]] == -1:
            continue
        color[t[0]] = 1 - color[v] if t[1] == 1 else color[v]
        q.append(t[0])

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

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

n = int(input())

path = [[] for i in range(n)]

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

global dist
dist = [-1 for i in range(n)]
dist[0] = 0

def dfs(now):
    for v,w in path[now]:
        if dist[v] == -1:
            dist[v] = w + dist[now]
            dfs(v)
    
dfs(0)

for i in dist:
    print(i%2)

Solution (Python):
n = int(input())
con = [-1] * n
g = [[] for i in range(n)]
for i in range(n-1):
  u,v,w = map(int,input().split())
  u-=1;v-=1;w%=2
  g[u].append([v,w])
  g[v].append([u,w])
con[0] = 0
stack = [0]
while stack:
  cur = stack.pop()
  for i,j in g[cur]:
    if con[i] == -1:
      con[i] = con[cur] + j
      stack.append(i)
for i in range(n):
  print('01'[con[i]%2::2])

Solution (Python):
n=int(input())
k=[[] for _ in range(n)]
for i in range(n-1):
  a,b,c=map(int,input().split())
  k[a-1].append([b-1,c])
  k[b-1].append([a-1,c])
s=[0]*n
from collections import deque
d=deque()
d.append(0)
v=[False]*n
v[0]=True
while d:
  g=d.popleft()
  for i in k[g]:
    if v[i[0]]:
      continue
    d.append(i[0])
    v[i[0]]=True
    if i[1]%2==0:
      s[i[0]]=s[g]
    else:
      s[i[0]]=[1,0][s[g]]
for i in s:
  print(i)

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

class Node:
    def __init__(self):
        self.val = None
        self.a = []

n = int(input())
nodes = []

for i in range(n):
    nodes.append(Node())

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

root = nodes[0]
root.val = True
nodeSet = set()

def traverse(node):
    if node in nodeSet:
        return
    else:
        nodeSet.add(node)

    for pair in node.a:
        adjNode = pair[0]
        dis = pair[1]
        if dis % 2 == 0:
            adjNode.val = node.val
        else:
            adjNode.val = not node.val
        traverse(adjNode)

traverse(root)

for i in range(n):
    node = nodes[i]
    if node.val:
        print(1)
    else:
        print(0)

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

class Node:
    
    def __init__(self):
        self.val = None
        self.color = None
        self.a = []

n = int(input())
nodes = []

for i in range(n):
    nodes.append(Node())
    

for i in range(n-1):
    u, v, w = map(int, input().split())
    node1 = nodes[u-1]
    node2 = nodes[v-1]
    node1.val = u
    node2.val = v
    node1.a.append([node2, w])
    node2.a.append([node1, w])







root = nodes[0]
root.color = True
nodeSet = set()

def traverse(node, distance):
    if node in nodeSet:
        return
    else:
        nodeSet.add(node)
    
    for pair in node.a:
        adjNode = pair[0]
        dis = pair[1]
        if (distance + dis) % 2 == 0:
            adjNode.color = root.color
        else:
            adjNode.color = not root.color
        traverse(adjNode, distance + dis)

traverse(root, 0)

for i in range(n):
    node = nodes[i]
    if node.color:
        print(1)
    else:
        print(0)

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

class Node:
    
    def __init__(self):
        self.val = None
        self.color = None
        self.a = []

n = int(input())
nodes = []

for i in range(n):
    nodes.append(Node())
    

for i in range(n-1):
    u, v, w = map(int, input().split())
    node1 = nodes[u-1]
    node2 = nodes[v-1]
    node1.val = u
    node2.val = v
    node1.a.append([node2, w])
    node2.a.append([node1, w])







root = nodes[0]
root.color = True
nodeSet = set()

def traverse(node, distance):
    if node in nodeSet:
        return
    else:
        nodeSet.add(node)
    
    for pair in node.a:
        adjNode = pair[0]
        dis = pair[1]
        if (distance + dis) % 2 == 0:
            adjNode.color = root.color
        else:
            adjNode.color = not root.color
        traverse(adjNode, distance + dis)

traverse(root, 0)

for i in range(n):
    node = nodes[i]
    if node.color:
        print(1)
    else:
        print(0)

Solution (Python):
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    n=int(input())
    E=[[] for _ in range(n)]
    for _ in range(n-1):
        u,v,w=map(int,input().split())
        u-=1; v-=1; w%=2
        E[u].append((v,w))
        E[v].append((u,w))

    d=[0]*n
    def dfs(v,p):
        for nv,w in E[v]:
            if(nv==p): continue
            d[nv]=d[v]^w
            dfs(nv,v)
    dfs(0,-1)
    print(*d,sep='\n')
resolve()

Solution (Python):
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    n=int(input())
    E=[[] for _ in range(n)]
    for _ in range(n-1):
        u,v,w=map(int,input().split())
        u-=1; v-=1; w%=2
        E[u].append((v,w))
        E[v].append((u,w))

    d=[0]*n
    def dfs(v,p):
        for nv,w in E[v]:
            if(nv==p): continue
            d[nv]=d[v]^w
            dfs(nv,v)
    dfs(0,-1)
    print(*d,sep='\n')
resolve()

Solution (Python):
from collections import deque

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

dist = [-1 for _ in range(n)]
dist[0] = 0
q = deque()
q.append(0)
while q:
    v = q.popleft()
    for nv, w in edges[v]:
        if dist[nv] != -1: continue
        dist[nv] = dist[v] + w
        q.append(nv)

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

Solution (Python):
n = int(input())
A = [[] for i in range(n+1)]
CHK = [False for i in range(n+1)]
COL = [0 for i in range(n+1)]
for i in range(n-1):
  u,v,w = map(int,input().split())
  w = w%2
  A[u].append((v,w))
  A[v].append((u,w))

cnt=0
Q = [1]
while cnt<n:
  p = Q.pop()
  childs = A[p]
  for c in childs:
    u1 = c[0]
    w1 = c[1]
    if not CHK[u1]:
      Q.append(u1)
      if w1==0:
        COL[u1] = COL[p]
      else:
        COL[u1] = 0 if COL[p]==1 else 1
  CHK[p] = True
  cnt+=1
  

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

Solution (Python):
import sys
sys.setrecursionlimit(100000)
input=sys.stdin.readline
n=int(input())
visitedlist=[-1 for  i in range(n)]
kilist=[[] for i in range(n)]
anslist=[0 for i in range(n)]
searchedlist=[-1 for i in range(n)]
for i in range(n-1):
        a,b,c=map(int,input().split())
        kilist[a-1].append((b,c))
        kilist[b-1].append((a,c))
def search(i):
        searchedlist[i-1]=1
        visitedlist[i-1]=1
        flag=0
        for j in kilist[i-1]:
            if visitedlist[j[0]-1]<0:
                visitedlist[j[0]-1]=1
                flag+=1
                anslist[j[0]-1]=anslist[i-1]+j[1]
        else:
            pass

        if flag>0:    
            for k in kilist[i-1]:
                if searchedlist[k[0]-1]==-1:
                    search(k[0])
search(2)
for i in anslist:
    print(i%2)

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

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

def dfs(v, p, dist):
    ans[v] = dist % 2
    for nv, w in tree[v]:
        if nv == p: continue
        dfs(nv, v, dist + w)

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

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

n=int(input())
visitedlist=[-1 for  i in range(n)]
kilist=[[] for i in range(n)]
anslist=[0 for i in range(n)]
searchedlist=[-1 for i in range(n)]
for i in range(n-1):
        a,b,c=map(int,input().split())
        kilist[a-1].append((b,c))
        kilist[b-1].append((a,c))
def search(i):
        searchedlist[i-1]=1
        visitedlist[i-1]=1
        flag=0
        for j in kilist[i-1]:
            if visitedlist[j[0]-1]<0:
                visitedlist[j[0]-1]=1
                flag+=1
                anslist[j[0]-1]=anslist[i-1]+j[1]
        else:
            pass

        if flag>0:    
            for k in kilist[i-1]:
                if searchedlist[k[0]-1]==-1:
                    search(k[0])
search(2)
for i in anslist:
    print(i%2)

Solution (Python):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
from collections import deque
def getN():
    return int(input())
def getList():
    return list(map(int, input().split()))
import math
from collections import deque

n = getN()
tree = [[] for i in range(n)]
visited = [0 for i in range(n)]
color = [0 for i in range(n)]

for i in range(n-1):
    a, b, c = getList()
    tree[a-1].append((b-1, c))
    tree[b-1].append((a-1, c))

for i, vert in enumerate(tree):
    if len(vert) == 1:
        root = i
        break

deq = deque()
deq.append(root)

while(len(deq) != 0):
    cur = deq.pop()
    for (target, dist) in tree[cur]:
        if visited[target] == 0:
            color[target] = (color[cur] + dist) % 2
            visited[target] = 1

            deq.append(target)



for c in color:
    print(c)

Solution (Python):
import sys
def dfs(n,c):
    if Ans[n] == -1:
        Ans[n] = c
        for m,w in Data[n]:
            if w % 2 == 0:
                dfs(m,c)
            else:
                dfs(m,1-c)
    elif Ans[n] == c:
        return
    else:
        return

sys.setrecursionlimit(100000)
N = int(input())
Data = []
Ans  = [-1] * N
for i in range(N):
    Data.append([])
for i in range(N-1):
    u,v,w = map(int,input().split())
    Data[u-1].append([v-1,w])
    Data[v-1].append([u-1,w])
dfs(0,0)

for a in Ans:
    print(a)

Solution (Python):


MOD = 10 ** 9 + 7

n = int(input())

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

dist = [-1] * n
dist[0] = 0
que = [0]
while len(que) != 0:
    i = que.pop()
    for j, w in graph[i]:
        if dist[j] == -1:
            dist[j] = dist[i] + w
            que.append(j)

for d in dist:
    print(d % 2)

Solution (Python):

import sys

def solve(N: int, u: "List[int]", v: "List[int]", w: "List[int]"):
    stack = [u[0]-1]
    answer = [-1]*N
    tree = [{} for _ in range(N)]
    for i in range(N-1):
        is_even = (w[i] % 2 == 0)
        tree[u[i]-1][v[i]-1] = is_even
        tree[v[i]-1][u[i]-1] = is_even
    answer[u[0]-1]=0
    
    while stack:
        p = stack.pop()
        neighbors = tree[p]
        for n in neighbors:
            if answer[n]<0:
                answer[n] = answer[p] if neighbors[n] else 1-answer[p]
                stack.append(n)

    for a in answer:
        print(a)
    return



def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  
    u = [int()] * (N - 1)  
    v = [int()] * (N - 1)  
    w = [int()] * (N - 1)  
    for i in range(N - 1):
        u[i] = int(next(tokens))
        v[i] = int(next(tokens))
        w[i] = int(next(tokens))
    solve(N, u, v, w)

if __name__ == '__main__':
    main()

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

visited = [0]* n
visited[0] = 1
ans = [0]*n
start_vertexes = [0]
 
while start_vertexes:
    start_vertex = start_vertexes.pop()
    for to, dist in to_dist[start_vertex]:
        if visited[to]: continue
        ans[to] = (ans[start_vertex]+dist)%2
        visited[to] = 1
        start_vertexes.append(to)
print(*ans, sep='\n')

Solution (Python):
n = int(input())
bw = [0] * (n + 1)
uvw = [[] for _ in range (n+1)]

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



nxt = [1]
bw[1] = 1

while len(nxt) != 0:
  cur = nxt.pop()
  while len(uvw[cur]) > 0:
    tmp = uvw[cur].pop()
    if tmp[1] % 2 == 0:
      jdg = 1
    else:
      jdg = -1

    if bw[tmp[0]] == 0:

      bw[tmp[0]] = bw[cur] * jdg
      nxt.append(tmp[0])

for i in range(1,n+1):
  if bw[i] == -1:
    print('0')
  else:
    print('1')

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

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

d = [-1] * N
d[0] = 0
q = [0]
while q:
    p = q.pop()
    for n, w in link[p]:
        if d[n] == -1:
            d[n] = d[p] + w
            q.append(n)

for i in d:
    print(i % 2)