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):
N = int(input())
nodes = {}
for _ in range(N-1):
    l, r, d = map(int, input().split())
    if nodes.get(str(l)) is None:
        nodes[str(l)] = {'to': [], 'color': -1}
    if nodes.get(str(r)) is None:
        nodes[str(r)] = {'to': [], 'color': -1}

    nodes[str(l)]['to'].append((str(r), d))
    nodes[str(r)]['to'].append((str(l), d))

q = [('1', 0)]
while q:
    node, color = q.pop()

    nodes[node]['color'] = color
    for n, d in nodes[node]['to']:
        if nodes[n]['color'] != -1:
            continue

        if d % 2 == 0:
            q.append((n, color))
        else:
            q.append((n, (color+1) % 2))


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

Solution (Python):
def d_even_relation(N, Nodes):
    from collections import deque
    graph = [{} for _ in range(N)]
    for u, v, w in Nodes:
        graph[u - 1][v - 1] = w
        graph[v - 1][u - 1] = w

    ans = [0] * N
    queue = deque([(-1, -1, 0)])
    while queue:
        previous, parent, child = queue.pop()
        if parent == -1:
            ans[child] = 0
        elif previous != child:
            length = graph[parent][child]
            if length % 2 == 0:
                ans[child] = ans[parent]
            else:
                ans[child] = 1 if ans[parent] == 0 else 0
        for k in graph[child].keys():
            if parent != k:
                queue.appendleft((parent, child, k))
    return '\n'.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(N, Nodes))

Solution (Python):
N = int(input())
nodes = {}
for _ in range(N-1):
    l, r, d = map(int, input().split())
    if nodes.get(str(l)) is None:
        nodes[str(l)] = {'to': [], 'color': -1}
    if nodes.get(str(r)) is None:
        nodes[str(r)] = {'to': [], 'color': -1}

    nodes[str(l)]['to'].append((str(r), d))
    nodes[str(r)]['to'].append((str(l), d))

q = [('1', 0)]
while q:
    node, color = q.pop()

    nodes[node]['color'] = color
    for n, d in nodes[node]['to']:
        if nodes[n]['color'] != -1:
            continue

        if d % 2 == 0:
            q.append((n, color))
        else:
            q.append((n, (color+1) % 2))


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

Solution (Python):
N = int(input())
d = {}
for i in range(N-1):
    u, v, w = map(int, input().split())
    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]]

isChecked = [False for i in range(N)]
ans = [0 for i in range(N)]
for k in d:
    c = ans[k-1]
    q = [[0, k]]
    while q:
        l = q[-1][0]
        p = q[-1][1]
        q.pop()
        
        if isChecked[p-1]:
            continue
        if l%2 == 0:
            ans[p-1] = c
        else:
            ans[p-1] = (c+1)%2
        isChecked[p-1] = True
        for e in d[p]:
            n = e[0]
            w = e[1]
            q.append([l+w, n])

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

Solution (Python):
def d_even_relation(N, Nodes):
    from collections import deque
    graph = [{} for _ in range(N)]
    for u, v, w in Nodes:
        graph[u - 1][v - 1] = w
        graph[v - 1][u - 1] = w

    ans = [0] * N
    queue = deque([(-1, -1, 0)])
    while queue:
        previous, parent, child = queue.pop()
        if parent == -1:
            ans[child] = 0
        elif previous != child:
            length = graph[parent][child]
            if length % 2 == 0:
                ans[child] = ans[parent]
            else:
                ans[child] = 1 if ans[parent] == 0 else 0
        for k in graph[child].keys():
            if parent != k:
                queue.appendleft((parent, child, k))
    return '\n'.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(N, Nodes))

Solution (Python):
import heapq
N = int(input())
L = []
edge = [[] for i in range(N)]
for i in range(N-1):
  x,y,z = map(int,input().split())
  edge[x-1].append([x-1,y-1,z])
  edge[y-1].append([x-1,y-1,z])
ans = ['TBD']*N
ans[0] = 0
edgelist = []
for i in edge[0]:
  heapq.heappush(edgelist,i)
