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:
def d_even_relation_dfs():
    import sys
    sys.setrecursionlimit(10**6)
    N = int(input())
    Edges = [[int(i) for i in input().split()] for j in range(N - 1)]

    graph = [[] for _ in range(N)]
    for u, v, w in Edges:  # 頂点は 0-indexed とする
        graph[u - 1].append((v - 1, w))
        graph[v - 1].append((u - 1, w))

    def distance_from_root(parent, current, distance, ret=None):
        """根 (頂点 0) から各頂点への距離"""
        if ret is None:
            ret = [0] * N

        ret[current] = distance
        for next_vertex, dist in graph[current]:
            if next_vertex != parent:
                distance_from_root(current, next_vertex, distance + dist, ret)
        return ret
    ans = (0 if d % 2 else 1 for d in distance_from_root(-1, 0, 0))  # 根の親は -1 番
    return ' '.join(map(str, ans))

print(d_even_relation_dfs())

Submission status: Accepted

Solution code:
def d_even_relation_bfs():
    from collections import deque
    N = int(input())
    Edges = [[int(i) for i in input().split()] for j in range(N - 1)]

    graph = [[] for _ in range(N)]
    for u, v, w in Edges:  # 頂点は 0-indexed とする
        graph[u - 1].append((v - 1, w))
        graph[v - 1].append((u - 1, w))
    distance_from_root = [0] * N  # 根は頂点 0 とする

    queue = deque([(-1, 0, 0)])  # 親と現在の頂点番号，根から親までの距離
    while queue:
        parent, current, distance = queue.pop()
        distance_from_root[current] = distance
        for next_vertex, dist in graph[current]:
            if parent != next_vertex:  # 木を「逆戻り」しない頂点だけ調べる
                queue.appendleft((current, next_vertex, distance + dist))
    ans = (1 if d % 2 == 0 else 0 for d in distance_from_root)
    return ' '.join(map(str, ans))

print(d_even_relation_bfs())

Submission status: Accepted

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


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

for i in range(N-1):
    a,b,w = map(int,input().split())
    G[a-1].append([b,w])
    G[b-1].append([a,w])
S = [-1]*N

def dfs(x,w,c):
    if w%2 !=0:
        c = 1-c
    S[x]=c
    for i in range(len(G[x])):
        x1 = G[x][i][0]-1
        if S[x1] != -1:
            continue
        w1 = G[x][i][1]
        dfs(x1,w1,c)

dfs(G[0][0][0]-1,G[0][0][1],0)
for i in range(N):
    print(S[i])

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 5 + 10)
def input(): return sys.stdin.readline().strip()

def resolve():
    
    # https://atcoder.jp/contests/abc070/tasks/abc070_d
    # https://atcoder.jp/contests/abc070/submissions/11681543
    from heapq import heapify, heappop, heappush
    
    inf = 10 ** 17
    
    
    def dijkstra_heap(start, edge):
        # 始点から各頂点への最短距離(頂点番号:0~N-1)
        d = [inf] * N
        used = [False] * N
        d[start] = 0
        used[start] = True
        edgelist = []
        # a:重み(//), b:次の頂点(%)
        for a, b in edge[start]:
            heappush(edgelist, a * (10 ** 6) + b)
    
        while len(edgelist):
            # まだ最短距離が決まっていない頂点の中から最小の距離のものを探す
            minedge = heappop(edgelist)
            if used[minedge % (10 ** 6)]:
                continue
            node = minedge % (10 ** 6)
            d[node] = minedge // (10 ** 6)
            used[node] = True
    
            for e in edge[node]:
                if not used[e[1]]:
                    heappush(edgelist, (e[0] + d[node]) * (10 ** 6) + e[1])
        return d
    
    
    # N:頂点数 W:辺数
    N = int(input())
    W = N-1
    
    edge = [[] for i in range(N)]
    # edge[i] : iから出る道の[重み,行先]の配列
    for _ in range(W):
        x, y, z = map(int, input().split())
        edge[x - 1].append((z, y - 1))
        edge[y - 1].append((z, x - 1))
    
    d = dijkstra_heap(0, edge)
    for i in d:
        print(i%2)
    
    
    
