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
INF = 10**18
import sys
from heapq import heapify,heappop,heappush,heappushpop


class PriorityQueue:
    
    
    def __init__(self,heap):
        self.heap = heap
        heapify(self.heap)
    
    
    def push(self,item):
        heappush(self.heap,item)
    
    
    def pop(self):
        return heappop(self.heap)
    
    
    def pushpop(self,item):
        return heappushpop(self.heap,item)
    
    
    def __call__(self):
        return self.heap
    
    
    def __len__(self):
        return len(self.heap)

def dijkstra(s):
    
    d = [INF] * n
    used = [True] * n 
    d[s] = 0
    used[s] = False
    edgelist = []
    q = PriorityQueue(edgelist)
    for e in edge[s]:
        q.push(e)
    while len(edgelist):
        minedge = q.pop()
        
        if not used[minedge[1]]:
            continue
        v = minedge[1]
        d[v] = minedge[0]
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                q.push([e[0]+d[v],e[1]])
    return d

if __name__ == "__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])
    ans = dijkstra(0)
    c_ans = [0]*n
    for i in range(n):
        if ans[i]%2 == 0:
            c_ans[i] = 0
        else:
            c_ans[i] = 1
    for i in range(n):
        print(c_ans[i])

Solution (Python):
n = int(input())
v = []
for i in range(n + 10):
    v.append([])

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

import collections
q = collections.deque([])
used = [None] * (n+10)
q.append([1,0])
while len(q) > 0:
    cur, color = q.pop()
    
    used[cur] = color
    for i in range(len(v[cur])):
        nind, w = v[cur][i]
        if used[nind] != None:
            continue
        if w % 2 == 0:
            q.append([nind, color])
        else:
            q.append([nind, 1-color])
for i in range(1, n+1):
    print(used[i])

Solution (Python):
N = int(input())
G = [[] for i in range(N)]
for i in range(N-1):
    A,B,C = list(map(int,input().split()))
    G[A-1].append([C,B-1]) 
    G[B-1].append([C,A-1])

from collections import deque
dist = [None]*N
que = deque([0])
dist[0] = 0
while que:
    v = que.popleft()
    d = dist[v]
    for c,w in G[v]:
        if dist[w] is not None:
            continue
        dist[w] = d + c
        que.append(w)
for i in range(N):
    print(dist[i]%2)

Solution (Python):
from collections import deque
n = int(input())
to = [[] for _ in range(n)]
for i in range(n-1):
    u, v, w = map(int, input().split())
    u , v = u-1, v-1
    to[u].append([v, w])
    to[v].append([u, w])
color = [-1] * n
color[0] = 0
q = deque([0])
while q:
    v = q.popleft()
    for u, w in to[v]:
        if color[u] != -1:
            continue
        if w % 2 != 0:
            color[u] = color[v] ^ 1
        else:
            color[u] = color[v]
        q.append(u)
for c in color:
    print(c)

Solution (Python):
from collections import deque
n = int(input())
to = [[] for _ in range(n)]
for i in range(n-1):
    u, v, w = map(int, input().split())
    u , v = u-1, v-1
    to[u].append([v, w])
    to[v].append([u, w])
color = [-1] * n
color[0] = False
q = deque([0])
while q:
    v = q.popleft()
    for u, w in to[v]:
        if color[u] != -1:
            continue
        if w % 2 != 0:
            color[u] = color[v] ^ 1
        else:
            color[u] = color[v]
        q.append(u)
for c in color:
    print(int(c))

Solution (Python):
from collections import deque

n = int(input())
L = [[] for _ in range(n)]
for _ in range(n-1):
    u, v, w = map(int, input().split())
    L[u-1].append((v-1, w))
    L[v-1].append((u-1, w))