while len(edgelist) != 0:
  ed = heapq.heappop(edgelist)
  if ans[ed[1]] == 'TBD':
    if ed[2]%2 == 0:
      if ans[ed[0]] == 0:
        ans[ed[1]] = 0
      else:
        ans[ed[1]] = 1
    else:
      if ans[ed[0]] == 0:
        ans[ed[1]] = 1
      else:
        ans[ed[1]] = 0
    for e in edge[ed[1]]:
      if ans[e[1]] == 'TBD':
        heapq.heappush(edgelist,e)
      elif ans[e[0]] == 'TBD':
        heapq.heappush(edgelist,e)
  elif ans[ed[0]] == 'TBD':
    if ed[2]%2 == 0:
      if ans[ed[1]] == 0:
        ans[ed[0]] = 0
      else:
        ans[ed[0]] = 1
    else:
      if ans[ed[1]] == 0:
        ans[ed[0]] = 1
      else:
        ans[ed[0]] = 0
    for e in edge[ed[0]]:
      if ans[e[1]] == 'TBD':
        heapq.heappush(edgelist,e)
      elif ans[e[0]] == 'TBD':
        heapq.heappush(edgelist,e)
for i in range(N):
  print(ans[i])

Solution (Python):
import sys

sys.setrecursionlimit(1000000)
n=int(input())
mat=[[] for i in range(n)]
group=[0]*n
group[0]=1
for i in range(n-1):
    u, v, w = map(int, input().split())
    mat[u-1].append((v-1, w))
    mat[v-1].append((u-1, w))
def C(kw, p, l):
    global group
    k, w = kw
    if w%2==1:
        p*=-1
    group[k]=p
    for kwi in mat[k]:
        if kwi[0]!=l:
            C(kwi, p, k)
for kwi in mat[0]:
    C(kwi, 1, 0)
for gi in group:
    if gi>0:
        print(1)
    else:
        print(0)

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

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

col = [-1 for _ 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%2)%2)

dfs(1, 0)

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

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



ret = {}
done = [0 for x in range(N)]

queue = [0]

for i in range(N):
    curr = queue.pop()
    if curr == 0:
        ret[0] = 0

    for neigh in x[curr]:
        if done[neigh[0]] == 1:
            continue
        if neigh[1] % 2 == 0:
            ret[neigh[0]] = ret[curr]
        else:
            ret[neigh[0]] = 0 if ret[curr] == 1 else 1

        queue.append(neigh[0])
    done[curr] = 1


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

Solution (Python):

import sys
import queue


def solve(N: int, adjacent):
    color = [0] * N
    visited = [False] * N

    visited[0] = True
    
    Q = queue.Queue()
    Q.put(0)
    while not Q.empty():
        u = Q.get()
        for v, w in adjacent[u]:
            if visited[v]:
                continue
            visited[v] = True
            if w == 0:
                color[v] = color[u]
            else:
                color[v] = (color[u] + 1) % 2
            Q.put(v)
    for c in color:
        print(c)



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

if __name__ == '__main__':
    main()

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

def BFS(K,edges,N):
  roots=[ [] for i in range(N)]
  for a,b,c in edges:
    roots[a-1]+=[(b-1,c)]
    roots[b-1]+=[(a-1,c)]
  dist=[-1]*N
  stack=[]
  stack.append(K)
  dist[K]=0
  while stack:
    label=stack.pop(-1)
    for i,c in roots[label]:
      if dist[i]==-1:
        dist[i]=dist[label]+c
        stack+=[i]
  return dist
 

edges=[]
N = int(input())
K = 1
for i in range(N-1):
  edges += [list(map(int,input().split()))]
distance = BFS(K-1,edges,N)
for i in range(N):
  print(distance[i] % 2)

Solution (Python):
inpl = lambda: list(map(int,input().split()))
class ParityTree:
    def __init__(self,N):
        self.parent = [-1]*int(N)
        self.parity = [0]*int(N)

    def root(self, n):
        if self.parent[n] < 0:
            return n, 0
        else:
            m, p = self.root(self.parent[n])
            self.parent[n] = m
            self.parity[n] = (p + self.parity[n]) % 2
            return m, self.parity[n]

    def merge(self, m, n, parity):
        rm, pm = self.root(m)
        rn, pn = self.root(n)
        if rm != rn:
            if -self.parent[rm] < -self.parent[rn]:
                rm, rn = rn, rm
            self.parent[rm] += self.parent[rn]
            self.parent[rn] = rm
            self.parity[rn] = (pm + pn + parity) % 2

    def size(self, n):
        return -self.parent[self.root(n)]
    
    def aresame(self, m, n):
        return self.root(m) == self.root(n)