resolve()

Submission status: Accepted

Solution code:
import sys, re
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees#, log2
from collections import deque, defaultdict, Counter
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop, heapify
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7
 
N = INT()
uvw = [LIST() for _ in range(N-1)]

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

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

#print(graph)

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

def DFS(node):
	for i, w in graph[node]:
		if color[i] == -1:
			if w%2:
				color[i] = color[node]^1
			else:
				color[i] = color[node]
			DFS(i)

DFS(0)

#print(color)

for x in color:
	print(x)

Submission status: Accepted

Solution code:
import sys, re
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees#, log2
from collections import deque, defaultdict, Counter
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop, heapify
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7
 
N = INT()
uvw = [LIST() for _ in range(N-1)]

graph = defaultdict(list)

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

#print(graph)

colors=[0]*N
colors[0]=1

def DFS(node):
	for x, w in graph[node]:
		if not colors[x]:
			if w%2:
				colors[x] = colors[node]*(-1)
			else:
				colors[x] = colors[node]
			DFS(x)

DFS(0)

#print(colors)

for x in colors:
	if x == 1:
		print(0)
	else:
		print(1)

Submission status: Accepted

Solution code:
import sys, re
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees#, log2
from collections import deque, defaultdict, Counter
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop, heapify
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7
 
N = INT()
uvw = [LIST() for _ in range(N-1)]

graph = defaultdict(list)

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

#print(graph)

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

def DFS(node):
	for x, w in graph[node]:
		if colors[x] == -1:
			if w%2:
				colors[x] = colors[node]^1
			else:
				colors[x] = colors[node]
			DFS(x)

DFS(0)

#print(colors)

for x in colors:
	print(x)

Submission status: Accepted

Solution code:
import sys, re
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees#, log2
from collections import deque, defaultdict, Counter
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop, heapify
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7
 
N = INT()
uvw = [LIST() for _ in range(N-1)]

graph = defaultdict(list)

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

#print(graph)

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

def DFS(node):
	for x, w in graph[node]:
		if not color[x]:
			if w%2 == 0:
				color[x] = color[node] 
			else:
				color[x] = color[node]*(-1)
			DFS(x)

DFS(0)

for x in color:
	if x == 1:
		print(0)
	elif x == -1:
		print(1)
	else:
		print("HOGE")

Submission status: Accepted

Solution code:
import sys, re
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees#, log2
from collections import deque, defaultdict, Counter
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop, heapify
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7
 
N = INT()
uvw = [LIST() for _ in range(N-1)]

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

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

#print(graph)

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

def DFS(n):
	for x, w in graph[n]:
		#print(x, w)
		if step[x] == -1:
			if (w+step[n])%2:
				step[x] = 1
			else:
				step[x] = 0
			#print(step)
			DFS(x)

DFS(0)

for ans in step:
	print(ans)

Submission status: Accepted

Solution code:
import sys
import collections
def input():
    return sys.stdin.readline()[:-1]
sys.setrecursionlimit(10000000)

n = int(input())
g = [[]for i in range(n)]
for i in range(n-1):
    u,v,w = map(int,input().split())
    u-=1
    v-=1
    g[u].append([v,w])
    g[v].append([u,w])
lis = [-1 for i in range(n)]
def dfs(i,j,color):
    for nec,leng in g[i]:
        if nec==j:continue
        if leng%2==0:
            lis[nec] = color
            dfs(nec,i,color)
        else:
            lis[nec] = 1-color
            dfs(nec,i,1-color)
lis[0]=0
dfs(0,-1,0)

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

Submission status: Accepted

Solution code:
#!python3

import sys
sys.setrecursionlimit(10 ** 6)


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

# input
N = int(input())
UVW = [LI() for _ in range(N - 1)]


# params
link = [[] for _ in range(N)]
for u, v, w in UVW:
    u -= 1
    v -= 1
    link[u].append((v, w))
    link[v].append((u, w))


def dfs(ans, x):
    for y, w in link[x]:
        if ans[y] is None:
            if w % 2 == 0:
                ans[y] = ans[x]
            else:
                ans[y] = 0 if ans[x] else 1
            dfs(ans, y)


