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(10**6)
from math import floor,ceil,sqrt,factorial,log
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from operator import itemgetter
from fractions import gcd
mod = 10 ** 9 + 7
inf = float('inf')
ninf = -float('inf')
 
#整数input
def ii(): return int(sys.stdin.readline().rstrip()) #int(input())
def mii(): return map(int,sys.stdin.readline().rstrip().split())
def limii(): return list(mii()) #list(map(int,input().split()))
def lin(n:int): return [ii() for _ in range(n)]
def llint(n: int): return [limii() for _ in range(n)]
#文字列input
def ss(): return sys.stdin.readline().rstrip() #input()
def mss(): return sys.stdin.readline().rstrip().split()
def limss(): return list(mss()) #list(input().split())
def lst(n:int): return [ss() for _ in range(n)]
def llstr(n: int): return [limss() for _ in range(n)]

#本当に貪欲法か？ DP法では？？
#本当に貪欲法か？ DP法では？？
#本当に貪欲法か？ DP法では？？

n=ii()
mat = [[] for _ in range(n)]

for i in range(n-1):
    a,b,w=mii()
    mat[a-1].append([b-1,w])
    mat[b-1].append([a-1,w])

visited=[2]*n

def dfs(now,dist):
    #距離加算，判定
    #(now,dist)
    if dist %2==0:
        visited[now]=0
    else:
        visited[now]=1

    for i,j in mat[now]:
        if visited[i]!=2:continue
        dfs(i,dist+j)

dfs(0,0)
print(*visited)

Submission status: Accepted

Solution code:
N = int(input())  #頂点数
tree = [[] for _ in range(N)]
dic = {}
for i in range(N-1):
    u, v, w = map(int, input().split())
    if u > v:
        u, v = v, u
    tree[u-1].append(v-1)
    tree[v-1].append(u-1)
    dic[(u-1, v-1)] = w

import sys
sys.setrecursionlimit(10 ** 8)

#black:1, white:0, none:-1
ans = [-1]*N
ans[0] = 0
flag = [False]*N

def dfs(i):
    flag[i] = True
    for j in tree[i]:
        if flag[j]:
            continue
        x = min(i, j)
        y = max(i, j)
        if dic[(x, y)] % 2 == 0:
            ans[j] = ans[i]
        else:
            if ans[i] == 0:
                ans[j] = 1
            else:
                ans[j] = 0
        if not(flag[j]):
            dfs(j)
            
dfs(0)

for answer in ans:
    print(answer)

Submission status: Accepted

Solution code:
#template
def inputlist(): return [int(k) for k in input().split()]
import sys
sys.setrecursionlimit(10**8)
#template
N = int(input())
tree = [[]*(N+1) for _ in range(N+1)]
dic = {}
for i in range(N-1):
    u,v,w = inputlist()
    if u > v:
        u,v = v,u
    tree[u].append(v)
    tree[v].append(u)
    dic[(u,v)] = w
seen = [False]*(N+1)
ans = ['-1']*(N+1)
ans[1] = '0'
def dfs(i):
    seen[i] = True
    for x in tree[i]:
        if seen[x]:
            continue
        k = min(i,x)
        s = max(i,x)
        if dic[(k,s)] % 2 == 0:
            ans[x] = ans[i]
            dfs(x)
        if dic[(k,s)] % 2 == 1:
            if ans[i] == '0':
                ans[x] = '1'
                dfs(x)
            if ans[i] == '1':
                ans[x] = '0'
                dfs(x)
dfs(1)
for i in range(1,N+1):
    print(ans[i])

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)
n=int(input())
a = [[]*n for _ in range(n)]
visited = [0] * n
dist = [0]*n
col = [1]*n

def dfs(i:"int", c:"int"):
    for j in a[i]:
        if not visited[j[0]]:
            visited[j[0]]=1
            if j[1]%2==0:
                col[j[0]]=c
            else:
                col[j[0]]=c*-1
            dfs(j[0], col[j[0]])



if __name__ == '__main__':
    for i in range(n-1):
        u,v,d = map(int, input().split())
        a[u-1].append([v-1, d])
        a[v-1].append([u-1, d])
    visited[0]=1
    dfs(0, 1)
    for i in range(n):
        print(col[i] if col[i]>0 else 0)

