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
'''
allinputs = iter(input().splitlines())
input = lambda : next(allinputs)


N = int(input())
q = []
c = [0] * N
l = [0] * N
A = [[] for i in range(N)]
W = [[] for i 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):
	if len(q) == 0:
		break
	i = q.pop(0)
	c[i] = 1
	k = 0
	for j in A[i]:
		if c[j] == 0:
			q.append(j)
			l[j] = l[i] + W[i][k]
		k += 1

for i in l:
	print('{}'.format(i%2))

Solution (Python):
import sys
input = sys.stdin.readline
'''
allinputs = iter(input().splitlines())
input = lambda : next(allinputs)


N = int(input())
q = []
c = [0] * N
l = [0] * N
A = [[] for i in range(N)]
W = [[] for i 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)
while len(q):
	i = q.pop(0)
	c[i] = 1
	k = 0
	for j in A[i]:
		if c[j] == 0:
			q.append(j)
			l[j] = l[i] + W[i][k]
		k += 1

for i in l:
	print('{}'.format(i%2))

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

n = int(input())
t = [[] for i in range(n + 1)]
r = [0 for i in range(n + 1)]

for i in range(n - 1):
    u, v, w = [int(j) for j in input().split(" ")]
    t[u].append((v, w))
    t[v].append((u, w))

def s(f, i):
    for k in t[i]:
        v, w = k
        if v != f:
            if w % 2 == 0:
                r[v] = r[i]
            else:
                r[v] = 1 - r[i]
            s(i, v)
s(0, 1)
print(" ".join(map(str, r[1:])))

Solution (Python):
from collections import deque
n = int(input())
path = {u:[] for u in range(1, n+1)}
for i in range(1, n):
    u, v, w = map(int, input().split())
    path[u].append((v,w))
    path[v].append((u,w))

queue = deque()
queue.append(1) 
distance_li = [-1] * (n+1)
distance_li[1] = 0




while len(queue) > 0:
    u = queue.popleft()
    for v,w in path[u]:
        if distance_li[v] != -1:
            continue
        distance_li[v] = (distance_li[u] + w) % 2
        queue.append(v)
for i in range(1,n+1):
    print(distance_li[i])

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))
used=[0]*N
ans=[0]*N
used[0]=1
que=deque([0])
while que:
  node=que.popleft()
  color=ans[node]
  for point,dist in Graph[node]:
    if used[point]:
      continue;
    if dist%2==0:
      ans[point]=color
    else:
      ans[point]=color^1
    que.append(point)
    used[point]=1
print(*ans, sep='\n')

Solution (Python):
from sys import setrecursionlimit
setrecursionlimit(10**8)


def dfs(i, d):
    
    for j, w in node_array[i]:
        if color_array[j] == -1:
            color_array[j] = (d + w) % 2
            dfs(j, d + w)


N = int(input())
node_array = [[] for i in range(N)]
color_array = [-1] * N

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

color_array[0] = 0
dfs(0, 0)

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

Solution (Python):
from sys import setrecursionlimit
setrecursionlimit(10**8)


def dfs(i, d):
    
    for j, w in node_array[i]:
        if color_array[j] == -1:
            color_array[j] = (d + w) % 2
            dfs(j, d + w)


N = int(input())
node_array = [[] for i in range(N)]
color_array = [-1] * N

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

color_array[0] = 0
dfs(0, 0)

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

Solution (Python):
N, = list(map(int, input().split()))
a = [{} for i in range(N)]
for i in range(N-1):
  u, v, w = list(map(int, input().split()))
  u -= 1
  v -= 1
  a[u][v] = w%2
  a[v][u] = w%2
r = [-1 for i in range(N)]
r[0] = 0
q = [0]
while q:
  i = q.pop(0)
  for aj in a[i].keys():
    if r[aj]==-1:
      r[aj] = (r[i]+a[i][aj])%2
      q.append(aj)
for i in range(N):
  print(r[i])

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

tree_num_array = [-1] * N