def main():
    ans = [None] * N
    ans[0] = 0
    dfs(ans, 0)
    for a in ans:
        print(a)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
#%% for atcoder uniittest use
import sys
input= lambda: sys.stdin.readline().rstrip()
sys.setrecursionlimit(10**9)
def pin(type=int):return map(type,input().split())
def tupin(t=int):return tuple(pin(t))
def lispin(t=int):return list(pin(t))
#%%code
def resolve():
    N,=pin()
    graph={i+1:dict() for i in range(N)}
    #print(graph)
    for i in range(N-1):
        u,v,w=pin()
        graph[u][v]=w%2
        graph[v][u]=w%2
    #print(graph)

    ans={i+1:0 for i in range(N)}
    seen={i+1:0 for i in range(N)}
    #ans[1]=0 (always)
    stack=[(1,0)]#pos,color
    while (stack!=[]):
        p,c=stack.pop()
        if seen[p]==1:continue

        seen[p]=1
        ans[p]=c
        for k,v in graph[p].items():
            stack.append((k,(c+v)%2))
    #print(ans)
    print(*ans.values(),sep="\n")
resolve()

Submission status: Accepted

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

N = int(input())
G = [[] for i in range(N)]
for i in range(N - 1):
    a, b, w = map(int, input().split())
    G[a - 1].append([b, w])
    G[b - 1].append([a, w])
S = [-1] * N

def func(x, w, c):
    if w % 2 != 0:
        c = 1 - c
    S[x] = c
    for i in range(len(G[x])):
        x1 = G[x][i][0] - 1
        if S[x1] != -1:
            continue
        w1 = G[x][i][1]
        func(x1, w1, c)

func(G[0][0][0] - 1, G[0][0][1], 0)
for i in range(N):
    print(S[i])

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(100000)

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

res = [None] * N
visited = [False] * (N+1)
def dfs(node, c, w):
  res[node-1] = c
  visited[node] = True

  for nei, nw, in adj_list[node]:
    if not visited[nei]:
      if (w+nw)%2 == 0:
        dfs(nei, 0, w+nw)
      else:
        dfs(nei, 1, w+nw)

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 6)
N = int(input())
uvw = [list(map(int, input().split())) for i in range(N - 1)]
R = [-1] * N
Q = [[] for i in range(N)]
for i in range(N - 1):
    Q[uvw[i][0] - 1].append([uvw[i][1], uvw[i][2]])
    Q[uvw[i][1] - 1].append([uvw[i][0], uvw[i][2]])

def func(i, s, d, l):
    
    if R[i] != -1:
        return

    if R[i] == -1:
        if l %2 == 0:
            R[i] = s
        else:
            R[i] = d
            tmp = s
            s = d
            d = tmp
    for j in range(len(Q[i])):
        func(Q[i][j][0] - 1, s, d, Q[i][j][1])

func(uvw[0][0] - 1, 0, 1, 0)
for i in range(len(R)):
    print(R[i])

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000)

n = int(input())
t = [[] for _ in range(n)]
color = [None for _ in range(n)]
visited = [False for _ in range(n)]


def dfs(n_num):
    visited[n_num] = True
    for i in t[n_num]:
        if visited[i[0]]:
            continue
        if i[1] % 2 == 0:
            color[i[0]] = color[n_num]
        else:
            color[i[0]] = abs(color[n_num] - 1)
        dfs(i[0])


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

color[0] = 0
dfs(0)
for i in color:
    print(i)

Submission status: Accepted

Solution code:
from queue import Queue
N = int(input())
G = [[] for _ in range(N)]
C = [[] for _ in range(N)]
for _ in range(N-1):
    a, b, w = map(int, input().split())
    a -= 1
    b -= 1
    G[a].append(b)
    C[a].append(w)
    G[b].append(a)
    C[b].append(w)
ans = [-1] * N
ans[0] = 0
que = Queue()
que.put(0)
while not que.empty():
    v = que.get()
    l = len(G[v])
    for i in range(l):
        u = G[v][i]
        w = C[v][i]
        if ans[u] != -1:
            continue
        ans[u] = (ans[v] + w) % 2
        que.put(u)
