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
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def II(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def SI(): return input()
YN = lambda b: print('YES') if b else print('NO')
yn = lambda b: print('Yes') if b else print('No')


N = II()
u_li = []
v_li = []
w_li = []
for i in range(N-1):
    u, v, w = LI()
    u_li.append(u)
    v_li.append(v)
    w_li.append(w)

# 連結リストを作成。計算量削減のために、距離の情報も持つ。
max_node = max(max(u_li), max(v_li))
neighbor = [[] for i in range(max_node+1)]
for i in range(N-1):
    neighbor[u_li[i]].append((v_li[i], w_li[i]))
    neighbor[v_li[i]].append((u_li[i], w_li[i]))

# 深さ優先探索をしつつ色を塗っていく。
from collections import deque
def depth_first(neighbor, start):
    visited, stack = [False]*(N+1), deque()
    stack.append(start)
    result = [None, 0] + [None]*(N-1)
    while len(stack) > 0:
        next_node = stack.pop()
        if visited[next_node]: continue
        visited[next_node] = True
        for nei in neighbor[next_node]:
            if result[nei[0]] is not None: continue
            if nei[1]%2 == 0:
                result[nei[0]] = result[next_node]
            else:
                result[nei[0]] = (result[next_node]+1)%2
            stack.append(nei[0])
    return result

colors = depth_first(neighbor, 1)

for ans in colors[1:]:
    print(ans)

Submission status: Accepted

Solution code:
from collections import deque

N = int(input())

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

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

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

q = deque([0])

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

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

Submission status: Accepted

Solution code:
from collections import deque

N = int(input())

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

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

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

q = deque()
q.append(0)

while q :
    a = q.popleft()
    
    for b,w in L[a] :
        if ans[b] == -1 :
            ans[b] = (ans[a] + w) % 2
            q.append(b)

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

Submission status: Accepted

Solution code:
def main():
    N = int(input())
    distance = [-1 for _ in range(N)]
    edges = [[] for _ in range(N)]
    nodes = [0]
    for _ 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))
    distance[0] = 0
    while any(d < 0 for d in distance):
        n = nodes.pop(0)
        for edge in edges[n]:
            m, d = edge[0], edge[1]
            if distance[m] == -1:
                distance[m] = distance[n] + d
                nodes.append(m)
    for d in distance:
        print(0 if d % 2 == 0 else 1)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import defaultdict, deque
def inpl(): return list(map(int, input().split()))

N = int(input())
D = defaultdict(list)

for _ in range(N-1):
    u, v, w = inpl()
    D[u].append((v, w))
    D[v].append((u, w))

color = [-1]*(N+1)
Q = deque()
color[1] = 0
Q.append(1)

while Q:
    u = Q.pop()
    c = color[u]
    for v, w in D[u]:
        if color[v] == -1:
            if w % 2:
                color[v] = int(not c)
            else:
                color[v] = c
            Q.append(v)

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

Submission status: Accepted

Solution code:
n=int(input());e=[[]for _ in[0]*-~n];q=[(1,0)];f=[-1]*n
for _ in[0]*~-n:v,w,c=map(int,input().split());e[v]+=(w,c),;e[w]+=(v,c),
while q:
 v,c=q.pop();f[v-1]=c%2
 for w,d in e[v]:
  if f[w-1]<0:q+=(w,c+d),
print(*f)

Submission status: Accepted

Solution code:
n=int(input());e=[[]for _ in[0]*-~n];q=[1];f=[0]+[-1]*~-n
for _ in[0]*~-n:v,w,c=map(int,input().split());e[v]+=(w,c),;e[w]+=(v,c),
while q:
 v=q.pop()
 for w,c in e[v]:
  if f[w-1]<0:f[w-1]=(f[v-1]+c)%2;q+=w,
print(*f)

Submission status: Accepted

Solution code:
n,*t=map(int,open(0).read().split());e=[[]for _ in[0]*n];q=[0];f=[0]+[-1]*~-n
for v,w,c in zip(t[::3],t[1::3],t[2::3]):e[v-1]+=(w-1,c),;e[w-1]+=(v-1,c),
while q:
 v=q.pop()
 for w,c in e[v]:
  if f[w]<0:f[w]=(c+f[v])%2;q+=w,
