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())

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))

"""
ex.
3
1 2 2
2 3 1
の場合、g = [[(1, 2)], [(0, 2), (2, 1)], [(1, 1)]]
"""



"""
根から各頂点への距離をd_iとする
u,vという2頂点について、その最小共通祖先をwとすると
uとvの距離=d_u+d_v-2d_w
第3項は常に偶数
d_uとd_vの偶奇が等しければ全体は偶数、偶奇が異なれば全体は奇数
例えば、d_iが偶数なら白に、奇数なら黒に塗るとすれば条件を満たす
"""

dq = deque([0])


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


while dq:
    t = dq.popleft()
    
    for i in g[t]:
        
        if ds[i[0]] == -1:
            
            ds[i[0]] = ds[t] + i[1]
            
            dq.append((i[0]))


for i in ds:
    if i % 2 == 0:
        print(0)
    else:
        print(1)

Solution (Python):
from collections import deque
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))
ds = [-1]*n
dq = deque([0])
ds[0] = 0
while dq:
    t = dq.popleft()
    for i in g[t]:
        if ds[i[0]] == -1:
            ds[i[0]] = ds[t] + i[1]
            dq.append((i[0]))
for i in ds:
    if i%2 == 0:
        print(0)
    else:
        print(1)

Solution (Python):
from collections import defaultdict, deque
 
 
def bfs(start):
    q = deque([start])
    dist = [-1] * N
    dist[start] = 0
    while q:
        v = q.popleft()
        for nv, nw in g[v]:
            if dist[nv] >= 0:
                continue
            dist[nv] = (dist[v] + nw) % 2
            q.append(nv)
    return dist
 
 
N, *UVW = map(int, open(0).read().split())
g = defaultdict(set)
 
ans = [0] * N
for u, v, w in zip(*[iter(UVW)] * 3):
    u -= 1
    v -= 1
    g[u].add((v, w))
    g[v].add((u, w))
print("\n".join(map(str, bfs(0))))

Solution (Python):
from collections import deque

def nearlist(N, LIST):  
    NEAR = [set([]) for _ in range(N)]
    DIST = {}
    for a, b, c in LIST:
        NEAR[a - 1].add(b - 1)
        NEAR[b - 1].add(a - 1)
        DIST[(a - 1, b - 1)], DIST[(b - 1, a - 1)] = c, c
    return NEAR, DIST


def bfs(NEAR, N):  
    ANS = [-1 for _ in range(N)]
    ANS[0] = 0
    que, frag = deque([0]), set([0])

    while len(que) > 0:
        q = que.popleft()
        for i in NEAR[q]:  
            if i in frag:  
                continue
            if dist[(q, i)] % 2 == 0:
                ANS[i] = ANS[q]
            elif dist[(q, i)] % 2 == 1:
                ANS[i] = -ANS[q] + 1
            que.append(i), frag.add(i)
    return ANS


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

near, dist = nearlist(n, uvw)
ans = bfs(near, n)
print(*ans, sep='\n')

Solution (Python):
N = int(input())
Tree = [[] for _ in range(N+1)]
UVW = []

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

root = 1
parent = [0] * (N+1)
order = []
stack = [root]

while stack:
    x = stack.pop()
    order.append(x)
    for y in Tree[x]:
        if y == parent[x]:
            continue
        parent[y] = x
        stack.append(y)

dis = [0] * (N+1)

for u, v, w in UVW:
  if parent[u] == v:
    dis[u] = w
  else:
    dis[v] = w

color = [-1] * (N+1)
color[root] = 0

for x in order:
  for y in Tree[x]:
    if y == parent[x]:
      continue
    if dis[y]%2 == 0:
      color[y] = color[x]
    else:
      color[y] = color[x] ^ 1

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

Solution (Python):
from collections import deque

N = int(input())
adj = [ [] for _ in range(N)]
clr = [-1 for _ in range(N)]

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

vis = [0 for _ in range(N)]
q = deque([(0,0)])

while q:
  p, c = q.popleft()
  clr[p] = c
  vis[p] = 1
  for x, w in adj[p]:
    if vis[x] == 0:
      q.append((x,(w+c)%2))
      

for c in clr:
  print(c)

