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:
import sys
sys.setrecursionlimit(1000000)

n = int(input())
tree = [[] for _ in range(n)]
color = [0]*n
for _ in range(n-1):
  a,b,c = map(int,input().split())
  a -= 1
  b -= 1
  tree[a].append((b,c))
  tree[b].append((a,c))
  
  
def dfs(i,before,cost):
  if cost == 1:
    color[i] = 1
  for j in tree[i]:
    if j[0] == before:
      continue
    dfs(j[0],i,(cost + j[1])%2 )
    
dfs(0,-1,0)

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

Submission status: Accepted

Solution code:
from collections import deque
n = int(input())
# 最終的に出力する色
colors = [-1] * n
# 重み付き無向グラフ
conns = [set() for _ in [0] * n] 

for x in range(1, n):
  v1, v2, dis = map(int, input().split())
  # (接続ノード, 重み) を加える
  conns[v1-1].add((v2-1, dis))
  conns[v2-1].add((v1-1, dis))

# BFSの為に根ノードを初期化. (基準ノード, 距離, 過去のノード)
q = deque([(0, 0, -1)])
# BFS開始
while q:
  v, dis, past = q.popleft()
  
  # 奇数なら1で,偶数なら0で塗る
  colors[v] = dis&1
  
  # 基準ノードから生える各エッジに対し
  for edge, w in conns[v]:
    
    # エッジが既に調べたものなら飛ばす
    if edge == past:
      continue
    # 根からここまでの距離を足しつつ,新しく探索先を追加.
    q.append((edge, dis + w, v))

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000)

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

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

def dfs(u, c):
    visited[u] = True   #; print('u, c', u, c)
    for vw in M[u]:
        v, w = vw       #; print(vw)
        if visited[v] == False:
            if w%2 == 0:
                color[v] = c * 0b1
            else:
                color[v] = c ^ 0b1
            #print('v, c', v, c)
            dfs(v, color[v])

dfs(u, 0)
for i in range(N):
    print(color[i])

Submission status: Accepted

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

N = int(input())
edges = [list(map(int,input().split())) for _ in range(N-1)]
A  = [[] for j in range(N+1)]

for edge in edges:
  A[edge[0]].append([edge[1],edge[2]])
  A[edge[1]].append([edge[0],edge[2]])
  
depth = [-1]*(N+1)
depth[1] = 0

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


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

Submission status: Accepted

Solution code:
n = int(input())
color = [-1] * n
edges = [[] for i in range(n)]
for i in range(n - 1):
    u, v, w = map(int, input().split())
    edges[u - 1].append((v - 1, w))
    edges[v - 1].append((u - 1, w))
q = [0]
color[0] = 0
while len(q) > 0:
    u = q.pop(0)
    for v, w in edges[u]:
        if color[v] < 0:
            q.append(v)
            color[v] = (color[u] + w) % 2
for i in range(n):
    print(color[i])

Submission status: Accepted

Solution code:
import os, sys, re, math, queue

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

for _ in range(N-1):
	u,v,w = list(map(int,input().split(' ')))
	if u in nodes:
		nodes[u].append((v,w % 2))
	else:
		nodes[u] = [(v,w % 2)]

	if v in nodes:		
		nodes[v].append((u,w % 2))
	else:
		nodes[v] = [(u,w % 2)]

q = queue.Queue()
fst = list(nodes.keys())[0]
q.put((fst,0))

while not q.empty():
	pos, color = q.get()
	colors[pos] = color
	for cand in nodes[pos]:
		if colors[cand[0]] == -1:
			if cand[1] == 0:
				q.put((cand[0], color))
			else:
				q.put((cand[0], (color+1) % 2))

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

Submission status: Accepted

Solution code:

N = int(input())
flag = [None] * (N+1)
edges = [[] for j in range(N+1)]

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


def dfs(i, color):
  visited = set()
  distances = [float("inf")] * (N + 1)
  stack = [i]
  distances[i] = 0
  flag[i] = color

  while stack:
    u = stack.pop()
    visited.add(u)

    for (v, w) in edges[u]:
      if v not in visited:
        stack.append(v)
        distances[v] = distances[u] + w
        if distances[v] % 2 == 0:
          flag[v] = color

