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

connect_list = [ [] for i in range(n) ]
distance_list = [ -1 for i in range(n) ]
color_list = [ "Gray" for i in range(n) ]
distance_list[0] = 0

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

search_list = [0]


while search_list != []:
	s = search_list[0]
	for i in connect_list[s]:
		if distance_list[i[0]] == -1:
			distance_list[i[0]] = (distance_list[s] + i[1]) % 2
			search_list.append(i[0])
	del search_list[0]

for i in distance_list:
	print(i)

Solution (Python):

import sys
input = sys.stdin.readline

n = int(input())

connect_list = [ [] for i in range(n) ]
distance_list = [ -1 for i in range(n) ]
color_list = [ "Gray" for i in range(n) ]
distance_list[0] = 0

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

search_list = [0]


while search_list != []:
	s = search_list[0]
	for i in connect_list[s]:
		if distance_list[i[0]] == -1:
			distance_list[i[0]] = (distance_list[s] + i[1]) % 2
			search_list.append(i[0])
	del search_list[0]

for i in distance_list:
	print(i)

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

connect_list = [ [] for i in range(n) ]
distance_list = [ -1 for i in range(n) ]
color_list = [ "Gray" for i in range(n) ]
distance_list[0] = 0

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

search_list = [0]


while search_list != []:
	s = search_list[0]
	for i in connect_list[s]:
		if distance_list[i[0]] == -1:
			distance_list[i[0]] = (distance_list[s] + i[1]) % 2
			search_list.append(i[0])
	del search_list[0]

for i in distance_list:
	print(i)

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

ans = [0 for i in range(n)]
q = [[0,0,-1]]
while q:
	u,w,v = q.pop(0)
	if w%2 == 0:
		ans[u] = 0
	else:
		ans[u] = 1
	for n,ww in lines[u]:
		if n == v:
			continue
		q.append([n,w+ww,u])
	
	
for a in ans:
	print(a)

Solution (Python):
from collections import deque

n = int(input())
neighbor = {}
for _ in range(n - 1):
    u, v, w = map(int, input().split())
    if u not in neighbor:
        neighbor[u] = deque()
    if v not in neighbor:
        neighbor[v] = deque()
    neighbor[u].append((v, w))
    neighbor[v].append((u, w))

color = {1: 0}
visited = set([1])
queue = deque([(1, 0)])

while len(queue) > 0:
    v, wsum = queue.pop()
    for u, w in neighbor[v]:
        if u in visited:
            continue
        visited.add(u)
        color[u] = (wsum + w) % 2
        queue.append((u, wsum + w))

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

Solution (Python):
from collections import deque

N = int(input())

A = {}
COLOR = [1] * N

for _ in range(N - 1):
  u, v, w = map(int, input().strip().split(' '))
  if u not in A: A[u] = {}
  if v not in A: A[v] = {}
  A[u][v] = w
  A[v][u] = w


def test(key, total_w=0):
  if key not in A:
    return

  COLOR[key - 1] = 0 if total_w % 2 == 0 else 1

  v = A.pop(key)
  for k, w in v.items():
    test(k, w + total_w)


queue = deque()
queue.append((1, 0))
current_key = 1

while len(queue) > 0:
  key, w = queue.popleft()
  if key not in A:
    continue

  COLOR[key - 1] = 0 if w % 2 == 0 else 1

  for child in A.pop(key).items():
    if child[0] in A:
      queue.append((child[0], w + child[1]))

for c in COLOR:
  print(c)

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

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

colors = [None for _ in range(n+1)]
colors[1] = 0

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

for u, v, w in uvws:
    edges[u][v] = w
    edges[v][u] = w

plan = set((1,))

while len(plan) > 0:
    g = plan.pop()
    for n, w in edges[g].items():
        if colors[n] is None:
            colors[n] = (colors[g] + w) % 2
            plan.add(n)

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

Solution (Python):
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])
c = [-1] * (n-1)
color = [0] + c
x = [0]
while x:
    current = x.pop(0)
    for y, d in l[current]:
        if color[y] > -1:
            continue
        color[y] = (color[current] + d)%2
        x.append(y)
