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

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

ans = [-1]*N
ans[0] = 0
q = deque()
q.append((0, 0))
while q:
    temp = q.popleft()
    u = temp[0]
    w = temp[1]
    for e in E[u]:
        if ans[e[0]] >= 0:
            continue
        if w+e[1] & 1 == 0:
            ans[e[0]] = 0
        else:
            ans[e[0]] = 1
        q.append((e[0], w+e[1]))

for a in ans:
    print(a)

Solution (Python):
from collections import deque
n=int(input())
v=tuple(tuple(map(lambda x: int(x)-1,input().split())) for _ in range(n-1))

node=[{} for _ in range(n)]
d=deque()
ans= [-1] * n
ans[0]=0
d.append(0)
for pair in v:
    node[pair[0]][pair[1]]=pair[2]
    node[pair[1]][pair[0]]=pair[2]
    
while True:
    if not d:
        break
    i=d.pop()
    for k in node[i].keys():
        if ans[k]!=-1:
          continue
        d.append(k)
        if node[i][k]%2==1:
            ans[k]=ans[i]
        else:
            ans[k]=1-ans[i]
print(*ans)

Solution (Python):
n=int(input())
node=[-1 for i in range(n)]
g=[[] for i in range(n)]
for i in range(n-1):
  u,v,w=map(int,input().split())
  u-=1
  v-=1
  w%=2
  g[u].append([v,w])
  g[v].append([u,w])
queue=[0]
node[0]=0
while len(queue)>0:
  t=queue.pop()
  for v,w in g[t]:
    if node[v]>-1:
      continue
    node[v]=node[t]^w
    queue.append(v)
for i in range(n):
  print(node[i])

Solution (Python):

import sys
sys.setrecursionlimit(10**6)
n = int(input())
tree = [[] for i in range(n)]
for i in range(n-1):
    u,v,w = map(int,input().split())
    tree[u-1].append((v-1,w))
    tree[v-1].append((u-1,w))
vis = [False]*n
color = [0]*n

def dfs_rec(now):
    for node,w in tree[now]:
        if not vis[node]:
            vis[node] = True
            if w%2==0:
                color[node] = color[now]
            else:
                color[node] = 1-color[now]
            dfs_rec(node)
    return
vis[0] = True
dfs_rec(0)
for c in color:
    print(c)

Solution (Python):
import heapq
import sys
sys.setrecursionlimit(4100000)
input = sys.stdin.readline

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

    return d


def main():
    N  = int(input())
    edge = [[] for _ in range(N)]
    for _ 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(0,N,edge)

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


if __name__ == "__main__":
    main()

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

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

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

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

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

from collections import deque 
def main():
    N = int(readline())
    to = [[] for _ in range(N)]
    wight = [[] for i in range(N)]
    for _ in range(N-1):
        u, v, w = map(int, readline().split())
        u-=1
        v-=1
        to[u].append(v)
        to[v].append(u)
        wight[u].append(w)
        wight[v].append(w)

    dq = deque()
    dq.append(0)
    dist = [-1 for _ in range(N)]
    dist[0] = 0
    while len(dq)>0:
        v = dq.popleft()
        for i in range(len(to[v])):
            nx = to[v][i] 
            cost = wight[v][i]
            if dist[nx] != -1:
                continue
            dist[nx] = (dist[v]+cost)%2
            dq.append(nx)

    for i in dist:
        print(i)
if __name__ == '__main__':
    main()

Solution (Python):
import sys

sys.setrecursionlimit(1000000)


def dfs(g: {}, v: int, seen: [], current_color: int):
    seen[v] = current_color
    for (next_v, next_w) in g[v]:
        
        if seen[next_v] != -1:
            if current_color == seen[next_v] and next_w % 2 == 1:
                return False
            elif current_color != seen[next_v] and next_w % 2 == 0:
                return False
            continue
        next_color = current_color if next_w % 2 == 0 else 1 - current_color
        
        if not dfs(g, next_v, seen, next_color):
            return False
    return True