dfs(1, 0)
for u in range(1, N+1):
  if flag[u] == None:
    dfs(u, 1)
    break

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

Submission status: Accepted

Solution code:
from collections import deque
N = int(input())
uvw = [[]for i in range(N)]
for i in range(N-1):
    u,v,w = list(map(int,input().split()))
    uvw[u-1].append([v-1,w%2])
    uvw[v-1].append([u-1,w%2])    
color = [-1 for i in range(N)]
color[0] = 0
que = deque()
que.append(0)
while que:
    q = que.popleft()
    colorq = color[q]
    for i in uvw[q]:
        if color[i[0]] == -1:
            que.append(i[0])
            if i[1] == 0:
                color[i[0]] = colorq
            else:
                color[i[0]] = abs(colorq-1)
for i in color:
    print(i)

Submission status: Accepted

Solution code:
# input = sys.stdin.readline
from bisect import *
from collections import *
from heapq import *
# import functools
# import itertools
# import math
N=int(input())
VUW=[list(map(int,input().split())) for i in range(N-1)]
data=[[] for i in range(N+1)]
nagasa={}
for v,u,w in VUW:
    data[v].append(u)
    data[u].append(v)
    v,u=min(v,u),max(v,u)
    nagasa.update({str(v)+" "+str(u):w})
kakutei=set([i for i in range(1,N+1)])
iro=[0 for i in range(N+1)]
#print(nagasa)
#print(data)
itta=set()
st=1
stack=deque([[st,0,st]])
while stack:
    v,m,st=stack.popleft()
    for u in data[v]:
        if not u in itta:
            itta.add(u)
            a,b=min(v,u),max(v,u)
            w=nagasa[str(a)+" "+str(b)]
            M=m+w

            if M%2==1:
                iro[u]=1
            stack.append([u,M,st])

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

Submission status: Accepted

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


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

for edge in edges:
  A[edge[0]].append([edge[1],edge[2]])
  A[edge[1]].append([edge[0],edge[2]])
  
depth = [-1] * (N+1)
depth[1] = 0

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

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

Submission status: Accepted

Solution code:
from collections import defaultdict
N=int(input())
E=defaultdict(list)
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))
ans=[-1]*N

stack=[0]
ans[0]=0
while stack:
    node=stack.pop()
    for to,w in E[node]:
        if ans[to]!=-1: continue
        ans[to]=ans[node]^(w&1)
        stack.append(to)

for c in ans:
    print(c)

Submission status: Accepted

Solution code:
import queue

import sys
input = sys.stdin.readline

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

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

q=queue.Queue()
ans=[0]*N
q.put((0,-1,0))#v,par,col

while not q.empty():
    v,p,c=q.get()
    for i in range(len(adj[v])):
        n_v=adj[v][i][0]
        if n_v!=p:
            n_c=(c+adj[v][i][1])%2
            ans[n_v]=n_c
            q.put((n_v,v,n_c))
            
[print(ans[i]) for i in range(N)]

Submission status: Accepted

Solution code:
import collections

def dfs(s_node):
    q = collections.deque()
    used = set()
    q.append(s_node)
    used.add(s_node)
    while len(q) > 0:
        prv_node = q.pop()
        for node, cost in g[prv_node]:
            if node in used:
                continue
            else:
                if cost % 2 == 0:
                    cols[node] = cols[prv_node]
                else:
                    cols[node] = -cols[prv_node]
                q.append(node)
                used.add(node)


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

cols = [-1 for _ in range(N)]
dfs(0)

[print(1) if cols[i] == 1 else print(0) for i in range(N)]

Submission status: Accepted

Solution code:
from collections import deque

N = int(input())
tree = [[] for _ in range(N)]
for _ in range(N - 1):
    u, v, w = map(int, input().split())
    u, v = u - 1, v - 1  # 番号: 0 ~ N-1 で統一
    w %= 2
    tree[u].append((v, w))
    tree[v].append((u, w))