print(*ans, sep='\n')

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
from itertools import accumulate
from itertools import permutations
from itertools import combinations
from collections import defaultdict
from collections import Counter
import fractions
import math
from collections import deque
from bisect import bisect_left
from bisect import insort_left
import itertools
from heapq import heapify
from heapq import heappop
from heapq import heappush
import heapq
import numpy as np
INF = float("inf")
#d = defaultdict(int)
#d = defaultdict(list)
#N = int(input())
#A = list(map(int,input().split()))
#S = list(input())
#S.remove("\n")
#N,M = map(int,input().split())
#S,T = map(str,input().split())
#A = [int(input()) for _ in range(N)]
#S = [input() for _ in range(N)]
#A = [list(map(int,input().split())) for _ in range(N)]
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))
color = [-1]*N
black = 0
white = 1
color[0] = white
def dfs(cur,parent):
    li = tree[cur]
    for chi,dis in li:
        if chi == parent:
            continue
        if dis % 2 == 0:
            color[chi] = color[cur]
            dfs(chi,cur)
        else:
            if color[cur] == black:
                color[chi] = white
            else:
                color[chi] = black
            dfs(chi,cur)
dfs(0,-1)
for i in color:
    print(i)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000000)
input = sys.stdin.readline

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

def dfs(u, c):
  color[u] = c
  for v, w in graph[u]:
    if color[v] == -1:
      if w % 2 == 0:
        dfs(v, c)
      else:
        dfs(v, abs(1-c))
  return

dfs(0, 0)
color = list(map(str, color))
print(*color)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(100001)

def dfs(node,w):
  weight = w
  for l in tree[node]:
    if color[l[0]] > -1:
      continue
    color[l[0]] = int (not ((l[1]%2==0) ^ color[node]))
    
    dfs(l[0],l[1])
    


N = int(input())
tree = {}
color = [-1]*(N+1)

for i in range(1,N+1):
  tree[i] = []
for i in range(N-1):
  u,v,w = map(int,input().split())
  tree[u].append([v,w])
  tree[v].append([u,w])
  
color[1] = 0
dfs(1,0)
print('\n'.join(map(str,color[1:])))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(100001)

def dfs(node,w):
  weight = w
  for l in tree[node]:
    if color[l[0]] > -1:
      continue
    if l[1]%2 == 0:
      color[l[0]] = color[node]
    else:
      color[l[0]] = int(not color[node])
    dfs(l[0],l[1])
    


N = int(input())
tree = {}
color = [-1]*(N+1)

for i in range(1,N+1):
  tree[i] = []
for i in range(N-1):
  u,v,w = map(int,input().split())
  tree[u].append([v,w])
  tree[v].append([u,w])
  
color[1] = 0
dfs(1,0)
color = [c  if c>-1 else 0 for c in color]
print('\n'.join(map(str,color[1:])))

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(2000000)


    N = int(input())
    edges = [[]for _ in range(N+1)]
    for _ in range(N-1):
        u,v,w = map(int,input().split())
        edges[u].append((v,w%2))
        edges[v].append((u,w%2))
    colors = [0]*(N+1)
    def dfs(n,p,c):
        colors[n] = c
        for nx,w in edges[n]:
            if nx != p:
                if w%2 == 0:
                    dfs(nx,n,c)
                else:
                    dfs(nx,n,(c+1)%2)

    dfs(1,0,0)
    for i in range(1,N+1):
        print(colors[i])

main()

Submission status: Accepted

Solution code:
n = int(input())
g = [[]for i in range(n)]
def swap(n):
    if n == 1:
        return 0
    else:
        return 1
for i in range(n-1):
    u,v,w = map(int,input().split())
    u = u-1
    v = v-1
    w = w%2
    g[u].append([v,w])
    g[v].append([u,w])
ans = [-1 for i in range(n)]
from collections import deque
d = deque([[0,0]]) #左は頂点の数字、右は塗った色
while d:
    p,q = d.pop()
    ans[p] = q
    for j,w in g[p]:
        if ans[j] != -1:
            continue
        else:
            if w == 1:
                d.append([j,swap(q)])
            else:
                d.append([j,q])
