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
from collections import deque
def solve():
  n = int(input())
  treenode = [[] for _ in range(n)]
  treecolor = [-2]*n
  for i in range(n-1):
    u,v,w = (int(i) for i in input().split())
    u -= 1
    v -= 1
    treenode[u].append((v,w%2))
    treenode[v].append((u,w%2))
  query = deque([(0,0,0)])
  while query:
    a,b,c = query.popleft()
    if b%2 == 0:
      treecolor[a] = c
      nextc = c
    else:
      treecolor[a] = 1^c
      nextc = 1^c
    for nextnode,weight in treenode[a]:
      if treecolor[nextnode] != -2:
        continue
      else:
        query.append((nextnode,weight,nextc))  
        treecolor[nextnode] = -1
  for i in treecolor:
    print(i)
solve()

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

n = int(input())
route = [[] for i in range(n)]
for i in range(n-1):
	u, v, w = map(int,input().split())
	route[u-1].append((v-1,w))
	route[v-1].append((u-1,w))
	
ans=[-1]*n
def dfs(p,d):
	ans[p] = d
	for i,j in route[p]:
		if ans[i] < 0:
		    dfs(i, (d+j) % 2)
dfs(0,0)

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

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

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

d = [0] * N
q = [0]
while q:
    p = q.pop()
    for n, w in link[p]:
        if d[n] == 0:
            d[n] = d[p] + w
            q.append(n)

for i in d:
    print(i % 2)

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

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

d = [-1] * N
d[0] = 0
q = [0]
while q:
  i = q.pop(0)
  for n, w in link[i]:
    if d[n] == -1:
      d[n] = d[i] + w
      q.append(n)

for i in d:
  print(i % 2)

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

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

d = [-1] * N
d[0] = 0
q = [0]
while q:
  i = q.pop()
  for n, w in link[i]:
    if d[n] == -1:
      d[n] = d[i] + w
      q.append(n)

for i in d:
  print(i % 2)

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N = int(readline())
m = map(int,read().split())
UVW = zip(m,m,m)



graph = [[] for _ in range(N+1)]
for u,v,w in UVW:
    graph[u].append((v,w))
    graph[v].append((u,w))

color = [0] * (N+1)
stack = [1]
parent = [0] * (N+1)
while stack:
    x = stack.pop()
    for y,w in graph[x]:
        if y == parent[x]:
            continue
        parent[y] = x
        color[y] = color[x]^(w&1)
        stack.append(y)

print('\n'.join(map(str,color[1:])))

Solution (Python):

import sys
input = lambda: sys.stdin.readline()[:-1]
sys.setrecursionlimit(10**8)


n = int(input())
uvw = [list(map(int, input().split())) for i in range(n-1)]
graph = [[] for i in range(n+1)]
color = [-1]*(n+1)
for u, v, w in uvw:
    graph[u].append((v, w))
    graph[v].append((u, w))

color[1] = 1
ne = [1]
while ne:
    t = ne.pop()
    for v, w in graph[t]:
        if color[v] == -1:
            ne.append(v)
            color[v] = color[t] if w % 2 == 0 else (color[t]+1) % 2

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

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

N = int(input())
G = [[] for _ in range(N+1)]

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

deq = deque()
deq.append(1)
res = [-1]*(N+1)
res[1] = 0

while deq:
  x = deq.popleft()
  for e, w in G[x]:
    if res[e] == -1:
      res[e] = (res[x]+w)%2
      deq.append(e)
[print(r) for r in res[1:]]

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

N = int(input())
G = [[] for _ in range(N+1)]

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

res = [0]*(N+1)

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

dfs(1, 0, 0)      
[print(r) for r in res[1:]]

Solution (Python):
import collections

n=int(input())
g=[[] for _ in range(n+1)] 
for _ in range(n-1):
  a,b,w=map(int,input().split())
  g[a].append((b,w))
  g[b].append((a,w))
q=collections.deque()
q.append(1)
checked=[0]*(n+1)
ans=[0]*(n+1)
ans[1]=0
while len(q)!=0:
  v=q.popleft()
  checked[v]=1
  for u,w in g[v]:
    if checked[u]==0:
      if w%2==0:
        ans[u]=ans[v]
      else:
        ans[u]=ans[v]^1
      q.append(u)