D = deque([0])
ans = [None] * N
ans[0] = 0
while D:
    x = D.popleft()
    for v, w in tree[x]:
        if ans[v] is None:
            ans[v] = (ans[x] + w) % 2
            D.append(v)

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**9)
N = int(input())
adjacent_list = [[] for _ in range(N)]
for _ in range(N-1):
    u, v, w = map(int,input().split())
    u -= 1
    v -= 1
    adjacent_list[u].append([v, w])
    adjacent_list[v].append([u, w])


colors = [-1]*N


def dfs(v, color):
    if colors[v] != -1: # 探索済みでないかチェック。
        return
    colors[v] = color
    for adjacent_v in adjacent_list[v]:
        if adjacent_v[1] % 2 == 0:
            dfs(adjacent_v[0], color)
        else:
            dfs(adjacent_v[0], 1-color)

dfs(0,0)

#print(*colors)
for i in range(N):
    print(colors[i])

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**9)
N = int(input())
adjacent_list = [[] for _ in range(N)]
for _ in range(N-1):
    u, v, w = map(int,input().split())
    u -= 1
    v -= 1
    adjacent_list[u].append([v, w])
    adjacent_list[v].append([u, w])


colors = [-1]*N


def dfs(v, color):
    if colors[v] != -1:
        return
    colors[v] = color
    for adjacent_v in adjacent_list[v]:
        if adjacent_v[1] % 2 == 0:
            dfs(adjacent_v[0], color)
        else:
            dfs(adjacent_v[0], 1-color)

dfs(0,0)

#print(*colors)
for i in range(N):
    print(colors[i])

Submission status: Accepted

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

from collections import deque

############### TESTCASE ###############
test = ""
#test = \
"""
3
1 2 2
2 3 1
ans:
0
0
1
"""

"""
5
2 5 2
2 3 10
1 3 8
3 4 2
ans:
1
0
1
0
1
"""
########################################
test = list(reversed(test.strip().splitlines()))
if test:
    def input2():
        return test.pop()
else:
    def input2():
        return input()
################# MAIN ################# 
        
n = int(input2())
edges = [0] * (n-1)
for i in range(n-1):
    edges[i] = tuple(map(int, input2().split()))

adjacency_list = [[] for i in range(n+1)]
for edge in edges:
    adjacency_list[edge[0]].append((edge[1], edge[2]))
    adjacency_list[edge[1]].append((edge[0], edge[2]))

nodeL = [None] * (n+1)
nodeL[1] = 0
nodeQ = deque([[1]])
while nodeQ:
    tmp = nodeQ.popleft()
    tmp = tmp[0]
    
    nodes = adjacency_list[tmp]
    for nd in nodes:
        if nodeL[nd[0]] == None:
            nodeL[nd[0]] = nodeL[tmp] ^ nd[1]%2
            nodeQ.append([nd[0]])

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)
N = int(input())
L = [-1 for i in range(N)]
flg = [0 for i in range(N)]
M = [[] for i in range(N)]
for i in range(N-1):
  u, v, w = map(int, input().split())
  M[u-1].append([v-1, w%2])
  M[v-1].append([u-1, w%2])
L[0] = 0
def dist(m, d):
  L[m] = d % 2
  for i in M[m]:
    if L[i[0]] == -1:
      dist(i[0], i[1] + d)
dist(0, 0)
for i in range(N):
  print(L[i])

Submission status: Accepted

Solution code:
import math
import sys
import numpy as np
sys.setrecursionlimit(10 ** 7)

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

n = int(input())

G = [[] for _ in range(n + 5)]
for i in range(n - 1):
    u, v, w = int_input()
    u -= 1
    v -= 1
    G[u].append([v, w])
    G[v].append([u, w])

ans = [-1] * (n + 5)

def dfs(k, dist):
    ans[k] = dist % 2
    for i in G[k]:
        if ans[i[0]] == -1:
            dfs(i[0], dist + i[1])
    
dfs(0, 0)

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)
N = int(input())
a = [[] for _ in range(N)]
ans = [0]*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])
def calc(u, b):
  for v, w in a[u]:
    if not b == v:
      ans[v]=(ans[u] + w)%2
      calc(v, u)
calc(0, -1)
for i in ans:
  if i % 2 == 0:
    print(0)
  else:
    print(1)