tree_num_max = -1
tree = {}
last_tree_num = -1
for node in node_array:
    
    i, j, w = node
    i = i - 1
    j = j - 1
    if tree_num_array[i] == -1 and tree_num_array[j] == -1:
        
        tree_num_max += 1
        tree[tree_num_max] = {i: 0, j: w}
        tree_num_array[i] = tree_num_max
        tree_num_array[j] = tree_num_max
        last_tree_num = tree_num_max
        continue
    elif tree_num_array[i] == -1:
        
        tree_num_added = tree_num_array[j]
        tree[tree_num_added][i] = tree[tree_num_added][j] + w
        tree_num_array[i] = tree_num_added
        last_tree_num = tree_num_added
    elif tree_num_array[j] == -1:
        
        tree_num_added = tree_num_array[i]
        tree[tree_num_added][j] = tree[tree_num_added][i] + w
        tree_num_array[j] = tree_num_added
        last_tree_num = tree_num_added
    else:
        tree_num_i = tree_num_array[i]
        tree_num_j = tree_num_array[j]
        
        if len(tree[tree_num_i]) > len(tree[tree_num_j]):
            tree_main_num = tree_num_i
            tree_main_value = tree[tree_main_num][i]
            tree_sub_num = tree_num_j
            tree_sub_value = tree[tree_sub_num][j]
        else:
            tree_main_num = tree_num_j
            tree_main_value = tree[tree_main_num][j]
            tree_sub_num = tree_num_i
            tree_sub_value = tree[tree_sub_num][i]

        for key, value in tree[tree_sub_num].items():
            tree[tree_main_num][
                key] = tree_main_value + w + abs(value - tree_sub_value)
            tree_num_array[int(key)] = tree_main_num
        last_tree_num = tree_main_num

ans_dict = sorted(tree[last_tree_num].items(), key=lambda x: int(x[0]))

for distance in ans_dict:
    print(distance[1] % 2)

Solution (Python):
from collections import deque

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

color = {}
queue = deque()
queue.append((0, 1, 0))  

while len(queue) > 0:
    pc, c, d = queue.popleft()
    if c in color:
        continue
    color[c] = pc if d % 2 == 0 else 1 - pc
    for v, w in adj[c]:
        queue.append((color[c], v, w))

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

Solution (Python):



def main():
    from collections import deque

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

    
    
    
    for i in range(n - 1):
        ui, vi, wi = map(int, input().split())
        ui -= 1
        vi -= 1
        graph[ui].append((vi, wi))
        graph[vi].append((ui, wi))

    ans = [-1 for _ in range(n)]
    q = deque()
    ans[0] = 0
    q.append(0)

    while q:
        vj = q.popleft()

        for uj, wj in graph[vj]:
            if ans[uj] != -1:
                continue

            ans[uj] = (ans[vj] + wj) % 2
            q.append(uj)

    print('\n'.join(map(str, ans)))


if __name__ == '__main__':
    main()

Solution (Python):



def main():
    from collections import deque

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

    for i in range(n - 1):
        ui, vi, wi = map(int, input().split())
        ui -= 1
        vi -= 1
        to[ui].append(vi)
        to[vi].append(ui)
        cost[ui].append(wi)
        cost[vi].append(wi)

    ans = [-1 for _ in range(n)]
    q = deque()
    ans[0] = 0
    q.append(0)

    while q:
        vj = q.popleft()

        for j in range(len(to[vj])):
            uj = to[vj][j]
            wj = cost[vj][j]

            if ans[uj] != -1:
                continue

            ans[uj] = (ans[vj] + wj) % 2
            q.append(uj)

    for a in ans:
        print(a)


if __name__ == '__main__':
    main()

Solution (Python):



def main():
    from collections import deque

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

    for i in range(n - 1):
        ui, vi, wi = map(int, input().split())
        ui -= 1
        vi -= 1
        to[ui].append(vi)
        to[vi].append(ui)
        cost[ui].append(wi)
        cost[vi].append(wi)

    ans = [-1 for _ in range(n)]
    q = deque()
    ans[0] = 0
    q.append(0)

    while q:
        vj = q.popleft()

        for j in range(len(to[vj])):
            uj = to[vj][j]
            wj = cost[vj][j]

            if ans[uj] != -1:
                continue

            ans[uj] = (ans[vj] + wj) % 2
            q.append(uj)

    for a in ans:
        print(a)


if __name__ == '__main__':
    main()

Solution (Python):

from collections import defaultdict
import sys
from Queue import Queue
N=input()
U=[];V=[];W=[]
G=defaultdict(list)
Dist={}
for _ in range(N-1):
    u,v,w=map(int,raw_input().split())
    u,v=min(u,v),max(u,v)
    U.append(u);V.append(v);W.append(w)    
    G[u].append(v)
    G[v].append(u)
    Dist[(u,v)]=Dist[(v,u)]=w