Solution (Python):
import sys
from collections import deque
import bisect
import copy
import heapq
import itertools
import math
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
mod = 10 ** 9 + 7

def read_values(): return map(int, input().split())
def read_index(): return map(lambda x: int(x) - 1, input().split())
def read_list(): return list(read_values())
def read_lists(N): return [read_list() for n in range(N)]


def f(N):
    res = 0
    while N != 0:
        b = format(N, "b").count("1")
        N %= b
        res += 1
    return res


def main():
    N = int(input())
    F = [[] for _ in range(N)]

    for _ in range(N - 1):
        u, v, w = read_values()
        u -= 1
        v -= 1
        F[u].append((v, w % 2))
        F[v].append((u, w % 2))

    D = [0] * N
    stack = [(0, 0, -1)]

    while stack:
        a, d, p = stack.pop()
        D[a] = d % 2

        for b, w in F[a]:
            if b == p:
                continue
            stack.append((b, (d + w) % 2, a))
    
    for d in D:
        print(d)


if __name__ == "__main__":
    main()

Solution (Python):

from typing import List, Tuple


def main():
    N, *X = map(int, open(0).read().split())
    tree: List[List[Tuple[int, int]]] = [[] for _ in range(N + 1)]
    for u, v, w in zip(*[iter(X)] * 3):
        w %= 2
        tree[u].append((v, w)), tree[v].append((u, w))

    color = [-1] * (N + 1)
    color[1] = 1
    stack = [1]
    while stack:
        u = stack.pop()
        cur = color[u]
        for v, w in tree[u]:
            if color[v] != -1:
                continue
            color[v] = cur ^ w
            stack.append(v)

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


if __name__ == "__main__":
    main()

Solution (Python):

from typing import List, Tuple


def main():
    N, *X = map(int, open(0).read().split())
    tree: List[List[Tuple[int, int]]] = [[] for _ in range(N + 1)]
    for u, v, w in zip(*[iter(X)] * 3):
        w %= 2
        tree[u].append((v, w)), tree[v].append((u, w))

    color = [-1] * (N + 1)
    color[1] = 1
    stack = [1]
    while stack:
        u = stack.pop()
        cur = color[u]
        for v, w in tree[u]:
            if color[v] != -1:
                continue
            color[v] = cur ^ w
            stack.append(v)

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


if __name__ == "__main__":
    main()

Solution (Python):
import sys
sys.setrecursionlimit(10**9)
def dfs(i):
  if reached[i] == 1:
    return
  reached[i] = 1
  for dic in uv[i]:
    to = dic["to"]
    w = dic["weight"]
    if w % 2 == 0:
      color[to] = color[i]
    else:
      color[to] = int(not color[i])
    dfs(to)

n = int(input())
color = [0]*(n+1)
reached = [0]*(n+1)
uv = [[] * (n+1) for i in range(n+1)]
for i in range(n-1):
  u,v,w = map(int,input().split())
  uv[u].append({"to":v, "weight":w})
  uv[v].append({"to":u, "weight":w})
dfs(1)
for i in color[1:]:
  print(i)

Solution (Python):
import sys
from sys import stdin
input = stdin.readline
sys.setrecursionlimit(20000000)
 
 
def main():
  N = int(input())
  G = [[] for _ in range(N+1)]
  for i in range(N-1):
    u, v, w = map(int, input().split())
    G[u].append((v, w))
    G[v].append((u, w))
 
  color = [-1]*(N+1)
  color[1] = 0
  
  
  
  
  
  
  
  
  
  
  
 
  def dfs(now):
    for next_, w in G[now]:
      if color[next_] == -1:
        color[next_] = (w % 2) ^ color[now]
        dfs(next_)
  dfs(1)
 
  for i in range(1, N+1):
    print(color[i])
 
 
if(__name__ == '__main__'):
  main()

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


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

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

  def dfs(now):
    for next_, w in G[now]:
      if color[next_] == -1:
        color[next_] = (w % 2) ^ color[now]
        dfs(next_)
  dfs(1)

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


if(__name__ == '__main__'):
  main()

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