Submission status: Accepted

Solution code:
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,pprint,fractions
sys.setrecursionlimit(10**8)
mod = 10**9+7
mod2 = 998244353
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpln(n): return list(int(sys.stdin.readline()) for i in range(n))

n = inp()
g = [[] for i in range(n)]
for i in range(n-1):
    a,b,c = inpl()
    g[a-1].append((b-1,c))
    g[b-1].append((a-1,c))
color = [-1] * n 
color[0] = 0
def dfs(node):
    for v,c in g[node]:
        if color[v] != -1:
            continue
        if (c) % 2:
            color[v] = 0 if color[node] else 1
        else: color[v] = 1 if color[node] else 0
        dfs(v)
dfs(0)

for i in color:
    print(i)

Submission status: Accepted

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

n = int(input())
g = [[] for _ in range(n)]

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

ans = [0] * n
def dfs(v,p,c):
  ans[v] = c
  for i in g[v]:
    if i[0] != p:
      if i[1] % 2 == 0:
        dfs(i[0], v, c)
      else:
        dfs(i[0], v, 1-c)
        
dfs(0,-1,0)

for i in ans:
  print(i)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(20000000)
def prepare(n,arr):
    nodeArr = [[] for i in range(n)]
    for ar in arr:
        nodeArr[ar[0]-1].append([ar[1]-1,ar[2]])
        nodeArr[ar[1]-1].append([ar[0]-1,ar[2]])
    return nodeArr

def dfs(currentNode,distance):
    res[currentNode] = distance
    for next in nodeArr[currentNode]:
        nextNode = next[0]
        nextNodeDistance = next[1]
        if res[nextNode] == -1:
            dfs(nextNode,distance + nextNodeDistance)




n = int(input())

arr = []

for i in range(n-1):
    arr.append([int(s) for s in input().split(" ")])

nodeArr = prepare(n, arr)


if n == 1:
    print(1)
else:
    res = [-1 for i in range(n)]

    dfs(0,0)

    result = [(re % 2) for re in res]

    for re in res:
        print(re % 2)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**9)


n = int(input())
COLORS = [True] * (n + 1)

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

def dfs(now, prev):
    for vertex in TREE[now]:
        if vertex == prev:
            continue
        else:
            next = vertex
        u, v = min(now, next), max(now, next)
        if LENGTHS[(u, v)] % 2 == 0:
            COLORS[next] = COLORS[now]
        else:
            COLORS[next] = not COLORS[now]
        dfs(next, now)
dfs(1, 0)

for i in range(1, n + 1):
    ans = int(COLORS[i])
    print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline

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

dic = {}
color = [0]*N
dist = {}
root = [0]*N

for i in range(N):
    dic[i+1] = []
for n in range(N-1):
    i = uvw[n][0]
    j = uvw[n][1]
    dic[i].append(j)
    dic[j].append(i)
    root[i-1] += 1
    root[j-1] += 1
    #color[(i,j)] = 0
    dist[(i,j)] = uvw[n][2]
    dist[(j,i)] = uvw[n][2]
root_node = root.index(1)+1
#ma = max(root)
def rec(now_node, now_dist):
    if now_dist%2==1:
        color[now_node-1] = 1
    tg_list = dic[now_node][:]
    for elem in tg_list:
        dic[elem].remove(now_node)
        rec(elem, now_dist + dist[(elem,now_node)])
rec(root_node,0)
#print(ma)
for n in range(N):
    #i = ab[n][0]
    #j = ab[n][1]
    print(color[n])

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from itertools import permutations
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    n = I()
    v = [[] for i in range(n)]
    for i in range(n-1):
        a,b,c = LI()
        a -= 1
        b -= 1
        v[a].append((b,c))
        v[b].append((a,c))
    bfs = [-1]*n
    q = deque([0])
    bfs[0] = 0
    ans = [0]*n
    while q:
        x = q.popleft()
        for y,c in v[x]:
            nd = bfs[x]+c
            if bfs[y] < 0:
                bfs[y] = nd
                ans[y] = nd&1
                q.append(y)
    for i in ans:
        print(i)
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
n=int(input())
li=[list(map(int,input().split())) for i in range(n-1)]

