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())
edge = [list(map(int, input().split())) for _ in range(n-1)]

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

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

q = deque([1])

dist = [0] * (n+1)
visited = [False] * (n+1)

while len(q) > 0:
    v = q.popleft()
    for w, d in adj[v]:
        if not visited[w]:
            visited[w] = True
            dist[w] = dist[v] + d
            q.append(w)



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

Solution (Python):
from math import ceil,floor,factorial,gcd,sqrt,log2,cos,sin,tan,acos,asin,atan,degrees,radians,pi,inf,comb
from itertools import accumulate,groupby,permutations,combinations,product,combinations_with_replacement
from collections import deque,defaultdict,Counter
from bisect import bisect_left,bisect_right
from operator import itemgetter
from heapq import heapify,heappop,heappush
from queue import Queue,LifoQueue,PriorityQueue
from copy import deepcopy
from time import time
from functools import reduce
import string
import sys
sys.setrecursionlimit(10 ** 7)
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def LIST()  : return list(MAP())

def bfs():
    dist = [-1]*n
    que = deque([0])
    dist[0] = 0
    while que:
        v = que.popleft()
        d = dist[v]
        for w in g[v]:
            if dist[w[0]] > -1:
                continue
            dist[w[0]] = d + w[1]
            que.append(w[0])
    return dist

n = INT()
g = [[] for i in range(n)]
for i in range(n-1):
    x, y, z = MAP()
    g[x-1].append([y-1, z])
    g[y-1].append([x-1, z])
for k in bfs():
    print(0 if k%2 == 0 else 1)

Solution (Python):

import sys
sys.setrecursionlimit(10**7)

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

colors=[0 for i in range(n)]

def dfs(v,color):
  colors[v-1]=color
  for i in es[v-1]:
    if i[1]%2==0 and colors[i[0]-1]==0:
      dfs(i[0],color)
    elif i[1]%2==1 and colors[i[0]-1]==0:
      dfs(i[0],(-1)*color)
  return colors

    
a=dfs(1,-1)
for i in a:
  if i==-1:
    print(0)
  else:
    print(1)

Solution (Python):
from collections import deque
n=int(input())
e=[[]for _ in range(n+1)]
c=[-1]*(n+1)
for _ in range(n-1):
  a,b,w=map(int,input().split())
  e[a]+=[(b,w)]
  e[b]+=[(a,w)]
q=deque([1])
c[1]=0
while q:
  now=q.popleft()
  for to,w in e[now]:
    if c[to]==-1:
      c[to]=(c[now]+w)%2
      q.append(to)
print(*c[1:],sep='\n')

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

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    mod=10**9+7
    N=I()
    adj=[[]for _ in range(N)]
    for i in range(N-1):
        u,v,w=MI()
        u-=1
        v-=1
        adj[u].append((v,w))
        adj[v].append((u,w))
        
    
    ans=[-1]*N
    import queue
    
    q=queue.Queue()
    q.put(0)
    ans[0]=0
    
    while not q.empty():
        v=q.get()
        for nv,w in adj[v]:
            if ans[nv]==-1:
                if ans[v]==0 and w%2==0:
                    ans[nv]=0
                elif ans[v]==0 and w%2==1:
                    ans[nv]=1
                elif ans[v]==1 and w%2==0:
                    ans[nv]=1
                else:
                    ans[nv]=0
                q.put(nv)
                
    for i in range(N):
        print(ans[i])
    
    

main()

Solution (Python):
n = int(input())
uv = [[] for _ in range(n+1)]
for i in range(n-1):
    u,v,w = map(int, input().split())
    uv[u].append([v,w])
    uv[v].append([u,w])
stack = [1]
ans = [-1]*(n+1)
ans[1]=0
while stack:
    x = stack.pop()
    for j,k in uv[x]:
        if ans[j] == -1:
            if k % 2 ==0:
                ans[j] = ans[x]
            else:
                ans[j] = (ans[x]+1)%2
            stack.append(j)
for m in range(n):
    print(ans[m+1])

Solution (Python):
from collections import deque
n=int(input())
uv=[[] for _ in range(n+1)]
for i in range(n-1):
    u,v,w=map(int,input().split())
    uv[u].append([v,w])
    uv[v].append([u,w])