for i in range(n):
    print(ans[i])

Submission status: Accepted

Solution code:
n = int(input())
g = [[]for i in range(n)]
def swap(n):
    if n == 1:
        return 0
    else:
        return 1
for i in range(n-1):
    u,v,w = map(int,input().split())
    u = u-1
    v = v-1
    w = w%2
    g[u].append([v,w])
    g[v].append([u,w])
ans = [-1 for i in range(n)]
from collections import deque
d = deque([[0,0]]) #左は頂点の数字、右は塗った色
while d:
    p,q = d.popleft()
    ans[p] = q
    for j,w in g[p]:
        if ans[j] != -1:
            continue
        else:
            if w == 1:
                d.append([j,swap(q)])
            else:
                d.append([j,q])
for i in range(n):
    print(ans[i])

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from collections import deque
import sys
try:
    from typing import List
except ImportError:
    pass


def solve(N: int, u: "List[int]", v: "List[int]", w: "List[int]"):
    G = [[] for _ in range(N)]
    for ui, vi, wi in zip(u, v, w):
        ui -= 1
        vi -= 1
        G[ui].append((vi, wi))
        G[vi].append((ui, wi))
    color = [-1] * N
    color[0] = 0
    q = deque([0])
    while q:
        s = q.popleft()
        for t, wi in G[s]:
            if color[t] >= 0:
                continue
            color[t] = (color[s] + wi) % 2
            q.append(t)
    for colori in color:
        print(colori)


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))
    solve(N, u, v, w)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque
N = int(input())
connection =[[] for i in range(N)]
for i in range(1,N):
    u,v,w = (int(x) for x in input().split())
    u -=1
    v -=1
    connection[u].append((v,w))
    connection[v].append((u,w))
#
start=0
node =[None]*N
node[start] =0
dq =deque()
dq.append(start)

#
while dq:
    sarch =dq.popleft()
    for nv,w in connection[sarch]:
        if node[nv] is None:
            node[nv] = (node[sarch] +w) %2
            dq.append(nv)   
print(*node,sep="\n")

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

ans = [0]*N
used_1 = [0]*N
used_2 = [0]*N
for i in range(N):
    if used_1[i] == 0:
        used_1[i] = 1
        u = i
        P = deque([])
        for j in range(len(T[i])):
            v = T[u][j][0]
            w = T[u][j][1]
            P.append(v)
            if used_2[v] == 1:
                k = ans[v]
                if k == 1:
                    if w == 1:
                        ans[u] = 0
                    else:
                        ans[u] = 1
                else:
                    if w == 1:
                        ans[u] = 1
                    else:
                        ans[u] = 0
                used_2[u] = 1
            elif used_2[u] == 1:
                k = ans[u]
                if k == 1:
                    if w == 1:
                        ans[v] = 0
                    else:
                        ans[v] = 1
                else:
                    if w == 1:
                        ans[v] = 1
                    else:
                        ans[v] = 0
                used_2[v] = 1
            else:
                if w == 1:
                    ans[v] = 1
                else:
                    pass
                used_2[u] = 1
                used_2[v] = 1
        while(True):
            i = P.popleft()
            if used_1[i] == 0:
                used_1[i] = 1
                u = i
                for j in range(len(T[i])):
                    v = T[u][j][0]
                    w = T[u][j][1]
                    P.append(v)
                    if used_2[v] == 1:
                        k = ans[v]
                        if k == 1:
                            if w == 1:
                                ans[u] = 0
                            else:
                                ans[u] = 1
                        else:
                            if w == 1:
                                ans[u] = 1
                            else:
                                ans[u] = 0
                        used_2[u] = 1
                    elif used_2[u] == 1:
                        k = ans[u]
                        if k == 1:
                            if w == 1:
                                ans[v] = 0
                            else:
                                ans[v] = 1
                        else:
                            if w == 1:
                                ans[v] = 1
                            else:
                                ans[v] = 0
                        used_2[v] = 1
                    else:
                        if w == 1:
                            ans[v] = 1
                        else:
                            pass
                        used_2[u] = 1
                        used_2[v] = 1
            if len(P) == 0:
                break