for col in color:
    print(col)

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

info = [[] for _ in range(0,n+1)]

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



frt = [1]
dis = [0] * (n+1)

while frt != []:
    x = frt.pop()
    for j in range(0,len(info[x])):
        dis[info[x][j][0]] = dis[x] + info[x][j][1]
        info[info[x][j][0]].remove([x,info[x][j][1]])
        frt.append(info[x][j][0])

for k in range(1,n+1):

    if dis[k] % 2 ==0:
        print(0)
    else:
        print(1)

Solution (Python):
class WeightedUnionFind:
    def __init__(self, size):
        """
        :param collections.Iterable nodes:
        """
        self._parents = [i for i in range(size)]
        self._ranks = [0 for _ in range(size)]
        self._sizes = [1 for _ in range(size)]
        
        self._weights = [0 for _ in range(size)]
 
    def unite(self, x, y, w):
        """
        x が属する木と y が属する木を併合
        :param x:
        :param y:
        :param w: x と y の重みの差; (重み y) - (重み x)
        :return:
        """
        rx = self.find(x)
        ry = self.find(y)
        if rx == ry:
            return
 
        
        if self._ranks[rx] > self._ranks[ry]:
            
            self._parents[ry] = rx
            self._sizes[rx] += self._sizes[ry]
            
            self._weights[ry] = w + self._weights[x] - self._weights[y]
        else:
            
            self._parents[rx] = ry
            self._sizes[ry] += self._sizes[rx]
            
            self._weights[rx] = -w + self._weights[y] - self._weights[x]
            if self._ranks[rx] == self._ranks[ry]:
                self._ranks[ry] += 1
 
    def find(self, x):
        """
        x が属する木の root
        :param x:
        :return:
        """
        if self._parents[x] == x:
            return x
        root = self.find(self._parents[x])
        self._weights[x] += self._weights[self._parents[x]]
        self._parents[x] = root
        return root
 
    def size(self, x):
        """
        x が属する木のノード数
        :param x:
        :return:
        """
        return self._sizes[self.find(x)]
 
    def weight(self, x):
        """
        :param x:
        :return:
        """
        
        self.find(x)
        return self._weights[x]
 
    def diff(self, x, y):
        """
        (y の重み) - (x の重み)
        :param x:
        :param y:
        :return:
        """
        if self.find(x) == self.find(y):
            return self._weights[y] - self._weights[x]
        return float('inf')
n=int(input())
uf=WeightedUnionFind(n)
for i in range(n-1):
    u,v,w=map(int, input().split())
    uf.unite(u-1,v-1,w)
C=[0]*n
for i in range(1,n):
    if uf.diff(i,0)%2==0:
        C[i]=0
    else:
        C[i]=1
for i in range(n):
    print(C[i])

Solution (Python):
from collections import deque
N=int(input())
uvw=list(list(map(int,input().split())) for _ in range(N-1))

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

colors=[-1]*N
colors[0]=0
queue=deque([1])

while len(queue)>0:
    x=queue.popleft()
    if all(colors[i]!=-1 for i in range(N)):
        break
    for j in graph_list[x-1]:
        if colors[j[0]-1]==-1:
            queue.append(j[0])
            colors[j[0]-1]=(2+colors[x-1]+j[1])%2
for p in colors:
    print(p)

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

def DFS(v, p ,c):
    res[v] = c
    for next in tree[v]:
        if next[0] == p:
            continue
        if next[1] % 2:
            DFS(next[0], v, 1-c)
        else:
            DFS(next[0], v, c)


n = int(input())
tree = [[] for i in range(n)]
res = [0] * n
for i in range(n-1):

    u, v, w = map(int, input().split())
    tree[u-1].append([v-1, w])
    tree[v-1].append([u-1, w])

DFS(0, -1, 1)

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

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

D = [-1 for k in range(N)]
D[G[0][0][0]] = 0
Q = [G[0][0]]