def main():
    n = int(input())

    g = {}
    for i in range(n-1):
        u, v, w = map(int, input().split())
        dic_a = g.setdefault(u-1, [])
        dic_a.append((v-1, w))
        dic_b = g.setdefault(v-1, [])
        dic_b.append((u-1, w))
    
    seen = [-1] * n

    is_bipartite = True

    for i in range(n):
        if seen[i] != -1:
            continue
        if not dfs(g, i, seen, 0):
            is_bipartite = False
            break

    if is_bipartite:
        for i in range(n):
            print(seen[i])
    else:
        print("is not bipartite")

main()

Solution (Python):
n=int(input())
g=[[] for _ in range(n)]
for _ in range(n-1):
  u,v,w=map(int,input().split())
  g[u-1]+=[(v-1,w%2)]
  g[v-1]+=[(u-1,w%2)]
l=[-1]*n
q=[(0,0)]
while q:
  a,b=q.pop(); l[a]=b
  for c,d in g[a]:
    if l[c]<0: q+=[(c,b^d)]
print(*l,sep='\n')

Solution (Python):
n=int(input())
g=[set() for _ in range(n)]
for _ in range(n-1):
  u,v,w=map(int,input().split())
  g[u-1].add((v-1,w%2))
  g[v-1].add((u-1,w%2))
l=[-1]*n
q=[(0,0)]
while q:
  a,b=q.pop()
  l[a]=b
  for c,d in g[a]:
    if l[c]>=0: continue
    q+=[(c,b^d)]
print(*l,sep='\n')

Solution (Python):
import sys
sys.setrecursionlimit(10**6)
n=int(input())
g=[set() for _ in range(n)]
for _ in range(n-1):
  u,v,w=map(int,input().split())
  g[u-1].add((v-1,w%2))
  g[v-1].add((u-1,w%2))
l=[-1]*n
def dfs(x,p=-1,s=0):
  l[x]=s
  for c,d in g[x]:
    if p==c: continue
    dfs(c,x,s^d)
dfs(0)
print(*l,sep='\n')

Solution (Python):
import sys
def input(): return sys.stdin.readline().strip()


def main():
    N = int(input())
    repn = [[] for _ in range(N)]
    for _ in range(N - 1):
        u, v, w = map(int, input().split())
        repn[u - 1].append((v - 1, w))
        repn[v - 1].append((u - 1, w))
    
    """
    Greedyに隣接する頂点ごとに色を塗っていけばよい
    """

    color = [-1] * N
    color[0] = 0
    q = [0]
    while q:
        v = q.pop()
        for u, w in repn[v]:
            if color[u] != -1:
                continue
            if w % 2 == 0:
                color[u] = color[v]
            else:
                color[u] = (1 + color[v]) % 2
            q.append(u)
    for ans in color:
        print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
import sys
import heapq


def input():
    return sys.stdin.readline().strip()


def dijkstra(start, n_nodes, edge):
    dist = [float("inf")] * n_nodes
    dist[start] = 0
    
    q = [(dist[start], start)]
    heapq.heapify(q)
    while q:
        
        d, i = heapq.heappop(q)
        
        
        if dist[i] < d:
            continue
        
        
        for cost, j in edge[i]:
            if dist[j] > dist[i] + cost:
                dist[j] = dist[i] + cost
                heapq.heappush(q, (dist[j], j))
    return dist


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


if __name__ == "__main__":
    main()

Solution (Python):
import sys
import heapq


def input():
    return sys.stdin.readline().strip()


def dijkstra(start, n_nodes, edge):
    dist = [float("inf")] * n_nodes
    dist[start] = 0
    
    q = [(dist[start], start)]
    heapq.heapify(q)
    while q:
        
        d, i = heapq.heappop(q)
        
        
        if dist[i] < d:
            continue
        
        
        for cost, j in edge[i]:
            if dist[j] > dist[i] + cost:
                dist[j] = dist[i] + cost
                heapq.heappush(q, (dist[j], j))
    return dist


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