stack=[1]
ans=[-1]*(n+1)
ans[1]=0
while stack:
    x=stack.pop()
    for j in uv[x]:
        if ans[j[0]]==-1:
            if j[1]%2==0:
                ans[j[0]]=ans[x]
            else:
                ans[j[0]]=(ans[x]+1)%2
            stack.append(j[0])

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

Solution (Python):
from collections import deque
n = int(input())
ans = [-1] * n
ans[0] = 0
d = [[] for _ in range(n)]

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

cnt = 0
queue = deque()
queue.append(0)
while queue:
    u = queue.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
            queue.append(v)


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

Solution (Python):
N = int(input())
u, v, w = [0]*(N-1), [0]*(N-1), [0]*(N-1)
n = [-1] * N

for i in range(N):
    n[i] = [0]*4
    n[i][1] = []
    n[i][2] = []

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

stack = [u[0]-1]

while True:
    num = stack.pop()
    n[num][3] = 1
    for i in range(len(n[num][1])):
        if n[n[num][1][i]][3] == 0:
            stack.append(n[num][1][i])
            if n[num][2][i] == 0:
                n[n[num][1][i]][0] = n[num][0]
            else:
                n[n[num][1][i]][0] = -1 * n[num][0] + 1
    if len(stack) == 0:
        break

for i in n:
    print(i[0])

Solution (Python):
'''
研究室PCでの解答
'''
import math

import queue
import bisect
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit


ipt = stdin.readline
setrecursionlimit(10**7)
mod = 10**9+7
dir = [(-1,0),(1,0),(0,-1),(0,1)]
alp = "abcdefghijklmnopqrstuvwxyz"


def main():
    n = int(ipt())
    way = [[] for i in range(n+1)]
    for i in range(n-1):
        u,v,w = map(int,ipt().split())
        way[u].append((v,w))
        way[v].append((u,w))

    col = [-1]*(n+1)
    q = [(1,0)]
    col[1] = 0
    while q:
        qi,ci = q.pop()

        for j,lj in way[qi]:
            if col[j] == -1:
                cj = (ci+lj)%2
                col[j] = cj
                q.append((j,cj))

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

    return None

if __name__ == '__main__':
    main()

Solution (Python):
def f(G, not_searched, results={0: '0'}):
    stack = []
    while len(not_searched) > 0:
        if len(stack) > 0:
            i = stack.pop()
            not_searched.remove(i)
        else:
            i = not_searched.pop()

        for key, val in G[i].items():
            if not key in not_searched:
                continue

            if val % 2 == 1:
                if results[i] == '0':
                    results[key] = '1'
                else:
                    results[key] = '0'
            else:
                results[key] = results[i]

            stack.append(key)

    return results

N = int(input())
G = [{} for _ in range(N)]
not_searched = set([i for i in range(N)])

if N == 1:
    print(results[0])
else:
    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

    results = f(G, not_searched)
    for i in range(N):
        print(results[i])

Solution (Python):
from sys import setrecursionlimit

setrecursionlimit(10 ** 6)

def dfs(now, prev):
    for nxt, w in edge[now]:
        if nxt == prev:
            continue
        
        dist[nxt] = dist[now] + w
        dfs(nxt, now)


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

dist = [0] * n
dfs(0, -1)

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

Solution (Python):
N = int(input())
dist_from_1 = [0 for i in range(N+1)]

paths = [dict() for i in range(N+1)]
for i in range(N-1):
    a, b, dist = map(int, input().split())
    paths[a][b] = dist
    paths[b][a] = dist

queue = [(0, 1, 0)]
while len(queue) != 0:
    prev, now, dist = queue.pop()
    dist_from_1[now] = dist
    for next in paths[now]:
        if next == prev:
            continue
        queue.append((now, next, dist + paths[now][next]))

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

Solution (Python):




import sys
import os
sys.setrecursionlimit(1000000)
from collections import defaultdict
adj = defaultdict(list)
dis =[0 for i in range(1000000)]
def dfs(u , p):
	for i , w in adj[u]:
		if i==p:
			continue
		dis[i]=dis[u]+w
		dis[i]=dis[i]%2
		dfs(i , u)
def main():
	n = int(input())
	for i in range(n-1):
		x, y , w = map(int , input().split())
		w = w%2
		adj[x].append([y , w])
		adj[y].append([x, w])
	dfs(1, 0)
	for i in range(1,n+1):
		print(dis[i])
if __name__ =="__main__":
	main()

