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



Sample input:
3
1 2 2
2 3 1


Sample output:
0
0
1

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
#from math import gcd
import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache

#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')
AZ = "abcdefghijklmnopqrstuvwxyz"

#############
# Functions #
#############

######INPUT######
def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]

######OUTPUT######
def P(arg): print(arg); return
def Y(): print("Yes"); return
def N(): print("No"); return
def E(): exit()
def PE(arg): print(arg); exit()
def YE(): print("Yes"); exit()
def NE(): print("No"); exit()

#####Shorten#####
def DD(arg): return defaultdict(arg)

#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n): return kaijo_memo[n]
  if(len(kaijo_memo) == 0): kaijo_memo.append(1)
  while(len(kaijo_memo) <= n): kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n): return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0): gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n): gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if n == r: return 1
  if n < r or r < 0: return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
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

#####MakeDivisors######
def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors

#####MakePrimes######
def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum

#####GCD#####
def gcd(a, b):
    while b: a, b = b, a % b
    return a

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#####BitCount#####
def count_bit(n):
  count = 0
  while n:
    n &= n-1
    count += 1
  return count

#####ChangeBase#####
def base_10_to_n(X, n):
  if X//n: return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

def base_10_to_n_without_0(X, n):
  X -= 1
  if X//n: return base_10_to_n_without_0(X//n, n)+[X%n]
  return [X%n]

#####IntLog#####
def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count

#############
# Main Code #
#############
N = I()
graph = [[] for i in range(N)]
for _ in range(N-1):
  u,v,w = IL()
  graph[u-1].append((v-1,w))
  graph[v-1].append((u-1,w))
  
color = [None for i in range(N)]
q = [0]
color[0] = 0

while q:
  u = q.pop()
  for v,w in graph[u]:
    if color[v]!=None:continue
    if w%2:
      color[v] = 1-color[u]
      q.append(v)
    else:
      color[v] = color[u]
      q.append(v)

for c in color:
  print(c)

Submission status: Accepted

Solution code:
from collections import deque

def bfs(start, g, visited):
    q = deque([start])
    visited[start] = 0
    while q:
        curr_node = q.popleft()
        for next_node, w in g[curr_node]:
            if visited[next_node] >= 0: continue
            visited[next_node] = (visited[curr_node] + w)%2
            q.append(next_node)


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

for v in visited[1:]:
    if v%2 == 0: print(0)
    else: print(1)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import numpy as np
from collections import deque
from collections import defaultdict
import heapq
import collections
import itertools
import bisect


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


def z():
    return int(input())


def S():
    return input()


def C(line):
    return [input() for _ in range(line)]

from heapq import heapify, heappush, heappop
def dijkstra(path, N, start):
    visited = [False] * N
    que = [(0, start)]
    heapify(que)  # 始点aから各頂点への(距離, 頂点ID)
    dist = [-1] * N  # 始点aから各頂点への距離
    dist[start] = 0  # 始点aからaへの距離は0
    while que:
        d, v = heappop(que)  # 始点から最短距離の頂点を(確定ノード)を取り出す
        visited[v] = True  # 確定フラグを立てる
        # 接続先ノードの情報を更新する
        for d, to in path[v]:
            cost = dist[v] + d
            if dist[to] < 0 or cost < dist[to]:
                dist[to] = cost
                if not visited[to]:
                    heappush(que, (cost, to))
    return dist
N = z()
# 0 を頂点とする根付き木を考える
path = [[] for _ in range(N)]
for i in range(N-1):
    u, v, w = zz()
    path[u-1].append((w, v-1))
    path[v-1].append((w, u-1))
dist = dijkstra(path, N, 0)
# print(dist)
ans = [0] * N
for i, d in enumerate(dist):
    if (d % 2 == 0):
        ans[i] = 0 
    else:
        ans[i] = 1

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

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.readline
from heapq import heapify, heappush, heappop

def dijkstra(path, N, start):
    visited = [False] * N
    que = [(0, start)]
    heapify(que)  # 始点aから各頂点への(距離, 頂点ID)
    dist = [-1] * N  # 始点aから各頂点への距離
    dist[start] = 0  # 始点aからaへの距離は0
    while que:
        d, v = heappop(que)  # 始点から最短距離の頂点を(確定ノード)を取り出す
        visited[v] = True  # 確定フラグを立てる
        # 接続先ノードの情報を更新する
        for d, to in path[v]:
            cost = dist[v] + d
            if dist[to] < 0 or cost < dist[to]:
                dist[to] = cost
                if not visited[to]:
                    heappush(que, (cost, to))

    return dist

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

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip()
from collections import deque

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

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