while len(Q) > 0:
    now = Q.pop()
    ima = now[0]
    for tsugi in G[ima]:
        if D[tsugi[0]] == -1:
            D[tsugi[0]] = tsugi[1] + D[ima]
            Q.append(tsugi)

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

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

sys.setrecursionlimit(10 ** 7)

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x) - 1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())


from heapq import heappush, heappop


def dijkstra(graph: list, node: int, start: int) -> list:
    
    INF = float("inf")
    dist = [INF] * node

    
    dist[start] = 0
    heap = [(0, start)]

    
    while heap:
        cost, cur_node = heappop(heap)

        for nex_cost, nex_node in graph[cur_node]:
            dist_cand = dist[cur_node] + nex_cost
            if dist_cand < dist[nex_node]:
                dist[nex_node] = dist_cand
                heappush(heap, (dist[nex_node], nex_node))

    return dist


n = ni()
graph = [[] for _ in range(n)]
for _ in range(n-1):
    u,v,w = li()
    u -= 1
    v -= 1

    graph[u].append((w, v))
    graph[v].append((w, u))

dist = dijkstra(graph, n, 0)

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

Solution (Python):
n = int(input())
tree = [[] for i in range(n+1)]

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


stack=[1]
visitted={}
ans=[0]*n

while stack:
    cur = stack.pop()
    pre=ans[cur-1]
    visitted.setdefault(cur,1)
    
    for v, w in tree[cur]:
        if v in visitted:
            continue
        if w % 2 == 1:
            ans[v-1]=(pre+1)%2
        else:
            ans[v-1]=pre
        stack.append(v)

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

Solution (Python):
"""
解説と提出 
"""

import sys
sys.setrecursionlimit(10 ** 6)


def solve():
    N = int(input())
    result = [-1] * N
    uvw_map = [[] for _ in range(N)]
    '''枝毎の距離相関図を作る'''
    for i in range(N - 1):
        u, v, w = map(int, input().split())
        u -= 1
        v -= 1
        uvw_map[u].append([v, w])
        uvw_map[v].append([u, w])
    
    
    
    result[0] = False
    result = paint(uvw_map, 0, result)
    for i in result:
        print(int(i))


def paint(uvw_map, num, result):
    
    num_map = uvw_map[num]
    
    nums = []
    for v, w in num_map:
        if result[v] != -1:
            continue
        result[v] = result[num] if w % 2 == 0 else not(result[num])
        
        nums.append(v)
    
    for n in nums:
        result = paint(uvw_map, n, result)
    return result


if __name__ == '__main__':
    solve()

Solution (Python):
from collections import deque

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

dist = [-1 for i in range(n)]
stack = deque([0])
while( len(stack) != 0 ):
    current = stack.popleft()
    current_dist = dist[current]

    for neibor_n, neibor_w in neibors[current]:
        if dist[neibor_n] == -1:
            stack.append( neibor_n )
            dist[neibor_n] = (neibor_w + current_dist) % 2  

for item in dist:
    print(item)

Solution (Python):
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]*n
ans[0]=0
from collections import deque
stack=deque([])
stack.append(0)
while stack:
    v=stack.popleft()
    for u, w in L[v]:
        if ans[u]!=-1:
            continue
        ans[u]=(ans[v]+w)%2
        stack.appendleft(u)
for a in ans:
    print(a)

Solution (Python):
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]*n
ans[0]=0
from collections import deque
que=deque([])
que.append(0)
while que:
    v=que.popleft()
    for u, w in L[v]:
        if ans[u]!=-1:
            continue
        ans[u]=(ans[v]+w)%2
        que.append(u)
for a in ans:
    print(a)

Solution (Python):
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]*n
ans[0]=0
from collections import deque
que=deque([])
que.append(0)
while que:
    v=que.popleft()
    for u, w in L[v]:
        if ans[u]!=-1:
            continue
        ans[u]=(ans[v]+w)%2
        que.append(u)
for a in ans:
    print(a)