def dfs(node, distance):
    for next_node, edge_size in G[node]:
        if ans[next_node] == -1:
            ans[next_node] = ((distance+edge_size) % 2)
            dfs(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
dfs(0, 0)
print(*ans, sep='\n')

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

def main():
    input = sys.stdin.readline
    N = int(input())
    d = defaultdict(list)
    for _ in range(N-1):
        u, v, w = map(int, input().split())
        d[u-1].append((v-1, w))
        d[v-1].append((u-1, w))

    dist = [0] * N
    q = deque()
    q.append((0, 0))
    visited = set()

    while len(q) > 0:
        q_ = deque()
        while len(q) > 0:
            node1, cost1 = q.popleft()

            dist[node1] = cost1
            visited.add(node1)

            for node2, cost2 in d[node1]:
                if node2 in visited:
                    continue

                q_.append((node2, cost1 + cost2))

        q = q_

    for d in dist:
        print(d % 2)


if __name__ == '__main__':
    main()

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


n = int(input())
col = [0]*n
next = [[] for i in range(n)]
d = [float('INF')]*n
d[0]=0

def dfs(now,parent):
    for next1,w1 in next[now]:
        if next1 == parent:
            continue
        elif d[next1]==float('INF'):
            d[next1]=d[now]+w1
            dfs(next1,now)

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

dfs(0,-1)

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

Solution (Python):
from collections import deque

n = int (input())
roots = [[] for _ in range(2*n)]
color = [0] * 2 * n

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

    if (w % 2 == 1):
        roots[u].append(v)
        roots[v].append(u)
    else:
        roots[u].append(u+n)
        roots[u+n].append(v)
        roots[v].append(v+n)
        roots[v+n].append(u)

d = deque()
d.append(0)
color[0] = 1

while(len(d)):
    temp = d.popleft()
    for i in roots[temp]:
        if(color[i] == 0):
            color[i] = color[temp] * (-1)
            d.append(i)

for i in range(n):
    print(max(0,color[i]))

Solution (Python):

from collections import deque, Counter
from heapq import heappop, heappush
from bisect import bisect_right
import sys
sys.setrecursionlimit(10**6)


N = int(input())
adj = [[] for _ in range(N)]
ans = [None] * N



def dfs(v,parent,c):
    ans[v] = c
    for u,w in adj[v]:
        if u == parent:
            continue
        dfs(u,v,1-c) if w & 1 else dfs(u,v,c)

def main():
    for i in range(N-1):
        u, v, w = map(int, input().split())
        adj[u-1].append((v-1,w))
        adj[v-1].append((u-1,w))
    
    dfs(0,-1,1)
    [print(v) for v in ans]

if __name__ == "__main__":
    main()

Solution (Python):

from collections import deque, Counter
from heapq import heappop, heappush
from bisect import bisect_right

def main():
    N = int(input())
    adj = [[] for _ in range(N)]
    for i in range(N-1):
        u, v, w = map(int, input().split())
        adj[u-1].append((v-1,w))
        adj[v-1].append((u-1,w))
    
    queue = deque([0])
    visit = [-1] * N
    visit[0] = 1
    
    while queue:
        now = queue.popleft()
        for u,w in adj[now]:
            if visit[u] < 0:
                queue.append(u)
                if w % 2 == 0:
                    visit[u] = visit[now]
                else:
                    visit[u] = (visit[now]+1) % 2
    [print(v) for v in visit]


if __name__ == "__main__":
    main()

Solution (Python):
import sys
sys.setrecursionlimit(10**7)
n=int(input())
edge=[[] for _ in range(n)]
dist=[-1]*n
for i in range(n-1):
    x,y,z=map(int,input().split())
    edge[x-1].append([y-1,z])
    edge[y-1].append([x-1,z])
def dfs(node,d):
    dist[node]=d
    for i in edge[node]:
        if dist[i[0]]==-1:
            dfs(i[0],d+i[1])
dfs(0,0)
print(*[i%2 for i in dist],sep='\n')

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

color = [-1]*N
color[0] = 0

import queue
q = queue.Queue()
q.put(0)
while not q.empty():
    v = q.get()
    for c, w in G[v]:
        if color[c] >= 0: continue
        color[c] = (color[v] + w)%2
        q.put(c)

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

Solution (Python):
import sys
INFTY=sys.maxsize
sys.setrecursionlimit(100000)

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

    return n,nList

WHITE=0
GRAY=1
BLACK=2
status=[]
color=[]

def dfs(s,nList):
    for u,w in nList[s]:
        if status[u]==WHITE:
            if w%2==0:
                color[u]=color[s]
            else:
                color[u]=(color[s]+1)%2
            status[u]=GRAY
            dfs(u,nList)
    status[s]=BLACK

def main(n,nList):
    global status
    global color

    status=[WHITE]*(n+1)
    color=[WHITE]*(n+1)
    dfs(1,nList)

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

if __name__=='__main__':
    n,nList=readinput()
    main(n,nList)

Solution (Python):
import sys
readline = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7

INF = 10**18
eps = 10**-7

N = int(readline())
ver = [[] for i in range(N+1)]
for i in range(N-1):
    u,v,w = map(int,readline().split())
    ver[u].append((v,w))
    ver[v].append((u,w))
color = [-1]*(N+1)
color[1] = 0
def dfs(fro,to,d):
    color[to] = d%2
    for v in ver[to]:
        if v[0] == fro:
            continue
        dfs(to,v[0],d+v[1])


for v in ver[1]:
    dfs(1,v[0],v[1])

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

Solution (Python):
import math,itertools,fractions,heapq,collections,bisect,sys,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]