Submission status: Accepted

Solution code:
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from heapq import heapify, heappop, heappush
 
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
 
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N = INT()
L = [LIST() for i in range(N-1)]
graph = defaultdict(list)

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

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

q = deque([0])
visited[0] = True
color[0] = 1

while q:
    a = q.pop()
    for node, w in graph[a]:
        if visited[node] == True:
            continue
        if w % 2 == 0:
            color[node] = color[a]
        else:
            color[node] = -1 * color[a]
        visited[node] = True
        q.append(node)
print(*[0 if c == 1 else 1 for c in color])

Submission status: Accepted

Solution code:
from collections import deque
#from math import factorial
import sys
sys.setrecursionlimit(2000000)
# import math
# import itertools
# import statistics
# import numpy as np
# import collections
n = int(input())
#n, m = list(map(int, input().split()))
d = [[] for i in range(n)]
for i in range(n-1):
    u, v, w = [int(j) for j in input().split()]
    d[u-1].append([v-1, w])  # 対応する頂点と距離
    d[v-1].append([u-1, w])

ans = [-1]*n
stack = [0]
ans[0] = 0

# print(d)
while stack:
    u = stack.pop()  # 見てるとこ
    for v, w in d[u]:  # 対のやつを調べる
        if ans[v] == -1:  # 未訪問の時
            if w % 2 == 0:
                ans[v] = ans[u]  # 対と同じ色
            else:
                ans[v] = (ans[u]+1) % 2
            stack.append(v)
    

for i in ans:
    print(i)

Submission status: Accepted

Solution code:
from queue import deque

n = int(input())
li = [[] for _ in range(n)]
length = {}
length_path = [0]*n

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

work_queue = deque([])
visited = [False]*n

work_queue.append(0)

while work_queue:
    now = work_queue.popleft()
    visited[now] = True
    for i in li[now]:
        if visited[i]:
            continue
        work_queue.append(i)
        visited[i] = True
        if now < i:
            length_path[i] = length_path[now]+length[(now,i)]
        else:
            length_path[i] = length_path[now]+length[(i,now)]

for i in length_path:
    print(i%2)

Submission status: Accepted

Solution code:
from sys import stdin
from collections import defaultdict,deque

N = int(stdin.readline().rstrip())
adj = defaultdict(set)

for i in range(N-1):
    u,v,w = [int(x) for x in stdin.readline().rstrip().split()]
    adj[u].add((v,w))
    adj[v].add((u,w))


ans = [0]*(N+1)
visit_p = deque()
visit_p.append((1,0))
visited = [False]*(N+1)
visited[1] = True


while visit_p:
    now_v,now_w = visit_p.popleft()
    for v,w in adj[now_v]:
        if visited[v]:
            continue
        ans[v] = w + now_w
        visited[v] = True
        visit_p.append((v,w+now_w))
for i in ans[1:]:
    if i % 2 == 0:
        print(0)
    else:
        print(1)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(100000000)
N = int(input())
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]]

color = [-1]*N 
def dfs(v, c):
  color[v] = c
  for next_v, w in graph[v]:
    if color[next_v] == c and w % 2 != 0:
      return 
    if color[next_v] == -1 and w % 2 == 0 and dfs(next_v, c) == False:
      return False
    if color[next_v] == -1 and w % 2 != 0 and dfs(next_v, abs(1-c)) == False:
      return False
  return True

dfs(0, 0)
for c in color:
  print(c)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)
def dfs(G,v,p):
    for nv,nw in G[v]:
        if(nv==p):
            continue
        if(nw%2==0):
            color[nv]=color[v]
        else:
            color[nv]=int(not color[v])
        dfs(G,nv,v)
N=int(input())
G=[[] for i in range(N)]
color=[-1]*N
for i in range(N-1):
    u,v,w=map(int,input().split())
    u,v=u-1,v-1
    G[u].append((v,w))
    G[v].append((u,w))
color[0]=0
dfs(G,0,-1)
print(*color,sep='\n')

Submission status: Accepted

Solution code:
N = int(input())
a = [0] * N
b = [[] for _ in range(N)]
for _ in range(N-1):
    x,y,z = map(int, input().split())
    x -= 1
    y -= 1
    b[x].append((y, z))
    b[y].append((x, z))