if __name__ == "__main__":
    main()

Solution (Python):
import heapq
import sys

sys.setrecursionlimit(10 ** 6)
INF = float("inf")
MOD = 10 ** 9 + 7


def input():
    return sys.stdin.readline().strip()


def dijkstra(edges, n_nodes, start=0):
    dist = [float("inf")] * n_nodes
    dist[start] = 0

    
    q = [(dist[start], start)]
    heapq.heapify(q)

    while q:
        d, i = heapq.heappop(q)

        if dist[i] < d:
            continue

        for weight, j in edges[i]:
            tmp = dist[i] + weight
            if dist[j] > tmp:
                dist[j] = tmp
                heapq.heappush(q, (dist[j], j))

    return dist


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

    dist = dijkstra(edges, N)

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


if __name__ == "__main__":
    main()

Solution (Python):
from collections import defaultdict


def main():
    N = int(input())
    adj_nodes = defaultdict(list)
    edge_lengths = defaultdict(int)
    for _ in range(N - 1):
        u, v, w = list(map(int, input().split()))
        u -= 1
        v -= 1
        adj_nodes[u].append(v)
        adj_nodes[v].append(u)
        edge_lengths[(u, v)] = w
        edge_lengths[(v, u)] = w
    
    distances = [0 for _ in range(N)]
    explored = [0 for _ in range(N)]
    start_node = 0
    frontier = [(start_node, None)]  
    while len(frontier) > 0:
        node, parent_node = frontier.pop()
        if parent_node is not None:
            distances[node] = distances[parent_node] + edge_lengths[(node, parent_node)]
        explored[node] = 1
        next_nodes = adj_nodes[node]
        for next_node in next_nodes:
            if explored[next_node] == 1:
                continue
            frontier.append((next_node, node))
    
    
    
    for node in range(N):
        color = 0 if distances[node] % 2 == 1 else 1
        print(color)


if __name__ == '__main__':
    main()

Solution (Python):
n=int(input())
G=[[] for i in range(n)]
for i in range(n-1):
  u,v,w=map(int,input().split())
  G[u-1].append([v-1,w])
  G[v-1].append([u-1,w])
dist=[-1]*n
from collections import deque
q=deque()
q.append(0)
dist[0]=0
while q:
  cur=q.popleft()
  for nx,nd in G[cur]:
    if dist[nx]!=-1:continue
    dist[nx]=(dist[cur]+nd)%2
    q.append(nx)
print(*dist,sep='\n')

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

for i in range(n):
    if color[i] == -1:
        print(0)
    elif color[i] == 1:
        print(1)

Solution (Python):
import heapq
def dijkstra_heap(s):
  d=[float("inf")]*n
  used=[True]*n 
  d[s]=0
  used[s]=False
  edgelist=[]
  for e in edge[s]:
    heapq.heappush(edgelist,e)
  while len(edgelist):
    minedge=heapq.heappop(edgelist)
    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]]:
        heapq.heappush(edgelist,[e[0]+d[v],e[1]])
  return d

n=int(input())
edge=[[] for i in range(n)]
for i in range(n-1):
  x,y,z=map(int,input().split())
  edge[x-1].append([z,y-1])
  edge[y-1].append([z,x-1])

ans=dijkstra_heap(0)
for i in range(n):
  print(ans[i]%2)

Solution (Python):
n=int(input())
l=[list(map(int,input().split())) for i in range(n-1)]
connection=[[] for i in range(n)]
for i in range(n-1):
  connection[l[i][0]-1].append(l[i][1]-1)
  connection[l[i][1]-1].append(l[i][0]-1)
d={}
for i in range(n-1):
  d[(l[i][0]-1,l[i][1]-1)]=l[i][2]
  d[(l[i][1]-1,l[i][0]-1)]=l[i][2]