print(*f)

Submission status: Accepted

Solution code:
n,*t=map(int,open(0).read().split())
e=[[]for _ in[0]*n]
for v,w,c in zip(t[::3],t[1::3],t[2::3]):
  e[v-1]+=(w-1,c),
  e[w-1]+=(v-1,c),
q=[0]
f=[0]+[-1]*~-n
while q:
  v=q.pop()
  for w,c in e[v]:
    if-1<f[w]:continue
    f[w]=(c+f[v])%2
    q+=w,
print(*f)

Submission status: Accepted

Solution code:
n,*t=map(int,open(0).read().split())
e=[[]for _ in range(n)]
for v,w,c in zip(t[::3],t[1::3],t[2::3]):
  e[v-1]+=(w-1,c),
  e[w-1]+=(v-1,c),
q=[(0,0)]
f=[0]+[-1]*~-n
while q:
  v,c=q.pop()
  for w,d in e[v]:
    if-1<f[w]:continue
    d=(c+d)%2
    f[w]=d
    q+=(w,d),
print(*f)

Submission status: Accepted

Solution code:
n,*t=map(int,open(0).read().split())
e=[[]for _ in range(n)]
for v,w,c in zip(t[::3],t[1::3],t[2::3]):
  e[v-1].append((w-1,c))
  e[w-1].append((v-1,c))
q=[(0,0)]
f=[0]+[-1]*~-n
while q:
  v,c=q.pop()
  for w,d in e[v]:
    if-1<f[w]:continue
    d=(c+d)%2
    f[w]=d
    q+=[(w,d)]
print(*f)

Submission status: Accepted

Solution code:
from collections import*
n,*t=map(int,open(0).read().split())
e=[[]for _ in range(n)]
for v,w,c in zip(t[::3],t[1::3],t[2::3]):
  e[v-1].append((w-1,c))
  e[w-1].append((v-1,c))
q=deque([(0,0)])
f=[0]+[-1]*~-n
while q:
  v,c=q.pop()
  for w,d in e[v]:
    if-1<f[w]:continue
    d=(c+d)%2
    f[w]=d
    q.append((w,d))
print(*f,sep='\n')

Submission status: Accepted

Solution code:
from collections import*
n,*t=map(int,open(0).read().split())
e=[[]for _ in range(n)]
for v,w,c in zip(t[::3],t[1::3],t[2::3]):
  e[v-1].append((w-1,c))
  e[w-1].append((v-1,c))
q=deque([(0,0)])
f=[0]+[-1]*~-n
while q:
  v,c=q.pop()
  for w,d in e[v]:
    if-1<f[w]:continue
    d=(c+d)%2
    f[w]=d
    q.append((w,d))
print(*f)

Submission status: Accepted

Solution code:
from collections import deque

N = int(input())
edges = {i: [] for i in range(N)}
for _ in range(N-1):
    x, y, z = map(int, input().split())
    edges[x-1].append((y-1, z%2))
    edges[y-1].append((x-1, z%2))
color = [None]*N

q = deque([(0, 0)])
while q:
    v, c = q.popleft()
    color[v] = c
    for u, w in edges[v]:
        if color[u] is None:
            if w == 0:
                q.append((u, c))
            else:
                q.append((u, c^1))
print(*color, sep='\n')

Submission status: Accepted

Solution code:
from collections import deque

N = int(input())
vw = [[] for _ in range(N)]
for i in range(N-1):
    a, b, w = map(int, input().split())
    vw[a-1].append((b-1, w))
    vw[b-1].append((a-1, w))
ans = [-1] * N
q = deque([(0, 0)])
while q:
    a, w = q.popleft()
    ans[a] = w % 2
    for b, c in vw[a]:
        if ans[b] == -1:
            q.append((b, w + c))
print("\n".join(map(str, ans)))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(100000)