Solution (Python):
import sys
import os
sys.setrecursionlimit(1000000)
from collections import defaultdict
adj = defaultdict(list)
dis =[0 for i in range(1000000)]
def dfs(u , p):
	for i , w in adj[u]:
		if i==p:
			continue
		dis[i]=dis[u]+w
		dis[i]=dis[i]%2
		dfs(i , u)
def main():
	n = int(input())
	for i in range(n-1):
		x, y , w = map(int , input().split())
		w = w%2
		adj[x].append([y , w])
		adj[y].append([x, w])
	dfs(1, 0)
	for i in range(1,n+1):
		print(dis[i])
if __name__ =="__main__":
	main()

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())
node = [[] for i in range(n)]

for i in range(n-1):
    u,v,w = map(int,readline().split())
    node[u-1].append((v-1,w))
    node[v-1].append((u-1,w))
ans = [-1]*n
ans[0] = 0
def dfs(fro, to, dis):
    ans[to] = dis%2
    for nxt, dist in node[to]:
        if nxt == fro:
            continue
        dfs(to, nxt, (dis+dist)%2)

for to,dis in node[0]:
    dfs(0,to,dis)

print("\n".join(map(str,ans)))

Solution (Python):

from collections import defaultdict, deque

N = int(input())
G = {}
for i in range(1, N+1):
    G[i] = []

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

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

que = deque()
que.append((1, 0))

while len(que) > 0:
    node, distance = que[0]
    que.popleft()

    ret[node] = distance % 2
    for next_node, next_distance in G[node]:
        if ret[next_node] == -1:
            que.append((next_node, distance + next_distance))

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

Solution (Python):




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


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

next_q = [(0, 0)]
while len(next_q)>0:
    nw, nc = next_q.pop()
    color[nw] = nc
    for nxt, nl in graph[nw]:
        if color[nxt]==-1:
            next_q.append((nxt,(nl+nc)%2))
for i in color:
    print(i)

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):
n = int(input())
visited = [False] * (n + 1)
distance = [0] * (n + 1)
prev = [0] * (n + 1)

from collections import defaultdict, deque
d = defaultdict(list)

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

q = deque([1])
while q:
    node = q.popleft()
    visited[node] = True
    for next_node, next_dist in d[node]:
        if not visited[next_node]:
            q.append(next_node)
            
            distance[next_node] = distance[node] + next_dist
    

for dist in distance[1:]:
    print(dist%2)

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 deque
readline = sys.stdin.readline
n = int(readline())
G = [[] for _ in range(n)]
for _ in range(n-1):
    u,v,w = map(int, readline().split())
    G[u-1].append((v-1,w))
    G[v-1].append((u-1,w))

V = [-1]*n
V[0] = 0
que = deque([0])
while que:
    nw = que.popleft()
    for nx,d in G[nw]:
        if V[nx]!=-1: continue
        V[nx] = (V[nw]+d)%2
        que.append(nx)

for v in V:
    print(v)

Solution (Python):
g = {}
a = int(input())
for i in range(a - 1):
    c = [int(s) for s in input().split()]
    if c[0] not in g: g[c[0]] = [(c[1], c[2])]
    else: g[c[0]].append((c[1], c[2]))

    if c[1] not in g: g[c[1]] = [(c[0], c[2])]
    else: g[c[1]].append((c[0], c[2]))

c = {}
d = {i: False for i in range(1, a + 1)}
c[1], d[1] = 0, True
Q = [1]
while(Q != []):
    r = Q.pop(0)
    for i in g[r]:
        if d[i[0]] == False:
            d[i[0]] = True
            Q.append(i[0])
            if i[1] % 2 == 0: c[i[0]] = c[r]
            else: c[i[0]] = (c[r] + 1) % 2
for i in range(1, a + 1): print(c[i])

Solution (Python):



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


def dfs(tree, n):
    visited = [False] * n
    dis = [0] * n
    even = set([0])
    stack = [0]
    while stack:
        v = stack.pop()
        cur_dis = dis[v]
        for next_v, d in tree[v]:
            if not visited[next_v]:
                visited[next_v] = True
                stack.append(next_v)
                dis[next_v] = cur_dis + d
                if (cur_dis + d) % 2 == 0:
                    even.add(next_v)
    return even

even = dfs(tree, n)
for i in range(n):
    if i in even:
        print(0)
    else:
        print(1)

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