d = [-1] * n
d[0] = 0
c = [0] * n
c[0] = 0
q = deque([0])
while q:
    t = q.popleft()
    dist = d[t]
    for v, w in L[t]:
        if d[v] < 0:
            d[v] = dist + w
            if d[v] % 2:
                c[v] = 1
            q.append(v)
for x in c:
    print(x)

Solution (Python):
import sys
from collections import deque

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


def main():
    N = int(readline())
    G = [[] for _ in range(N)]
    for _ in range(N - 1):
        u, v, w = map(int, readline().split())
        G[u - 1].append((v - 1, w))
        G[v - 1].append((u - 1, w))

    color = [0] * N

    def dfs(v, p, c):
        color[v] = c
        for nv, w in G[v]:
            if nv == p:
                continue
            if w % 2:
                dfs(nv, v, 1 - c)
            else:
                dfs(nv, v, c)

    dfs(0, -1, 0)
    print(*color, sep='\n')
    return


if __name__ == '__main__':
    main()

Solution (Python):
import sys
from collections import deque

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


def main():
    N = int(readline())
    G = [[] for _ in range(N)]
    for _ in range(N - 1):
        u, v, w = map(int, readline().split())
        G[u - 1].append((v - 1, w))
        G[v - 1].append((u - 1, w))

    dist = [-1] * N
    color = [0] * N
    dist[0] = 0
    queue = deque([0])
    while queue:
        v = queue.popleft()
        for nv, cost in G[v]:
            if dist[nv] == -1:
                dist[nv] = dist[v] + cost
                color[nv] = dist[nv] % 2
                queue.append(nv)

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


if __name__ == '__main__':
    main()

Solution (Python):
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n = int(input())
from collections import defaultdict
ns = defaultdict(set)
for i in range(n-1):
    u,v,w = map(int,input().split())
    u -= 1
    v -= 1
    ns[u].add((w, v))
    ns[v].add((w, u))
    
q = [(0,0)]
ans = [None]*n
ans[0] = 0
while q:
    d,u = q.pop()
    for w,v in ns[u]:
        if ans[v] is None:
            val = (w+d)%2
            q.append((val, v))
            ans[v] = val
write("\n".join(map(str, ans)))

Solution (Python):
from copy import deepcopy
from collections import deque
def main():
    def find(x):
        if par[x] < 0:
            return x
        else:
            par[x] = find(par[x])
            return par[x]
    def unite(x, y):
        x = find(x)
        y = find(y)
        if x == y:
            return False
        else:
            if par[x] > par[y]:
                x, y = y, x
            par[x] += par[y]
            par[y] = x
            return True
    def roots():
        return [i for i, x in enumerate(par) if x < 0]

    n = int(input())
    par = [-1] * n
    uvw = {e:[] for e in range(n)}

    for _ in range(n - 1):
        u, v, w = map(int, input().split())
        u -= 1
        v -= 1
        uvw[u].append((u, v, w))
        uvw[v].append((v, u, w))
        unite(u, v)
    root_node = roots()[0]
    color = [-1] * n
    color[root_node] = 0
    node_next = deque()
    node_next.append(root_node)
    node_next_next = deque()
    node_seen = set()

    while len(node_seen) < n:
        while node_next:
            node_togo = node_next.popleft()
            if node_togo in node_seen:
                continue
            else:
                node_seen.add(node_togo)
            
            node_adj = uvw[node_togo]
            node_next_next += [i[1] for i in node_adj]
            
            for adj in node_adj:
                if adj[1] in node_seen or color[adj[1]] != -1:
                    continue
                if adj[2] % 2 == 0:
                    color[adj[1]] = color[node_togo]
                else:
                    color[adj[1]] = color[node_togo] ^ 1
        node_next = deepcopy(node_next_next)
        node_next_next = deque()
    print(*color, sep='\n')


if __name__ == '__main__':
    main()

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

def bfs():
  ans[0]=0
  que=[0]
  while(que):
    now=que.pop(0)
    for i,j in l[now]:
      if ans[i]==-1:
        if j%2==0:
          ans[i]=ans[now]
        else:
          ans[i]=(ans[now]+1)%2
        que.append(i)