for i in ans:
    print(i)

Submission status: Accepted

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

def dijkstra_heap(s):
    #始点sから各頂点への最短距離
    d = [float("inf")] * n
    used = [True] * n #True:未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    for e in edge[s]:
        heapq.heappush(edgelist,e)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if not used[minedge[1]]:
            continue
        v = minedge[1]
        d[v] = minedge[0]
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,[e[0]+d[v],e[1]])
    return d

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

Submission status: Accepted

Solution code:
import numpy as np
from scipy.sparse.csgraph import shortest_path
import heapq
n = int(input())
edge = [[] for i in range(n)]
for i in range(n-1):
    u, v, w = map(int, input().split())
    u -= 1
    v -= 1
    edge[u].append([w, v])
    edge[v].append([w, u])

def dijkstra_heap(s):
    #始点sから各頂点への最短距離
    d = [float("inf")] * n
    used = [True] * n #True:未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    for e in edge[s]:
        heapq.heappush(edgelist,e)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if not used[minedge[1]]:
            continue
        v = minedge[1]
        d[v] = minedge[0]
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,[e[0]+d[v],e[1]])
    return d

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

Submission status: Accepted

Solution code:
from collections import defaultdict
import sys
sys.setrecursionlimit(1000000)

class edge:
    def __init__(self, to, cost):
        self.to, self.cost = to, cost

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

    color = [0] * (N+1)

    def dfs(ver):
        for e in g[ver]:
            if color[e.to] == 0 and e.cost%2 == 0:
                color[e.to] = color[ver]
                dfs(e.to)
            elif color[e.to] == 0 and e.cost%2 == 1:
                color[e.to] = (-1) * color[ver]
                dfs(e.to)
    color[1] = 1
    dfs(1)
    for i in range(1, N+1):
        if color[i] == -1: color[i] = 0
    print(*color[1:], sep='\n')
    return

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from functools import reduce
from fractions import gcd
import math
import bisect
import itertools
import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline
INF = float("inf")
MOD = 1000000007


class Edge:
    def __init__(self, to, cost):
        self.to = to
        self.cost = cost


visited = []
vertex = []
def dfs(G, v, d):
    visited[v] = True
    if d % 2 == 0:
        vertex[v] = 0
    else:
        vertex[v] = 1

    for edge in G[v]:
        nv = edge.to
        if visited[nv]:
            continue
        nd = d + edge.cost
        dfs(G, nv, nd)


def main():
    N = int(input())
    G = [[] for _ in range(N)]
    for _ in range(N-1):
        a, b, cost = map(int, input().split())
        a -= 1; b -= 1
        G[a].append(Edge(b, cost))
        G[b].append(Edge(a, cost))

    for _ in range(N):
        visited.append(False)
        vertex.append(0)
    
    dfs(G, 0, 0)

    for v in vertex:
        print(v)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().rstrip()
from collections import deque
def main():
    n=int(input())
    graph=[[]for _ in range(n)]
    for _ in range(n-1):
        u,v,w=map(int,input().split())
        graph[u-1].append((v-1,w))
        graph[v-1].append((u-1,w))
    D=[-1]*n
    D[0]=0
    que=deque([0])
    while que:
        q=que.popleft()
        qw=D[q]
        for nn,w in graph[q]:
            if D[nn]==-1:
                D[nn]=qw+w
                que.append(nn)
    for d in D:
        if d%2==0:
            print(0)
        else:
            print(1)


if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
n = int(input())
tree = [[] for i in range(n)]
d_list = [0]*n

stack = []
for i in range(n-1):
  u,v,w = map(int,input().split())
  tree[u-1].append((u-1,v-1,w))
  tree[v-1].append((v-1,u-1,w))
while len(tree[0]) > 0:
  e = tree[0].pop()
  stack.append(e)
#print(stack)
while len(stack) > 0:
  u,v, w = stack.pop()
  if d_list[v] == 0:
    d_list[v] = d_list[u]+w
  while len(tree[v]) > 0:
    e = tree[v].pop()
    stack.append(e)
  #print(stack)
for v in d_list:
  if v % 2 == 0:
    print(0)
  else:
    print(1)