#色の情報を記録する配列を作る。0が白で、1が黒
col=[-1]*(n+1) #最初は全ての頂点が情報なし。
col[1]=0 #頂点1の色は白。

#2点間の距離の情報を記録する配列を作る…と思ったがO(n^2)やわこれ
#ついでにグラフも作る。距離の情報はグラフに入れることにしよう
graph = [[] for _ in range(n+1)]

for x,y,z in li:
  graph[x].append([y,z])
  graph[y].append([x,z])

def dfs(v):
    dist = [-1] * (n+1)
    stack = [v]
    dist[v] = 0
    while stack:
        v = stack.pop()
        dw = dist[v] + 1
        for w,z in graph[v]: #頂点vに接続してる点についての調査
            if dist[w] >= 0: #0以上であれば既に調査済み
                continue
            dist[w] = dw #調査済みでない場合は、distに現在の深さを記録。
            if z%2:
              col[w]=col[v]^1
            else:
              col[w]=col[v]
            stack.append(w)
    return col
print(*dfs(1)[1:], sep="\n")

Submission status: Accepted

Solution code:
from collections import deque

N = int(input())
G = [[] for _ in range(N)]  # (頂点, コスト)
for _ 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))

ans = [-1 for _ in range(N)]
q = deque()

ans[0] = 0
q.append(0)

while q:
    v = q.popleft()
    for u, w in G[v]:
        if ans[u] != -1:
            continue
        ans[u] = (ans[v] + w) % 2
        q.append(u)

for a in ans:
    print(a)

Submission status: Accepted

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

stack = [0]
color = [-1] * n
color[0] = 0
while stack:
    v = stack.pop()
    for b, w in vs[v]:
        if color[b] == -1:
            color[b] = (color[v] + w) % 2
            stack.append(b)

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

Submission status: Accepted

Solution code:
# coding: utf-8

def paint():
	while len(stack) > 0:
		node = stack.pop()
		for n in adj_list[node]:
			if color_list[n[0]] != "-1":
				continue

			stack.append(n[0])

			if n[1] % 2 == 0:
				color_list[n[0]] = color_list[node]
			else:
				if color_list[node] == "0":
					color_list[n[0]] = "1"
				else:
					color_list[n[0]] = "0"

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

for i in range(N - 1):
	elm = [int(x) for x in input().split()]
	adj_list[elm[0] - 1].append([elm[1] - 1, elm[2]])
	adj_list[elm[1] - 1].append([elm[0] - 1, elm[2]])

color_list = ["-1"] * N
color_list[0] = "0"

import sys
sys.setrecursionlimit(10000)

stack = [0]
paint()

for c in color_list:
	print(c)

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.readline

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


def dfs(a):
    dist = [-1] * (n + 1)
    stack = [a]
    dist[a] = 0
    while stack:
        v = stack.pop()
        for b, w in graph[v]:
            if dist[b] == -1:
                dist[b] = (dist[v] + w) % 2
                stack.append(b)
            else:
                continue
    return dist


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

Submission status: Accepted

Solution code:
from collections import defaultdict, deque

N = int(input())
edges = defaultdict(list)
for _ in range(N - 1):
    u, v, w = map(int, input().split())
    u -= 1
    v -= 1
    w = w % 2 == 0  # True if even
    edges[u].append((v, w))
    edges[v].append((u, w))

colors = [None] * N
colors[0] = 0
queue = deque()
queue.append((0, 0))
while queue:
    v1, c1 = queue.popleft()
    for v2, w in edges[v1]:
        if colors[v2] is not None:
            continue
        if w:
            colors[v2] = c1
        else:
            colors[v2] = 1 - c1
        queue.append((v2, colors[v2]))
for c in colors:
    print(c)

Submission status: Accepted

Solution code:
from collections import deque
N = int(input())
G = {}
for _ in range(N-1):
    u,v,w = map(int,input().split())
    if u not in G:
        G[u] = []
    G[u].append((v,w%2))
    if v not in G:
        G[v] = []
    G[v].append((u,w%2))