bfs()
for i in ans:print(i)

Solution (Python):
N=int(input())
links=[set() for _ in [0]*N]
for i in range(1,N):
  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=[(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,w+d,v))
print('\n'.join(map(str,ans)))

Solution (Python):
import sys
sys.setrecursionlimit(10000000)
MOD = 10 ** 9 + 7
INF = 10 ** 15

def main():
    N = int(input())
    G = [[] for _ in range(N)]
    for _ in range(N - 1):
        a,b,c = map(int,input().split())
        a -= 1
        b -= 1
        G[a].append((b,c))
        G[b].append((a,c))
    
    color = [0] * N
    dist = [-1] * N
    stack = [0]
    dist[0] = 0
    while stack:
        v = stack.pop()
        for e,c in G[v]:
            if dist[e] >= 0:
                continue
            dist[e] = dist[v] + c
            color[e] = dist[e]%2
            stack.append(e)
    print('\n'.join(map(str,color)))
if __name__ == '__main__':
    main()

Solution (Python):
from collections import deque

N = int(input())
edge = [[] for i in range(N)]
color = [-1] * 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([])
q.append((0,0))

while(q):
    cur, col = q.popleft()
    color[cur] = col
    for next, weight in edge[cur]:
        if color[next] != -1:
            continue

        if weight % 2:
            q.append((next, 1-col))
            color[next] = 1-col
        else:
            q.append((next, col))
            color[next] = col

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

Solution (Python):
import sys
from collections import defaultdict
readline = sys.stdin.buffer.readline
sys.setrecursionlimit(10**8)


def geta(fn=lambda s: s.decode()):
    return map(fn, readline().split())


def gete(fn=lambda s: s.decode()):
    return fn(readline().rstrip())


def main():
    N = gete(int)
    g = [set() for _ in range(N+1)]
    for _ in range(N-1):
        u, v, w = geta(int)
        g[u].add((v, w))
        g[v].add((u, w))

    dist = [-1] * (N+1)
    color = [-1]*(N+1)

    dist[1] = 0
    color[1] = 0

    def dfs(i, d):

        dist[i] = d
        color[i] = 0 if d & 1 == 0 else 1

        for j, wj in g[i]:
            if dist[j] < 0:
                dfs(j, d + wj)

    dfs(1, 0)

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


if __name__ == "__main__":
    main()

Solution (Python):

"""
@author: H_Hoshigi
49min 40sec
"""




def main():
    N = int(input())
    edge_list = [list(map(int, input().split()))  for i in range(N-1)]

    
    
    
    
    
    adj_list = [[] for i in range(N)]
    for edge in edge_list:
        adj_list[edge[0]-1].append([edge[1]-1, edge[2]%2])
        adj_list[edge[1]-1].append([edge[0]-1, edge[2]%2])

    
    INF = 2
    distance_list = [ INF for i in range(N)]
    distance_list[0] = 0

    
    dfs_list = [0]

    
    while dfs_list:
        now_node = dfs_list.pop(-1)
        now_dist = distance_list[now_node]
        for edge in adj_list[now_node]:
            if distance_list[edge[0]] == INF:
                distance_list[edge[0]] = (now_dist+edge[1])%2
                dfs_list.append(edge[0])
    
    
    for dist in distance_list:
        print(dist)
    return

if __name__ == "__main__":
    main()

Solution (Python):
n = int(input())
edge = [[int(i) for i in input().split()] for j in range(n-1)]
graph = [[] for _ in range(n+1)]
for i in range(n-1):
    u, v, w = edge[i][0], edge[i][1], edge[i][2] % 2
    graph[u].append((v,w))
    graph[v].append((u,w))

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