vis=[False]*(10**5+1)
color=[None]*(10**5+1)
q=Queue()
vis[1]=True
color[1]=0
curCol=1
for u in G[1]:q.put(u)
while not q.empty():
    child=q.get()
    vis[child]=True
    par=None
    for n in G[child]:
        if vis[n]: 
            par=n;break
    dist=Dist[(par,child)]
    if dist%2==0: color[child]=color[par]
    else: color[child]=color[par]^1
    for ch in G[child]:
        if not vis[ch]: q.put(ch)

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

Solution (Python):
N = int(input())
q = []
c = [0 for i in range(N)]
l = [0 for i in range(N)]
A = [[] for i in range(N)]
W = [[] for i in range(N)]

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

q.append(0)
while len(q):
	i = q.pop(0)
	c[i] = 1
	k = 0
	for j in A[i]:
		if c[j] == 0:
			q.append(j)
			l[j] = l[i] + W[i][k]
		k = k + 1

for i in l:
	print('{}'.format(i%2))

Solution (Python):
import heapq

def dijkstra(graph,node,start):
    dist = [float("inf") for _ in range(node)]
    dist[start] = 0
    q = []
    heapq.heappush(q,[0,start])

    while(q):
        cost, cur_node = heapq.heappop(q)
        if dist[cur_node] < cost:
            continue
        for next_cost, next_node in graph[cur_node]:
            dist_cand = dist[cur_node]+next_cost
            if dist_cand < dist[next_node]:
                dist[next_node] = dist_cand
                heapq.heappush(q,(dist[next_node],next_node))
    return dist
    

n  = int(input())
adj = [[] for _ in range(n)]
for i in range(n-1):
    u,v,w = map(int,input().split())
    u -= 1
    v -= 1
    adj[u].append((w,v))
    adj[v].append((w,u))
shortest = dijkstra(adj,n,0)
for i in shortest:
    print(i%2)

Solution (Python):
import heapq

def dijkstra(graph, node, start):
    dist = [float("inf") for _ in range(node)]

    dist[start] = 0
    q = []
    heapq.heappush(q, (0, start))

    while q:
        cost, cur_node = heapq.heappop(q)

        if dist[cur_node] < cost:
            continue

        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
                heapq.heappush(q, (dist[nex_node], nex_node))

    return dist


n = int(input())
adj = [[] for _ in range(n)]
for i in range(n - 1):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    adj[a].append((c, b))
    adj[b].append((c, a))
shortest = dijkstra(adj, n, 0)
for i in shortest:
    print(i % 2)

Solution (Python):
import sys

sys.setrecursionlimit(1000000)

n = int(input())

ulist = []

for _ in range(n+1):
    ulist.append([])

vlist = [False]*(n+1)

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

def check(checkV, fromV):
    for data in ulist[checkV]:
        if data[0] != fromV:
            vlist[data[0]] = vlist[checkV] if data[1] % 2 == 0 else not vlist[checkV]
            check(data[0], checkV)

check(1, 0)

for i in range(1,n+1):
    print(1 if vlist[i] else 0)

Solution (Python):
import sys

n = int(input())
links = [set() for _ in [0] * n]
for line in sys.stdin:
	u, v, w = map(int, line.split())
	u -= 1
	v -= 1
	links[u].add((v, w))
	links[v].add((u, w))
ans = [-1] * n
q = [(0, 0, -1)]
while q:
	v, d, p = q.pop()
	if d % 2 == 0:
		ans[v] = 0
	else:
		ans[v] = 1
	for u, w in links[v]:
		if u == p:
			continue
		q.append((u, d + w, v))
print('\n'.join(map(str, ans)))

Solution (Python):
def solve(n, u, v, w):
    res = [-1] * (n+1)
    res[1] = 0
    E = {_: [] for _ in (set(u) | set(v))}
    W = {}
    for u_i, v_i, w_i in zip(u, v, w):
        E[u_i].append(v_i)
        E[v_i].append(u_i)
        W[(u_i, v_i)] = w_i
        W[(v_i, u_i)] = w_i
    que = [1]
    while que:
        s = que.pop(0)
        for t in E[s]:
            if res[t] != -1:
                continue
            d = W[s,t]
            que.append(t)
            if d % 2 == 0:
                res[t] = res[s]
            else:
                res[t] = 1 - res[s]
    return "\n".join(map(str, res[1:]))