l = [(0, -1, 0)]
while l:
    x, s, t = l.pop()
    if t % 2 == 0:
        a[x] = 0
    else:
        a[x] = 1
    for v, w in b[x]:
        if v == s:
            continue
        l.append((v, x, t + w))

for x in a:
    print(x)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 9)
input = sys.stdin.readline


def main():
    N = int(input())
    en = [[] for _ in range(N)]
    on = [[] for _ in range(N)]
    for i in range(N - 1):
        u, v, w = map(int, input().split())
        if w % 2:
            on[u - 1].append(v - 1)
            on[v - 1].append(u - 1)
        else:
            en[u - 1].append(v - 1)
            en[v - 1].append(u - 1)

    color = [-1] * N
    stack = [(0, -1, 0)]
    while stack:
        node, parent, col = stack.pop()
        if color[node] >= 0:
            continue
        color[node] = col
        for k in en[node]:
            if k != parent:
                stack.append((k, node, col))
        for k in on[node]:
            if k != parent:
                stack.append((k, node, (col + 1) % 2))

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


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 9)
input = sys.stdin.readline


def main():
    N = int(input())
    en = [[] for _ in range(N)]
    on = [[] for _ in range(N)]
    for i in range(N - 1):
        u, v, w = map(int, input().split())
        if w % 2:
            on[u - 1].append(v - 1)
            on[v - 1].append(u - 1)
        else:
            en[u - 1].append(v - 1)
            en[v - 1].append(u - 1)

    color = [None] * N
    stack = [(0, -1, 0)]
    while stack:
        node, parent, col = stack.pop()
        if color[node] is not None:
            continue
        color[node] = col
        for k in en[node]:
            if k != parent:
                stack.append((k, node, col))
        for k in on[node]:
            if k != parent:
                stack.append((k, node, (col + 1) % 2))

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


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 9)
input = sys.stdin.readline

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

color = [None] * N
stack = [(0, -1, 0)]
while stack:
    node, parent, col = stack.pop()
    if color[node] is not None:
        continue
    color[node] = col
    for k in en[node]:
        if k != parent:
            stack.append((k, node, col))
    for k in on[node]:
        if k != parent:
            stack.append((k, node, (col + 1) % 2))

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

Submission status: Accepted

Solution code:
N=int(input())
tree=[set() for _ in range(N)]
for i in range(1,N):
    u,v,w=map(int,input().split())
    u=u-1
    v=v-1
    tree[u].add((v,w))
    tree[v].add((u,w))
ans=[-1]*N
q=[(0,0,-1)]
while q:
    now, ndis, priv = q.pop()
    if ndis % 2 == 0:
        ans[now] = 0
    else:
        ans[now] = 1
    for nex, dis in tree[now]:
        if nex == priv:
            continue
        q.append((nex, ndis + dis, now))
for i in ans:
    print(i)

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 = [-1]*n
ans[0]=0
q = [0]
cnt = 0

while q:
    u = q.pop()
    for v,w in d[u]:
        if ans[v]==-1:
            if w%2==0:
                ans[v]=ans[u]
            else:
                ans[v]=(ans[u]+1)%2
            q.append(v)
for i in ans:
    print(i)

Submission status: Accepted

Solution code:
from collections import deque

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


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

q = deque([0])
color[0] = 0
flag = 1
while len(q) != 0:
    u = q.popleft()
    for v, w in G[u]:
        if color[v] != -1: #訪問済みの時
            if w % 2 == 1 and color[v] == color[u]:
                flag = 0
            continue
        if w % 2 == 0:
            color[v] = color[u]
            q.append(v)
        else:
            color[v] = 1 - color[u]
            q.append(v)

if flag:
    for i in range(N):
        print(color[i])

Submission status: Accepted

Solution code:
# D - Even Relation

from collections import deque

n = int(input())

# adjacency list
alist = [[] for _ in range(n)]

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

#print(alist)

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

q = deque()
q.append(0)

while len(q)>0:
    node = q.popleft()
    for i, j in alist[node]:
        if dlist[i]<0:
            q.append(i)
            dlist[i] = (dlist[node] + j)%2
        else:
            continue