while stack:
    x = stack.pop()
    cx = color[x]
    dx = dist[x]
    for y, w in graph[x]:
        if color[y] >= 0:
            continue
        dist[y] = dist[x] + w
        if dist[x] ^ dist[y] == 0:
            color[y] = color[x]
        else:
            color[y] = (color[x] + 1) % 2
        stack.append(y)
print('\n'.join([str(n) for n in color[1:]]))

Solution (Python):
n = int(input())
edge = [[int(i) for i in input().split()] for j in range(n-1)]
graph = [[] for _ in range(n+1)]
for i in range(n-1):
    u, v, w = edge[i][0], edge[i][1], edge[i][2] % 2
    graph[u].append((v,w))
    graph[v].append((u,w))

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

while stack:
    x = stack.pop()
    cx = color[x]
    dx = dist[x]
    for y, w in graph[x]:
        if color[y] >= 0:
            continue
        dist[y] = dist[x] + w
        if dist[x] ^ dist[y] == 0:
            color[y] = color[x]
        else:
            color[y] = (color[x] + 1) % 2
        stack.append(y)
print('\n'.join([str(n) for n in color[1:]]))

Solution (Python):
import sys
sys.setrecursionlimit(10**7)
n = int(input())
to = [[] for _ in range(n)]
for _ in range(n - 1):
    u, v, w = map(int, input().split())
    u -= 1
    v -= 1
    to[u].append((v, w))
    to[v].append((u, w))
ans = [-1] * n
def dfs(u=0, c=0, parent=-1):
    ans[u] = c
    for v, w in to[u]:
        if v == parent:
            continue
        dfs(v, (c + w) & 1, u)

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

Solution (Python):
import sys
from io import StringIO
import unittest
import os

sys.setrecursionlimit(999999999)


def dfs(now, edge, colors):
    
    for i in edge[now]:
        
        if not colors[i[0]] == -1:
            continue

        
        
        colors[i[0]] = (i[1] % 2 + colors[now]) % 2

        
        dfs(i[0], edge, colors)



def resolve():
    n = int(input())
    uvw = [list(map(int, input().split())) for i in range(n - 1)]

    edge = [[] for i in range(n + 1)]

    
    
    for i in uvw:
        edge[i[0]].append([i[1], i[2]])
        edge[i[1]].append([i[0], i[2]])

    
    colors = [-1 for i in range(n + 1)]

    
    colors[1] = 1

    dfs(1, edge, colors)

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