n = int(input())
u = [0] * n
v = [0] * n
w = [0] * n
for i in range(n-1):
    u[i], v[i], w[i] = map(int, input().split())
print(solve(n, u, v, w))

Solution (Python):
import sys
sys.setrecursionlimit(10000000)
N = int(input())
JU = [-1 for _ in range(N)]

LI = [[] for _ in range(N)]
for _ in range(N-1):
    u,v,w = map(int,input().split())
    W = w%2
    LI[u-1].append([v-1,W])
    LI[v-1].append([u-1,W])
def dfs(x):
    for i in range(len(LI[x])):
        j = LI[x][i][0]
        k = LI[x][i][1]
        if JU[j] == -1:
            if JU[x] == 0:
                if k == 0:
                    JU[j] = 0
                    dfs(j)
                else:
                    JU[j] = 1
                    dfs(j)
            else:
                if k == 0:
                    JU[j] = 1
                    dfs(j)
                else:
                    JU[j] = 0
                    dfs(j)

JU[0] = 0
dfs(0)
for i in range(N):
    print(JU[i])

Solution (Python):
n = int(input())
gr = [dict() for _ in range(n)]
l = [10*6]*n
l[0]= 0
for _ in range(n-1):
  x,y,w = map(int, input().split())
  w %= 2
  gr[x-1][y-1] = w
  gr[y-1][x-1] = w
  
seen = set()
q = [0]
while q:
  cur = q.pop()
  seen.add(cur)
  for x in set(gr[cur].keys())-seen:
    l[x] = l[cur] + gr[cur][x]
    q.append(x)
for i in range(n):
  print(l[i]%2)

Solution (Python):
N = int(input())
G = [[] for i in range(N)]
for i in range(N-1):
  u, v, w = list(map(int, input().split()))
  u -= 1
  v -= 1
  w = w % 2
  G[u].append([v, w])
  G[v].append([u, w])
  
res = [-1] * N
"""
def dfs(u, p, c):
  res[u] = c
  for n in G[u]:
    if n[0] == p or res[n[0]] != -1:
      continue
    if n[1] == 1:
      dfs(n[0], u, 1-c)
    else:
      dfs(n[0], u, c)
"""
from collections import deque
q = deque()

def search(q):
  while q:
    u, p, c = q.popleft()
    if res[u] == -1:
      for n in G[u]:
        if n[0] == p or res[n[0]] != -1:
          continue
        if n[1] == 1:
          q.append((n[0], u, 1-c))
        else:
          q.append((n[0], u, c))
    res[u] = c
  
  
def main():
  q.append((0, -1, 1))
  search(q)
  for i in res:
    print(i)
  
  
if __name__ == "__main__":
  main()

Solution (Python):

import sys
sys.setrecursionlimit(1000000)
def dfs(now,color):
    col[now]=color
    for n,w in nodes[now]:
        if col[n]!=-1:
            continue
        if w%2==0:
            dfs(n,color)
        else:
            dfs(n,1-color)

n=int(input())

nodes=[]
for i in range(n+1):
    nodes.append([])
for i in range(n-1):
    s,e,w = map(int,input().split())
    nodes[s].append((e,w))
    nodes[e].append((s,w))

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

dfs(1,1)

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

Solution (Python):
import sys
sys.setrecursionlimit(1000000)
N = int(input())
e = [ [] for i in range(N+1)]
for i in range(N-1):
    u, v, w = map(int, input().split())
    e[u].append((v,w))
    e[v].append((u,w))

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

def dfs(x,c):
    col[x] = c
    for v,w in e[x]:
        if col[v] == -1:
            dfs(v , c+w)

dfs(1,0)



for i in range(1,N+1):
    print(col[i] % 2)

Solution (Python):
import sys
sys.setrecursionlimit(1000000)
N = int(input())
e = [ [] for i in range(N+1)]
for i in range(N-1):
    u, v, w = map(int, input().split())
    e[u].append((v,w))
    e[v].append((u,w))

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

def dfs(x,c):
    col[x] = c
    for v,w in e[x]:
        if col[v] == -1:
            dfs(v , c+w)

dfs(1,0)



for i in range(1,N+1):
    print(col[i] % 2)