def func(num,pr):
  global l,ans

  if len(l[num])!=0:
    for z in l[num]:
      if z[0]==pr:
        continue

      if pr==-1:
        ans[z[0]]=z[1]
      else:
        ans[z[0]]=ans[num]+z[1]
      func(z[0],num)

N=int(input())
l=[ [] for z in range(N)]
ans=[0]*N


for z in range(N-1):
  u,v,w=list(map(int,input().split(" ")))
  l[u-1].append((v-1,w))
  l[v-1].append((u-1,w))

func(0,-1)

#print(l)
#print(ans)


for z in ans:
  if z%2==0:
    print(1)
  else:
    print(0)

Submission status: Accepted

Solution code:
def main():
    n = int(input().rstrip())
    from collections import defaultdict
    
    edges = defaultdict(dict)
    for i in range(n - 1):
        a, b, distance = [int(x) for x in input().rstrip().split(" ")]
        edges[a][b] = distance
        edges[b][a] = distance

    passed = {1: 0}

    distances = {1: 0}
    candidates = [(1, 0)]
    total_distance = 0
    while candidates:
        a, total_distance = candidates.pop(0)
        for b, distance in edges[a].items():
            if not b in passed:
                distances[b] = total_distance + distance
                passed[b] = 1
                candidates.append((b, total_distance + distance))
    for number in range(1, n + 1):
        print(distances[number] % 2)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n = int(input())
links = [[] for _ in range(n + 1)]
for _ in range(n - 1):
    u, v, w = map(int, input().split())
    links[u].append((v, w))
    links[v].append((u, w))
ans = [-1] * (n + 1)
q = [(1, 0, 0)]
while q:
    v, d, p = q.pop()
    ans[v] = d
    for u, w in links[v]:
        if u == p:
            continue
        q.append((u, d + w, v))
print('\n'.join(map(lambda x: str(x % 2), ans[1:])))

Submission status: Accepted

Solution code:
n = int(input())
x,ans,q = [[] for i in range(n+1)],[-1]*(n+1),[]
for i in range(n-1):
    u,v,w = (int(i) for i in input().split())
    x[u].append((v,w%2))
    x[v].append((u,w%2))
for i,j in x[1]: q.append((i,1,j))
ans[1] = 0
while q:
    i,p,d = q.pop()
    ans[i] = abs(d-ans[p])
    for j,k in x[i]:
        if ans[j]==-1: q.append((j,i,k))
for i in ans[1:]: print(i)

Submission status: Accepted

Solution code:
n = int(input())
v = [list(map(int,input().split())) for _ in range(n-1)]
g = {}
for a,b,w in v:
    if a not in g:
        g[a] = []
    if b not in g:
        g[b] = []
    g[a].append([b,w])
    g[b].append([a,w])
from collections import deque
queue = deque([[1,0]])
b = [-1]*n
b[0] = 0
while queue:
    q,d = queue.popleft()
    if d%2==1:
        b[q-1] = 0
    else:
        b[q-1] = 1
    for new_q in g[q]:
        v_,d_ = new_q
        if b[v_-1]==-1:
            queue.appendleft([v_,d+d_])
for i in b:
    print(i)

Submission status: Accepted

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

n = int(input())
uvw = [tuple(int(x) for x in input().split()) for _ in range(n-1)]

c = [-1] * n

r = [[] for _ in range(n)]

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


def f(p):
    count = 0
    for x, w in r[p]:
        if c[x] == -1:
            if w % 2 == 0:
                c[x] = c[p]
                f(x)
            else:
                c[x] = (c[p] + 1) % 2
                f(x)
            count += 1


c[0] = 0
f(0)

for x in c:
    print(x)

Submission status: Accepted

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

n = int(input())
uvw = [tuple(int(x) for x in input().split()) for _ in range(n-1)]

c = [-1] * n

r = [[] for _ in range(n)]

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

def f(p):
    count = 0
    for x, w in r[p]:
        if c[x] == -1:
            if w % 2 == 0:
                c[x] = c[p]
                f(x)
            else:
                c[x] = (c[p] + 1) % 2
                f(x)
            count += 1
    #print(count)