Solution (Python):
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]*n
ans[0]=0
from collections import deque
stack=deque([])
stack.append(0)
while stack:
    v=stack.popleft()
    for u, w in L[v]:
        if ans[u]!=-1:
            continue
        ans[u]=(ans[v]+w)%2
        stack.appendleft(u)
for a in ans:
    print(a)

Solution (Python):
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]*n
ans[0]=0
que=[0]
import queue
que=queue.Queue()
que.put(0)
while not que.empty():
    v=que.get()
    for u, w in L[v]:
        if ans[u]!=-1:
            continue
        ans[u]=(ans[v]+w)%2
        que.put(u)
for a in ans:
    print(a)

Solution (Python):
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]*n
ans[0]=0
stack=[0]
while stack:
    v=stack.pop()
    for u, w in L[v]:
        if ans[u]!=-1:
            continue
        ans[u]=(ans[v]+w)%2
        stack.insert(0,u)
for a in ans:
    print(a)

Solution (Python):
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]*n
ans[0]=0
que=[0]
while que:
    v=que.pop()
    for u, w in L[v]:
        if ans[u]!=-1:
            continue
        ans[u]=(ans[v]+w)%2
        que.append(u)
for a in ans:
    print(a)

Solution (Python):
import sys

sys.setrecursionlimit(1000000)

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

V = [0] * N
D = [0] * N
C = [0] * N


def dfs(n, c):
    if V[n] == 1:
        return
    C[n] = c
    V[n] = 1
    for w in M[n]:
        if w[1] % 2 == 0:
            dfs(w[0], c)
        else:
            dfs(w[0], (c + 1) % 2)

dfs(0, 0)
for c in C:
    print(c)

Solution (Python):
import queue

n = int(input())
links = [set() for _ in [0] * n]
for i in range(n-1):
    u, v, w = map(int, input().split())
    u -= 1
    v -= 1
    links[u].add((v, w))
    links[v].add((u, w))
ans = [-1] * n
q = queue.Queue()
q.put((0, 0, -1))
while not q.empty():
    v, d, p = q.get()
    if d % 2 == 0:
        ans[v] = 0
    else:
        ans[v] = 1
    for u, w in links[v]:
        if u == p:
            continue
        q.put((u, d + w, v))
for i in ans:
    print(i)

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

def dfs(v, p, c):
    res[v] = c
    for next in link[v]:
        if next[0] == p:
            continue
        if next[1] % 2:
            dfs(next[0], v, 1-c)
        else:
            dfs(next[0], v, c)


N = int(input())
link = [[] * N for _ in range(N)]
res = [0] * N
for i 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])

dfs(0, -1, 1)

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

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

def dfs(v, p, c):
    
    res[v] = c
    for next in link[v]:
        if next[0] == p:
            continue
        
        if next[1] % 2:
            dfs(next[0], v, 1-c)
        
        else:
            dfs(next[0], v, c)


N = int(input())
link = [[] * N for _ in range(N)]
res = [0] * N
for i 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])
    
dfs(0, -1, 1)

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

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

def dfs(v, p, c):
    res[v] = c
    for next in link[v]:
        if next[0] == p:
            continue
        if next[1] % 2:
            dfs(next[0], v, 1-c)
        else:
            dfs(next[0], v, c)


N = int(input())
link = [[] * N for _ in range(N)]
res = [0] * N
for i 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])
    
dfs(0, -1, 1)

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

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

def dfs(v, p, c):
    res[v] = c
    for next in link[v]:
        if next[0] == p:
            continue
        if next[1] % 2:
            dfs(next[0], v, 1-c)
        else:
            dfs(next[0], v, c)


N = int(input())
link = [[]  for _ in range(N)]
res = [0] * N
for i 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])
    
dfs(0, -1, 1)

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

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


def func(v, c):
    for next_v, w in graph[v]:
        if color[next_v] == -1:
            color[next_v] = (c + w) & 1
            func(next_v, c + w) 

n = int(input())
graph = [[] for _ in range(n)]
color = [-1] * n

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


color[0] = 0
func(0, 0)

for i in color:
    print(i)

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):
import sys
sys.setrecursionlimit(20000000)