Solution (Python):
from collections import deque
n=int(input())
v=[0 for i in range(n-1)]
u=[0 for i in range(n-1)]
w=[0 for i in range(n-1)]
da=[[] for i in range(n)]
for i in range(n-1):
  u[i],v[i],w[i]=map(int,input().split())
  da[u[i]-1].append(i)
  da[v[i]-1].append(i)
  u[i]-=1
  v[i]-=1
que=[0]
co=0
ans=[-1 for i in range(n)]
di=[0 for i in range(n)]
ans[0]=0
while co<n:
  x=que.pop()
  if di[x]%2==0:
    ans[x]=0
  else:
    ans[x]=1
  for i in da[x]:
    if ans[u[i]]<0:
      di[u[i]]=di[x]+w[i]
      que.append(u[i])
    if ans[v[i]]<0:
      di[v[i]]=di[x]+w[i]
      que.append(v[i])
  co+=1
for i in ans:
  print(i)

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

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

dist=[-1 for _ in range(N)]
def measure(src):
    for v,w in edges[src]:
        if dist[v]==-1:
            dist[v]=dist[src]+w
            measure(v)

dist[0]=0
measure(0)

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

Solution (Python):
N = int(input())
uvw = [[int(_) for _ in input().split()] for i in range(N - 1)]

from collections import defaultdict

uv = defaultdict(dict)

for u, v, w in uvw:
    uv[u][v] = w
    uv[v][u] = w
    
l = {1: 0}

s = [1]

while s:
    ns = []
    for i in s:
        for j in uv[i]:
            if not j in l:
                l[j] = l[i] + uv[i][j]
                ns.append(j)
    s = ns

for i in range(1, N + 1):
    print(l[i] % 2)

Solution (Python):
import sys

sys.setrecursionlimit(1000000000)

n = int(input())

ulist = []

for _ in range(n):
    ulist.append([])

vlist = [True] * n

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


def check(checkV, fromV):
    for data in ulist[checkV]:
        if data[0] != fromV:
            vlist[data[0]] = vlist[checkV] if data[1] % 2 == 0 else not vlist[checkV]
            check(data[0], checkV)

check(0, -1)

for i in range(n):
    print(1 if vlist[i] else 0)

Solution (Python):
import queue

N = int(input())

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

q = queue.Queue()
q.put((1, 0))
while(not q.empty()):
    v, w = q.get()
    dist[v-1] = w
    for nv, nw in adj[v]:
        if(dist[nv-1]!=-1):
            continue
        q.put((nv, dist[v-1]+nw))

for c in dist:
    print(c%2)

Solution (Python):
N = int(input())
d = {i+1: [] for i 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])

dist = {i+1: -1 for i in range(N)}
stack = [1]
dist[1] = 0

while len(stack) != 0:
    prev = stack.pop()
    prev_d = dist[prev]
    for v, w in d[prev]:
        if dist[v] == -1:
            stack.append(v)
            dist[v] = prev_d + w

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

Solution (Python):

import copy
import random
import bisect 
import fractions 
import math
import sys

mod = 10**9+7
sys.setrecursionlimit(mod) 

N = int(input())
graph = [set() for i in range(N+1)]

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


res = [None for i in range(N+1)]


def dfs(node,p,color): 
    res[node] = color
    for new_node,w in graph[node]:
        if new_node == p:continue
        if w == 1:dfs(new_node,node,1-color)
        else:dfs(new_node,node,color)


dfs(0,-1,0)

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

Solution (Python):

import copy
import random
import bisect 
import fractions 
import math
import sys



mod = 10**9+7
sys.setrecursionlimit(mod)

N = int(input())
graph = [set() for i in range(N+1)]

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


res = [None for i in range(N+1)]


def dfs(node,p,color): 
    res[node] = color
    for new_node,w in graph[node]:
        if new_node == p:
            pass
        else:
            if w == 1:dfs(new_node,node,1-color)
            else:dfs(new_node,node,color)


dfs(0,-1,0)

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

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


def rec(edges, nodes, cp, cdistance, visited):
    if not visited[cp]:
        visited[cp] = True
        nodes[cp] = (cdistance % 2 == 0)
        if edges[cp]:
            for v, w in edges[cp]:
                rec(edges, nodes, v, cdistance + w, visited)


def main():
    N = int(input())
    nodes = [False] * N
    visited = [False] * N
    edges = [[] for _ in range(N)]

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

    rec(edges, nodes, 0, 0, visited)

    for n in nodes:
        print(0 if n else 1)