def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

color=[-1]*100100
G=[[] for _ in range(100100)]

def f(st):
  st_c=color[st]
  for v,d in G[st]:
    if color[v]!=-1:
      continue

    if d%2==0:
      color[v]=st_c
    else:
      color[v]=abs(st_c-1)

    f(v)

def main():
  n=I()
  for _ in range(n-1):
    a,b,c=LI()
    a-=1
    b-=1
    G[a].append((b,c))
    G[b].append((a,c))

  color[0]=0
  f(0)

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

main()

Solution (Python):
from collections import deque
n = int(input())
g = [[]for i in range(n)]
for _ in range(n-1):
  a, b, c = map(int, input().split())
  g[a-1].append([b-1,c])
  g[b-1].append([a-1,c])
ans = [0 for i in range(n)]
v = [-1 for i in range(n)]
v[0] = 0
d = deque([0])
while len(d):
  x = d.popleft()
  for i,j in g[x]:
    if v[i] == -1:
      d.append(i)
      b = ans[x] +j
      ans[i] = b
      if b%2 ==1:
        v[i] = 1
      else:
        v[i] = 0
print("\n".join(map(str,v)))

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

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])

def dfs(node, dist):
    for nxt_node, edge_size in G[node]:
        if ans[nxt_node] == -1:
            ans[nxt_node] = ((dist + edge_size) % 2)
            dfs(nxt_node, dist + edge_size)

ans = [-1] * n
dfs(0, 0)
print(*ans, sep='\n')

Solution (Python):
import sys

sys.setrecursionlimit(1000000)

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


def dfs(n: int, c: int):
    colors[n] = c
    
    for even_idx in relation[n][0]:
        if colors[even_idx] is not None:
            continue
        else:
            dfs(even_idx, colors[n])
    
    for odd_idx in relation[n][1]:
        if colors[odd_idx] is not None:
            continue
        else:
            dfs(odd_idx, 1 - colors[n])


if __name__ == '__main__':
    dfs(1, 0)
    for ans in list(map(int, colors[1:])):
        print(ans)

Solution (Python):
from collections import deque
N=int(input())
lst=[[] for i in range(N)]
for i in range(N-1):
    U,V,W=map(int,input().split())
    lst[U-1].append([U-1,V-1,W])
    lst[V-1].append([V-1,U-1,W])

ans_lst=[-1]*N
queue=deque([])
for i in lst[0]:
    queue.append(i)
ans_lst[0]=0
while queue:
    u,v,w=queue.popleft()
    if ans_lst[v]==-1:
        ans_lst[v]=(ans_lst[u]+w)%2
        for i in lst[v]:
            queue.append(i)

for i in ans_lst:
    print(i)

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

Solution (Python):

MOD = 10 ** 9 + 7
INFI = 10**10