res = [-1]*N
res[0] = 0
q = [0]
while len(q):
  v = q.pop()
  for u,w in e[v]:
    if res[u]>=0:
      continue
    res[u] = res[v]+w
    q.append(u)

for r in res:
  print(r%2)

Solution (Python):

import sys
sys.setrecursionlimit(10**7)
import bisect
import heapq
import itertools
import math
from collections import Counter, defaultdict, deque
from copy import deepcopy
from decimal import Decimal
from math import gcd
from operator import add, itemgetter, mul, xor
def cmb(n,r,mod):
  bunshi=1
  bunbo=1
  for i in range(r):
    bunbo = bunbo*(i+1)%mod
    bunshi = bunshi*(n-i)%mod
  return (bunshi*pow(bunbo,mod-2,mod))%mod
mod = 10**9+7
def I(): return int(input())
def LI(): return list(map(int,input().split()))
def MI(): return map(int,input().split())
def LLI(n): return [list(map(int, input().split())) for _ in range(n)]

n = I()
graph =[[]*(n+1) for i in range(n+1)]
ans = [0]*(n+1)
for i in range(n-1):
    u,v,w = map(int,input().split())
    w = w%2
    graph[u].append([v,w])
    graph[v].append([u,w])

def dfs(v,p,c,ans):
    ans[v] = c
    for i in graph[v]:
        if i[0] == p:
            continue
        if i[1] == 1:
            dfs(i[0],v,1-c,ans)
        if i[1] == 0:
            dfs(i[0],v,c,ans)
dfs(1,0,0,ans)
for i in ans[1:]:
    print(i)

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

V=[0 for i in range(n+1)]
V[1]=1
ans=[0 for i in range(n+1)]
que=[1]
head=0

while len(que)>head:
    now=que[head]
    head+=1
    for nex in L[now]:
        if V[nex[0]]==0:
            V[nex[0]]=1
            ans[nex[0]]=ans[now]^nex[1]
            que.append(nex[0])
    
for pri in ans[1:]:
    print(pri)

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


visited = [0] * N
visited[0] = 1
queue = [0]
while queue:
  x = queue.pop()
  for i, value in root[x]:
    if value % 2 == 0:
      ans[i] = ans[x]
    else:
      ans[i] = abs(1 - ans[x])
    if visited[i] == 0:
      visited[i] = 1
      queue.append(i)
      

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

Solution (Python):
import sys

sys.setrecursionlimit(10**7)


def dfs(s, to, color):
    for next_v, step in to[s]:
        if color[next_v] == -1:
            if step % 2 == 0:
                color[next_v] = color[s]
            else:
                color[next_v] = color[s] ^ 1
            dfs(next_v, to, color)


def solve():
    N = int(input())
    to = [[] for _ in range(N)]
    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])

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


if __name__ == "__main__":
    solve()

Solution (Python):
def abc126_d():
    import sys
    sys.setrecursionlimit(10010010)
    read = sys.stdin.buffer.read
    inp = iter(map(int, read().split()))

    N = next(inp)
    G = [[] for _ in range(N)]
    for _ in range(N-1):
        u = next(inp) - 1
        v = next(inp) - 1
        w = next(inp)
        G[u].append((v, w))
        G[v].append((u, w))

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

    def dfs(u):
        for v, w in G[u]:
            if color[v] != -1: continue
            if w % 2 == 0:
                color[v] = color[u]
            else:
                color[v] = abs(color[u] - 1)
            dfs(v)

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

if __name__ == '__main__':
    abc126_d()

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

done = {}
todo = [(0, 0, 0)]
while todo:
    i, c, d = todo.pop()
    for ni, dd in G[i]:
        if ni in done:
            continue
        nd = d + dd
        nc = nd % 2
        todo.append((ni, nc, nd))
    done[i] = c

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

Solution (Python):
from sys import setrecursionlimit
setrecursionlimit(10 ** 7)
n = int(input())
uvw = [list(map(int, input().split())) for i in range(n - 1)]
d = [-1 for i in range(n)]
edge = [[] for i in range(n)]
for u, v, w in uvw:
    edge[u - 1].append((v - 1, w))
    edge[v - 1].append((u - 1, w))
def dfs(now, D):
    d[now] = D
    for i, j in edge[now]:
        if d[i] == -1:
            dfs(i, D + j)
dfs(0, 0)
for i in d:
    print(i % 2)