ans = [-1] * N
queue = deque([0])

#頂点1を0色に塗る
ans[0] = 0

while queue:
    a = queue.popleft()
    for ve in edge[a]:
        if ans[ve[0]] == -1:
            if ve[1] == 0:
                ans[ve[0]] = ans[a]
            else:
                ans[ve[0]] = (ans[a]+1) % 2
            queue.append(ve[0])

for a in ans:
    print(a)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7) #再帰関数の上限,10**5以上の場合python
import math
from copy import copy, deepcopy
from copy import deepcopy as dcp
from operator import itemgetter
from bisect import bisect_left, bisect, bisect_right#2分探索
#bisect_left(l,x), bisect(l,x)#aはソート済みである必要あり。aの中からx未満の要素数を返す。rightだと以下
from collections import deque
#deque(l), pop(), append(x), popleft(), appendleft(x)
#q.rotate(n)で → にn回ローテート
from collections import Counter#文字列を個数カウント辞書に、
#S=Counter(l),S.most_common(x),S.keys(),S.values(),S.items()
from itertools import accumulate,combinations,permutations#累積和
#list(accumulate(l))
from heapq import heapify,heappop,heappush
#heapify(q),heappush(q,a),heappop(q) #q=heapify(q)としないこと、返り値はNone
#import fractions#古いatcoderコンテストの場合GCDなどはここからimportする
from functools import lru_cache#pypyでもうごく
#@lru_cache(maxsize = None)#maxsizeは保存するデータ数の最大値、2**nが最も高効率
from decimal import Decimal

def input(): 
    x=sys.stdin.readline()
    return x[:-1] if x[-1]=="\n" else x
def printl(li): _=print(*li, sep="\n") if li else None
def argsort(s, return_sorted=False): 
    inds=sorted(range(len(s)), key=lambda k: s[k])
    if return_sorted: return inds, [s[i] for i in inds]
    return inds
def alp2num(c,cap=False): return ord(c)-97 if not cap else ord(c)-65
def num2alp(i,cap=False): return chr(i+97) if not cap else chr(i+65)
def matmat(A,B):
    K,N,M=len(B),len(A),len(B[0])
    return [[sum([(A[i][k]*B[k][j]) for k in range(K)]) for j in range(M)] for i in range(N)]
def matvec(M,v):
    N,size=len(v),len(M)
    return [sum([M[i][j]*v[j] for j in range(N)]) for i in range(size)]
def T(M):
    n,m=len(M),len(M[0])
    return [[M[j][i] for j in range(n)] for i in range(m)]
def main():
    mod = 1000000007
    #w.sort(key=itemgetter(1),reversed=True)  #二個目の要素で降順並び替え

    N = int(input())
    #N, K = map(int, input().split())
    #A = tuple(map(int, input().split())) #1行ベクトル
    #L = tuple(int(input()) for i in range(N)) #改行ベクトル
    #S = tuple(tuple(map(int, input().split())) for i in range(N)) #改行行列
    edge = [[] for i in range(N)]
    for i in range(N-1):#木の場合M=N-1
        a,b,w = map(int,input().split())
        edge[a-1].append((w,b-1))
        edge[b-1].append((w,a-1)) #有向のばあいコメントアウト

    def dfs():
        q=deque([(0,0)])
        visited=[False]*N
        while len(q):
            e,w=q.pop()#ここをpopleftにすると幅優先探索BFSになる
            if visited[e]:continue
            visited[e]=1 if w%2==0 else 2
            for dw,ne in edge[e]:
                q.append((ne,w+dw))
        return visited
    x=dfs()
    for xi in x:
        if xi==1:
            print(0)
        else:
            print(1)



if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
(n,),*t=[map(int,t.split())for t in open(0)]
*e,=eval('[],'*-~n)
q=[(1,0)]
f=[-1]*n
for v,w,c in t:e[v]+=(w,c),;e[w]+=(v,c),
for v,c in q:
 f[v-1]=c&1
 for w,d in e[v]:q+=[(w,c+d)]*(f[w-1]<0)
print(*f)

Submission status: Accepted