for i in range(1,n+1):
  print(ans[i])

Solution (Python):





import sys
sys.setrecursionlimit(10**7)

n=int(input())
node=[None]*n
edge=[[] for _ in range(n)]


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


def dfs(v,p,c):
    node[v]=c
    for vv,w in edge[v]:
        if vv==p:continue
        dfs(vv,v,1-c) if w%2 else dfs(vv,v,c)


dfs(0,-1,0)

for e in node:
    print(e)

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

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

color = [-1] * N

def dfs(v=0, pv=-1, d=0):
    color[v] = d % 2
    for nv, nw in ad[v]:
        if nv == pv:
            continue
        nd = d + nw
        dfs(nv, v, nd)
        
dfs()
for c in color:
    print(c)

Solution (Python):
def is_bipartite(graph, start, n):
    stack = [start]
    visited = [-1] * (n+1)
    visited[start] = 0
    while stack:
        u = stack.pop()
        for v,w in graph[u].items():
            if visited[v] != -1:
                continue
            visited[v] = (visited[u] ^ 1) if w % 2 else visited[u]
            stack.append(v)
    return visited

n = int(input())
graph = {}

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

[print(color) for color in is_bipartite(graph, 1, n) if color > -1]

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

N = int(input())
edges = [[] for _ in range(N)]

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

colors = [None] * N

def set_color(x, c):
    colors[x] = c
    for y, sgn in edges[x]:
        if colors[y] == None:
            set_color(y, c*sgn)