Solution (Python):
import heapq

def dijkstra(G, s, dist):
    dist[s] = 0
    Q = [[0,s]]
    heapq.heapify(Q)

    while(len(Q) > 0):
        cur_d, cur_v = heapq.heappop(Q)
        cur_d *= -1
        
        if(cur_d > dist[cur_v]): continue

        for e in G[cur_v]:
            to, cost = e[0], e[1]
            if(dist[cur_v] + cost < dist[to]):
                dist[to] = dist[cur_v] + cost
                heapq.heappush(Q, [-dist[to], to])

N = int(input())

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

dist = [1e18] * N
dijkstra(G,0,dist)

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

Solution (Python):

from collections import deque

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

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

colors = [-1] * (N + 1)
colors[1] = 0
q = deque([1])
while q:
    u = q.popleft()
    for v, w in graph[u]:
        if colors[v] >= 0:
            continue

        if w % 2 == 0:
            colors[v] = colors[u]
        else:
            colors[v] = 1 - colors[u]
        q.append(v)

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

Solution (Python):
import sys
sys.setrecursionlimit(10**6)
read = sys.stdin.read
readlines = sys.stdin.readlines
def main():
    def dfs(node):
        for adjnode in edges[node]:
            if colors[adjnode[0]] == -1:
                if adjnode[1] % 2 == 0:
                    colors[adjnode[0]] = colors[node]
                else:
                    colors[adjnode[0]] = colors[node] ^ 1
                dfs(adjnode[0])
    
    n = int(input())
    edges = {e: [] for e in range(n)}
    for _ in range(n - 1):
        u, v, w = map(int, input().split())
        u -= 1
        v -= 1
        edges[u].append((v, w))
        edges[v].append((u, w))
    
    colors = [-1] * n
    colors[0] = 0
    dfs(0)
    
    print(*colors, sep='\n')


if __name__ == '__main__':
    main()

Solution (Python):

from copy import copy
N=int(input())
G=[[] for _ in range(N)]
di=[-1]*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])

di[0]=0

for i in range(1,N):
    if di[i]!=-1:continue
    seen=[0]*N
    stack=[[0,0]]
    while stack:
        y,d=stack.pop()
        if seen[y]==1:continue
        seen[y]=1
        for z, dist in G[y]:
            if seen[z] == 0:
                di[z] = d + dist
                stack.append([z, d + dist])

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

Solution (Python):

from copy import copy
N=int(input())
G=[[] for _ in range(N)]
di=[-1]*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])

di[0]=0
for g,w in G[0]:
    di[g]=w

for i in range(1,N):
    if di[i]!=-1:continue
    seen=[0]*N
    stack=copy(G[0])
    seen[0]=1
    dis=0
    while stack:
        y,d=stack.pop()
        if seen[y]==1:continue
        seen[y]=1
        if y==i:
            di[i]=dis+d
            break
        else:
            for z,dist in G[y]:
                if seen[z]==0:
                    di[z]=dis+d+dist
                    stack.append([z,dis+d+dist])

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

Solution (Python):
from collections import deque

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

for i in range(N-1):
  u,v,w=map(int,input().split())
  G[u][v]=w
  G[v][u]=w
  
for i in range(1,N+1):
  if len(G[i])==1:
    start=i
    break

def bfs(s):
    seen = [0 for i in range(N+1)]
    d = [0 for i in range(N+1)]
    todo = deque([])
    now = s
    seen[now]=1
    todo.append(now)
    while 1:
      if len(todo)==0:break
      a = todo.popleft()
      for b in G[a]:
        if seen[b] == 0:
          seen[b] = 1
          todo.append(b)
          d[b] += d[a] + G[a][b]
    return d

d = bfs(start)
for i in range(1,N+1):
  d_ = d[i]
  if d_ % 2 == 0:print(0)
  else:print(1)

Solution (Python):
import collections
import heapq

def cin():
    in_ = list(map(int,input().split()))
    if len(in_) == 1:  return in_[0]
    else:  return in_