Solution code:
import sys
import copy
sys.setrecursionlimit(10**7)
def dfs(graph,v,dist_mod):
    color[v] = dist_mod
    for next_v,dist in graph[v]:
        if color[next_v] != -1:
            continue
        dfs(graph,next_v,(dist_mod+dist)%2)
n = int(input())
uvw = [list(map(int,input().split())) for _ in range(n-1)]
g = [[] for _ in range(n)]
color = [-1]*n
for i in range(n-1):
    g[uvw[i][0]-1].append([uvw[i][1]-1,uvw[i][2]])
    g[uvw[i][1]-1].append([uvw[i][0]-1,uvw[i][2]])
dfs(g,0,0)
for i in range(n):
    print(color[i])

Submission status: Accepted

Solution code:
"""bfs"""

import sys
sys.setrecursionlimit(10**6)

n = int(input())

to = [[] for _ in range(n)]
cost = [[] for _ in range(n)]

for i in range(n-1):
    a,b,w = map(int, input().split())
    a -= 1; b -= 1
    to[a].append(b); cost[a].append(w)
    to[b].append(a); cost[b].append(w)

ans = [-1]*n # 頂点を探索済みかどうか判定するために初期値を-1に
ans[0] = 0

import queue

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

while not q.empty():
    v = q.get()
    for i in range(len(to[v])):
        u = to[v][i]
        w = cost[v][i]
        if ans[u] != -1: continue
        ans[u] = (ans[v]+w)%2
        q.put(u)
        
print(*ans)

Submission status: Accepted

Solution code:
"""dfs"""

import sys
sys.setrecursionlimit(10**6)

n = int(input())
 
G = {}
for i in range(n):
    G.update({i:[]})

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

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

def dfs(graph, v, c):
    color[v] = c
    
    for next_v in graph[v]:
        if color[next_v[0]] != -1: continue
        dist = next_v[1]
        if dist == 0:
            next_c = c
        elif dist == 1:
            next_c = 1 - c
        
        dfs(graph, next_v[0], next_c)

dfs(G, 0, 0)

print(*color)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(200000)

n = int(input())
 
G = {}
for i in range(n):
    G.update({i: []})
 
for i in range(n - 1):
    u, v, w = map(int, input().split())
    G[u - 1].append([v - 1, w % 2])
    G[v - 1].append([u - 1, w % 2])
 
color = [-1 for i in range(n)]
 
def dfs(graph, v, c):
    color[v] = c
    
    for next_v in graph[v]:
        dis = next_v[1]
        if color[next_v[0]] != -1:
            continue
        
        if dis == 0:
            n_c = c
        elif dis == 1:
            n_c = 1 - c
        
        dfs(graph, next_v[0], n_c)
 
dfs(G, 0, 0)
[print(i) for i in color]

Submission status: Accepted

Solution code:
# coding: utf-8
# hello worldと表示する
#float型を許すな
#numpyはpythonで
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil,pi,factorial
from operator import itemgetter
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
def SI(): return input().rstrip()
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
inf = 10**17
mod = 10**9 + 7

n=I()
tree=[[] for i in range(n)]
for i in range(n-1):
    u,v,w=MI()
    u-=1
    v-=1
    tree[u].append([v,w])
    tree[v].append([u,w])
q=deque([[0,0]])
al=[-1 for i in range(n)]
#al[0]=0
col=[0 for i in range(n)]
def dfs(a,b):
    al[a]=0
    col[a]=b
    for x,y in tree[a]:
        if al[x]<0:
            dfs(x,(y+b)%2)
dfs(0,0)
#print(col)
for i in range(n):
    print(str(col[i]))

Submission status: Accepted

Solution code:
# coding: utf-8
# hello worldと表示する
#float型を許すな
#numpyはpythonで
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil,pi,factorial
from operator import itemgetter
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
def SI(): return input().rstrip()
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
inf = 10**17
mod = 10**9 + 7

n=I()
tree=[[] for i in range(n)]
for i in range(n-1):
    u,v,w=MI()
    u-=1
    v-=1
    tree[u].append([v,w])
    tree[v].append([u,w])
q=deque([[0,0]])
al=[-1 for i in range(n)]
al[0]=0
col=[0 for i in range(n)]
while q:
    a,b=q.popleft()
    #print(a,b)
    for x,y in tree[a]:
        if (b+y)%2==1:
            col[x]=1
            if al[x]==-1:
                q.append([x,1])
                al[x]=0
        else:
            if al[x]==-1:
                q.append([x,0])
                al[x]=0
