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

Solution (Python):

from collections import defaultdict,deque
from heapq import heappush, heappop
from itertools import permutations
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    n = I()
    v = [[] for i in range(n)]
    for i in range(n-1):
        a,b,c = LI()
        a -= 1
        b -= 1
        v[a].append((b,c))
        v[b].append((a,c))
    bfs = [-1]*n
    q = deque([0])
    bfs[0] = 0
    ans = [0]*n
    while q:
        x = q.popleft()
        for y,c in v[x]:
            nd = bfs[x]+c
            if bfs[y] < 0:
                bfs[y] = nd
                ans[y] = nd&1
                q.append(y)
    for i in ans:
        print(i)
    return


if __name__ == "__main__":
    solve()

Solution (Python):
n=int(input())
li=[list(map(int,input().split())) for i in range(n-1)]


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



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

for x,y,z in li:
  graph[x].append([y,z])
  graph[y].append([x,z])

def dfs(v):
    dist = [-1] * (n+1)
    stack = [v]
    dist[v] = 0
    while stack:
        v = stack.pop()
        dw = dist[v] + 1
        for w,z in graph[v]: 
            if dist[w] >= 0: 
                continue
            dist[w] = dw 
            if z%2:
              col[w]=col[v]^1
            else:
              col[w]=col[v]
            stack.append(w)
    return col
print(*dfs(1)[1:], sep="\n")

Solution (Python):
from collections import deque

N = int(input())
G = [[] for _ in range(N)]  
for _ 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 for _ in range(N)]
q = deque()

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

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

for a in ans:
    print(a)

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

stack = [0]
color = [-1] * n
color[0] = 0
while stack:
    v = stack.pop()
    for b, w in vs[v]:
        if color[b] == -1:
            color[b] = (color[v] + w) % 2
            stack.append(b)

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

Solution (Python):


def paint():
	while len(stack) > 0:
		node = stack.pop()
		for n in adj_list[node]:
			if color_list[n[0]] != "-1":
				continue

			stack.append(n[0])

			if n[1] % 2 == 0:
				color_list[n[0]] = color_list[node]
			else:
				if color_list[node] == "0":
					color_list[n[0]] = "1"
				else:
					color_list[n[0]] = "0"

N = int(input())
adj_list = [[] for i in range(N)]

for i in range(N - 1):
	elm = [int(x) for x in input().split()]
	adj_list[elm[0] - 1].append([elm[1] - 1, elm[2]])
	adj_list[elm[1] - 1].append([elm[0] - 1, elm[2]])

color_list = ["-1"] * N
color_list[0] = "0"

import sys
sys.setrecursionlimit(10000)

stack = [0]
paint()

for c in color_list:
	print(c)

Solution (Python):
import sys

input = sys.stdin.readline

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


def dfs(a):
    dist = [-1] * (n + 1)
    stack = [a]
    dist[a] = 0
    while stack:
        v = stack.pop()
        for b, w in graph[v]:
            if dist[b] == -1:
                dist[b] = (dist[v] + w) % 2
                stack.append(b)
            else:
                continue
    return dist


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

Solution (Python):
from collections import defaultdict, deque

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

colors = [None] * N
colors[0] = 0
queue = deque()
queue.append((0, 0))
while queue:
    v1, c1 = queue.popleft()
    for v2, w in edges[v1]:
        if colors[v2] is not None:
            continue
        if w:
            colors[v2] = c1
        else:
            colors[v2] = 1 - c1
        queue.append((v2, colors[v2]))
for c in colors:
    print(c)

Solution (Python):
from collections import deque
N = int(input())
G = {}
for _ in range(N-1):
    u,v,w = map(int,input().split())
    if u not in G:
        G[u] = []
    G[u].append((v,w%2))
    if v not in G:
        G[v] = []
    G[v].append((u,w%2))
que = deque([(1,0)])
hist = [0 for _ in range(N+1)]
hist[1] = 1
col = [0 for _ in range(N+1)]
while que:
    u,c = que.popleft()
    for x in G[u]:
        v,w = x[0],x[1]
        if hist[v]==0:
            if w==0:
                col[v] = c
                que.append((v,c))
            else:
                col[v] = 1-c
                que.append((v,1-c))
            hist[v] = 1
for i in range(1,N+1):
    print(col[i])

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

l=[-1]*n
s=[(1,0)]
while s:
    b,c=s.pop()
    l[b]=c%2
    for x,y in g[b]:
        if l[x]==-1:
            s.append((x,y+c))