'''
def dfs(node, par, dist):
    dlist[node] = dist%2
    for i, j in alist[node]:
        if i==par:
            continue
        else:
            dfs(i, node, dist+j)
dfs(0,0,0)
'''

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

Submission status: Accepted

Solution code:
# solution

from collections import deque

data = int(input())
g = tuple(set() for _ in range(data))
for _ in range(data - 1):
    u, v, w = map(int, input().split())
    u -= 1
    v -= 1
    g[u].add((v, w))
    g[v].add((u, w))

d = [-1] * data
d[0] = 0

q = deque()
q.append(0)

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

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

Submission status: Accepted

Solution code:
from collections import deque
n = int(input())
g = [[] for _ in range(n)]
ln = []

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

q = deque([0])
par = [0] * n
order = []

while q:
    x = q.pop()
    order.append(x)
    for y in g[x]:
        if y == par[x]:
            continue
        par[y] = x
        q.append(y)

chr_l = [0] * n
for a, b, l in ln:
    if par[a] == b:
        chr_l[a] = l
    else:
        chr_l[b] = l

#print(ln, g, order)
#print(chr_l)

color = [-1] * n
color[0] = 0
org = [0, 1]

for x in order:
    for y in g[x]:
        if y == par[x]:
            continue
        if chr_l[y] % 2 == 0:
            color[y] = color[x]
        else:
            color[y] = color[x] ^ 1
print("\n".join(map(str, color)))

Submission status: Accepted

Solution code:
import sys
from io import StringIO
import unittest

sys.setrecursionlimit(100**3)

def coloring(v, p, vs, cs, color):
	cs[v] = color
	for e in vs[v]:
		if e[0] == p:
			continue
		nc = color if e[1] % 2 == 0 else 1 - color
		coloring(e[0], v, vs, cs, nc)

def resolve():
	n = int(input())
	vs = [[] for _ in range(n)]
	cs = [None]*n
	for i in range(n-1):
		u, v, w = map(int, input().split())
		vs[u-1].append([v-1, w])
		vs[v-1].append([u-1, w])
	coloring(0, None, vs, cs, 1)
	for i in cs:
		print(i)
resolve()

Submission status: Accepted

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

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

for _ in range(N-1):
    u,v,w=[int(x) for x in input().split()]
    if w&1:
        edge[u].append((v,-1))
        edge[v].append((u,-1))
    else:
        edge[u].append((v,1))
        edge[v].append((u,1))
    
color = [None]*(N+1)

def set_color(v,c):
    color[v]=c
    for x,sgn in edge[v]:
        if color[x] is None:
            set_color(x,sgn*c)
set_color(1,1)