#print(col)
for i in range(n):
    print(str(col[i]))

Submission status: Accepted

Solution code:
import networkx as nx

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

G = nx.Graph()

color = [0 for _ in range(N)]

for u, v, w in UVW:
    G.add_edge(u - 1, v - 1, weight=w)

color[0] = -1

pred, dist = nx.dijkstra_predecessor_and_distance(G, 0)

c = [dist[i] for i in range(N)]
ans = [1 if i % 2 == 0 else 0 for i in c]
print(*ans)

Submission status: Accepted

Solution code:
import collections

n = int(input())
v = []
for i in range(n+10):
    v.append([])

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

q = collections.deque([])
used = [None] * (n+10)
q.append([1,0])
while len(q) > 0:
    cur, color = q.pop()
    used[cur] = color
    for i in range(len(v[cur])):
        nind, w = v[cur][i]
        if used[nind] != None:
            continue
        if w % 2 == 0:
            q.append([nind, color])
        else:
            q.append([nind, 1-color])
for i in range(1, n+1):
    print(used[i])

Submission status: Accepted

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

Ans = [-1]*N
P = deque([0])
Ans[0] = 0
while(len(P) > 0):
    a = P.popleft()
    for i in T[a]:
        if Ans[i[0]] == -1:
            if i[1] == 0:
                Ans[i[0]] = Ans[a]
            else:
                Ans[i[0]] = (Ans[a] + 1) % 2
            P.append(i[0])
for i in Ans:
    print(i)

Submission status: Accepted

Solution code:
n = int(input())

ikeru = [[] for _ in range(n)]
for i in range(n-1):
	a, b, c = map(int, input().split())
	ikeru[a-1].append((b-1, c))
	ikeru[b-1].append((a-1, c))

#fukasa = [0 for _ in range(n)]
#fukasamoto = [0 for _ in range(n)]
kaisuu = 0
settansaku = set([])
setmada = {0}
kouho = 1
guuki = [0 for _ in range(n)]

while kouho != 0:
	kaisuu += 1
	for i in list(setmada):
		settansaku.add(i)
		setmada.remove(i)
		kouho -= 1
		for k, leng in ikeru[i]:
			if not k in setmada:
				if not k in settansaku:
					setmada.add(k)
					guuki[k] = (guuki[i] + leng) % 2
					kouho += 1
					#fukasa[k] = kaisuu
					#fukasamoto[k] = i+1

print("\n".join([str(guuki[i]) for i in range(n)]))

Submission status: Accepted

Solution code:
N = int(input())
D = {i: [] for i in range(N)}
distD = {}
for i in range(N-1):
    u, v, w = map(int, input().split())
    u -= 1
    v -= 1
    D[u].append(v)
    D[v].append(u)
    distD[u*N+v], distD[v*N+u] = w, w
clr = [-1 for _ in range(N)]
clr[0] = 0
s = [0]
pnt = 0
cnt = 1
while pnt < cnt:
    n = cnt
    for i in range(pnt, cnt):
        L = D[s[i]]
        for j in L:
            if clr[j] == -1:
                clr[j] = (clr[s[i]] + distD[s[i]*N+j]) % 2
                s.append(j)
                cnt += 1
    pnt = n
for i in range(N):
    print(clr[i])

Submission status: Accepted

Solution code:
def INT():
    return int(input())

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

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

from collections import deque

N = INT()
Tree = [[] for _ in range(N)]

for _ in range(N - 1):
    u, v, w = MI()
    Tree[u - 1].append((v - 1, w))
    Tree[v - 1].append((u - 1, w))
    
color = [0] * N
queue = deque([0])
visited = [False] * N

while queue:
    q = queue.popleft()
    visited[q] = True
    
    for t in Tree[q]:
        if not visited[t[0]]:
            if t[1] % 2 == 0:
                color[t[0]] = color[q]
                
            else:
                if color[q] == 0:
                    color[t[0]] = 1
                else:
                    color[t[0]] = 0
            
            queue.append(t[0])
        
for c in color:
    print(c)

Submission status: Accepted

Solution code:
from collections import deque

n = int(input())
a = [[] for _ in range(n)]
for _ in range(n - 1):
    u, v, w = map(int, input().split())
    a[u - 1].append((v - 1, w))
    a[v - 1].append((u - 1, w))