import math
from collections import deque
import itertools
import heapq

from fractions import Fraction
import copy
from functools import lru_cache
from collections import defaultdict
import pprint




def sosuhante(n):
    for k in range(2, int(math.sqrt(n))+1):
        if n% k ==0:
            return False
    return True
def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result

def kingaku(a,b,n):
    keta=len(str(n))
    return a*n+b*keta

def my_index(l, x, default=False):
    if x in l:
        return l.index(x)
    else:
        return default




def ret(a):
    c=[None]*(len(a)-1)
    if len(a)==1:
        return a[0]
    elif len(a)==0:
        return 0
    for i in range(1,len(a)):
        c[i-1]=abs(a[i]-a[i-1])
    return ret(c)

def soinsubunkai(n):
    a = []
    i = 1
    while i*i <= n:
        if n % i == 0 and i!=1:
            a.append(i)
            n=n//i

        if n% i !=0 or i==1:
            i += 1
    nokori=[n]
    return a + nokori

def make_divisors(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[::-1]

def main():
    n=int(input())
    dis=[INFI for _ in range(n+1)]
    graph=[[] for _ in range(n+1)]
    for i in range(n-1):
        a,b,c=map(int,input().split())
        graph[a].append([b,c])
        graph[b].append([a,c])
    stack=[]
    visited=[0 for _ in range(n+1)]
    dis[0]=0
    dis[1]=0
    for i in graph[1]:
        stack.append(i[0])
        dis[i[0]]=i[1]
    while True:
        s=stack.pop()
        for i in graph[s]:
            if visited[i[0]]==0:
                stack.append(i[0])
                dis[i[0]]=dis[s]+i[1]
                visited[i[0]]=1
        if len(stack)==0:
            break

    for i in range(1,n+1):
        if dis[i]%2==0:
            print(0)
        else:
            print(1)




if __name__ == "__main__":

    main()

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    def dfs(v, p):
        for u, w in tree[v]:
            if u == p:
                continue
            else:
                dist[u] = dist[v] + w
                dfs(u, v)

    n = int(input())
    tree = [[] for _ in range(n)]
    for _ 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])

    dist = [0] * n
    dfs(0, -1)
    res = []
    for d in dist:
        res.append(0 if d % 2 == 0 else 1)
    print(*res, sep="\n")


if __name__ == '__main__':
    resolve()

Solution (Python):
from collections import defaultdict, deque


def bfs(start):
    q = deque([start])
    dist = [-1] * N
    dist[start] = 0
    while q:
        v = q.popleft()
        for nv, nw in g[v]:
            if dist[nv] >= 0:
                continue
            dist[nv] = (dist[v] + nw) % 2
            q.append(nv)
    return dist


N, *UVW = map(int, open(0).read().split())
g = defaultdict(set)

ans = [0] * N
for u, v, w in zip(*[iter(UVW)] * 3):
    u -= 1
    v -= 1
    g[u].add((v, w))
    g[v].add((u, w))
print("\n".join(map(str, bfs(0))))

Solution (Python):
import sys
from collections import defaultdict


sys.setrecursionlimit(1_000_000)


def dfs(v):
    for nv, nw in g[v]:
        if visited[nv]:
            continue
        if nw % 2:
            ans[nv] = ans[v] ^ 1
        else:
            ans[nv] = ans[v]
        visited[nv] = True
        dfs(nv)


N, *UVW = map(int, open(0).read().split())
g = defaultdict(set)

ans = [0] * N
for u, v, w in zip(*[iter(UVW)] * 3):
    u -= 1
    v -= 1
    g[u].add((v, w))
    g[v].add((u, w))
visited = [False] * N
visited[0] = True
dfs(0)
print("\n".join(map(str, ans)))

Solution (Python):
from collections import defaultdict


N, *UVW = map(int, open(0).read().split())
g = defaultdict(set)

ans = [0] * N
for u, v, w in zip(*[iter(UVW)] * 3):
    u -= 1
    v -= 1
    g[u].add((v, w))
    g[v].add((u, w))
visited = {0}
stack = [0]
while stack:
    v = stack.pop()
    for nv, nw in g[v]:
        if nv in visited:
            continue
        if nw % 2:
            ans[nv] = ans[v] ^ 1
        else:
            ans[nv] = ans[v]
        stack.append(nv)
        visited.add(v)