for  i in l:
    print(i)

Solution (Python):
import sys
sys.setrecursionlimit(500*500)
N = int(input())
edges = [list(map(int,input().split())) for _ in range(N-1)]
A = [[] for _ in range(N+1)]

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

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

def dfs(A,s):
    for v in A[s]:
        if depth[v[0]] == -1:
            depth[v[0]] = depth[s] + v[1]
            dfs(A,v[0])    
dfs(A,1)
for d in depth[1:]:
    if d % 2 == 0:
        print(0)
    else:
        print(1)

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

def dfs(pos, not_pos, tree_dict, ans_li, length):
  n_li = tree_dict[pos]
  for n, w in n_li:
    if n == not_pos:
      continue
    new_length = length+w
    if new_length%2 == 0:
      ans_li[n] = 0
    else:
      ans_li[n] = 1
    ans = dfs(n, pos, tree_dict, ans_li, new_length)
  return ans_li

def run():
  N = int(input())
  tree_dict = {}
  ans_li = [0]*(N+1)
  for n in range(N-1):
    u, v, w = map(int, input().split())
    tree_dict.setdefault(u, []).append((v, w))
    tree_dict.setdefault(v, []).append((u, w))
  length = 0
  ans = dfs(1, -1, tree_dict, ans_li, length)
  for a in ans[1:]:
    print(a)
    

if __name__ == '__main__':
  run()

Solution (Python):
N = int(input())
d = dict(zip([i for i in range(1, N+1)], [[] for _ in range(N)]))
 
for i in range(N-1):
  u, v, w = map(int, input().split())
  d[u].append([v, w])
  d[v].append([u, w])
  
colors = [0 for i in range(N)]
l = [[1, 1]]
while l:
  node, parent = l.pop()
  edges = d[node]
  for v, w in edges:
    if v == parent:
      continue
    colors[v-1] = (colors[node-1]+w)%2
    l.append([v, node])
    
for c in colors:
  if c==1:
    print(0)
  else:
    print(1)

Solution (Python):
import sys

sys.setrecursionlimit(500*500);

def dfs(G,v,bef_v,ind_num):
	if v == bef_v :
		seen[v] = 0;
	else :
		
		if G[bef_v][1][ind_num] % 2 :
			seen[v] = int(not seen[bef_v]);
		else :
			seen[v] = seen[bef_v];
	
	for i in range(len(G[v][0])) :
		next_v = G[v][0][i];
		if seen[next_v]==-1 :
			dfs(G,next_v,v,i);


n = int(input());
G = [[0]*2 for i in range(n) ];
for i in range(n) :
	G[i][0] = [];
	G[i][1] = [];
for i in range(n-1) :
	s = input().split(' ');
	u = int(s[0])-1;
	v = int(s[1])-1;
	w = int(s[2]);
	G[u][0].append(v);
	G[v][0].append(u);
	G[u][1].append(w);
	G[v][1].append(w);


seen = [-1]*n;
dfs(G,0,0,0);

for i in range(n):
	print(seen[i]);

Solution (Python):
import sys
from collections import deque
sys.setrecursionlimit(10**9)
INF=10**18
def input():
    return sys.stdin.readline().rstrip()

def main():
    N=int(input())
    edge=[[] for _ in range(N)]
    for _ 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))
    queue=deque()
    queue.append(0)
    used=[False]*N
    l=[0]*N
    while queue:
        node=queue.popleft()
        used[node]=True
        for childnode,weight in edge[node]:
            if not used[childnode]:
                if weight%2:
                    l[childnode]=int(not l[node])
                else:
                    l[childnode]=l[node]
                queue.append(childnode)
    for x in l:
        print(x)
        

if __name__ == '__main__':
    main()

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

def main():
    N = int(input())
    T = [[] for j in range(N + 1)]
    for i in range(N - 1):
        u, v, w = [int(x) for x in input().split()]
        T[u].append([v, w])
        T[v].append([u, w])

    ans = [0] * (N + 1)

    visited = set()
    visited.add(1)
    q = deque()
    q.append(1)

    while q:
        x = q.pop()
        for v in T[x]:
            if v[0] in visited:
                continue
            visited.add(v[0])
            q.append(v[0])
            if v[1] & 1:
                ans[v[0]] = (ans[x] + 1) % 2
            else:
                ans[v[0]] = ans[x]

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



        