d = [-1] * n
todo = deque([(0, 0)])
seen = set()
while todo:
    p, e = todo.popleft()
    if p in seen:
        continue
    seen.add(p)
    d[p] = e
    for pi, ei in a[p]:
        todo.append((pi, e + ei))
for di in d:
    print(di % 2)

Submission status: Accepted

Solution code:
from heapq import heappop, heappush

n = int(input())
a = [[] for _ in range(n)]
for _ in range(n - 1):
    u, v, w = map(int, input().split())
    a[u - 1].append((v - 1, w))
    a[v - 1].append((u - 1, w))
d = [-1] * n
todo = [(0, 0)]
seen = set()
while todo:
    e, p = heappop(todo)
    if p in seen:
        continue
    seen.add(p)
    d[p] = e
    for pi, ei in a[p]:
        heappush(todo, (e + ei, pi))
for di in d:
    print(di % 2)

Submission status: Accepted

Solution code:
from collections import deque
import sys
sys.setrecursionlimit(10**9)


def mi(): return map(int,input().split())
def ii(): return int(input())
def isp(): return input().split()

def main():
    N = ii()

    u = 0
    graph = [[] for _ in range(10**5+10)]
    for i in range(N-1):
        u,v,w=mi()
        graph[u].append((v,w))
        graph[v].append((u,w))

    seen = set()
    stack = deque([u])

    ans=[[] for _ in range(N+1)]
    ans[u] = 0
    while stack:
        current = stack.popleft()

        for next, w in graph[current]:
            if next in seen: continue
            if w%2==0:
                ans[next] = ans[current]
            else:
                ans[next] = 0 if ans[current] == 1 else 1

            seen.add(next)
            stack.append(next)



    print(*ans[1:],sep='\n')




if __name__ == "__main__":
  main()

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
#mod = 998244353
INF = 10**18
eps = 10**-7

N = int(readline())

nodes = [{} for i in range(N+1)]

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

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

def dfs(start,to,dist):
    ver = nodes[start][to]
    ans[to] = (dist + ver)%2
    for k in nodes[to].keys():
        if k != start:
            dfs(to,k,dist+ver)

for k in nodes[1].keys():
    dfs(1,k,0)

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(200_000)

def solve(N: int, u: "List[int]", v: "List[int]", w: "List[int]"):
    from collections import namedtuple
    Edge = namedtuple("Edge", "to cost")
    edges = [[] for _ in range(N)]
    for uu, vv, ww in zip(u, v, w):
        edges[uu-1].append(Edge(vv-1, ww))
        edges[vv-1].append(Edge(uu-1, ww))
    colors = [None] * N
    def dfs(n, c):
        if colors[n] is not None:
            return
        colors[n] = c
        for nn, w in edges[n]:
            dfs(nn, (c+w)%2)
    dfs(0, 0)
    return colors


# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    u = [int()] * (N - 1)  # type: "List[int]"
    v = [int()] * (N - 1)  # type: "List[int]"
    w = [int()] * (N - 1)  # type: "List[int]"
    for i in range(N - 1):
        u[i] = int(next(tokens))
        v[i] = int(next(tokens))
        w[i] = int(next(tokens))
    print(*solve(N, u, v, w), sep="\n")

def test():
    import doctest
    doctest.testmod()

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

Submission status: Accepted

Solution code:
n = int(input())
d = [[] for i 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])

ans = [[] for i in range(n)]
ans[0].append(0)
q = [0]

while q:
    x = q.pop()
    for u,w in d[x]:
        if not ans[u]:
            buf = ans[x][0]
            if w%2==1:
                buf = (buf+1)%2
            ans[u].append(buf)
            q.append(u)

for i in ans:
    print(*i)

Submission status: Accepted

Solution code:
n=int(input())
a=[-1 for i in range(n)]
d=[[] for i in range(n)]
for i in range(n-1):
    u,v,w=map(int,input().split())
    u-=1
    v-=1
    d[u].append([v,w])
    d[v].append([u,w])
e=0
a[0]=0
l=[]
for i,j in d[0]:
    a[i]=(a[0]+j)%2
    l.append(i)
while len(l)>0:
    b=l.pop()
    for i,j in d[b]:
        if a[i]==-1:
            a[i]=(a[b]+j)%2
            l.append(i)