n = int(input())
g = [[] for i in range(n)]
for i in range(n-1):
    u,v,w = map(int,input().split())
    u-=1;v-=1
    g[u].append([v,w])
    g[v].append([u,w])
ans = [-1]*n
def dfs(x,y):
    for i,j in g[x]:
        if ans[i] == -1:
            ans[i] = (y+j)%2
            dfs(i,y+j)
dfs(0,0)
for i in ans:
    print(i)

Solution (Python):
N=int(input())
uvw=[list(map(int,input().split())) for _ in range(N-1)]
q=[[] for _ in range(N)]
max=10**15
dist=[0]+[max for i in range(N-1)]
for i in range(N-1):
    q[uvw[i][0]-1].append((uvw[i][1]-1,uvw[i][2]))
    q[uvw[i][1]-1].append((uvw[i][0]-1,uvw[i][2]))
now=0
now_d=0

while(True):
    if q[q[now][-1][0]]==[]:
        q[now].pop()
        if q[now]==[]:
            break
    if dist[q[now][-1][0]]!=max:
        if len(q[now])!=1:
            q[now]=[q[now][-1]]+q[now][:-1]
    posi=q[now][-1]
    if dist[posi[0]]==max:
        dist[posi[0]]=now_d+posi[1]
    now_d=dist[posi[0]]
    q[now].pop()
    now=posi[0]
    posi=q[posi[0]][0]
for i in range(N):
    if dist[i]%2==0:
        print(0)
    else:
        print(1)

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

def cur(current,e,dist,color):
    for it in e[current]:
        if color[it]!=-1: continue
        color[it]=(color[current]+dist[(it,current)])%2
        cur(it,e,dist,color)

N=int(input())
e=[[] for i in range(N+1)]
dist={}
for i in range(N-1):
    u,v,w=map(int,input().split())
    e[u].append(v)
    e[v].append(u)
    dist[(u,v)],dist[(v,u)]=w,w
memo=[-1]*N




color=[-1]*(N+1)
color[1]=0
cur(1,e,dist,color)

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

Solution (Python):
from collections import deque

N = int(input())

edge = [[] for _ in range(N)]
check = [False] * N
dist = [0] * 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))

q = deque([0])

while q :
    current = q.popleft()
    if check[current] :
        continue

    check[current] = True
    for ad , w in edge[current] :
        if not check[ad] :
            q.append(ad)
            dist[ad] = dist[current] + w

for w in dist :
    print(w % 2)

Solution (Python):

import sys
import copy
import collections
from bisect import bisect_left
from bisect import bisect_right
from collections import defaultdict
from heapq import heappop, heappush
	
def main():
	N = int(input())
	MP = Graph()
	
	for i in range(N-1):
		u, v, w = map(int, input().split(" "))
		u -= 1
		v -= 1
		if w % 2 == 0:
			MP.add_edge(u, v, 0)
			MP.add_edge(v, u, 0)
		else:
			MP.add_edge(u, v, 1)
			MP.add_edge(v, u, 1)
	
	tmp = Dijkstra(MP, 0)
	
	for i in range(N):
		if i == 0:
			print(0)
			continue
			
		tmptmp = tmp.shortest_distance(i)
		if tmptmp % 2 == 0:
			print(0)
		else:
			print(1)
			
	
	
	
class Graph(object):
    
    def __init__(self):
        self.graph = defaultdict(list)

    def __len__(self):
        return len(self.graph)

    def add_edge(self, src, dst, weight=1):
        self.graph[src].append((dst, weight))

    def get_nodes(self):
        return self.graph.keys()