for x in color[1:]:
    print((x+1)//2)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000000)
N = int(input())

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

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

def dfs(u, c):
    color[u] = c
    for v, w in G[u]:
        if color[v] != -1:
            if color[v] == c and w % 2 != 0:
                return False
        else:
            if w % 2 == 0:
                dfs(v, c)
            else:
                dfs(v, 1-c)
    return True

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

import queue

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

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

    ans = [-1 for i in range(N)]
    ans[0] = 0

    que = queue.Queue()
    que.put(0)
    while not(que.empty()):
        mm = que.get()
        for uv in UV[mm]:
            que.put(uv[0])
            if uv[1]%2==0:
                ans[uv[0]] = ans[mm]
            else:
                ans[uv[0]] = (ans[mm]+1)%2
        UV[mm] = []

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

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque
n = int(input())
d = [0]*(n+1)
tree = [[] for _ in range(n+1)]
for i in range(n-1):
  u,v,w = map(int,input().split())
  tree[u].append([v,w])
  tree[v].append([u,w])
q = deque([1])
done = [0]*(n+1)
done[1] = 1
while q:
  now = q.popleft()
  for l in tree[now]:
    if not done[l[0]]:
      q.append(l[0])
      done[l[0]] = 1
      d[l[0]] = d[now] + l[1]
for i in range(1,n+1):
  print(d[i]%2)

Submission status: Accepted

Solution code:
N = int(input())

Dist = [[] for j in range(N)]
Seen = [-1] * N

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

que = [0]
Seen[0] = 0
flag = True
while -1 in Seen:
    now = que.pop()
    for next, distance in Dist[now]:
        if Seen[next] == -1:
            que.insert(0, next)
            if distance % 2 == 0:
                Seen[next] = Seen[now]
            else:
                Seen[next] = 1 - Seen[now]
for i in range(N):
    print(Seen[i])

Submission status: Accepted

Solution code:
from collections import deque

N=int(input())
L=[[] for _ in range(N+1)]
for a in range(N-1):
    u,v,w=map(int,input().split())  #これで良いのか
    L[u].append((v,w))
    L[v].append((u,w))

dist=[-1]*(N+1)
q=deque()
color=[-1]*(N+1)

dist[1]=0
q.append(1)
color[1]=0
while q:
    now=q.popleft()
    for next in L[now]:
        if dist[next[0]]==-1:
            q.append(next[0])
            dist[next[0]]=dist[now]+next[1]
            if dist[next[0]]%2==0:
                color[next[0]]=0
            else:
                 color[next[0]]=1

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

Submission status: Accepted

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

stack = [(0, -1, 0)]
while stack:
    v, par, dist = stack.pop()
    if dist % 2 == 0:
        ans[v] = 0
    else:
        ans[v] = 1
    for child, child_dist in tree[v]:
        if child == par:
            continue
        stack.append((child, v, dist + child_dist))

for x in ans:
    print(x)

Submission status: Accepted

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

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

colors = [0] * N
def dfs(vNow, vPar):
    color = colors[vNow]
    for v2, wt in adjL[vNow]:
        if v2 == vPar: continue
        if wt%2:
            colors[v2] = 1-color
        else:
            colors[v2] = color
        dfs(v2, vNow)

dfs(0, -1)

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

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline


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

def dfs(s):
    stack = [s]
    Color = [-1]*N
    Color[s] = 0
    while stack:
        p = stack.pop()
        for np, w in graph[p]:
            if Color[np] == -1:
                Color[np] = Color[p]^(w%2)
                stack.append(np)
    return Color

if __name__ == "__main__":
    Color = dfs(0)
    print(*Color, sep="\n")

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline


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

def dfs(s):
    Ind = [0]*N
    stack = [s]
    Color = [0]*N
    while stack:
        p = stack[-1]
        if Ind[p] == len(graph[p]):
            stack.pop()
        elif len(stack) > 1 and stack[-2] == graph[p][Ind[p]][0]:
            Ind[p] += 1
        else:
            ch, w = graph[p][Ind[p]]
            Ind[p] += 1
            stack.append(ch)
            Color[ch] = Color[p]^(w%2)
    return Color

Color = dfs(0)
print(*Color, sep="\n")

Submission status: Accepted

Solution code:
from collections import deque

n = int(input())

neighbors = [[] for i in range(n+1)]

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

checked = [False] * (n+1)
colors = [0] * (n+1)

d = deque([1])
while len(d) > 0:
    u = d.pop()
    checked[u] = True

    for v, w in neighbors[u]:
        if checked[v]:
            continue

        if (colors[u] == 0 and w % 2 == 1) or (colors[u] == 1 and w % 2 == 0):
            colors[v] = 1

        d.append(v)

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

Submission status: Accepted

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

n=int(input())
l=[-1]*n
p=[[] for _ in range(n)]
for i in range(n-1):
    ui,vi,wi=map(int,input().split())
    p[ui-1].append([vi,wi])
    p[vi-1].append([ui,wi])

def tr1(x,y):
    #print(x)
    #print(y)
    
    if l[x-1]!=-1:
        return
    l[x-1]=y
    for i in range(len(p[x-1])):
        tr1(p[x-1][i][0],(y+p[x-1][i][1])%2)
tr1(1,0)
for j in range(n):
    print(l[j])

Submission status: Accepted

Solution code:
from collections import defaultdict
import queue
N = int(input())

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

visited = [False for _ in range(N)]
visited[start] = True
all_length =  [0 for _  in range(N)]
q = queue.Queue()
q.put(start)
while not q.empty():
    i = q.get()
    for v, w in d[i].items():
        if not visited[v]:
            q.put(v)
            visited[v] = True
            all_length[v] = all_length[i] + w
for length in all_length:
    print(length % 2)

Submission status: Accepted

Solution code:
N=int(input())
link=[[]for _ in range(N)]
node=[-1]*N
for _ in  range(N-1):
  u,v,w=map(int,input().split())
  w%=2
  link[u-1].append([v-1,w])
  link[v-1].append([u-1,w])
node[0]=0
q=[0]
while q:
  x=q.pop(0)
  for i,j in link[x]:
    if node[i]==-1:
      q.append(i)
      if j==1 :
        node[i]=(node[x]+1)%2
      elif j==0:
        node[i]=node[x]
print(*node,sep='\n')

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000000)

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