def bfs(v):
  distance=[-1]*n
  distance[v]=0
  next=[v]
  next2=set()
  visited=[-1]*n
  visitct=0
  while len(next)!=0 and visitct!=n:
    for i in range(len(next)):
      if visited[next[i]]==-1:
        visited[next[i]]=1
        visitct+=1
        for j in range(len(connection[next[i]])):
          if visited[connection[next[i]][j]]==-1:
            distance[connection[next[i]][j]]=distance[next[i]]+d[(next[i],connection[next[i]][j])]
            next2.add(connection[next[i]][j])
    next=list(next2)
    next2=set()
  return distance

ans=bfs(0)
for i in range(n):
  print(ans[i]%2)

Solution (Python):
from heapq import heappush, heappop, heapify

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

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

    edge[u].append((w, v))
    edge[v].append((w, u))

dist = [float('inf')] * N
visited = [False] * N
dist[0] = 0
visited[0] = True

count = N-1
q = edge[0]
heapify(q)

while q and count:
    w, v = heappop(q)

    if visited[v]: continue
    visited[v] = True
    dist[v] = w
    count -= 1

    for c, u in edge[v]:
        if not visited[u]: heappush(q, (w+c, u))

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

Solution (Python):
import sys
sys.setrecursionlimit(10**9)
N=int(input())

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

check=[0]*N
ans=[0]*N
def solve(x):
  check[x]=1
  for i,d in graph[x]:
    if check[i]==0:
      ans[i]=(ans[x]+d)%2
      solve(i)
solve(0)
for i in range(N):
  print(ans[i])

Solution (Python):
N = int(input())
from collections import deque

tree = [{} for _ in range(N)]

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

queue = deque()
queue.append((0, 0))

while queue:
    v, w = queue.pop()
    color[v] = w%2
    for i in tree[v].keys():
        if color[i]==-1:
            queue.append((i, w+tree[v][i]))

for c in color:
    print(c)

Solution (Python):
N = int( input() )
d = [ [] for _ in range( N )]

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

s = [( 0, 0 )]
l = [ -1 ] * N
while s != []:
  a, w = s.pop()
  l[ a ] = w % 2
  for i, j in d[ a ]:
    if l[ i ] == -1:
      s.append( ( i , j + w ) )
for i in l:
  print( i )

Solution (Python):
N=int(input())
G=[[] for i in range(N)]
for i in range(N-1):
    u,v,w=map(int,input().split())
    u-=1; v-=1; w%=2
    G[u].append([v,w])
    G[v].append([u,w])
col=[-1 for i in range(N)]
col[0]=0
 
from collections import deque
dq=deque([0])
 
while len(dq)>0:
    p=dq.popleft()
    for i in range(len(G[p])):
        if col[G[p][i][0]]==-1: 
            dq.append(G[p][i][0]) 
            col[G[p][i][0]]=(col[p]+G[p][i][1])%2 
        
for i in col:
    print(i)

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

from collections import deque
dq=deque([0])

while len(dq)>0:
    p=dq.popleft()
    for i in range(len(G[p])):
        if col[G[p][i][0]]==-1:
            dq.append(G[p][i][0])
            col[G[p][i][0]]=(col[p]+G[p][i][1])%2
        
for i in col:
    print(i)

Solution (Python):
import sys
import math  
import bisect  
import queue  


def input():
    return sys.stdin.readline().rstrip()


def main():
    N = int(input())

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

    state = [0 for _ in range(N)]
    visit = [False for _ in range(N)]
    que = queue.Queue()
    que.put((0, 0))
    while not que.empty():
        c, d = que.get()
        if d % 2 == 0:
            state[c] = 1
        visit[c] = True
        for pos, w in node[c]:
            if not visit[pos]:
                que.put((pos, d + w))

    for s in state:
        print(s)


if __name__ == '__main__':
    main()

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

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

stack = [0]
d = [-1] * n
d[0] = 0

while stack:
    u = stack.pop()
    for v, w in adj[u]:
        if d[v] == -1:
            d[v] = d[u] + w
            d[v] %= 2
            stack.append(v)

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