class Dijkstra(object):
    
    def __init__(self, graph, start):
        self.g = graph.graph

        
        
        self.dist = defaultdict(lambda: float('inf'))
        self.dist[start] = 0

        
        self.prev = defaultdict(lambda: None)

        
        self.Q = []
        heappush(self.Q, (self.dist[start], start))

        while self.Q:
            
            dist_u, u = heappop(self.Q)
            if self.dist[u] < dist_u:
                continue
            for v, weight in self.g[u]:
                alt = dist_u + weight
                if self.dist[v] > alt:
                    self.dist[v] = alt
                    self.prev[v] = u
                    heappush(self.Q, (alt, v))

    def shortest_distance(self, goal):
        
        return self.dist[goal]

    def shortest_path(self, goal):
        
        path = []
        node = goal
        while node is not None:
            path.append(node)
            node = self.prev[node]
        return path[::-1]
        
	
if __name__ == "__main__":
	main()

Solution (Python):
from collections import defaultdict
import sys
sys.setrecursionlimit(1000000)

n = int(input())
s = [list(map(int,input().split())) for i in range(n-1)]
t = defaultdict(list)
for i in range(n-1):
    p = [s[i][1],s[i][2]]
    q = [s[i][0],s[i][2]]
    t[s[i][0]] += [p]
    t[s[i][1]] += [q]

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

def Tree(dic,a,x,lo):
    for i in range(len(dic[x])):
        if a[dic[x][i][0]-1] != -1:
            continue
        else:
            save = lo
            lo += dic[x][i][1]
            a[dic[x][i][0]-1] = lo
            a = Tree(dic,a,dic[x][i][0],lo)
            lo = save
    return a

lis = Tree(t,a,1,0)
for i in range(n):
    if lis[i] % 2 == 0:
        print(0)
    else:
        print(1)

Solution (Python):
from collections import deque

n=int(input())
l=[[] for _ in range(n)]
cost=[[] for _ in range(n)]
ans=[-1 for _ in range(n)]
ans[0]=0
q=deque([])
q.append(0)
for iii in range(n-1):
  a,b,w=[int(_) for _ in input().split()]
  a-=1
  b-=1
  l[a].append(b)
  cost[a].append(w)
  l[b].append(a)
  cost[b].append(w)
while not q==deque([]):
  v=q.popleft()
  for jjj in range(len(l[v])):
    u = l[v][jjj]
    w = cost[v][jjj]
    if not ans[u]==-1:
      continue
    ans[u]=(ans[v]+w)%2
    q.append(u)
for a in ans:
  print(a)

Solution (Python):
read = input
n = int(read())
v = [[] for i in range(n+1)] 
used = [0 for i in range(n+1)] 
def add(f,t,w):
    v[f].append((t, w))
for i in range(n-1):
    f,t,w = map(int, read().split())
    add(f,t,w)
    add(t,f,w)

from queue import Queue
q = Queue() 










q.put_nowait((1, 0, -1)) 
while not q.empty():
    f, s, fa = q.get_nowait()
    if s % 2 == 0: 
        used[f] = 1 
    for t, w in v[f]:

        if t == fa:continue  
        q.put_nowait(
            (t, w + s, f)
        )
    
for i in used[1:]: 
    print(used[i])

Solution (Python):
import collections
N = int(input())
tree = [[] for i in range(N+1)]

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

for i in range(1, N+1):
    if len(tree[i]) == 1:
        start = i
        break
queue = collections.deque()
queue.append([start, 0])
ans = [-1] * (N+1)
ans[start] = 0


while len(queue) > 0:
    now = queue.popleft()
    for next in tree[now[0]]:
        if ans[next[0]] == -1:
            queue.append(next)
            ans[next[0]] = (ans[now[0]] + next[1])%2
for i in range(1, N+1):
    print(ans[i])

Solution (Python):
import collections
N = int(input())
tree = [[] for i in range(N+1)]

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

for i in range(1, N+1):
    if len(tree[i]) == 1:
        start = i
        break
queue = collections.deque()
queue.append([start, 0])
ans = [-1] * (N+1)
ans[start] = 0


while len(queue) > 0:
    now = queue.popleft()
    for next in tree[now[0]]:
        if ans[next[0]] == -1:
            queue.append(next)
            ans[next[0]] = (ans[now[0]] + next[1])%2
for i in range(1, N+1):
    print(ans[i])