N = int(input())
pt = ParityTree(N)
for i in range(N-1):
    u, v, w = inpl()
    pt.merge(u-1,v-1,w)

for i in range(N):
    print(pt.root(i)[1])

Solution (Python):
import sys
sys.setrecursionlimit(10**6)
def dfs(s):
    visited[s]=1
    for v in adj[s]:
        if v not in visited:
            if (s,v) in we:
                y[v]=y[s]+we[(s,v)]
            elif (v,s) in we:
                y[v]=y[s]+we[(v,s)]
            dfs(v)
n=int(input())
adj={}
we={}
visited={}
y=[0]*(n+1)
for q in range(n-1):
    a,b,w=map(int,input().split())
    if a not in adj:
        adj[a]=[b]
    else:
        adj[a].append(b)
    if b not in adj:
        adj[b]=[a]
    else:
        adj[b].append(a)
    we[(a,b)]=w
if n>1:
	dfs(1)
for i in range(1,n+1):
    if y[i]%2==0:
        print(0)
    else:
        print(1)

Solution (Python):
import sys
input = sys.stdin.readline
n=int(input())
E=[]
for i in range(n-1):
  u,v,w=map(int,input().split())
  E.append([u,v,w])
def BFS(edges,N):
  roots=[[] for i in range(N)]
  for a,b,c in edges:
    roots[a-1]+=[(b-1,c)]
    roots[b-1]+=[(a-1,c)]
  dist=[-1]*N
  stack=[]
  stack.append(0)
  dist[0]=0
  while stack:
    label=stack.pop(-1)
    for i,c in roots[label]:
      if dist[i]==-1:
        dist[i]=dist[label]+c
        stack+=[i]
  return dist
D=BFS(E,n)
for i in range(n):
  print(0 if D[i]%2==0 else 1)

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

tree = [list() for _ in range(N)]
color = [-1 for _ in range(N)]
color[0] = 0

for _ in range(N-1):
    u, v, w = map(int, input().strip().split(' '))
    tree[u-1] += [(v-1, w % 2)]
    tree[v-1] += [(u-1, w % 2)]


stack = [0]
while len(stack) > 0:
    pos = stack.pop()
    for (p, w) in tree[pos]:
        if color[p] == -1:
            color[p] = color[pos] ^ w
            stack.append(p)

for c in color:
    print(c)

Solution (Python):


import sys


s2nn = lambda s: [int(c) for c in s.split(' ')]
ss2nn = lambda ss: [int(s) for s in ss]
ss2nnn = lambda ss: [s2nn(s) for s in ss]
i2s = lambda: sys.stdin.readline().rstrip()
i2n = lambda: int(i2s())
i2nn = lambda: s2nn(i2s())
ii2ss = lambda n: [sys.stdin.readline().rstrip() for _ in range(n)]
ii2nn = lambda n: ss2nn(ii2ss(n))
ii2nnn = lambda n: ss2nnn(ii2ss(n))

def main():
    N = i2n()
    d = [[] for _ in range(N)]
    
    
    for _ in range(N-1):
        u, v, w = i2nn()
        b = w % 2 == 0
        d[u-1].append((v-1, b))
        d[v-1].append((u-1, b))
    nn = [-1 for _ in range(N)]
    nn[0] = 0
    def main2(src):
        links = d[src]
        c = nn[src]
        for dst, b in links:
            if nn[dst] == -1:
                nn[dst] = c if b else 1-c
                main2(dst)
    
    que = [0]
    que2 = []
    while True:
        if len(que) == 0:
            break
        que2 = []
        for src in que:
            links = d[src]
            c = nn[src]
            for dst, b in links:
                if nn[dst] == -1:
                    nn[dst] = c if b else 1-c
                    que2.append(dst)
        que = que2
    for n in nn:
        print(n)

main()