Solution (Python):


import sys



















def main():
    mod = 1000000007                  
    inf = float('inf')
    sys.setrecursionlimit(10**6)    
    def input(): return sys.stdin.readline().rstrip()
    def ii():  return int(input())
    def mi():  return map(int, input().split())
    def mi_0(): return map(lambda x: int(x)-1, input().split())
    def lmi(): return list(map(int, input().split()))
    def lmi_0(): return list(map(lambda x: int(x)-1, input().split()))
    def li():  return list(input())

        
    n = ii()
    tree = [[] for _ in range(n+1)]    
    for _ in range(n-1):
        u, v, w = mi()
        tree[u].append((v, w))
        tree[v].append((u, w))
    color = [None] * (n+1)
    root = 1
    def dfs(u=root, prev=-1, evenp=True):
        color[u] = evenp
        
        for v, d in tree[u]:
            if v == prev:
                continue
            if d % 2 == 0:
                dfs(v, prev=u, evenp=evenp)
            else:
                dfs(v, prev=u, evenp=not evenp)
    dfs()
    for vertex_color in color[1:]:
        print('1') if vertex_color else print('0')





if __name__ == "__main__":
    main()

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

def distn(node,distance):
    for next_node,edge_size in G[node]:
        if ans[next_node] == -1:
            ans[next_node] = ((distance+edge_size)%2)
            distn(next_node,distance+edge_size)

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

ans=[-1]*n
distn(0,0)
print(*ans,sep="\n")

Solution (Python):
import sys,queue,math,copy,itertools,bisect,collections
sys.setrecursionlimit(10**7)
LI = lambda : [int(x) for x in sys.stdin.readline().split()]
NI = lambda : int(sys.stdin.readline())

N = NI()
edge = [[] for _ in range(N+1)]
color = [-1] * (N+1)
for _ in range(N-1):
    u,v,w = LI()
    edge[u].append((v,w))
    edge[v].append((u,w))

def set_color(u,c):
    color[u] = c
    for v,w in edge[u]:
        if color[v] >= 0 : continue
        set_color(v,(w % 2) ^ c)
set_color(1,0)
print(*color[1:],sep='\n')

Solution (Python):
import sys,queue,math,copy,itertools,bisect,collections
sys.setrecursionlimit(10**7)
INF = 10**18
MOD = 10**9 + 7
LI = lambda : [int(x) for x in sys.stdin.readline().split()]
_LI = lambda : [int(x)-1 for x in sys.stdin.readline().split()]
NI = lambda : int(sys.stdin.readline())

N = NI()
edge = [[] for _ in range(N+1)]
color = [-1] * (N+1)
for _ in range(N-1):
    u,v,w = LI()
    edge[u].append((v,w))
    edge[v].append((u,w))

def set_color(u,c):
    color[u] = c
    for v,w in edge[u]:
        if color[v] >= 0 : continue
        set_color(v,(w % 2) ^ c)
set_color(1,0)
print(*color[1:],sep='\n')

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

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

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

ans = [0] * N


def dfs(cur, prev, dist):
    if dist % 2 == 0:
        ans[cur] = 1
    else:
        ans[cur] = 0
    for n, d in graph[cur]:
        if n != prev:
            dfs(n, cur, dist + d)


dfs(0, -1, 0)
for a in ans:
    print(a)

Solution (Python):
import heapq
def dijkstra_heap(s):
    d = [float("inf")] * n
    used = [True] * n
    d[s] = 0
    used[s] = False
    edgelist = []
    for e in edge[s]:
        heapq.heappush(edgelist,e)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        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]]:
                heapq.heappush(edgelist,[e[0]+d[v],e[1]])
    return d
n = int(input())
edge = [[] for i in range(n+1)]
for i in range(n-1):
    x,y,z = map(int,input().split())
    edge[x-1].append([z,y-1])
    edge[y-1].append([z,x-1])
dist = dijkstra_heap(0)
for i in dist:
    print(i%2)

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