c[0] = 0
f(0)

for x in c:
    print(x)

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())
    # グラフに頂点と距離を追加
    G[u-1].append((v-1,w))
    G[v-1].append((u-1,w))


used = [0] * N
que = deque([0])
ans = [False] * N
while que:
    # print(list(que))
    u = que.popleft()
    for v,w in G[u]:
        if used[v]:
            # すでにチェックされていたら無視
            continue
        else:
            # wが奇数⇨色を分ける
            # wが偶数⇨色をそのまま
            if w%2 == 0:
                ans[v] = ans[u]
            else:
                ans[v] = not ans[u]
            # print(w,ans[u],ans[v])
            que.append(v)
            used[u] = True
for a in ans:
    print(int(a))

Submission status: Accepted

Solution code:
from collections import deque


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

X = [[] for _ in range(N)]
for v in V:
    X[v[0]-1].append((v[0],v[1],v[2]))
    X[v[1]-1].append((v[1],v[0],v[2]))
# print(X)
color = [-1] * N
color[0] = 0

que = deque()
que.append(1)

while len(que) > 0:
    v = que.popleft()
    for x in X[v-1]:
#         print(x)
        b = x[1]
        dist = x[2]
        color_a = color[v-1]
        if  color[b-1] != -1:
            continue
        que.append(b)
        if dist % 2 == 0:
            color[b-1] = 0 if color_a == 0 else 1
        else:
            color[b-1] = 0 if color_a == 1 else 1

for c in color:
    print(c)

Submission status: Accepted

Solution code:
import queue

n = int(input())

connect = [ [] for _ in range(n)]
distances = dict()

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

    connect[u].append(v)
    connect[v].append(u)
    distances[(u, v)] = w
    distances[(v, u)] = w

colors = [-1] * n
colors[0] = 0
q = queue.Queue()
q.put(0)