set_color(0, 1)
for z in colors:
    print((z+1)//2)

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

N = int(input())
edges = [[] for _ in range(N)]

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

colors = [None] * N
def set_color(x, c):
    colors[x] = c
    for y, sgn in edges[x]:
        if colors[y] == None:
            set_color(y, c*sgn)
set_color(0, 1)
for z in colors:
    print((z+1)//2)

Solution (Python):
import sys
sys.setrecursionlimit(10**6)
n=int(input())
edge=[[]for i in range(n+1)]
for i in range(n-1):
    a,b,c=map(int,input().split())
    if c%2==0:
        edge[a].append((b,1))
        edge[b].append((a,1))
    else:
        edge[a].append((b,-1))
        edge[b].append((a,-1))
        

ans=[None]*(n+1)


def set_color(x,col):
    ans[x]=col
    for i,j in edge[x]:
        if ans[i] is None:
            set_color(i,j*col)
    
    
set_color(1,1)
            
for i in ans[1:]:
    print((i+1)//2)

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 7)


def dfs(v):
    for u, w in e[v]:
        if c[u] != -1:
            continue
        c[u] = (c[v] + w) % 2
        dfs(u)


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

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

dfs(0)

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

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

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

g = [[] for _ in range(n)]

for u, v, w in uvw:
    u -= 1
    v -= 1
    g[u].append([v, w])
    g[v].append([u, w])


WHITE = 0
GRAY = 1
BLACK = 2

ds = [0] * n
colors = [WHITE] * n


def dfs(u):
    if colors[u] == BLACK:
        return

    colors[u] = GRAY

    for v, w in g[u]:
        if colors[v] == WHITE:
            ds[v] = ds[u] + w
            dfs(v)

    colors[u] = BLACK


dfs(0)

for d in ds:
    print(d % 2)

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

g = [[] for _ in range(n)]

for u, v, w in uvw:
    u -= 1
    v -= 1
    g[u].append([v, w])
    g[v].append([u, w])


WHITE = 0
GRAY = 1
BLACK = 2

ds = [0] * n
colors = [WHITE] * n
ps = [-1] * n


def dfs(s):
    stack = []

    ds[s] = 0
    colors[s] = BLACK
    ps[s] = -1
    stack.append(ds[s])

    while stack:
        u = stack[-1]
        colors[u] = GRAY

        for v, w in g[u]:
            if colors[v] == WHITE:
                stack.append(v)
                ds[v] = ds[u] + w
                ps[v] = u
                g[u].remove([v, w])
                g[v].remove([u, w])
                break

        else:
            stack.pop()
            colors[u] = BLACK

    return ds, ps


dfs(0)

for d in ds:
    print(d % 2)

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

g = [[] for _ in range(n)]

for u, v, w in uvw:
    u -= 1
    v -= 1
    g[u].append([v, w])
    g[v].append([u, w])


WHITE = 0
GRAY = 1
BLACK = 2

ds = [0] * n
colors = [WHITE] * n
ps = [-1] * n


def dfs(s):
    global ds, colors, ps

    stack = []

    ds[s] = 0
    colors[s] = BLACK
    ps[s] = -1
    stack.append(ds[s])

    while stack:
        u = stack[-1]
        colors[u] = GRAY

        for v, w in g[u]:
            if colors[v] == WHITE:
                stack.append(v)
                ds[v] = ds[u] + w
                ps[v] = u
                g[u].remove([v, w])
                g[v].remove([u, w])
                break

        else:
            stack.pop()
            colors[u] = BLACK

    return ds, ps


dfs(0)

for d in ds:
    print(d % 2)

Solution (Python):
import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

def solve(M: list, d: list, visited: list, u: int = 0):
    global N
    visited[u] = True
    for m in M[u]:
        i = m[0]
        w = m[1]
        if not visited[i]:
            d[i] = d[u] + w
            solve(M, d, visited, i)


def main():
    global N
    N = int(input())
    M = [[] for _ in range(N)]
    for _ in range(N-1):
        u, v, w = map(int, input().split())
        M[u-1].append((v-1, w))
        M[v-1].append((u-1, w))
    visited = [False] * N
    d = [0] * N
    solve(M, d, visited)
    for i in d:
        if i%2 == 0:
            print(0)
        else:
            print(1)

if __name__ == '__main__': main()

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

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

for i in range(n-1):
    u,v,w=map(int,input().split())
    if w%2==0:
        edge[u].append((v,1))
        edge[v].append((u,1))
    else:
        edge[u].append((v,-1))
        edge[v].append((u,-1))
        
color=[None]*(n+1)

def set_color(x,col):
    color[x]=col
    
    for i,j in edge[x]:
        if color[i] is None:
            set_color(i,j*col)

set_color(1,1)
for i in color[1:]:
    print((i+1)//2)

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

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

for i in range(n-1):
    u,v,w=map(int,input().split())
    if w%2==0:
        edge[u].append((v,1))
        edge[v].append((u,1))
    else:
        edge[u].append((v,-1))
        edge[v].append((u,-1))
        
color=[None]*(n+1)

def set_color(x,col):
    color[x]=col
    
    for i,j in edge[x]:
        if color[i] is None:
            set_color(i,j*col)

set_color(1,1)
for i in color[1:]:
    print((i+1)//2)

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

n=int(input())

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

for i in range(n-1):
    v1,v2,w=map(int,input().split())
    if w%2!=0:
        edge[v1].append((v2,-1))
        edge[v2].append((v1,-1))
    else:
        edge[v1].append((v2,1))
        edge[v2].append((v1,1))

color=[None]*(n+1)        
def set_color(x,col):
    color[x]=col
    
    for i,j in edge[x]:
        if color[i] is None:
            set_color(i,j*col)
set_color(1,1)

for x in color[1:]:
    print((x+1)//2)

Solution (Python):
import heapq
import sys

input = sys.stdin.readline

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

def main():
    N = int(input())
    edge = [[] for i in range(N)]

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

    D = dijkstra_heap(0,edge,N)
    first = D[0]
    for d in D:
        if abs(d - first) % 2 == 0:
            print(0)
        else:
            print(1)

main()

Solution (Python):
import sys
sys.setrecursionlimit(10**7)
N=int(input())
L=[[] for _ in range(N)]
for i in range(N-1):
  u,v,w=map(int,input().split())
  w=w%2
  L[u-1].append([v,w])
  L[v-1].append([u,w])
  

col=[-1]*N
def dfs(p):
  for i in L[p-1]:
    if col[i[0]-1]!=-1:
      pass
    else:
      col[i[0]-1]=abs(i[1]-col[p-1])
      dfs(i[0])

col[0]=0
dfs(1)

for i in col:
  print(i)

Solution (Python):
import math
import collections
import itertools
import sys
import bisect
from heapq import heappop,heappush,heapify
sys.setrecursionlimit(10**6)
def MAP(): return list(map(int,input().split()))
def INT(): return int(input())
def FLOAT(): return float(input())
MOD = 10**9+7


N = INT()
G = [dict() for _ in range(N)]
for i in range(N-1):
    u,v,w=map(int,input().split())
    G[u-1][v-1]=w
    G[v-1][u-1]=w
color=[-1 for _ in range(N)]
dist=[-1 for _ in range(N)]
dist[0]=0
q=[0]
while q:
    r=q.pop()
    for p in G[r]:
        if dist[p]!=-1:
            continue
        dist[p]=dist[r]+G[r][p]
        q.append(p)
for i in range(N):
    color[i]=dist[i]%2
for ans in color:
    print(ans)

Solution (Python):


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

Node = [None]*N 
Node[0] = True
queue = deque([0])  
while queue != deque([]):
    p = queue.popleft()
    for u,w in S[p]:    
        if Node[u] == None: 
            queue.append(u) 
            Node[u] = Node[p]^(w%2==1)  



for i in range(N):
    print([0,1][Node[i]])

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

global color 
global adlist
color = [0 for _ in range(100001)] 

def make_adlist(N, uvw):
  global adlist
  adlist = [[] for _ in range(N)]
  for u, v, w in uvw:
    adlist[u-1] += [[v-1, w%2]]
    adlist[v-1] += [[u-1, w%2]]
  return adlist 

def dfs(v, c):
  global color
  global adlist
  color[v] = c
  for next_v, w in adlist[v]:
    if color[next_v] != 0:
      continue
    if color[next_v] == 0 and w % 2 != 0:
      dfs(next_v, -c)
    elif color[next_v] == 0 and w % 2 == 0:
      dfs(next_v, c)

  return 


def main():
  N = int(input())
  uvw = [list(map(int, input().split())) for _ in range(N-1)]
  adlist = make_adlist(N, uvw)
  dfs(0, 1)
  for c in color[:N]:
    if c == 1:
      print(1)
    else:
      print(0)


if __name__ == "__main__":
  main()

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

def main():
    def dfs(i=0,oi=-1):
        for ki,w in to[i]:
            if ki==oi:continue
            ans[ki]=(ans[i]+w)%2
            dfs(ki,i)

    n=int(input())
    to=defaultdict(list)
    for _ 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])
    ans=[-1]*n
    ans[0]=0
    dfs()
    for x in ans:
        print(x)
main()

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

n = int(input())
edges = [[int(i) for i in input().split()] for _ in range(n - 1)]

BLACK = 1
WHITE = 0
UNKNOWN = -1

import sys
if n == 1:
    print(BLACK)
    sys.exit(0)

colors = [UNKNOWN] * (n + 1)

graph = [[] for _ in range(n + 1)]
for e in edges:
    graph[e[0]].append((e[1], e[2]))
    graph[e[1]].append((e[0], e[2]))

def dfs(graph, colors, current_point, current_color):
    colors[current_point] = current_color

    for next_point_info in graph[current_point]:
        if colors[next_point_info[0]] != UNKNOWN:
            continue
        if (next_point_info[1] % 2 == 0):
            next_color = current_color
        else:
            next_color = 1 - current_color
        dfs(graph, colors, next_point_info[0], next_color)

dfs(graph, colors, 1, BLACK)
for c in colors[1:]:
    print(c)

Solution (Python):
import sys
from collections import defaultdict, deque

def dfs():
  queue = deque()
  queue.append([0,0])
  done = set([0])
  ans =[0] + [-1]*(N-1)
  while len(queue) != 0:
    prv_node, prv_edge = queue.pop()
    for node, edge in graph[prv_node]:
      if node in done: continue
      if (prv_edge + edge)%2==0:ans[node] = '0'
      else:ans[node] = '1'
      
      queue.append([node, prv_edge+edge])
      done.add(node)
  [print(a) for a in ans]
    
input = sys.stdin.readline

N = int(input())
graph = defaultdict(list)
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])

dfs()

Solution (Python):
n = int(input())
Edges = [list(map(int,input().split())) for i in range(n-1)]
for edge in Edges:
    edge[0] -= 1
    edge[1] -= 1
    edge[2] %= 2

Graph = [[] for i in range(n)]
for edge in Edges:
    Graph[edge[0]].append([edge[1],edge[2]])
    Graph[edge[1]].append([edge[0],edge[2]])

Color = [-1 for i in range(n)]
Color[0] = 0

stack = [0]

while stack:
    node = stack.pop()
    for adj in Graph[node]:
        if Color[adj[0]] == -1:
            if adj[1] == 0:
                Color[adj[0]] = Color[node]
            elif Color[node] == 0:
                Color[adj[0]] = 1
            else:
                Color[adj[0]] = 0
            stack.append(adj[0])

for color in Color:
    print(color)

Solution (Python):
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

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

rem = {}

for i in range(n):
  rem[i] = 1
  
ans = [0 for _ in range(n)]

def check(p, tmp):
  rem.pop(p)
  for n, w in d[p]:
    if n in rem:
      ntmp = (tmp + w) % 2
      ans[n] = ntmp
      check(n, ntmp)
      
check(0, 0)

for res in ans:
  print(res)

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

for i in range(N-1):
    VW[i][0] -= 1
    VW[i][1] -= 1

edges = [list() for _ in range(N)]
for i in range(N-1):
    edges[VW[i][0]].append((VW[i][1],VW[i][2]))
    edges[VW[i][1]].append((VW[i][0],VW[i][2]))

D = [-1 for _ in range(N)]
D[VW[0][0]] = 0
stack = [VW[0][0]]

while stack:
    s = stack.pop(-1)
    for (i,c) in edges[s]:
        if D[i] == -1:
            D[i] = D[s] +c
            stack.append(i)

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

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

T = [[] for _ in range(N)]
for i in range(N-1):
    u, v = A[i][0] - 1, A[i][1] - 1
    d = A[i][2] % 2 
    T[u].append([v, d])
    T[v].append([u, d])

visited = [True] + [False] * (N-1)
ans = [0] * N
que = deque([0]) 
while len(que) > 0:
    q = que.popleft()
    for v, d in T[q]:
        if visited[v]:
            pass
        else:
            que.append(v)
            visited[v] = True
            ans[v] = (ans[q] + d) % 2
            
for a in ans:
    print(a)

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


def dfs(v, c, C, visited, G):
    visited[v] = True
    C[v] = c

    for nv, w in G[v]:
        if visited[nv]:
            continue
        dfs(nv, c^w, C, visited, G)


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

    C = [0]*N
    visited = [False]*N
    dfs(0, 0, C, visited, G)
    for c in C:
        print(c)
    
        


if __name__ == '__main__':
    main()

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


def dfs(v, c, C, visited, G):
    visited[v] = True
    C[v] = c

    for nv, w in G[v]:
        if visited[nv]:
            continue
        dfs(nv, c^w, C, visited, G)


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

    C = [0]*N
    visited = [False]*N
    dfs(0, 0, C, visited, G)
    for c in C:
        print(c)
    
        


if __name__ == '__main__':
    main()

Solution (Python):

n = int(input())
nodes = [[] for _ in range(n)]
length = [-1]*n
for _ in range(n-1):
    ui, vi, wi = list(map(int, input().split()))
    nodes[ui-1].append((vi-1, wi%2))
    nodes[vi-1].append((ui-1, wi%2))

stack = []
stack.append(nodes[0][0])
while stack:
    current = stack.pop(-1)
    if length[current[0]] != -1:
        continue
    length[current[0]] = current[1]
    for nextnode in nodes[current[0]]:
        if length[nextnode[0]] != -1:
            continue
        stack.append([nextnode[0],(current[1]+nextnode[1])%2])
for i in length:
    print(i)

Solution (Python):
from collections import defaultdict
import queue

def getlist():
	return list(map(int, input().split()))

class Graph(object):
    def __init__(self):
        self.graph = defaultdict(list)

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

    def add_edge(self, a, b, w):
        self.graph[a].append([b, w])

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

class BFS(object):
    def __init__(self, graph, N):
        self.g = graph.graph
        self.dist = [0] * (N + 1)
        self.visit = [0] * (N + 1)
        self.Q = queue.Queue()
        self.Q.put(1)

        while not self.Q.empty():
            v = self.Q.get()
            for i, w in self.g[v]:
            	if self.visit[i] == 0:
            		self.dist[i] = self.dist[v] + w
            		self.Q.put(i)
            		self.visit[i] = 1

    def weight(self):
        return self.dist

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

XX = BFS(G, N)
ans = XX.weight()
for i in range(1, N + 1):
	if ans[i] % 2 == 0:
		print(0)
	else:
		print(1)

Solution (Python):
def solve():
	from collections import deque
	n,*l=map(int,open(0).read().split())
	con=[[] for _ in range(n)]
	dist=[-1]*n
	dist[0]=0
	for a,b,c in zip(*[iter(l)]*3):
		con[a-1].append((b-1,c%2))
		con[b-1].append((a-1,c%2))
 
	stk=deque([0])
	while stk:
		cur=stk.pop()
		for nxt,d in con[cur]:
			if dist[nxt]<0:
				stk.append(nxt)
				dist[nxt]=(dist[cur]+d)%2

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

if __name__=="__main__":
	solve()

Solution (Python):
def solve():
	from collections import deque
	n,*l=map(int,open(0).read().split())
	con=[[] for _ in range(n)]
	dist=[None]*n
	dist[0]=0
	for a,b,c in zip(*[iter(l)]*3):
		con[a-1]+=[(b-1,c%2)]
		con[b-1]+=[(a-1,c%2)]
 
	stk=deque([0])
	while stk:
		cur=stk.pop()
		for nxt,d in con[cur]:
			if dist[nxt]==None:
				stk.append(nxt)
				dist[nxt]=(dist[cur]+d)%2

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

if __name__=="__main__":
	solve()

Solution (Python):
def solve():
	n,*l=map(int,open(0).read().split())
	con=[[] for _ in range(n)]
	dist=[None]*n
	dist[0]=0
	for a,b,c in zip(*[iter(l)]*3):
		con[a-1].append((b-1,c%2))
		con[b-1].append((a-1,c%2))
 
	stk=[0]
	while stk:
		cur=stk.pop()
		for nxt,d in con[cur]:
			if dist[nxt]==None:
				stk.append(nxt)
				dist[nxt]=(dist[cur]+d)%2

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

if __name__=="__main__":
	solve()

Solution (Python):
def solve():
	from collections import deque
	n,*l=map(int,open(0).read().split())
	con=[[] for _ in range(n)]
	dist=[None]*n
	dist[0]=0
	for a,b,c in zip(*[iter(l)]*3):
		con[a-1].append((b-1,c%2))
		con[b-1].append((a-1,c%2))
 
	stk=deque([0])
	while stk:
		cur=stk.pop()
		for nxt,d in con[cur]:
			if dist[nxt]==None:
				stk.append(nxt)
				dist[nxt]=(dist[cur]+d)%2

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

if __name__=="__main__":
	solve()

Solution (Python):
def solve():
	from collections import deque
	n,*l=map(int,open(0).read().split())
	con=[[] for _ in range(n)]
	dist=[None]*n
	dist[0]=0
	for a,b,c in zip(*[iter(l)]*3):
		con[a-1].append((b-1,c%2))
		con[b-1].append((a-1,c%2))
 
	que=deque([0])
	while que:
		cur=que.popleft()
		for nxt,d in con[cur]:
			if dist[nxt]==None:
				que.append(nxt)
				dist[nxt]=(dist[cur]+d)%2

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

if __name__=="__main__":
	solve()

Solution (Python):
from collections import deque
n,*l=map(int,open(0).read().split())
con=[[] for _ in range(n)]
dist=[None]*n
dist[0]=0
for a,b,c in zip(*[iter(l)]*3):
	con[a-1].append((b-1,c%2))
	con[b-1].append((a-1,c%2))

que=deque([0])
while que:
	cur=que.popleft()
	for nxt,d in con[cur]:
		if dist[nxt]==None:
			que.append(nxt)
			dist[nxt]=dist[cur]^d

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

Solution (Python):
from collections import defaultdict
import queue

def getlist():
	return list(map(int, input().split()))

class Graph(object):
    def __init__(self):
        self.graph = defaultdict(list)

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

    def add_edge(self, a, b, w):
        self.graph[a].append([b, w])
        self.graph[b].append([a,w])

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

class BFS(object):
    def __init__(self, graph, N):
        self.g = graph.graph
        self.dist = [0] * (N + 1)
        self.visit = [0] * (N + 1)
        self.Q = queue.Queue()
        
        self.Q.put(1)

        while not self.Q.empty():
            v = self.Q.get()
            for i, w in self.g[v]:
            	if self.visit[i] == 0:
            		self.dist[i] = self.dist[v] + w
            		self.Q.put(i)
            		self.visit[i] = 1

    def weight(self):
        return self.dist

N = int(input())
G = Graph()
for i in range(N - 1):
	u, v, w = getlist()
	G.add_edge(u, v, w)
XX = BFS(G, N)
ans = XX.weight()
for i in range(1, N + 1):
	if ans[i] % 2 == 0:
		print(0)
	else:
		print(1)

Solution (Python):
from collections import defaultdict
import queue

def getlist():
	return list(map(int, input().split()))

class Graph(object):
    def __init__(self):
        self.graph = defaultdict(list)

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

    def add_edge(self, a, b, w):
        self.graph[a].append([b, w])
        self.graph[b].append([a,w])

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

class BFS(object):
    def __init__(self, graph, N):
        self.g = graph.graph
        self.dist = [0] * (N + 1)
        self.visit = [0] * (N + 1)
        self.Q = queue.Queue()
        self.visit[1] = 1
        self.Q.put(1)

        while not self.Q.empty():
            v = self.Q.get()
            for i, w in self.g[v]:
            	if self.visit[i] == 0:
            		self.dist[i] = self.dist[v] + w
            		self.Q.put(i)
            		self.visit[i] = 1

    def weight(self):
        return self.dist

N = int(input())
G = Graph()
for i in range(N - 1):
	u, v, w = getlist()
	G.add_edge(u, v, w)
XX = BFS(G, N)
ans = XX.weight()
for i in range(1, N + 1):
	if ans[i] % 2 == 0:
		print(0)
	else:
		print(1)

Solution (Python):
n = int(input())
peer = [[] for _ in range(n)]
for _ in range(n-1):
  u,v,w = map(int,input().split())
  u -= 1
  v -= 1
  w %= 2
  peer[u].append([v,w])
  peer[v].append([u,w])
now = [0]
clr = [-1 for _ in range(n)]
clr[0] = 0
while now:
  last = now
  now = []
  for x in last:
    for y in peer[x]:
      if clr[y[0]] == -1:
        now.append(y[0])
        clr[y[0]] = clr[x] ^ y[1]
for z in clr:
  print(z)

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

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

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

import queue
def dfs(v):
    color[v] = dist[v] % 2
    q = queue.LifoQueue()
    q.put(v)

    while not q.empty():
        vv = q.get()
        for next_v in g[vv]:
            if color[next_v[0]] == -1 and next_v[1] != 0:
                dist[next_v[0]] = dist[vv] + next_v[1]
                color[next_v[0]] = dist[next_v[0]] % 2
                q.put(next_v[0])


dfs(0)

for c in color:
    print(c)

Solution (Python):
from collections import deque

N = int(input())
S = [[]for i in range(N)]
for i in range(N-1):
    u,v,w = map(int,input().split())
    S[u-1].append([v-1,w])
    S[v-1].append([u-1,w])
Node = [None]*N
Node[0] = True
queue = deque([0])
while queue != deque([]):
    p = queue.popleft()
    for u,w in S[p]:
        if Node[u] == None:
            queue.append(u)
            Node[u] = (Node[p])^(w%2==1)
for i in range(N):
    print([0,1][Node[i]])