if __name__ == '__main__':
    main()

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

N=int(input())
uvw=[list(map(int, input().split())) for i in range(N-1)]
nodelink=[[] for i in range(N+1)]
for i in range(N-1):
  nodelink[uvw[i][0]].append([uvw[i][1], uvw[i][2]])
  nodelink[uvw[i][1]].append([uvw[i][0], uvw[i][2]])
  
color=[-1]*(N+1)

def f(nuru, iro):
  color[nuru]=iro
  tonari=nodelink[nuru]
  for nuruyo in tonari:
    if color[nuruyo[0]]<0:
      if (nuruyo[1]%2)==0:
        f(nuruyo[0], iro)
      else:
        f(nuruyo[0], 1-iro)
      
f(1, 0)

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

Solution (Python):
N, = map(int, input().split())
import sys
sys.setrecursionlimit(10**6)
d = [set() for _ in range(N+1)]
Cs = [0 for _ in range(N+1)]
for _ in range(N-1):
    u, v, p = map(int, input().split())
    d[u].add((v, p))
    d[v].add((u, p))

def it(v, p):
    for u, c in d[v]:
        if u == p:
            continue
        Cs[u] = int(not Cs[v]) if c%2 else Cs[v]
        it(u, v)
it(1, None)
for i in range(1, N+1):
    print(Cs[i])

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


dist = [float('inf')] * N
stack = [[0, 0]]
while stack:
    n, d = stack.pop()
    dist[n] = d

    for to, w in T[n]:
        if dist[to] != float('inf'):
            continue

        stack.append([to, d + w])

ans = [d % 2 for d in dist]
print(*ans, sep='\n')

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


ans = [-1] * N
stack = [[0, 0]]
while stack:
    n, color = stack.pop()
    ans[n] = color

    for to, w in T[n]:
        if ans[to] != -1:
            continue

        if w % 2 == 0:
            stack.append([to, color])
        else:
            stack.append([to, color ^ 1])

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

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

d = dict(zip([i for i in range(1, N+1)], [[] for _ in range(N)]))

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

colors = [0 for i in range(N)]
l = [[1, 1]]
while l:
  node, parent = l.pop()
  edges = d[node]
  for v, w in edges:
    if v == parent:
      continue
    
    colors[v-1] = (colors[node-1]+w)%2
    l.append([v, node])

for c in colors:
  print(c)

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


def dfs(u):
    for v, w in edge[u]:
        if trail[v] is None:
            trail[v] = (trail[u] + w) % 2
            dfs(v)


N = int(input())
trail = [None] * N
edge = [[] for _ in range(N)]

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

trail[0] = 0
dfs(0)

for t in trail:
    print(t)

Solution (Python):
import sys
sys.setrecursionlimit(10**7)
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))
    
ans = [0] * n

def dfs(v,p,c):
    ans[v] = c
    for i in g[v]:
        if i[0] != p:
            if i[1] % 2 ==0:
                dfs(i[0],v,c)
            else:
                dfs(i[0],v,1-c)

dfs(0,-1,0)

for i in ans:
    print(i)

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

N=int(input())
L=[0]*(N-1) 
MAP=[-1]*(N+1)
MAP[1]=0
for i in range(N-1):
    L[i]=list(map(int,input().split()))
    t=[L[i][1],L[i][0],L[i][2]]
    L.append(t)

L1=sorted(L,key=lambda x: (x[0],x[1]))
LIST=[[]for i in range(N+1)]

for i in range(len(L)):
    LIST[L1[i][0]].append([L1[i][1],L1[i][2]])

def calc(k):
    global MAP
    for i in range(len(LIST[k])):
        
        if(MAP[LIST[k][i][0]]==-1):
            MAP[LIST[k][i][0]]=(MAP[k]+LIST[k][i][1])%2
            
            calc(LIST[k][i][0])

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

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

color[0] = True
li = [0]
while li:
    p = li.pop()
    for q, w in UV[p]:
        if color[q] is not None:
            continue
        if w & 1:
            color[q] = not color[p]
        else:
            color[q] = color[p]
        li.append(q)

print(*[int(i) for i in color], sep="\n")

Solution (Python):
import sys
from collections import deque
input = sys.stdin.readline
n = int(input())
abe = [list(map(int, input().split(' '))) for i in range(n-1)]
graph = [[] for i in range(n+1)]
parent = [0 for i in range(n+1)]
edge = [0 for i in range(n+1)]
root = 1
order = []
deq = deque([root])
for a,b,e in abe:
    graph[a].append(b)
    graph[b].append(a)