Solution (Python):
from collections import deque
N = input()
A = [[] for i in range(N)]
for i in range(N-1):
	a2,b2,c2 = map(int, raw_input().split())
	A[a2-1].append([b2-1,c2])
	A[b2-1].append([a2-1,c2])
A2 = [-1]*N
A2[0] = 0
q = deque([0])
while q:
	c = q.popleft()
	l = A2[c]
	for c0,c1 in A[c]:
		if(A2[c0] != -1):
			continue
		else:
			A2[c0] = (l + c1)%2
			q.append(c0)
for t in A2:
	print(t)

Solution (Python):
from collections import deque

N = int(input())

node = [[] for _ in range(N + 1)]

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


color = [-1] * (N + 1)
Q = deque()
for n, p in node[1]:
    Q.append((n, p, 1))

color[1] = 0

while Q:
    a, b, cur = Q.popleft()
    if b:
        color[a] = color[cur]
    else:
        color[a] = 1 - color[cur]

    for n, p in node[a]:
        if color[n] == -1:
            Q.append((n, p, a))

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

Solution (Python):
from collections import deque

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

adj = [[] for _ in range(N+1)]
for b in branch:
  adj[b[0]].append([b[1],b[2]])
  adj[b[1]].append([b[0],b[2]])

ans = [-1] * (N+1)
deq = deque()
deq.appendleft(1)
while len(deq) > 0:
  v = deq.pop()
  for u, w in adj[v]:
    if ans[u] == -1:
      deq.appendleft(u)
    if ans[v] == -1 and ans[u] == -1:
      if w % 2 == 0:
        ans[v] = 0
        ans[u] = 0
      else:
        ans[v] = 0
        ans[u] = 1
    elif ans[v] == 0:
      if w % 2 == 0:
        ans[u] = 0
      else:
        ans[u] = 1
    else:
      if w % 2 == 0:
        ans[u] = 1
      else:
        ans[u] = 0
for i in range(1,N+1):
  print(ans[i])

Solution (Python):
from queue import Queue

N = int(input())

BLACK = -1
GRAY = 0
WHITE = 1
nodes = [GRAY] * N
nodes[0] = BLACK
neighbors = [[] for _ in range(N)]

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


def bfs():
    q = Queue()
    q.put(0)
    while not q.empty():
        u = q.get()

        neiss = neighbors[u]
        for neis in neiss:
            v, w = neis
            if nodes[v] == GRAY:
                if w % 2 == 0:
                    nodes[v] = nodes[u]
                else:
                    nodes[v] = -nodes[u]
                q.put(v)


bfs()

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

Solution (Python):
from collections import defaultdict, deque

def main():
    n = int(input())
    edges = defaultdict(list)

    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))
    
    vertexes = solve(edges, n)
    for v in vertexes:
        print(v)

def solve(edges, n):
    vertexes = [None for _ in range(n)]
    vertexes[0] = 0

    q = deque()
    q.append(0)

    while q:
        u = q.popleft()

        for v, w in edges[u]:
            if vertexes[v] is not None:
                continue
            if w % 2 == 0:
                vertexes[v] = vertexes[u]
            else:
                vertexes[v] = 1 - vertexes[u]
            q.append(v)
    
    return vertexes
    
main()

Solution (Python):

import sys
input = sys.stdin.readline

N = int(input())
lis = [[0,True]for _ in range(N)]
adj =[{}for _ in range(N)]
for i in range(N-1):
    i,j,w = map(int,input().split())
    i -= 1
    j -= 1
    w = w%2
    adj[i][j]=w
    adj[j][i]=w

lis[0][1] =False
tsugi =[0]
while len(tsugi)!=0:
    foo = []
    for i in tsugi:
        for j in adj[i].keys():
            if lis[j][1]:
                lis[j][0]=lis[i][0]+adj[i][j]
                foo.append(j)
            adj[j].pop(i)
        adj[i].clear()
    tsugi = foo

ans = [str(i[0]%2) for i in lis]
print("\n".join(ans))

Solution (Python):
import numpy as np
import math
import sys

sys.setrecursionlimit(1000000)

def contrary_bit(bit):
    if (bit == 1):
        return 0
    elif (bit == 0):
        return 1
    else:
        print("error")