Solution (Python):
N = int(input())
uvw = [list(map(int,input().split())) for i in range(N-1)]
u = []
v = []
distance = []
for i in range(N-1):
    u.append(uvw[i][0])
    v.append(uvw[i][1])
    distance.append(uvw[i][2])
graph = [dict() for i in range(N)]
for i in range(N-1):
    graph[u[i]-1][v[i]-1] = distance[i]
    graph[v[i]-1][u[i]-1] = distance[i]

trav = [-1]*N
trav[0]=0
pos = [0]
while len(pos)>0:
    r = pos.pop()
    for i in graph[r]:
        if trav[i] != -1:
            continue
        else:
            trav[i] = trav[r]+graph[r][i]
            pos.append(i)

color = [0]*N
for i in range(N):
    color[i] = trav[i]%2
    print(color[i])

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
used[0] = 1
q = deque([0])  
ans = [0] * N

while q:    
    u = q.popleft()
    color = ans[u]
    for v, w in G[u]:   
        if used[v]:
            continue
        if w % 2:   
            ans[v] = 1 - color
        else:       
            ans[v] = color
        q.append(v) 
        used[v] = 1

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

Solution (Python):
import sys
if sys.version_info[0] == 2:
    input = raw_input
sys.setrecursionlimit(2 ** 31 -1)

res = None
G = None

def dfs(jibun_v, p, jibun_c):
    global res
    global G

    res[jibun_v] = jibun_c
    

    tonari_nodes = G[jibun_v]
    for tonari_v, w in tonari_nodes:
        
        
        if res[tonari_v] != -1:
            continue

        else:
            if w % 2 == 0:
                tonari_c = jibun_c
            else:
                tonari_c = 1 - jibun_c

            dfs(tonari_v, jibun_v, tonari_c)
    

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

    global G
    G = [[] for _ in range(N)]

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

    global res
    res = [-1 for _ in range(N)]
    
    jibun_v = 0
    p = -1
    jibun_c = 0
    dfs(jibun_v, p, jibun_c)

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

main()

Solution (Python):
import sys
if sys.version_info[0] == 2:
    input = raw_input
sys.setrecursionlimit(2 ** 31 -1)

res = None
G = None

def dfs(jibun_v, p, jibun_c):
    global res
    global G

    res[jibun_v] = jibun_c
    

    tonari_nodes = G[jibun_v]
    for tonari_v, w in tonari_nodes:
        
        
        if res[tonari_v] != -1:
            continue

        else:
            if w % 2 == 0:
                tonari_c = jibun_c
            else:
                tonari_c = 1 - jibun_c

            dfs(tonari_v, jibun_v, tonari_c)
    

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

    global G
    G = [[] for _ in range(N)]

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

    global res
    res = [-1 for _ in range(N)]
    
    jibun_v = 0
    p = -1
    jibun_c = 0
    dfs(jibun_v, p, jibun_c)

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

main()

Solution (Python):
n=int(input())
edge=[]
node=[]
for i in range(n-1):
    u,v,w=map(int,input().split())
    edge.append([u,v,w])
    node.append([])
node.append([])
dist=[-1]*n
for i in range(n-1):
    [u,v,w]=edge[i]
    node[u-1].append([v-1,w])
    node[v-1].append([u-1,w])


def bfs(node,l):
    stack=[]
    for [v,w] in node[l]:
        stack.append([v,l,w])
    while stack:
        [v,l,w]=stack.pop()
        if(dist[v]==-1):
            dist[v]=(dist[l]+w)%2
            for [v1,w1] in node[v]:
                stack.append([v1,v,w1])
    
dist[0]=1
bfs(node,0)
for i in range(n):
    print(dist[i],end='\n')

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

q = []
visited = [0] * N
ans = [0] * N
A = [[] for _ in range(N)]  
W = [[] for _ in range(N)]  

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

q.append(0)  
for _ in range(N):
    u = q.pop(0)
    visited[u] = 1
    k = 0
    for v in A[u]:
        if visited[v]==0:
            q.append(v)
            ans[v] = ans[u] + W[u][k]
        k += 1

for a in ans:
    print(a%2)