G = [[] for i in range(N+1)]
for i in range(N-1):
    G[data[i][0]].append((data[i][1],data[i][2]))
    G[data[i][1]].append((data[i][0],data[i][2]))

from collections import deque

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

q = deque([1])

while q:
    n = q.pop()
    for d,e in G[n]:
        if D[d] != -1:
            continue
        elif e % 2 == 1:
            D[d] = 1-D[n]
            q.append(d)
        else:
            D[d] = D[n]
            q.append(d)

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

Solution (Python):
from collections import deque

N = int(input())
tree = [dict() for _ in range(N+1)]
color = [0]*(N+1)
parent = [0]*(N+1)
for _ in range(N-1):
    u, v, w = map(int, input().split())
    w %= 2
    tree[u][v] = w
    tree[v][u] = w

que = deque([1])
while len(que) != 0:
    u = que.pop()
    Rel, c, p = tree[u], color[u], parent[u]
    for v in Rel.keys():
        if v == p:
            continue
        elif Rel[v] == 0:
            color[v] = c
        else:
            color[v] = c^1
        parent[v] = u
        que.append(v)

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

Solution (Python):
from collections import deque


def main():
    vertices = int(input())
    tree = [[] for _ in range(vertices)]
    for _ in range(vertices - 1):
        u, v, length = map(int, input().split())
        u -= 1
        v -= 1
        tree[u].append([v, length])
        tree[v].append([u, length])
    root_index = 0
    max_deg = 0
    for i in range(vertices):
        if max_deg < len(tree[i]):
            root_index = i
            max_deg = len(tree[i])
    queue = deque([[root_index, 0]])
    is_checked = [False for _ in range(vertices)]
    is_checked[root_index] = True
    answer = ["0" for _ in range(vertices)]
    while queue:
        now_v, dist_from_root = queue.pop()
        for next_v, length in tree[now_v]:
            if not is_checked[next_v]:
                is_checked[next_v] = True
                if (dist_from_root + length) % 2:
                    answer[next_v] = "1"
                queue.append([next_v, dist_from_root + length])
    print("\n".join(answer))


if __name__ == '__main__':
    main()

Solution (Python):
import sys
sys.setrecursionlimit(10**6)
from math import floor,ceil,sqrt,factorial,log
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from operator import itemgetter
from fractions import gcd
mod = 10 ** 9 + 7
inf = float('inf')
ninf = -float('inf')
 

def ii(): return int(sys.stdin.readline().rstrip()) 
def mii(): return map(int,sys.stdin.readline().rstrip().split())
def limii(): return list(mii()) 
def lin(n:int): return [ii() for _ in range(n)]
def llint(n: int): return [limii() for _ in range(n)]

def ss(): return sys.stdin.readline().rstrip() 
def mss(): return sys.stdin.readline().rstrip().split()
def limss(): return list(mss()) 
def lst(n:int): return [ss() for _ in range(n)]
def llstr(n: int): return [limss() for _ in range(n)]





n=ii()
mat = [[] for _ in range(n)]

for i in range(n-1):
    a,b,w=mii()
    mat[a-1].append([b-1,w])
    mat[b-1].append([a-1,w])

visited=[2]*n

def dfs(now,dist):
    
    
    if dist %2==0:
        visited[now]=0
    else:
        visited[now]=1

    for i,j in mat[now]:
        if visited[i]!=2:continue
        dfs(i,dist+j)

dfs(0,0)
print(*visited)

Solution (Python):
N = int(input())  
tree = [[] for _ in range(N)]
dic = {}
for i in range(N-1):
    u, v, w = map(int, input().split())
    if u > v:
        u, v = v, u
    tree[u-1].append(v-1)
    tree[v-1].append(u-1)
    dic[(u-1, v-1)] = w

import sys
sys.setrecursionlimit(10 ** 8)


ans = [-1]*N
ans[0] = 0
flag = [False]*N