def dfs(adj_lists, nodes, node):
    
    neighbors = adj_lists[node]
    for neighbor in neighbors:
        if (nodes[neighbor[0]] != -1):
            
            continue
        else:
            if neighbor[1] % 2 == 0:
                
                nodes[neighbor[0]] = nodes[node]
                nodes = dfs(adj_lists, nodes, neighbor[0])
            else:
                nodes[neighbor[0]] = contrary_bit(nodes[node])
                nodes = dfs(adj_lists, nodes, neighbor[0])
    return nodes

def main():
    N = int(input())
    adj_lists = {}
    for i in range(1, N + 1):
        adj_lists[i] = []
    nodes = [-1] * (N + 1)
    for _ in range(N - 1):
        u, v, w = map(int, input().split())
        adj_lists[u].append((v, w))
        adj_lists[v].append((u, w))
    nodes[1] = 1
    nodes = dfs(adj_lists, nodes, 1)
    ans = nodes[1:]
    for color in ans:
        print(color)

if __name__ == '__main__':
    main()

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

g_list = [[] for _ in range(n)]
for gi in g:
    g_list[gi[0] - 1].append([gi[1] - 1, gi[2] % 2])
    g_list[gi[1] - 1].append([gi[0] - 1, gi[2] % 2])


color = [-1] * n

from collections import deque

q = deque()

color[0] = 0
q.append(0)
while q:
    v = q.popleft()
    for i, j in g_list[v]:
        if color[i] == -1:
            color[i] = (color[v] + j) % 2
            q.append(i)

[print(c) for c in color]

Solution (Python):
from collections import deque

def bfs(li,f,n):
    queue = deque([1])
    f[1] = 1
    count = 0
    ans = [0 for i in range(n+1)]
    while queue:
        point = queue.popleft()
        
        for i in li[point]:
            if f[i[0]] == -1:
                f[i[0]] = 1
                if ans[point] == 0 and i[1]%2 != 0:
                    ans[i[0]] = 1
                elif ans[point] == 1 and i[1]%2 == 0:
                    ans[i[0]] = 1
                queue.append(i[0])
    for i in ans[1:]:
        print(i)


n=int(input())
li=[[] for i in range(n+1)]
for i in range(n-1):
    f,t,w = map(int,input().split())
    li[f].append((t,w))
    li[t].append((f,w))
f=[-1 for i in range(n+1)]
bfs(li,f,n)

Solution (Python):
from collections import defaultdict
from queue import Queue
N = int(input())
e_dict = {}

num_e_count = defaultdict(int)
edge_dict = defaultdict(list)
for _ in range(N-1):
    u, v, w = tuple(map(int, input().split()))
    e_dict[(u, v)] = not bool(w%2)
    e_dict[(v, u)] = not bool(w%2)
    num_e_count[v]+=1
    num_e_count[u]+=1
    edge_dict[v].append(u)
    edge_dict[u].append(v)

start_point = None
for k, v in num_e_count.items():
    if v == 1:
        start_point = k
        break


result = [None] * N

result[start_point-1] = 1

done_set = set()
next_points = Queue(maxsize=N)
next_points.put(start_point)

while len(done_set) < N:
    u = next_points.get()
    for v in edge_dict[u]:
        if v not in done_set:
            next_points.put(v)
            if e_dict[(u, v)]:
                result[v-1] = result[u-1]
            else:
                result[v-1] = 1 - result[u-1]
        done_set.add(u)

for r in result:
    print(r)

Solution (Python):
from heapq import heappush, heappop
def dijkstra(graph:list, node:int, start:int) -> list:
    
    inf = float('inf')
    dist = [inf]*node

    dist[start] = 0
    heap = [(0,start)]
    while heap:
        cost,thisNode = heappop(heap)
        for NextCost,NextNode in graph[thisNode]:
            dist_cand = dist[thisNode]+NextCost
            if dist_cand < dist[NextNode]:
                dist[NextNode] = dist_cand
                heappush(heap,(dist[NextNode],NextNode))
    return dist
    



from collections import defaultdict
from heapq import heappop, heappush

class Graph(object):

    def __init__(self):
        self.graph = defaultdict(list)

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

    def add_edge(self, From, To, cost=1):
        self.graph[From].append((To,cost))

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