while deq:
    x = deq.popleft()
    order.append(x)
    for y in graph[x]:
        if parent[x] == y:
            continue
        parent[y] = x
        deq.append(y)
for a,b,e in abe:
    if parent[a] == b:
        edge[a] = e
    else:
        edge[b] = e
ans = [0 for i in range(n+1)]
for x in order:
    if x == 1:
        continue
    if edge[x]%2 == 0:
        ans[x] = ans[parent[x]]
    else:
        ans[x] = 1-ans[parent[x]]
del ans[0]
print(*ans,sep="\n")

Solution (Python):
n = int(input())
T = [[] for i in range(n)] 
D = [-1] * n 
D[0] = 0 


Q = [0] 

for i in range(n - 1):
    u, v, w = map(int, input().split())
    T[u - 1].append([v - 1, w])
    T[v - 1].append([u - 1, w])
while Q:
    q = Q.pop()
    for adj, w in T[q]: 
        if D[adj] < 0: 
            D[adj] = (D[q] + w)%2
            Q.append(adj)
for d in D:
    print(d)

Solution (Python):
n = int(input())
T = [[] for i in range(n)]
for i in range(n - 1):
    u, v, w = map(int, input().split())
    T[u - 1].append([v - 1, w])
    T[v - 1].append([u - 1, w])
D = [-1] * n
D[0] = 0
Q = [0]
while Q:
    q = Q.pop()
    for adj, w in T[q]: 
        if D[adj] < 0: 
            D[adj] = D[q] + w
            Q.append(adj)
for d in D:
    print(d % 2)

Solution (Python):
N = int(input())
tree = [list() for _ in range(N)]
for _ in range(N-1):
    u, v, w = map(int, input().split())
    tree[u-1].append((v-1, w))
    tree[v-1].append((u-1, w))
stack = [0]
ans = [0] * N
searched = [False] * N
while stack:
    node = stack.pop()
    searched[node] = True
    for v, w in tree[node]:
        if searched[v]:
            continue
        if w % 2 != 0:
            ans[v] = ans[node] ^ 1
        else:
            ans[v] = ans[node]
        stack.append(v)
print(*ans, sep='\n')

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

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


def dfs(edge, pd):
    for child, d in edges[edge]:
        if ans[child-1] != -1:
            continue
        cd = pd + d
        if cd % 2 == 0:
            ans[child-1] = 0
        else:
            ans[child-1] = 1
        dfs(child, cd)


def solve():
    dfs(1, 0)
    for i in range(N):
        print(ans[i])


if __name__ == '__main__':
    solve()

Solution (Python):
import sys
from collections import deque
sys.setrecursionlimit(10**6)
if sys.platform in (['ios','darwin','win32']):
	sys.stdin=open('Untitled.txt')
input = sys.stdin.readline
def INT(): return int(input())
def MAP(): return [int(s) for s in input().split()]

def main():
	N = INT()
	UVW = [MAP() for _ in range(N-1)]
	
	G = [[] for _ in range(N)]
	for u, v, w in UVW:
		G[u-1].append([v-1, w])
		G[v-1].append([u-1, w])
		
	C = [-1] * N
	C[0] = 0
	queue = deque()
	for i in range(N):
		queue.append(i)
		while queue:
			v = queue.popleft()
			for child in G[v]:
				nv, dist = child
				if C[nv] != -1: continue
				if not dist % 2:
					
					C[nv] = C[v]
				else:
					
					C[nv] = C[v] ^ 1
				queue.appendleft(nv)
	
	for c in C:
		print(c)

if __name__ == '__main__':
	main()

Solution (Python):