if __name__ == '__main__':
    main()

Solution (Python):
import sys
n = int(input())
mark = [[[],[]]for _ in range(n+1)]
color = [0 for _ in range(n+1)]
done = set()
for i in range(n-1):
    a,b,c = map(int,sys.stdin.readline().split())
    if c&1:
        mark[a][1].append(b)
        mark[b][1].append(a)
    else:
        mark[a][0].append(b)
        mark[b][0].append(a)
run = [1]
temp = []
while(len(run))>0:
    next = run.pop(0)
    done.add(next)
    
    if color[next]==0:
        for v in mark[next][1]:
            if v not in done:
                color[v]=1
                temp.append(v)
        for v in mark[next][0]:
            if v not in done:
                temp.append(v)
    else:
        for v in mark[next][0]:
            if v not in done:
                color[v] = 1
                temp.append(v)
        for v in mark[next][1]:
            if v not in done:
                temp.append(v)
    if len(run)==0:
        run=run+temp
        temp=[]
    
for i in range(1,n+1):
    sys.stdout.write(str(color[i])+'\n')

Solution (Python):
n = int(input())
edges = [set() for _ in range(n)]
for i in range(n-1):
    u,v,w = [int(i)-1 for i in input().split()] 
    edges[u].add((v,w+1))
    edges[v].add((u,w+1))
ans = [-1]*n
q = [(0,0,-1)]
while q:
    v,d,p = q.pop()
    if d%2 == 0:
        ans[v] = 0
    else:
        ans[v] = 1
    for u,w in edges[v]:
        if u == p:
            continue
        q.append((u,d+w,v))
for i in range(n):
    print(ans[i])

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

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)]
def measure(src):
    """
    srcを根とした木に対し、根から各頂点までの距離を求める
    """
    for v, w in edges[src]:
        if dist[v] == -1:
            dist[v] = dist[src] + w
            measure(v)

dist[0] = 0
measure(0)

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

Solution (Python):
def d_even_relation_dfs(N, Nodes):  
    import sys
    sys.setrecursionlimit(10**6)
    graph = [[] for _ in range(N)]
    for u, v, w in Nodes:  
        graph[u - 1].append((v - 1, w))
        graph[v - 1].append((u - 1, w))

    def distance_from_root(parent, current, distance, ret=[0] * N):  
        def dfs(p, c, d):
            ret[c] = d
            for next_edge, dist in graph[c]:
                if next_edge != p:  
                    dfs(c, next_edge, d + dist)
        dfs(parent, current, distance)
        return ret
    ans = (1 if d % 2 == 0 else 0 for d in distance_from_root(-1, 0, 0))  
    return ' '.join(map(str, ans))

N = int(input())
Nodes = [[int(i) for i in input().split()] for j in range(N - 1)]
print(d_even_relation_dfs(N, Nodes))

Solution (Python):
def d_even_relation_bfs(N, Nodes):  
    from collections import deque
    graph = [[] for _ in range(N)]
    for u, v, w in Nodes:  
        graph[u - 1].append((v - 1, w))
        graph[v - 1].append((u - 1, w))
    distance_from_root = [0] * N  

    queue = deque([(-1, 0, 0)])  
    while queue:
        parent, current, distance = queue.pop()
        distance_from_root[current] = distance
        for next_edge, dist in graph[current]:
            if parent != next_edge:  
                queue.appendleft((current, next_edge, distance + dist))
    ans = (1 if d % 2 == 0 else 0 for d in distance_from_root)
    return ' '.join(map(str, ans))

N = int(input())
Nodes = [[int(i) for i in input().split()] for j in range(N - 1)]
print(d_even_relation_bfs(N, Nodes))

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

n = int(input())
nodes = [[] for _ in range(n)]
visited = [False for _ in range(n)]
dist = [0 for _ in range(n)]

def dfs(i, d):
  dist[i] = d
  for cn, c in nodes[i]:
    if not visited[cn]:
      visited[cn] = True
      dfs(cn, d+c)

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

visited[0] = True
dfs(0, 0)

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

Solution (Python):
import math
import sys
sys.setrecursionlimit(100000)
N=int(input())
edges=[[] for i in range(N+1)]
d=[-1 for i in range(N+1)]
for i in range(1,N):
	u,v,w=[int(i) for i in input().split()]
	edges[u].append([v,w])
	edges[v].append([u,w])