class Dijkstra(object):

    def __init__(self, graph, start):
        self.g = graph.graph
        self.dist = defaultdict(lambda:float('inf'))
        self.dist[start] = 0
        self.prev = defaultdict(lambda: None)
        self.Q = []
        heappush(self.Q,(self.dist[start], start))

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

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

    def shortest_path(self, goal):
        path = []
        node = goal
        while node is not None:
            path.append(node)
            node = self.prev[node]

        return path[::-1]

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

dijkstra = Dijkstra(g,0)
for i in range(N):
    print(dijkstra.shortest_distance(i)%2)

Solution (Python):
import sys
sys.setrecursionlimit(10**5+1)
n = int(input())
if n==1:
  print(0)
  exit()
from collections import defaultdict
edge = defaultdict(list)
for i in range(n-1):
  u, v, w = list(map(int, input().split()))
  edge[u].append((v, w))
  edge[v].append((u, w))
graph = [-1 for i in range(n+1)]

def dfs(x, c):
  nexts = edge.get(x)
  if nexts is None:
    return
  if graph[x]!=-1:
    return
  else:
    graph[x] = c
  for y, w in nexts:
    if w%2:
      dfs(y, not c)
    else:
      dfs(y, c)

dfs(1, 0)
for i in range(1, n+1):
  print(int(graph[i]))

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








from queue import Queue
q = Queue()










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

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

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

N = int(input())

edges = [{} for i in range(N)]
colors = [0 for i in range(N)]

def dfs(s, dist):

    for key, val in edges[s].items():
        d = dist + val
        if d % 2 == 0:
            colors[key] = 0 
        else :
            colors[key] = 1
        
        if s in edges[key]:
            del edges[key][s]

        dfs(key, d)

    return

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

dfs(0, 0)

for color in colors:
    print(color)

Solution (Python):
import sys
sys.setrecursionlimit(100000)
def search(i, visited, ns, ans) :
    
    visited[i] = True
    for next, weight in ns[i]:
        if visited[next] == False:
            if weight % 2 == 0:
                ans[next] = ans[i]
            else:
                ans[next] = (ans[i]+1) % 2
            search(next, visited, ns, ans)


def dfs(ns, ans):
    visited = [False] * len(ns)
    search(0, visited, ns, ans)

def main():
    n = int(input())
    ns = [[] for _ in range(n)]
    for _ in range(n-1):
        (st,end,weight) = map(int,input().split())
        ns[st-1].append((end - 1,weight))
        ns[end-1].append((st-1,weight))
    ans = [False] * n
    dfs(ns, ans)
    for a in ans:
        if a:
            print(1)
        else:
            print(0)

if __name__ == '__main__':
    main()

Solution (Python):
from collections import deque

N = int(input())

node = [[] for _ in range(N + 1)]

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


color = [-1] * (N + 1)
Q = deque()
for n, p in node[1]:
    Q.append((n, p, 1))

color[1] = 0

while Q:
    a, b, cur = Q.popleft()
    if b:
        color[a] = color[cur]
    else:
        color[a] = 1 - color[cur]

    for n, p in node[a]:
        if color[n] == -1:
            Q.append((n, p, a))

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

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

n=int(input())
g=[[] for i in range(1+n)]
v=[0]*(1+n)
c=[-1]*(1+n)
flg=False
for i in range(n-1):
    a,b,w=map(int,input().split())
    g[a].append((b,w))
    g[b].append((a,w))
    if w%2==1:
        flg=True

def bfs(x):
    if v[x]!=0:
        return
    q=deque()
    q.append(x)
    v[x]=1
    while len(q)>0:
        cur=q.popleft()

        for nei in g[cur]:
            y=nei[0]
            d=nei[1]
            if v[y]==0:
                q.append(y)
                v[y]=1
                if d%2==1:
                    c[y]=1-c[cur]
                else:
                    c[y]=c[cur]
            

c[1]=0
bfs(1)

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

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

from heapq import heappush, heappop

def dijkstra(graph, start):
    A = [None] * (N)
    queue = [(0, start)]
    while queue:
        path_len, v = heappop(queue)
        if A[v] is None: 
            A[v] = path_len
            for w, edge_len in graph[v].items():
                if A[w] is None:
                    heappush(queue, (path_len + edge_len, w))

    
    return [0 if x is None else x for x in A]