print("\n".join(map(str, ans)))

Solution (Python):
import sys
import heapq
import re
from itertools import permutations
from bisect import bisect_left, bisect_right
from collections import Counter, deque
from math import factorial, sqrt, ceil, gcd
from functools import lru_cache, reduce
from decimal import Decimal
from operator import mul

INF = 1 << 60
MOD = 1000000007
sys.setrecursionlimit(10 ** 7)



class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())


def dijkstra_heap(s, edge, n):
    
    d = [10**20] * 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 factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr


def combinations_count(n, r):
    if n < r:
        return 0
    r = min(r, n - r)
    numer = reduce(mul, range(n, n - r, -1), 1)
    denom = reduce(mul, range(1, r + 1), 1)
    return numer // denom


def lcm(x, y):
    return (x * y) // gcd(x, y)


def lcm_list(numbers):
    return reduce(lcm, numbers, 1)


def gcd_list(numbers):
    return reduce(gcd, numbers)


def is_prime(n):
    if n <= 1:
        return False
    p = 2
    while True:
        if p ** 2 > n:
            break
        if n % p == 0:
            return False
        p += 1
    return True



def eratosthenes(limit):
    A = [i for i in range(2, limit+1)]
    P = []

    while True:
        prime = min(A)
        
        if prime > sqrt(limit):
            break
            
        P.append(prime)
            
        i = 0
        while i < len(A):
            if A[i] % prime == 0:
                A.pop(i)
                continue
            i += 1
            
    for a in A:
        P.append(a)
            
    return P


def permutation_with_duplicates(L):

    if L == []:
        return [[]]

    else:
        ret = []

        
        S = sorted(set(L))

        for i in S:

            data = L[:]
            data.remove(i)

            for j in permutation_with_duplicates(data):
                ret.append([i] + j)

        return ret

def make_divisors(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[::-1]


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

ans = [-1 for i in range(n)]
queue = deque([0])
while queue:
    now = queue.popleft()
    if ans[now] != -1:
        continue
    ans[now] = 0
    for i in tree[now]:
        if ans[i[0]] == -1:
            continue
        if ans[i[0]] == 0:
            if i[1] % 2 == 0:
                ans[now] = 0
            else:
                ans[now] = 1
        elif ans[i[0]] == 1:
            if i[1] % 2 == 0:
                ans[now] = 1
            else:
                ans[now] = 0
        break
    for i in tree[now]:
        queue.append(i[0])

for i in ans:
    print(i)

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

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

node_colors = [-1] * (N+1)

def route(last, now, dist):
    for next_node, next_distance in paths[now].items():
        node_colors[next_node] = (dist + next_distance) % 2
        if next_node != last:
            route(now, next_node, dist + next_distance)

node_colors[1] = 0

route(0, 1, 0)

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

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

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

node_colors = [-1] * (N+1)

def route(last, now, dist):
    for next_node, next_distance in zip(paths[now].keys(), paths[now].values()):
        node_colors[next_node] = (dist + next_distance) % 2
        if next_node != last:
            route(now, next_node, dist + next_distance)

node_colors[1] = 0

route(0, 1, 0)

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

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

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

node_colors = [-1] * (N+1)

def route(last, now, dist):
    for next_node, next_distance in zip(paths[now].keys(), paths[now].values()):
        node_colors[next_node] = (dist + next_distance) % 2
        if next_node != last:
            route(now, next_node, dist + next_distance)

node_colors[1] = 0

route(0, 1, 0)

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

Solution (Python):
from collections import deque

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

M = N-1
G = [deque([]) for i in range(N+1)]

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

def dfs(v):
    stack = deque([v])
    distance[v] = 0
    
    while stack:   
        tmp = stack[0]
        if G[tmp]:
            w = G[tmp].popleft() 
            if distance[w[0]] < 0:
                distance[w[0]] = (distance[tmp] + w[1]) % 2
                stack.append(w[0])
        else:
            stack.popleft()
    return distance

distance = dfs(1)
for i in range(N):
    print(distance[i+1])