w = [u_v_w[i][2] for i in range(N-1)]

tree = [[] for i in range(N)]

for i in range(N-1):
    u = u_v_w[i][0]
    v = u_v_w[i][1]
    tree[u-1].append((v,w[i]))
    tree[v-1].append((u,w[i]))

ans = [0] * N
ans[0] = 1
def dfs(now):
    global ans
    for next in tree[now-1]:
        if ans[next[0]-1]:
            continue
        if next[1] % 2 == 0:
            ans[next[0]-1] = ans[now-1]
        else:
            ans[next[0]-1] = ans[now-1] * (-1)
        dfs(next[0])

dfs(1)
for i in range(len(ans)):
    if ans[i] == 1:
        print(0)
    else:
        print(1)

Submission status: Accepted

Solution code:
from collections import deque
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])
color = [-1]*n
que = deque([[0, -1, 0]])
while que:
    u, v, c = que.popleft()
    color[u] = c
    for i, j in edge[u]:
        if i == v: continue
        que.append([i, u, (c+j)%2])
print(*color, sep="\n")

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000)


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


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

c = [0] * n


def dfs(i=0, r=-1, co=0):
    c[i] = co
    for j, k in e[i]:
        if j != r:
            dfs(j, i, (co+k) % 2)


dfs()
print("\n".join(map(str, c)))

Submission status: Accepted

Solution code:
import collections, math, bisect

local = False
if local:
    file = open("input.txt", "r")
    import time

def inp():
    if local:
        return file.readline().rstrip()
    else:
        return input().rstrip()

def ints():
    return [int(_) for _ in inp().split()]


if local:
    start=time.time()

N = int(inp())

connection = [dict() for i in range(N)]

for i in range(1, N):
    u,v,w = ints()

    connection[u-1][v-1] = w
    connection[v-1][u-1] = w

colors = ["0"]*N
visited = set()

stck = [(0,0)]
visited.add(0)

while len(stck)>0:
    vertex, cur_dist = stck.pop(-1)

    if cur_dist%2==0:
        colors[vertex] = "0"
    else:
        colors[vertex] = "1"

    for nextVertex in connection[vertex]:
        if nextVertex not in visited:
            visited.add(nextVertex)
            stck.append((nextVertex, cur_dist+connection[vertex][nextVertex]))

for c in colors:
    print(c)


if local:
    fin = (time.time()-start)*1000
    print("{:.2f}".format(fin) + "ms")

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:
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
 
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N = INT()
L = [LIST() for i in range(N-1)]
color = [0] * N
color[0] = 1
graph = defaultdict(list)
for u, v, w in L:
    graph[u-1].append((v-1, w))
    graph[v-1].append((u-1, w))

q = [0]

while q:
    a = q.pop()
    for node, w in graph[a]:
        if color[node] == 0:
            if w % 2 == 0:
                color[node] = color[a]
            else:
                color[node] = -1 * color[a]
            q.append(node)
for c in color:
    print(1 if c == -1 else 0)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(100**4)

class Edge():
	def __init__(self, v, w):
		self._v = v
		self._w = w
	def v(self):
		return self._v
	def w(self):
		return self._w

def dfs(v, g, colors, color = 0):
	colors[v] = color
	if not len(g[v]):
		return
	for nv in g[v]:
		if colors[nv.v()] != -1:
			continue
		nc = color if nv.w() % 2 == 0 else 1 - color
		dfs(nv.v(), g, colors, nc)

def resolve():
	n = int(input())
	colors = [-1]*n
	g = [list() for _ in range(n)]
	for _ in range(n-1):
		u, v, w = map(int, input().split())
		g[v-1].append(Edge(u-1, w))
		g[u-1].append(Edge(v-1, w))
	for i in range(n):
		if colors[i] != -1:
			continue
		dfs(i, g, colors)
	for c in colors:
		print(c)
resolve()