while not q.empty():
    x = q.get()

    for y in connect[x]:
        if colors[y] != -1:
            continue
        colors[y] = (colors[x] + distances[(x, y)]) % 2
        q.put(y)

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

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
import itertools
sys.setrecursionlimit(10**5)
stdin = sys.stdin
bisect_left = bisect.bisect_left
bisect_right = bisect.bisect_right
def LI(): return list(map(int, stdin.readline().split()))
def LF(): return list(map(float, stdin.readline().split()))
def LI_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def II(): return int(stdin.readline())
def IF(): return float(stdin.readline())
def LS(): return list(map(list, stdin.readline().split()))
def S(): return list(stdin.readline().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')

#A
def A():
    n, k = LI()
    s = S()
    s[k-1] = s[k-1].lower()
    print("".join(s))

    return

#B
def B():
    s = S()
    a = int("".join(s[:2]))
    b = int("".join(s[2:]))
    if 0 < a <= 12:
        if 0 < b <= 12:
            print("AMBIGUOUS")
        else:
            print("MMYY")
    elif a == 0:
        if 0 < b <= 12:
            print("YYMM")
        else:
            print("NA")
    else:
        if 0 < b <= 12:
            print("YYMM")
        else:
            print("NA")
    return

#C
def C():
    n, k = LI()
    ans = 0
    if k == 1:
        print(1)
        return
    nibuiti = [None for i in range(int(math.log2(k) + 1))]
    for num in range(int(math.log2(k) + 1)):
        if num == 0:
            nibuiti[num] = 1 / 2
            continue
        nibuiti[num] = nibuiti[num-1]/2
        
    for i in range(1, n + 1):
        if i >= k:
            ans += 1
            continue
        b = nibuiti[int(math.log2((k - 1) // i))]
        ans += b
    print(ans/n)
    return

#D
def D():
    n = II()
    color = [0 for i in range(n)]
    edge = [[] for i in range(n)]
    for i in range(n - 1):
        v, u, w = LI_()
        edge[v].append((u,w+1))
        edge[u].append((v,w+1))
    check = [True for i in range(n)]
    for i in range(n):
        q = deque()
        q.append(i)
        
        while q:
            a = q.pop()
            if check:
                check[a] = False
                for k,w in edge[a]:
                    if check[k]:
                        q.append(k)
                        if w % 2:
                            color[k] = color[a] ^ 1
                        else:
                            color[k] = color[a]
    for c in color:
        print(c)
    return

#E
def E():
    return

#F
def F():
    return

#G
def G():
    return

#H
def H():
    return

#Solve
if __name__ == '__main__':
    D()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)
n=int(input())
G=[[]for i in range(n+1)]
for i in range(n-1):
    a, b, c = map(int,input().split())
    G[a] += (b,c),
    G[b] += (a,c),
    
d = [0]*(n+1) #1から各点への距離
def f(v,p,u): #v:今見ているとこ p:一つ前に見たとこ u:1からの距離
    d[v] = u
    for t, c in G[v]:
        if p != t:
            f(t,v,u+c)
f(1,0,0)
for i in range(n):
    if d[i+1] % 2 == 0:
        print(1)
    else:
        print(0)

Submission status: Accepted

Solution code:
#!/usr/bin/env python
from math import *

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


colors = [None for i in range(N)]

q = [0]
colors[0]=0
while len(q)!=0:
    u = q.pop()
    for v,w in tonaris[u]:
        tonaris[v].remove((u,w))
        colors[v] = colors[u] ^ w
        q.append(v)

for color in colors:
    print(color)

Submission status: Accepted

Solution code:
N = int(input())

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

path = [[] for _ in range(N+1)]

for u, v, w in uvw :
    path[u].append((v, w))
    path[v].append((u, w))

paint = [0] * (N + 1)

queue = [1]
visited = [False] * (N + 1)

while queue :
    current = queue.pop(0)
    w = paint[current]

    for destination, w_ in path[current] :
        if not visited[destination] :
            paint[destination] = (w + w_) & 1
            queue.append(destination)
            visited[destination] = True

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

Submission status: Accepted

Solution code:
from collections import deque

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

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

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

q = deque()
q.append(0)

while q:
    x = q.popleft()
    for y, w in v[x]:
        if bfs_map[y]:
            if w%2 :
                ans[y] = ans[x] ^ 1
            else:
                ans[y] = ans[x]
            bfs_map[y] = 0
            q.append(y)
    
for i in ans:
    print(i)

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
n = int(input())

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

que.append(1)
color[1]=0


while(len(que)!=0): 
    node = que.pop()
    for next_node,w in tree[node]:
        if color[next_node]==-1:
            # print((color[node]+cost[node][next_node])%2)
            color[next_node]=(color[node]+w)%2
            que.append(next_node)
            # print(color)
for i in range(1,len(color)):
    print(color[i])

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict
import heapq

class Dijkstra():
    def __init__(self):
        self.edges = defaultdict(list)
    
    def add_edge(self, a, b, cost, directed=False):
        self.edges[a].append((b,cost))
        if not directed:
            self.edges[b].append((a,cost))
        
    def delete_edge(self, a, b):
        self.edges[a] = [item for item in self.edges[a] if item[0] != b]
        self.edges[b] = [item for item in self.edges[a] if item[0] != a]

    def Dijkstra_search(self, start=0):
        '''
        Returns min distances to every node from start node(input).
        '''

        # defaultdict to store minimum cost to visit each node
        distances = defaultdict(lambda: float('inf'))
        distances[start] = 0 # start node is zero-cost

        # initialize a priorit queue with heapq
        q = []
        heapq.heappush(q, (0, start))

        # store flags for each node to mark if the node has been visited
        if_visited = defaultdict(bool)

        while q:
            # search from a new node whose cost is known to be minimum among items in queue 
            cost_current, node_current = heapq.heappop(q)
            
            # skip if the node has already been visited
            if if_visited[node_current]:
                continue
            
            else:
                if_visited[node_current] = True

                # visit adjacent nodes
                for node_visiting, cost_visiting in self.edges[node_current]:

                    if if_visited[node_visiting]: # check if already visited
                        continue
                    
                    cost_cumulative = cost_current + cost_visiting

                    if cost_cumulative < distances[node_visiting]: # check if current path is worthy updating
                        distances[node_visiting] = cost_cumulative
                        heapq.heappush(q, (cost_cumulative, node_visiting))

        return distances


input = sys.stdin.readline
N = int(input())
g = Dijkstra()

while True:
    s = input()
    if s == '':
        break
    
    a, b, c = map(int, s.rstrip().split())
    a -= 1
    b -= 1
    g.add_edge(a,b,c)

distance = g.Dijkstra_search()

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
n = int(input())
g = [[] for i in range(n)]
c = [-1 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])


q = [0]
while (len(q) > 0):
    v = q.pop()
    for u, w in g[v]:
        if c[u] != -1:
            continue
        q.append(u)
        c[u] = (c[v] + w) % 2

for v in c:
    print(v)

Submission status: Accepted

Solution code:
import sys


def visit(current, v, dist, color):
    for ele in v[current]:
        if color[ele] != -1:
            continue
        if dist[(ele, current)] % 2 == 0:
            color[ele] = color[current]
        else:
            if color[current] == 0:
                color[ele] = 1
            else:
                color[ele] = 0
        visit(ele, v, dist, color)

def main():
    sys.setrecursionlimit(100100)
    num = int(input())

    v = [[] for i in range(num + 1)]

    dist = {}

    for i in range(1, num):
        a, b, d = map(int, input().split())
        v[a].append(b)
        v[b].append(a)
        dist[(a, b)] = d
        dist[(b, a)] = d

    color = [-1 for i in range(num + 1)]
    color[1] = 0
    visit(1, v, dist, color)

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

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(20000000)

n = int(input())
g = [[] for i in range(n)]
c = [-1 for i in range(n)]

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


def dfs(p, d):
    if c[p] == -1:
        c[p] = d
        for x, w in g[p]:
            dfs(x, d ^ w)


dfs(0, 0)

for i in range(len(c)):
    print(c[i])

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(100100)

n = int(input())
g = [[] for i in range(n)]
c = [-1 for i in range(n)]

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


def dfs(p, d):
    if c[p] == -1:
        c[p] = d
        for x, w in g[p]:
            dfs(x, d ^ w)


dfs(0, 0)

for i in range(len(c)):
    print(c[i])

Submission status: Accepted

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

import sys
sys.setrecursionlimit(100000)

def dfs(graph, color, visit, idx):
    visit[idx] = True
    if len(graph[idx]) == 0:
        return
    for i, w in graph[idx]:
        if visit[i] is True:
            continue
        if w%2 == 0:    # 同色で塗る
            color[i] = color[idx]
        else:   # 異色で塗る
            color[i] = 1 - color[idx]   # 1-cで異色になる
        dfs(graph, color, visit, i)


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

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

color[0] = 0    # 添え字0をcolor0と置く
dfs(graph, color, visit, 0)

for c in color:
    print(c)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(100100)

N=int(input())
G=[[] for i in range(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))
res=[-1]*N
def dfs(v,p,c):
    res[v]=c
    for nv,w in G[v]:
        if res[nv]>=0:
            continue
        dfs(nv,v,(c+w)%2)
        """
        if w&1:
            dfs(nv,v,1-c)
        else:
            dfs(nv,v,c)
        """
dfs(0,-1,0)
for i in res:
    print(i)

Submission status: Accepted

Solution code:
import sys
import math 
ni = lambda: int(ns())
na = lambda: list(map(int, input().split()))
ns = lambda: input()

N=ni()
G=[dict() for i in range(N)]
for i in range(N-1):
    u,v,w=na()
    G[u-1][v-1]=w
    G[v-1][u-1]=w

dist=[-1 for i in range(N)]
color=[0 for i in range(N)]
dist[0]=0
q=[0]
while(len(q)>0):
    r=q.pop()
    for p in G[r]:
        if(dist[p]!=-1):
            continue
        else:
            dist[p]=dist[r]+G[r][p]
            q.append(p)
for i in range(N):
    if(dist[i]%2==0):
        color[i]=1

for ans in color:
    print(ans)

Submission status: Accepted

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

from collections import deque

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

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

que = deque([0])    # 添え字0からアクセス開始
color[0] = 0    # 添え字0をcolor0と置く
while len(que) > 0:
    idx = que.popleft()
    visit[idx] = True
    for i, w in graph[idx]:
        if visit[i] is True:
            continue
        if w%2 == 0:    # 同色で塗る
            color[i] = color[idx]
            que.append(i)
        else:   # 異色で塗る
            color[i] = 1 - color[idx]   # 1-cで異色になる
            que.append(i)

for c in color:
    print(c)

Submission status: Accepted

Solution code:
N=int(input())
G=[[] for i in range(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))
reached=[0]*N
stack=[0]
reached[0]=[1]
res=[-1]*N
res[0]=0
while(stack):
    v=stack.pop()
    for nv,w in G[v]:
        if reached[nv]:
            continue
        if w & 1:
            res[nv]=1-res[v]
        else:
            res[nv]=res[v]
        stack.append(nv)
        reached[nv]=1
for i in res:
    print(i)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(100100)
n=int(input())
route=[[] for i in range(n)]
for i in range(n-1):
	u,v,w=map(int,input().split())
	route[u-1].append((v-1,w))
	route[v-1].append((u-1,w))
ans=[-1]*n
def dfs(p,d):
	ans[p]=d
	for i,j in route[p]:
		if ans[i]<0:dfs(i,(d+j)%2)
dfs(0,0)
for i in range(n):
	print(ans[i])

Submission status: Accepted

Solution code:
from collections import deque

n = int(input())

node = [-1 for _ in range(n)]
que = deque()
neighbors = [[] for _ in range(n)]

for _ in range(n - 1):
    v1, v2, w = map(int, input().split())
    v1, v2 = v1 - 1, v2 - 1
    neighbors[v1].append((v2, w))
    neighbors[v2].append((v1, w))

que.append(0)
node[0] = 0
while len(que) > 0:
    p = que.popleft()
    for neighbor in neighbors[p]:
        v, w = neighbor
        if node[v] == -1:
            if w % 2 == 0:
                node[v] = node[p]
            else:
                if node[p] == 1:
                    node[v] = 0
                else:
                    node[v] = 1
            que.append(v)

for ni in node:
    print(ni)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)
 
*D, = open(0)
n = int(D[0])
 
v = [[] for _ in range(n+1)]
 
dist = {}
 
for i in range(1, n):
    a, b, d = map(int, D[i].split())
    v[a].append(b)
    v[b].append(a)
    dist[(a,b)]=d
    dist[(b,a)]=d
 
def visit(current, v, dist, color):
   
    for it in v[current]:
        if color[it] != None:
            continue
        if dist[(it, current)]%2 == 0:
            color[it] = color[current]
        else:
            color[it] = not color[current]
        visit(it, v, dist, color)
        
color = [None for _ in range(n+1)]
color[1]=True
visit(1, v, dist, color)
 
for i in range(1, n+1):
    if color[i]:
        print('0')
    else:
        print('1')

Submission status: Accepted

Solution code:
import numpy as np

n=int(input())
E=[]
node_l=np.zeros(n)
node_l[0]=1
for i in range(n-1):
    u,v,w=map(int,input().split())
    #print(u,v,w)
    E.append((u,v,w))
#print(E,W)

def bfs(node,l):
    root=[[] for i in range(n)]
    for a,b,c in l:
        root[a-1]+=[(b-1,c)]
        root[b-1]+=[(a-1,c)]
    stack=[]
    stack.append(node-1)
    #print(root)
    dist=[-1]*n
    dist[node-1]=0
    while stack:
        #print(stack)
        buf=stack.pop(-1)
        for v,weight in root[buf]:
            if dist[v]==-1:
                dist[v]=dist[buf]+weight
                stack.append(v)
    return dist

for i in bfs(1,E):
    print(i%2,end='\n')