def kyori(u):
	for v,w in edges[u]:
		if d[v]==-1:
			d[v]=d[u]+w
			kyori(v)
d[1]=0
kyori(1)
for i in d[1:]:
	if i%2==0:
		print(1)
	else:
		print(0)

Solution (Python):
import math
import sys
sys.setrecursionlimit(30000)
N=int(input())
edges=[[] for i in range(N+1)]
d=[-1 for i in range(N+1)]
for i in range(1,N):
	u,v,w=[int(i) for i in input().split()]
	edges[u].append([v,w])
	edges[v].append([u,w])
def kyori(u):
	for v,w in edges[u]:
		if d[v]==-1:
			d[v]=d[u]+w
			kyori(v)
d[1]=0
kyori(1)
for i in d[1:]:
	if i%2==0:
		print(1)
	else:
		print(0)

Solution (Python):
import sys
sys.setrecursionlimit(10**6)
n = int(input())
edge = [[] for i in range(n)]
colors = [0] * n
for i in range(n-1):
    u, v, w = [int(item) for item in input().split()] 
    u -= 1
    v -= 1
    edge[u].append([v, w % 2])
    edge[v].append([u, w % 2])
    
def dfs(frm, n, d):
    for tv, tw in edge[n]:
        if tv == frm:
            continue
        else:
            td = (d + tw) % 2
            if td == 1:
                colors[tv] = 1 
            else:
                colors[tv] = 0 
            dfs(n, tv, td)
    return True

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

Solution (Python):

from collections import deque

def solve2():
    N = int(raw_input())
    to = [ [] for i in range(N) ]
    cost= [ [] for i in range(N) ]
    for i in range(N - 1):
        ui,vi,wi = [int(_) for _ in raw_input().split()]
        ui -= 1
        vi -= 1
        to[ui].append(vi)
        cost[ui].append(wi)
        to[vi].append(ui)
        cost[vi].append(wi)
    
    ret = [-1] * N
    que = deque()
    ret[0] = 0
    que.append(0)
    while len(que) > 0:
        visit = que.popleft()
        for i in range(len(to[visit])):
            u = to[visit][i]
            w = cost[visit][i]
            if ret[u] != -1:
                continue
            ret[u] = (ret[visit] + w) % 2
            que.append(u)
    for i in range(N):
        print ret[i]

if __name__ == '__main__':
    solve2()

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

tree_list = []
for i in range(N):
  tree_list.append([])

for i in range(N-1):
  ui,vi,wi=map(int,input().split())
  tree_list[ui-1].append((vi-1,wi%2))
  tree_list[vi-1].append((ui-1,wi%2))

paint_list = [-1]*N
paint_list[0] = 0
queue = [0]
while(True):
  if len(queue) == 0:
    break  
  
  new_queue = []
  for q in queue:
    for u,w in tree_list[q]:
      if paint_list[u] == -1:
        paint_list[u] = paint_list[q]^w
        new_queue.append(u)
  queue = new_queue  
    
for i in paint_list:
  print(i)

Solution (Python):
import os, sys, re, math, queue

N = int(input())

nodes = {}
colors = [-1 for _ in range(N+1)]
for _ in range(N-1):
    s = input().split(' ')
    u,v,w = int(s[0]), int(s[1]), int(s[2])
    if u not in nodes:
        nodes[u] = [(v,w)]
    else:
        nodes[u].append((v,w))

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

q = queue.Queue()
f = list(nodes.keys())[0]
q.put((f,0))

while not q.empty():
    cur = q.get()
    colors[cur[0]] = cur[1]
    next = nodes[cur[0]]
    for n in next:
        if colors[n[0]] == -1:
            if n[1] % 2 == 0:
                q.put((n[0], cur[1]))
            else:
                q.put((n[0], (cur[1]+1) % 2))

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

Solution (Python):
import queue

N = int(input())
to_list = [ [] for i in range(N) ]
cost_list = [ [] for i in range(N) ]
ans = [ -1 for i in range(N) ]

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


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

while(not q.empty()):
    v = q.get()
    for i in range(len(to_list[v])):
        u = to_list[v][i]
        w = cost_list[v][i]
        if ans[u] != -1:
            continue
        ans[u] = (ans[v] + w) % 2
        q.put(u)

for a in ans:
    print(a)