class TestClass(unittest.TestCase):
    def assertIO(self, assert_input, output):
        stdout, sat_in = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(assert_input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, sat_in
        self.assertEqual(out, output)

    def test_input_1(self):
        test_input = """3
1 2 2
2 3 1"""
        output = """0
0
1"""
        self.assertIO(test_input, output)

    def test_input_2(self):
        test_input = """5
2 5 2
2 3 10
1 3 8
3 4 2"""
        output = """1
0
1
0
1"""
        self.assertIO(test_input, output)

    
    def tes_t_1original_1(self):
        test_input = """データ"""
        output = """データ"""
        self.assertIO(test_input, output)



if __name__ == "__main__":
    if os.environ.get("USERNAME") is None:
        
        resolve()

    else:
        
        unittest.main()

Solution (Python):
import sys
from io import StringIO
import unittest
import os

sys.setrecursionlimit(1000000)

def dfs(now, edge, colors):
    
    for i in edge[now]:
        
        if not colors[i[0]] == -1:
            continue

        
        
        colors[i[0]] = (i[1] % 2 + colors[now]) % 2

        
        dfs(i[0], edge, colors)



def resolve():
    n = int(input())
    uvw = [list(map(int, input().split())) for i in range(n - 1)]

    edge = [[] for i in range(n + 1)]

    
    
    for i in uvw:
        edge[i[0]].append([i[1], i[2]])
        edge[i[1]].append([i[0], i[2]])

    
    colors = [-1 for i in range(n + 1)]

    
    colors[1] = 1

    dfs(1, edge, colors)

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



class TestClass(unittest.TestCase):
    def assertIO(self, assert_input, output):
        stdout, sat_in = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(assert_input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, sat_in
        self.assertEqual(out, output)

    def test_input_1(self):
        test_input = """3
1 2 2
2 3 1"""
        output = """0
0
1"""
        self.assertIO(test_input, output)

    def test_input_2(self):
        test_input = """5
2 5 2
2 3 10
1 3 8
3 4 2"""
        output = """1
0
1
0
1"""
        self.assertIO(test_input, output)

    
    def tes_t_1original_1(self):
        test_input = """データ"""
        output = """データ"""
        self.assertIO(test_input, output)



if __name__ == "__main__":
    if os.environ.get("USERNAME") is None:
        
        resolve()

    else:
        
        unittest.main()

Solution (Python):
import collections
n = int(raw_input())
adj = collections.defaultdict(list)
for _ in range(n - 1):
	u, v, w = map(int, raw_input().split(' '))
	adj[u].append((v,w))
	adj[v].append((u,w))
h = [-1 for _ in range(n+1)]
h[1] = 0
def dfs(h, adj):
	stack = collections.deque([1])
	while(stack):
		u = stack.pop()
		for v,w in adj[u]:
			if h[v] == -1:
				h[v] = (1- h[u]) if (w % 2) else h[u]
				stack.append(v) 
dfs(h, adj)
for node in range(1, n + 1):  print h[node]

Solution (Python):
import collections
n = int(raw_input())

adj = collections.defaultdict(list)

for _ in range(n - 1):
	u, v, w = map(int, raw_input().split(' '))
	adj[u].append((v,w))
	adj[v].append((u,w))
h = { 1:0 }
def dfs(h, adj):
	stack = collections.deque([1])
	while(stack):
		u = stack.pop()
		for v,w in adj[u]:
			if v not in h:
				h[v] = (1- h[u]) if (w % 2) else h[u]
				stack.append(v) 
dfs(h, adj)
for node in range(1, n + 1): 
	print h[node]

Solution (Python):
import collections
n = int(raw_input())

adj = collections.defaultdict(list)

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


q = collections.deque([(1,0)])
h = { 1:0 }
while(q):
	u,c = q.popleft()
	for v,w in adj[u]:
		if v not in h:
			h[v] = (1- c) if (w % 2) else c
			q.append((v,h[v]))

for node in range(1, n + 1): 
	print h[node]

Solution (Python):
dic = {1:0,0:1}

from collections import deque 

q = deque([])

N = int(input())

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

q.append([1,0,0])

while len(q)>0:
    now,dist,pre = q.pop()
    ans[now] = (ans[pre] + dist%2)%2
    for i in tree[now]:
        if i[0]!=pre:
            q.append([i[0],i[1],now])

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

Solution (Python):
from sys import stdin, setrecursionlimit
from collections import deque


def main():
    input = stdin.buffer.readline
    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 = [-1] * n

    q = deque([0])
    ans[0] = 0

    while q:
        u = q.popleft()

        for v, w in g[u]:
            if ans[v] == -1:
                ans[v] = (ans[u] + w) % 2
                q.append(v)

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


if __name__ == "__main__":
    setrecursionlimit(10000)
    main()

Solution (Python):
n = int(input())
uvw = [0]*(n-1)
for i in range(n-1):
    uvw[i] = list(map(int,input().split()))
V = [[] for i in range(n+1)]
for u,v,w in uvw:
    V[u].append([v,w])
    V[v].append([u,w])
from collections import deque
q = deque([])
now = 1
reach = [0]*(n+1)
reach[now] = 2
q.append(now)
while q:
    x = q.popleft()
    for L in V[x]:
        if reach[L[0]] == 0:
            q.append(L[0])
            reach[L[0]] = reach[x] + L[1]
for A in reach[1:]:
    if A%2 == 0:
        print(0)
    else:
        print(1)

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


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

    q = deque()
    q.append(0)
    color = [-1 for _ in range(N)]
    color[0] = True

    

    while q:
        v = q.popleft()
        for w, nv in edge[v]:
            if color[nv] == -1:
                if w % 2 == 0:
                    color[nv] = color[v]
                else:
                    color[nv] = not color[v]
                q.append(nv)

    
    for c in color:
        if c:
            print(0)
        else:
            print(1)


if __name__ == '__main__':
    solve()

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

def dfs(now):
    for to,dis in G[now]:
        if color[to] == -1:
            color[to] = (color[now] + dis) % 2
            dfs(to)

N = int(input())
G = [[] for _ in range(N)]
color = [-1] * N
color[0] = 0 

for i in range(N-1):
    a,b,c = map(int,input().split())
    a -= 1
    b -= 1
    G[a].append([b,c%2])
    G[b].append([a,c%2])


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

Solution (Python):
def BFS(x):
    v = deque([x])
    d[x]=0
    
    while v:
        a = v.popleft()
        for num in L[a]:
            if d[num]==-1:
                d[num]= d[a]+dic[(a,num)]
                v.append(num)

from collections import deque
N=int(input())
u=[0]*(N-1)
v=[0]*(N-1)
w=[0]*(N-1)
d=[-1 for _ in range(N)]
dic={}
L=[ [] for _ in range(N)]
for i in range(N-1):
    u[i],v[i],w[i] = map(int,input().split())
    u[i] -=1
    v[i] -=1
    L[u[i]].append(v[i])
    L[v[i]].append(u[i])
    dic[ (u[i],v[i])]=w[i]
    dic[ (v[i],u[i])]=w[i]
    



BFS(0)

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

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 i in edges:
    a[i[0]].append([i[1],i[2]])
    a[i[1]].append([i[0],i[2]])
    

depth = [-1 for _ in range(n+1)]
depth[0] = 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(10 ** 6)
input = sys.stdin.readline

def dfs(d, v, p):
    if (d & 1):
        C[v] = 1
    for w, u in E[v]:
        if u == p:
            continue
        dfs(d ^ w, u, v)

N = int(input())
C = [0] * N
E = [[] for _ in range(N)]
for i in range(N-1):
    u, v, w = map(int, input().split())
    u -= 1
    v -= 1
    E[u].append((w % 2, v))
    E[v].append((w % 2, u))
dfs(0, 0, -1)
print(*C, sep='\n')

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

ans = [-1 for i in range(n+1)]

d = deque()
d.append(1)
ans[1] = 0
while d:
    now = d.popleft()
    for i , j in route[now]:
        if ans[i] == -1:
            if j % 2 == 0:
                ans[i] = ans[now]
            elif j % 2 == 1:
                ans[i] = (ans[now]+1)%2
            d.append(i)

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

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

Q = deque()
Q.append(0)
c = [-1] * N
c[0] = 0
while len(Q) > 0:
    q = Q.popleft()
    pc = c[q]
    for g, w in G[q]:
        if c[g] != -1:
            continue
        if w % 2 == 0:
            c[g] = pc
        else:
            c[g] = 1 - pc
        Q.append(g)

for i in c:
    print(i)

Solution (Python):
class Tree(): 
    def __init__(self, n, edge, indexed=1):
        self.n = n
        self.tree = [[] for _ in range(n)]
        for e in edge:
            self.tree[e[0] - indexed].append((e[1] - indexed, e[2]))
            self.tree[e[1] - indexed].append((e[0] - indexed, e[2]))

    def setroot(self, root):
        self.root = root
        self.parent = [None for _ in range(self.n)]
        self.parent[root] = -1
        self.depth = [None for _ in range(self.n)]
        self.depth[root] = 0
        self.distance = [None for _ in range(self.n)]
        self.distance[root] = 0
        self.order = []
        self.order.append(root)
        self.cost = [0 for _ in range(self.n)]
        self.size = [1 for _ in range(self.n)]
        stack = [root]
        while stack:
            node = stack.pop()
            for adj, cost in self.tree[node]:
                if self.parent[adj] is None:
                    self.parent[adj] = node
                    self.depth[adj] = self.depth[node] + 1
                    self.distance[adj] = self.distance[node] + cost
                    self.cost[adj] = cost
                    self.order.append(adj)
                    stack.append(adj)
        for node in self.order[::-1]:
            for adj, cost in self.tree[node]:
                if self.parent[node] == adj:
                    continue
                self.size[node] += self.size[adj]

import sys
input = sys.stdin.readline

N = int(input())
E = [tuple(map(int, input().split())) for _ in range(N - 1)]
t = Tree(N, E)
t.setroot(0)

for i in range(N):
    if t.distance[i] % 2 == 0:
        print(0)
    else:
        print(1)

Solution (Python):
import sys
import math
from collections import deque

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()



def make_adjlist_nond(n, edges):
    res = [[] for _ in range(n + 1)]
    for edge in edges:
        res[edge[0]].append([edge[1], edge[2]])
        res[edge[1]].append([edge[0], edge[2]])
    return res


def main():
    N = NI()
    edges = [NLI() for _ in range(N-1)]
    graph = make_adjlist_nond(N, edges)
    colors = [0]*(N+1)

    def dfs(node, prev):
        for goto, dist in graph[node]:
            if goto == prev:
                continue
            colors[goto] = 1 - colors[node] if dist % 2 else colors[node]
            dfs(goto, node)

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


if __name__ == "__main__":
    main()

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


def main():
    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=[-1]*n
    
    def sub(node,distance):
        for next_node, edge in G[node]:
            if ans[next_node]==-1:
                ans[next_node]=(distance+edge)%2
                sub(next_node,(distance+edge)%2)
    sub(0,0)
    
    for i in ans:
        print(i)
main()

Solution (Python):
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
import heapq
import math
from fractions import gcd
import random
import string
import copy
from itertools import permutations
from operator import mul
from functools import reduce
from bisect import bisect_left, bisect_right

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






N = getN()
edges = [[] for i in range(N)]
for i in range(N - 1):
    u, v, d = getNM()
    edges[u - 1].append([v - 1, d])
    edges[v - 1].append([u - 1, d])

def dij(start):
    dist = [float('inf') for i in range(N)]
    dist[start] = 0
    pq = [(0, start)]

    while len(pq) > 0:
        d, now = heapq.heappop(pq)
        if (d > dist[now]):
            continue
        for i in edges[now]:
            if dist[i[0]] > dist[now] + i[1]:
                dist[i[0]] = dist[now] + i[1]
                heapq.heappush(pq, (dist[i[0]], i[0]))
    return dist

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

Solution (Python):
from collections import deque
n = int(input())
to = [[] for i in range(n)]
col = [0] + [-1] * (n - 1)

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

search = deque([0])
while search:
    v = search.popleft()
    for nv, nw in to[v]:
        if col[nv] != -1:
            continue
        col[nv] = (col[v] + nw) % 2
        search.append(nv)
print(*col, sep='\n')

Solution (Python):
import sys
sys.setrecursionlimit(10**6)
n=int(input())
path=[[] for i in range(n)]
for i in range(n-1):
    u,v,w=map(int,input().split())
    path[u-1].append((v-1,w%2))
    path[v-1].append((u-1,w%2))
ans=[0]+[-1]*(n-1)
def dfs(i):
    global n,path,ans
    for j in path[i]:
        if ans[j[0]]==-1:
            if j[1]:
                ans[j[0]]=1-ans[i]
                dfs(j[0])
            else:
                ans[j[0]]=ans[i]
                dfs(j[0])
dfs(0)
print("\n".join(map(str,ans)))