def dfs(i):
    flag[i] = True
    for j in tree[i]:
        if flag[j]:
            continue
        x = min(i, j)
        y = max(i, j)
        if dic[(x, y)] % 2 == 0:
            ans[j] = ans[i]
        else:
            if ans[i] == 0:
                ans[j] = 1
            else:
                ans[j] = 0
        if not(flag[j]):
            dfs(j)
            
dfs(0)

for answer in ans:
    print(answer)

Solution (Python):

def inputlist(): return [int(k) for k in input().split()]
import sys
sys.setrecursionlimit(10**8)

N = int(input())
tree = [[]*(N+1) for _ in range(N+1)]
dic = {}
for i in range(N-1):
    u,v,w = inputlist()
    if u > v:
        u,v = v,u
    tree[u].append(v)
    tree[v].append(u)
    dic[(u,v)] = w
seen = [False]*(N+1)
ans = ['-1']*(N+1)
ans[1] = '0'
def dfs(i):
    seen[i] = True
    for x in tree[i]:
        if seen[x]:
            continue
        k = min(i,x)
        s = max(i,x)
        if dic[(k,s)] % 2 == 0:
            ans[x] = ans[i]
            dfs(x)
        if dic[(k,s)] % 2 == 1:
            if ans[i] == '0':
                ans[x] = '1'
                dfs(x)
            if ans[i] == '1':
                ans[x] = '0'
                dfs(x)
dfs(1)
for i in range(1,N+1):
    print(ans[i])

Solution (Python):
import sys
sys.setrecursionlimit(10**6)
n=int(input())
a = [[]*n for _ in range(n)]
visited = [0] * n
dist = [0]*n
col = [1]*n

def dfs(i:"int", c:"int"):
    for j in a[i]:
        if not visited[j[0]]:
            visited[j[0]]=1
            if j[1]%2==0:
                col[j[0]]=c
            else:
                col[j[0]]=c*-1
            dfs(j[0], col[j[0]])



if __name__ == '__main__':
    for i in range(n-1):
        u,v,d = map(int, input().split())
        a[u-1].append([v-1, d])
        a[v-1].append([u-1, d])
    visited[0]=1
    dfs(0, 1)
    for i in range(n):
        print(col[i] if col[i]>0 else 0)

Solution (Python):
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from heapq import heapify, heappop, heappush
 
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
 
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N = INT()
L = [LIST() for i in range(N-1)]
graph = defaultdict(list)

for u, v, w in L:
    graph[u-1].append((v-1, w))
    graph[v-1].append((u-1, w))

color = [0] * N
visited = [False] * N

q = deque([0])
visited[0] = True
color[0] = 1

while q:
    a = q.pop()
    for node, w in graph[a]:
        if visited[node] == True:
            continue
        if w % 2 == 0:
            color[node] = color[a]
        else:
            color[node] = -1 * color[a]
        visited[node] = True
        q.append(node)
print(*[0 if c == 1 else 1 for c in color])

Solution (Python):
from collections import deque

import sys
sys.setrecursionlimit(2000000)





n = int(input())

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

ans = [-1]*n
stack = [0]
ans[0] = 0


while stack:
    u = stack.pop()  
    for v, w in d[u]:  
        if ans[v] == -1:  
            if w % 2 == 0:
                ans[v] = ans[u]  
            else:
                ans[v] = (ans[u]+1) % 2
            stack.append(v)
    

for i in ans:
    print(i)

Solution (Python):
from queue import deque

n = int(input())
li = [[] for _ in range(n)]
length = {}
length_path = [0]*n

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

work_queue = deque([])
visited = [False]*n

work_queue.append(0)

while work_queue:
    now = work_queue.popleft()
    visited[now] = True
    for i in li[now]:
        if visited[i]:
            continue
        work_queue.append(i)
        visited[i] = True
        if now < i:
            length_path[i] = length_path[now]+length[(now,i)]
        else:
            length_path[i] = length_path[now]+length[(i,now)]

for i in length_path:
    print(i%2)