import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(1000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n = I()
edges = [[] for _ in range(n)]

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

ans = [None]*n
ans[0] = 0

que = deque()
que.append(0)
while que:
    v = que.popleft()
    for u,c in edges[v]:
        if ans[u] != None:
            continue
        if c % 2 == 0:
            ans[u] = ans[v]
        else:
            ans[u] = (ans[v]+1) % 2
        que.append(u)
print(*ans)

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

N = int(input())

tree = {}
for i in range(1,N):
    u, v, w = map(int, input().split())
    w = w%2
    if u in tree:
        tree[u].append([v,w])
    else:
        tree[u] = [[v,w]]

    if v in tree:
        tree[v].append([u,w])
    else:
        tree[v] = [[u,w]]

iro = [-1]*(N)
def seachTree(current, parent):
    if len(tree[current]) == 0:
        return

    for elms in tree[current]:
        if elms[0] == parent:
            continue
        if elms[1] == 0:
            iro[elms[0]-1] = iro[current-1]
        else:
            iro[elms[0]-1] = not iro[current-1]

        seachTree(elms[0], current)

iro[0] = False
seachTree(1, 0)
for val in iro:
    print(int(val))

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


dist = [0] * N 
stack = [(0,-1)] 
while stack: 
  vrt, _from = stack.pop()
  for _to, w in edge[vrt].copy():
    if _to == _from:
      continue
    stack.append((_to, vrt))
    dist[_to] = dist[vrt] + w
    
for i in range(N):
  print(dist[i]%2)

Solution (Python):
import sys
sys.setrecursionlimit(pow(10, 7))

def dfs(v, c):
	color[v] = c
	for x in glaph[v]:
		u, w = x[0], x[1]
		if color[u] != -1:
			continue
		if w%2 == 0:
			dfs(u, c)
		else:
			dfs(u, 1-c)
			
n = int(input())
color = [-1]*n
glaph = [[]*n for _ in range(n)]
for _ in range(n-1):
	u,v,w = map(int, input().split())
	glaph[u-1].append((v-1, w))
	glaph[v-1].append((u-1, w))	

dfs(v=0, c=0)
for i in color:
	print(i)

Solution (Python):
import sys
sys.setrecursionlimit(pow(10, 7))

def dfs(v, c, parent):
	color[v] = c
	for x in glaph[v]:
		u, w = x[0], x[1]
		if color[u] != -1:
			continue
		if w%2 == 0:
			dfs(u, c, v)
		else:
			dfs(u, 1-c, v)
			
n = int(input())
glaph = [[]*n for _ in range(n)]
color = [-1]*n

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

dfs(v=0, c=0, parent=0)


for i in color:
	print(i)

Solution (Python):
import heapq
import sys

input = sys.stdin.readline

def dijkstra_heap(s,edge,n):
    
    d = [float("inf")] * n
    used = [True] * n 
    d[s] = 0
    used[s] = False
    edgelist = []
    for a,b in edge[s]:
        heapq.heappush(edgelist,a*(10**6)+b)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        
        if not used[minedge%(10**6)]:
            continue
        v = minedge%(10**6)
        d[v] = minedge//(10**6)
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,(e[0]+d[v])*(10**6)+e[1])
    return d

def main():
    N = int(input())
    edge = [[] for i in range(N)]
    for i in range(N-1):
        u, v, w = map(int, input().split())
        u -= 1
        v -= 1
        edge[u].append([w,v])
        edge[v].append([w,u])
    d = dijkstra_heap(0,edge,N)
    for i in range(N):
        if d[i] % 2 == 0:
            print(0)
        else:
            print(1)

if __name__ == "__main__":
    main()

Solution (Python):
import sys
sys.setrecursionlimit(pow(10, 7))



def dfs(v, p, c):
    res[v] = c
    for e in G[v]:
        if e[0] == p:
            continue
        if e[1] & 1:
            dfs(e[0], v, 1-c)
        else:
            dfs(e[0], v, c)


N = int(input())

G = [[] for _ in range(N)]
res = [0] * 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])
dfs(0, -1, 1)
print('\n'.join(map(str, res)))

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

stack = [0]
judge = [False] * n
while stack:
    node = stack.pop()
    judge[node] = True
    for snode, distance in tree[node]:
        if judge[snode]:
            continue
        if distance % 2 != 0:
            ans[snode] = ans[node] ^ 1
        else:
            ans[snode] = ans[node]
        stack.append(snode)
print(*ans, sep='\n')

Solution (Python):
def main():
    N = int(input())
    d = {}
    for _ in range(N-1):
        u, v, w = map(int, input().split())
        w %= 2
        if u in d:
            d[u].append((v, w))
        else:
            d[u] = [(v,w)]
        if v in d:
            d[v].append((u, w))
        else:
            d[v] = [(u,w)]
    cur = [1]
    nextp = []
    l = [0] * N
    v = set(range(1, N+1))
    while v:
        for i in cur:
            v.remove(i)
            for j, k in d[i]:
                if j in v:
                    l[j-1] = 1 - l[i-1] if k else l[i-1]
                    nextp.append(j)
        cur = nextp
        nextp = []
    return l