que = deque([(1,0)])
hist = [0 for _ in range(N+1)]
hist[1] = 1
col = [0 for _ in range(N+1)]
while que:
    u,c = que.popleft()
    for x in G[u]:
        v,w = x[0],x[1]
        if hist[v]==0:
            if w==0:
                col[v] = c
                que.append((v,c))
            else:
                col[v] = 1-c
                que.append((v,1-c))
            hist[v] = 1
for i in range(1,N+1):
    print(col[i])

Submission status: Accepted

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

l=[-1]*n
s=[(1,0)]
while s:
    b,c=s.pop()
    l[b]=c%2
    for x,y in g[b]:
        if l[x]==-1:
            s.append((x,y+c))

for  i in l:
    print(i)

Submission status: Accepted

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

def dfs(pos, not_pos, tree_dict, ans_li, length):
  n_li = tree_dict[pos]
  for n, w in n_li:
    if n == not_pos:
      continue
    new_length = length+w
    if new_length%2 == 0:
      ans_li[n] = 0
    else:
      ans_li[n] = 1
    ans = dfs(n, pos, tree_dict, ans_li, new_length)
  return ans_li

def run():
  N = int(input())
  tree_dict = {}
  ans_li = [0]*(N+1)
  for n in range(N-1):
    u, v, w = map(int, input().split())
    tree_dict.setdefault(u, []).append((v, w))
    tree_dict.setdefault(v, []).append((u, w))
  length = 0
  ans = dfs(1, -1, tree_dict, ans_li, length)
  for a in ans[1:]:
    print(a)
    

if __name__ == '__main__':
  run()

Submission status: Accepted

Solution code:
N = int(input())
d = dict(zip([i for i in range(1, N+1)], [[] for _ in range(N)]))
 
for i in range(N-1):
  u, v, w = map(int, input().split())
  d[u].append([v, w])
  d[v].append([u, w])
  
colors = [0 for i in range(N)]
l = [[1, 1]]
while l:
  node, parent = l.pop()
  edges = d[node]
  for v, w in edges:
    if v == parent:
      continue
    colors[v-1] = (colors[node-1]+w)%2
    l.append([v, node])
    
for c in colors:
  if c==1:
    print(0)
  else:
    print(1)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(500*500);

def dfs(G,v,bef_v,ind_num):
	if v == bef_v :
		seen[v] = 0;
	else :
		#print(bef_v,v,G[v],weight[bef_v][v],seen[bef_v])
		if G[bef_v][1][ind_num] % 2 :
			seen[v] = int(not seen[bef_v]);
		else :
			seen[v] = seen[bef_v];
	
	for i in range(len(G[v][0])) :
		next_v = G[v][0][i];
		if seen[next_v]==-1 :
			dfs(G,next_v,v,i);


n = int(input());
G = [[0]*2 for i in range(n) ];
for i in range(n) :
	G[i][0] = [];
	G[i][1] = [];
for i in range(n-1) :
	s = input().split(' ');
	u = int(s[0])-1;
	v = int(s[1])-1;
	w = int(s[2]);
	G[u][0].append(v);
	G[v][0].append(u);
	G[u][1].append(w);
	G[v][1].append(w);


seen = [-1]*n;
dfs(G,0,0,0);

for i in range(n):
	print(seen[i]);

Submission status: Accepted

Solution code:
import sys
from collections import deque
sys.setrecursionlimit(10**9)
INF=10**18
def input():
    return sys.stdin.readline().rstrip()

def main():
    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))
    queue=deque()
    queue.append(0)
    used=[False]*N
    l=[0]*N
    while queue:
        node=queue.popleft()
        used[node]=True
        for childnode,weight in edge[node]:
            if not used[childnode]:
                if weight%2:
                    l[childnode]=int(not l[node])
                else:
                    l[childnode]=l[node]
                queue.append(childnode)
    for x in l:
        print(x)
        

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from collections import deque

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

    ans = [0] * (N + 1)

    visited = set()
    visited.add(1)
    q = deque()
    q.append(1)

    while q:
        x = q.pop()
        for v in T[x]:
            if v[0] in visited:
                continue
            visited.add(v[0])
            q.append(v[0])
            if v[1] & 1:
                ans[v[0]] = (ans[x] + 1) % 2
            else:
                ans[v[0]] = ans[x]

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



        


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**5+1)