class Dijkstra():
    
    def __init__(self):  self.e = collections.defaultdict(list)

    def add(self, u, v, d, directed = False):
        self.e[u].append([v, d])
        self.e[v].append([u, d]) 

    def delete(self, u, v):
        self.e[u] = [_ for _ in self.e[u] if _[0] != v]
        self.e[v] = [_ for _ in self.e[v] if _[0] != u]

    def Dijkstra_search(self, s):

        d = collections.defaultdict(lambda: float('inf'))
        prev = collections.defaultdict(lambda: None)
        d[s] = 0
        q = []
        heapq.heappush(q, (0, s))
        v = collections.defaultdict(bool)
        while q:
        
            k, u = heapq.heappop(q)
            if v[u]:  continue
            v[u] = True

            for uv, ud in self.e[u]:
                if v[uv]:  continue
                vd = k + ud
                if d[uv] > vd:
                    d[uv] = vd
                    prev[uv] = u
                    heapq.heappush(q, (vd, uv))

        return d, prev

    def getDijkstraShortestPath(self, start, goal):
        _, prev = self.Dijkstra_search(start)
        shortestPath = []
        node = goal
        while node is not None:
            shortestPath.append(node)
            node = prev[node]
        return shortestPath[::-1]

graph = Dijkstra()
N = cin()
for i in range(N - 1): 
    in_ = cin()
    graph.add(in_[0] - 1, in_[1] - 1, in_[2])
min_w, prev = graph.Dijkstra_search(0)
ans = [0 for _ in range(N)]
for i in range(N):  print(min_w[i] % 2)

Solution (Python):
import queue
n=int(input())
e=[[] for _ in range(n)]
INF=10**18
d=[INF]*n
for _ in range(n-1):
  v,u,w=map(int,input().split())
  e[v-1]+=[(u-1,w)]
  e[u-1]+=[(v-1,w)]
q=queue.Queue()
q.put(0)
d[0]=0
while not q.empty():
  now=q.get()
  for to,dis in e[now]:
    if d[to]==INF:
      d[to]=d[now]+dis
      q.put(to)
for i in d:
  print(i%2)

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):
def main():
    n = int(input())
    ki = {}
    for i in range(1,n+1):
        ki[i] = []
    for i in range(n-1):
        u,v,w = map(int,input().split())
        ki[u] += [[v,w%2]]
        ki[v] += [[u,w%2]]
    cl = [-1 for i in range(n)]
    cl[0] = 0
    que = [0]
    while len(que)>0:
        q = que.pop(0)
        for v in ki[q+1]:
            if cl[v[0]-1] != -1:
                continue
            if v[1]==1:
                cl[v[0]-1] = (cl[q]+1)%2
                que.append(v[0]-1)
            else:
                cl[v[0]-1] = cl[q]
                que.append(v[0]-1)
    for i in range(n):
        print(cl[i])

if __name__ == "__main__":
    main()

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 deque

n = int(input())
tree = {i: set() for i in range(n)}
cost = {}
for _ in range(n-1):
    u, v, w = map(lambda x: int(x)-1, input().split())
    tree[u].add(v)
    tree[v].add(u)
    cost[(u, v)] = w + 1

color = [-1] * n
color[0] = 0
que = deque([0])
while que:
    now = que.popleft()
    for i in tree[now]:
        if color[i] != -1:
            continue
        if cost[(min(now, i), max(now, i))] % 2 == 0:
            color[i] = color[now]
        else:
            color[i] = color[now] ^ 1
        que.append(i)
print('\n'.join(map(str, color)))

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

node = [[] for _ in range(n)]
color = [-1] * n
color[0] = 0

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

q = queue.Queue()
q.put(0)

while not q.empty():
    i = q.get()
    c = color[i]
    for j, w in node[i]:
        if color[j] < 0:
            color[j] = c if w % 2 == 0 else (c + 1) % 2
            q.put(j)

for c in color:
    print(c)

Solution (Python):
import sys
from collections import deque


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


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

    color = [False] * N
    color[0] = 0
    q = deque([1])

    while q:
        u = q.popleft()
        c1 = color[u - 1]
        for c, w in edge[u]:
            if color[c - 1] is False:
                q.append(c)
                color[c - 1] = (c1 + w) % 2

    print(*color)


if __name__ == "__main__":
    main()

Solution (Python):
import sys
from collections import deque


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


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

    color = [False] * (N + 1)
    color[1] = 0
    q = deque([1])
    pass
    while q:
        u= q.popleft()
        c1 = color[u]
        for c,w in edge[u]:
            if color[c] is False:
                q.append(c)
                color[c] = (c1+w)%2

    color.pop(0)
    print(*color)

if __name__ == "__main__":
    main()