l = main()
for i in l:
    print(i)

Solution (Python):
from collections import Counter, deque

N = int(input())

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

udict ={}
uvdict = {}
lst = []
ans = [-1]*(N+1)
for u, v, w in uvw:
    if u in udict:udict[u].append(v)
    else:udict[u] =[v]
    if v in udict:udict[v].append(u)
    else:udict[v] =[u]
    lst.append(u)
    lst.append(v)
    uvdict[(u,v)] = w
cnt = Counter(lst)

cnt_max = cnt.most_common()[0][0]
nxt = deque()
nxt.append(cnt_max)
passed = [0]*(N+1)

d = [0]*(N+1)

while nxt!=deque([]):
    l1 = nxt.popleft()
    for l2 in udict[l1]:
        if passed[l2]==1:continue
        d[l2] = d[l1] + uvdict[min(l1, l2), max(l1, l2)]
        
        nxt.append(l2)
    passed[l1]=1
for i in d[1:]:
    print(i%2)

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

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

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

import queue

q=queue.Queue()
q.put(0)

while not q.empty():
	now=q.get()

	for ne,weight in g[now]:
		if color[ne]!=-1:
			continue
		if weight%2==0:
			color[ne]=color[now]
		else:
			color[ne]=abs(color[now]-1)
		q.put(ne)

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

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

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


parent = [0] * N
for v,_ in edge[0]:
    parent[v] = 0
open_list = deque([0])
while open_list:
    now = open_list.popleft()
    for v,w in edge[now]:
        if v == parent[now]:
            continue
        open_list.append(v)
        parent[v] = now



path = [0] * N
open_list = deque([0])
while open_list:
    now = open_list.popleft()
    for v,w in edge[now]:
        if v == parent[now]:
            continue
        open_list.append(v)
        path[v] = path[now] + w

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

Solution (Python):
from collections import deque

N=int(input())
a=[set() for v in range(N)] 
for e in range(1,N):
    u,v,w=map(int,input().split())
    a[u-1].add((v-1,w))
    a[v-1].add((u-1,w))

d=[-1 for v in range(N)] 

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

for di in d:
    print(di%2)

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

stack = [0]
ans = [-1]*N
ans[0] = 0
while stack:
    x = stack.pop()
    for v,w in e_list[x]:
        if ans[v] != -1:
            continue
        else:
            ans[v] = ans[x]^w
            stack.append(v)
print(*ans,sep='\n')

Solution (Python):

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

color=[0]*(n+1)
q = [(-1,0,0)]
while q:
    parent,x,l = q.pop()
    for y in tree[x]:
        if y[0] == parent:
            continue
        q.append((x,y[0],y[1]))
    if l%2==1:
        color[x+1]=1-color[parent+1]
    else:
        color[x+1]=color[parent+1]

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

Solution (Python):
from collections import deque
N=int(input())
ten=[0]*N
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])
que=deque()
que.append(0)
visited=[[0] for i in range(N)]
visited[0]=1
while que:
    v=que.pop()
    for u in G[v]:
        
        if visited[u[0]]==1:
            continue
        if u[1]%2==0:
            ten[u[0]]=ten[v]
        else:
            if ten[v]==0:
                ten[u[0]]=1
                
            else:
                ten[u[0]]=0
        
        visited[u[0]]=1
        que.appendleft(u[0])
for i in range(N):
    print(ten[i])

Solution (Python):
from collections import deque
N=int(input())
ten=[0]*N
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])

que=deque()
que.append(0)
visited=[[0] for i in range(N)]
visited[0]=1
while que:
    v=que.pop()
    for u in G[v]:
        
        if visited[u[0]]==1:
            continue
        if u[1]%2==0:
            ten[u[0]]=ten[v]
        else:
            ten[u[0]]=1-ten[v]
        
        visited[u[0]]=1
        que.appendleft(u[0])
for i in range(N):
    print(ten[i])

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

N = int(input())
tree = [[] for i in range(N)]
color = [-1] * 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))


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


color[0] = 0
dfs(0)
print('\n'.join(map(str, color)))

Solution (Python):
from collections import deque

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


check = [-1] * (N + 1)
check[1] = 0
D = deque()
D.append(1)

while D:
  d=D.popleft()
  for a in A[d]:
    if check[a[0]]==-1:
      D.append(a[0])
      check[a[0]]=(check[d]+a[1])%2

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