graph = {}
for a,b,c in edges:
    a = a-1
    b = b-1
    if not a in graph:
        graph[a] = {}
    if not b in graph:
        graph[b] = {}
    graph[a][b] = c
    graph[b][a] = c
    
    
shortest = dijkstra(graph, 0)

for s in shortest:
    print(s % 2)

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

n = int(input())
ans = [-1]*(n+1)
data =[[] for i in range(n+1)]

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

ans[1] = 1
def color(i):
    for v, w in data[i]:
        if ans[v] == -1:
            if w % 2 == 0:
                ans[v] = ans[i]
            else:
                ans[v] = 1 - ans[i]
            color(v)
    return

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

Solution (Python):
import sys
sys.setrecursionlimit(100000000)
from collections import defaultdict
N = int(input())
tree = defaultdict(list)
for i in range(N-1):
    u,v,w = map(int,input().split())
    tree[u].append((v,w))
    tree[v].append((u,w))

ans = {}
reached = [False] * (N+1)

def dfs(u,v,s):
    reached[v] = True
    if s % 2 == 0: ans[v] = 0
    else: ans[v] = 1
    for n in tree[v]:
        if not reached[n[0]]:
            dfs(v,n[0],s+n[1])

ans[1] = 0
reached[1] = True
for v in tree[1]:
    dfs(1,v[0],v[1])

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

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

d = dict()
for u, v, w in UVW:
    if u-1 not in d:
        d[u-1] = []
    if v-1 not in d:
        d[v-1] = []
    d[u-1] += [(v-1, w)]
    d[v-1] += [(u-1, w)]

visited = [False]*(N)
visited[0] = True
l = [0]*N
q = [0]
while q:
    
    len_q = len(q)
    for u in q[:]:
        for v, w in d[u]:
            if visited[v] == True:
                continue
            visited[v] = True
            if w%2 == 0:
                l[v] = l[u]
            else:
                l[v] = (l[u]+1)%2
            q.append(v)
    q = q[len_q:]
            
    

for m in l:
    print(m)

Solution (Python):
from heapq import heappush, heappop
def dijkstra(graph:list, node:int, start:int) -> list:
    
    inf = float('inf')
    dist = [inf]*node

    dist[start] = 0
    heap = [(0,start)]
    while heap:
        cost,thisNode = heappop(heap)
        for NextCost,NextNode in graph[thisNode]:
            dist_cand = dist[thisNode]+NextCost
            if dist_cand < dist[NextNode]:
                dist[NextNode] = dist_cand
                heappush(heap,(dist[NextNode],NextNode))
    return dist
    



from collections import defaultdict
from heapq import heappop, heappush

class Graph(object):

    def __init__(self):
        self.graph = defaultdict(list)

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

    def add_edge(self, From, To, cost=1):
        self.graph[From].append((To,cost))

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

class Dijkstra(object):

    def __init__(self, graph, start):
        self.g = graph.graph
        self.dist = defaultdict(lambda:float('inf'))
        self.dist[start] = 0
        self.prev = defaultdict(lambda: None)
        self.Q = []
        heappush(self.Q,(self.dist[start], start))

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

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

    def shortest_path(self, goal):
        path = []
        node = goal
        while node is not None:
            path.append(node)
            node = self.prev[node]

        return path[::-1]

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

dijkstra = Dijkstra(g,0)
for i in range(N):
    print(dijkstra.shortest_distance(i)%2)

Solution (Python):
N = int(input())
V = [[] for _ in range(N+1)]
check = [0]*(N+1)
color = [0]*(N+1)
d = dict()
for _ in range(N-1):
    u, v, w = map(int, input().split())
    V[u].append((v, w))
    V[v].append((u, w))

color[1] = 1
check[1] = 1
queue = []
for u, w in V[1]:
    queue.append((u, w))
    d[u] = color[1]
while queue:
    u, w = queue.pop()
    check[u] = 1
    if w % 2:
        if d[u]:
            color[u] = 0
        else:
            color[u] = 1
    else:
        color[u] = d[u]
    for next_u, next_w in V[u]:
        if check[next_u] == 0:
            queue.append((next_u, next_w))
            d[next_u] = color[u]

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