print(*a,sep='\n')

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(500*500)

graph = []
distance = []

def dfs(G, v, dist = 0):
    #print(v)
    distance[v-1] = dist

    for i in range(0,len(G[v-1]),2):
        #print(i, G[v-1][i])
        if distance[G[v-1][i]-1] != -1:
            continue
        dist += G[v-1][i+1]
        #print(1,1,dist)
        dfs(G, G[v-1][i], dist)
        dist -= G[v-1][i+1]

N = int(input())

for i in range(N):
    graph.append([])
    distance.append(-1)

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


#print(graph)
#print(distance)

dfs(graph, 1)

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

#print(graph)
#print(distance)

Submission status: Accepted

Solution code:
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][v] = w
    G[v][u] = w

ans = [0] * N
todo = [(0, 0)]
done = set()
while todo:
    p, d = todo.pop()
    for np, dd in G[p].items():
        if not np in done:
            nd = d + dd
            ans[np] = nd % 2
            todo.append((np, nd))
    done.add(p)

for x in ans:
    print(x)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**9)
def dfs(parent,current,distance):
  global m
  m[current]=distance
  for child in graph[current]:
    if child[0]==parent:
      continue
    dfs(current,child[0],distance+child[1])
n=int(input())
graph=[]
for i in range(n+1):
  graph.append([])
m=[0]*(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])
dfs(1,1,0)
for i in range(1,n+1):
  if m[i]%2==0:
    print(1)
  else:
    print(0)

Submission status: Accepted

Solution code:
N = int(input())
graph = [[] for  _ in range(N)]
now = 0
for _ in range(N-1):
    x,y,w = map(int,input().split())
    x -= 1
    y -= 1
    graph[x].append((y,w))
    graph[y].append((x,w))
    now = x
    
vis = [0 for _ in range(N)]

even = set()
odd = set()
import sys
sys.setrecursionlimit(10000000)


def dfs(now):
    #print(now)
    for nv in graph[now]:
        if vis[nv[0]]: continue
        if nv[1] % 2 == 0:
            if now in even:
                even.add(nv[0])
            else:
                odd.add(nv[0])
        else:
            if now in even:
                odd.add(nv[0])
            else:
                even.add(nv[0])
        vis[nv[0]] = 1
        dfs(nv[0])
vis[x] = 1
even.add(x)
dfs(x)

for i in range(N):
    if i in even:
        print(1)
    else:
        print(0)

Submission status: Accepted

Solution code:
from collections import deque

def dfs(start):
  stack = deque([[start, 0]])
  while stack:
    p, c = stack.popleft()
    for next, distance in graph[p]:
      if visited[next] == -1:
        if distance % 2 == 0:
          visited[next] = int(c)
        else:
          visited[next] = int(not c)
        stack.append([next, visited[next]])

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

visited = [-1] * n
visited[0] = 0
dfs(0)
for v in visited:
    print(v)

Submission status: Accepted

Solution code:
from collections import deque
from collections import defaultdict

n = int(input())

graph = defaultdict(set)
visited = [1] * 2 + [0] * (n - 1)
ans = [0] * (n + 1)

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

q = deque([1])

while q:
    curr = q.popleft()
    visited[curr] = 1
    for v, w in graph[curr]:
        if not visited[v]:
            ans[v] = (ans[curr] + w) % 2
            q.append(v)
        else:
            continue

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

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
from collections import deque


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

    if v not in e:
        e[v] = [[u,w]]
    else:
        e[v].append([u,w])


que = deque()
que.append([1,0,0])
ans = [-1 for i in range(n)]
ans[0] = 0
no_one = True
flag = True
while True:
    if len(que) == 0:
        break
    top = que.popleft()
    st = top[0]
    for edge in e[st]:
        ecos = edge[1]
        nex = edge[0]
        if ans[nex-1] == -1:
            cos0 = top[1]+ecos
            cos1 = top[2]+ecos

            if cos0 %2 == 0:
                que.append([nex,0,cos1])
                ans[nex-1] = 0
            elif cos1 %2 == 0:
                que.append([nex,cos0,0])
                ans[nex-1] = 1
            else:
                if no_one:
                    que.append([nex, cos0, 0])
                    ans[nex - 1] = 1
                else:
                    flag = False
                    break

    if not flag:
        break
    # print(que)

for a in ans:
    print(a)
# print(ans)