N=int(input())
uvw=[list(map(int, input().split())) for i in range(N-1)]
nodelink=[[] for i in range(N+1)]
for i in range(N-1):
  nodelink[uvw[i][0]].append([uvw[i][1], uvw[i][2]])
  nodelink[uvw[i][1]].append([uvw[i][0], uvw[i][2]])
  
color=[-1]*(N+1)

def f(nuru, iro):
  color[nuru]=iro
  tonari=nodelink[nuru]
  for nuruyo in tonari:
    if color[nuruyo[0]]<0:
      if (nuruyo[1]%2)==0:
        f(nuruyo[0], iro)
      else:
        f(nuruyo[0], 1-iro)
      
f(1, 0)

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

Submission status: Accepted

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


dist = [float('inf')] * N
stack = [[0, 0]]
while stack:
    n, d = stack.pop()
    dist[n] = d

    for to, w in T[n]:
        if dist[to] != float('inf'):
            continue

        stack.append([to, d + w])

ans = [d % 2 for d in dist]
print(*ans, sep='\n')

Submission status: Accepted

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


ans = [-1] * N
stack = [[0, 0]]
while stack:
    n, color = stack.pop()
    ans[n] = color

    for to, w in T[n]:
        if ans[to] != -1:
            continue

        if w % 2 == 0:
            stack.append([to, color])
        else:
            stack.append([to, color ^ 1])

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

Submission status: Accepted

Solution code:
N = int(input())

d = dict(zip([i for i in range(1, N+1)], [[] for _ in range(N)]))

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

colors = [0 for i in range(N)]
l = [[1, 1]]
while l:
  node, parent = l.pop()
  edges = d[node]
  for v, w in edges:
    if v == parent:
      continue
    
    colors[v-1] = (colors[node-1]+w)%2
    l.append([v, node])

for c in colors:
  print(c)

Submission status: Accepted

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


def dfs(u):
    for v, w in edge[u]:
        if trail[v] is None:
            trail[v] = (trail[u] + w) % 2
            dfs(v)


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

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

trail[0] = 0
dfs(0)

for t in trail:
    print(t)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)
n = int(input())
g = [[] for _ in range(n)]

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

def dfs(v,p,c):
    ans[v] = c
    for i in g[v]:
        if i[0] != p:
            if i[1] % 2 ==0:
                dfs(i[0],v,c)
            else:
                dfs(i[0],v,1-c)

dfs(0,-1,0)

for i in ans:
    print(i)

Submission status: Accepted

Solution code:
N = int(input())
color = [None] * N
UV = [[] for _ in range(N)]
for _ in range(N-1):
    u, v, w = map(int, input().split())
    u -= 1
    v -= 1
    UV[u].append((v, w))
    UV[v].append((u, w))

color[0] = True
li = [0]
while li:
    p = li.pop()
    for q, w in UV[p]:
        if color[q] is not None:
            continue
        if w & 1:
            color[q] = not color[p]
        else:
            color[q] = color[p]
        li.append(q)

print(*[int(i) for i in color], sep="\n")

Submission status: Accepted

Solution code:
import sys
from collections import deque
input = sys.stdin.readline
n = int(input())
abe = [list(map(int, input().split(' '))) for i in range(n-1)]
graph = [[] for i in range(n+1)]
parent = [0 for i in range(n+1)]
edge = [0 for i in range(n+1)]
root = 1
order = []
deq = deque([root])
for a,b,e in abe:
    graph[a].append(b)
    graph[b].append(a)
while deq:
    x = deq.popleft()
    order.append(x)
    for y in graph[x]:
        if parent[x] == y:
            continue
        parent[y] = x
        deq.append(y)
for a,b,e in abe:
    if parent[a] == b:
        edge[a] = e
    else:
        edge[b] = e
ans = [0 for i in range(n+1)]
for x in order:
    if x == 1:
        continue
    if edge[x]%2 == 0:
        ans[x] = ans[parent[x]]
    else:
        ans[x] = 1-ans[parent[x]]
del ans[0]
print(*ans,sep="\n")