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
input = sys.stdin.readline
def ii(): return int(input())
def mi(): return map(int, input().rstrip().split())
def lmi(): return list(map(int, input().rstrip().split()))
def li(): return list(input().rstrip())
# template

# BEGIN CUT HERE
from queue import Queue
def bfs(field, sy, sx, wall, dir):
    h = len(field)
    w = len(field[0])
    dp = [[-1 for _j in range(w)] for _i in range(h)]
    q = Queue()

    dp[sy][sx] = 0
    q.put((sy, sx))
    
    dy = [1, -1, 0, 0, 1, 1, -1, -1]
    dx = [0, 0, 1, -1, 1, -1, 1, -1]
    def isin(x,y): return 0 <= y and y < h and 0 <= x and x < w
    
    while not q.empty():
        y, x = q.get()
        for k in range(dir):
            ny,nx = y+dy[k],x+dx[k]
            if not isin(nx, ny) or field[ny][nx] == wall:
                continue
            elif dp[ny][nx] != -1:
                continue
            dp[ny][nx] = dp[y][x] + 1
            q.put((ny,nx))
        
    return dp
    
# END CUT HERE

def ABC088_D():
    h, w = mi()
    s = [['' for _j in range(w)] for _i in range(h)]
    for i in range(h):
        s[i] = li()
    dp = bfs(s, 0, 0, '#', 4)
    if dp[h - 1][w - 1] < 0:
        print(-1)
    else:
        cnt = 0
        for i in range(h):
            for j in range(w):
                cnt += s[i][j] == '.'
        print(cnt - (dp[h - 1][w - 1] + 1)) # 0-indexed
# verified on 2019/06/13
# Python3:29ms https://atcoder.jp/contests/abc088/submissions/5898220
# Pypy3:239ms https://atcoder.jp/contests/abc088/submissions/5898207
# https://atcoder.jp/contests/abc088/tasks/abc088_d

def ATC002_A():
    R, C = mi()
    sy, sx = mi()
    gy, gx = mi()
    s = [['' for _j in range(C)] for _i in range(R)]
    for i in range(R):
        s[i] = li()
    dp = bfs(s, sy-1, sx-1, '#', 4) # 0-indexed
    print(dp[gy-1][gx-1]) # 0-indexed

# グリッドでないbfs
def ABC126_D():
    N= ii()
    G = [[] for i in range(N)]
    for i in range(N-1):
        a, b, w = mi()
        a -= 1
        b -= 1
        G[a].append((b,w))
        G[b].append((a,w))
    dist = [-1 for _ in range(N)]
    que = Queue()
    for v in range(N):
        if dist[v] != -1:
            # v が探索済ならスルー
            continue
        dist[v] = 0
        que.put(v)
        while not que.empty():
            v = que.get()
            for nv,nw in G[v]:
                if dist[nv] == -1:
                    dist[nv] = dist[v] + nw
                    que.put(nv)
    for i in dist:
        if i % 2 == 0:
            print(0)
        else:
            print(1)
# verified on 2019/06/28
# Python3 https://atcoder.jp/contests/abc126/submissions/6141196


if __name__ == '__main__':
    # ABC088_D()
    # ATC002_A()
    ABC126_D()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
def ii(): return int(input())
def mi(): return map(int, input().rstrip().split())
def lmi(): return list(map(int, input().rstrip().split()))
def li(): return list(input().rstrip())
# template

# BEGIN CUT HERE
from queue import Queue
def bfs(field, sy, sx, wall, dir):
    h = len(field)
    w = len(field[0])
    dp = [[-1 for _j in range(w)] for _i in range(h)]
    q = Queue()

    dp[sy][sx] = 0
    q.put((sy, sx))
    
    dy = [1, -1, 0, 0, 1, 1, -1, -1]
    dx = [0, 0, 1, -1, 1, -1, 1, -1]
    def isin(x,y): return 0 <= y and y < h and 0 <= x and x < w
    
    while not q.empty():
        y, x = q.get()
        for k in range(dir):
            ny,nx = y+dy[k],x+dx[k]
            if not isin(nx, ny) or field[ny][nx] == wall:
                continue
            elif dp[ny][nx] != -1:
                continue
            dp[ny][nx] = dp[y][x] + 1
            q.put((ny,nx))
        
    return dp
    
# END CUT HERE

def ABC088_D():
    h, w = mi()
    s = [['' for _j in range(w)] for _i in range(h)]
    for i in range(h):
        s[i] = li()
    dp = bfs(s, 0, 0, '#', 4)
    if dp[h - 1][w - 1] < 0:
        print(-1)
    else:
        cnt = 0
        for i in range(h):
            for j in range(w):
                cnt += s[i][j] == '.'
        print(cnt - (dp[h - 1][w - 1] + 1)) # 0-indexed
# verified on 2019/06/13
# Python3:29ms https://atcoder.jp/contests/abc088/submissions/5898220
# Pypy3:239ms https://atcoder.jp/contests/abc088/submissions/5898207
# https://atcoder.jp/contests/abc088/tasks/abc088_d

def ATC002_A():
    R, C = mi()
    sy, sx = mi()
    gy, gx = mi()
    s = [['' for _j in range(C)] for _i in range(R)]
    for i in range(R):
        s[i] = li()
    dp = bfs(s, sy-1, sx-1, '#', 4) # 0-indexed
    print(dp[gy-1][gx-1]) # 0-indexed

# グリッドでないbfs
def ABC126_D():
    N= ii()
    G = [[] for i in range(N)]
    for i in range(N-1):
        a, b, w = mi()
        a -= 1
        b -= 1
        G[a].append((b,w))
        G[b].append((a,w))
    is_bipartite = True
    dist = [-1 for _ in range(N)]
    que = Queue()
    for v in range(N):
        if dist[v] != -1:
            # v が探索済ならスルー
            continue
        dist[v] = 0
        que.put(v)
        while not que.empty():
            v = que.get()
            for nv,nw in G[v]:
                if dist[nv] == -1:
                    dist[nv] = dist[v] + nw
                    que.put(nv)

    for i in dist:
        if i % 2 == 0:
            print(0)
        else:
            print(1)


if __name__ == '__main__':
    # ABC088_D()
    # ATC002_A()
    ABC126_D()

Submission status: Accepted

Solution code:
N=int(input())
from collections import defaultdict
branch=defaultdict(dict)
for i in range(N-1):
    u,v,w=map(int,input().split())
    u-=1
    v-=1
    branch[u][v]=w
    branch[v][u]=w
dist=[float('inf')]*N
dist[0]=0
check={0}
while len(check)>0:
    now=check.pop()
    for nex,d in branch[now].items():
        if dist[nex]>dist[now]+d:
            dist[nex]=dist[now]+d
            check|={nex}
for i in range(N):
    print(dist[i]%2)

Submission status: Accepted

Solution code:
# using main() makes code faster from the point of view of "access to variables in global name-space"
# def main():

""" convenient functions
# for i, a in enumerate(iterable)
# q, mod = divmod(a, b)
# divmod(x, y) returns the tuple (x//y, x%y)
# manage median(s) using two heapq https://atcoder.jp/contests/abc127/tasks/abc127_f
"""

import sys
sys.setrecursionlimit(10**7)
from itertools import accumulate, combinations, permutations, product # https://docs.python.org/ja/3/library/itertools.html
# accumulate() returns iterator! to get list: list(accumulate())
from math import factorial, ceil, floor
def factorize(n):
    """return the factors of the Arg and count of each factor
    
    Args:
        n (long): number to be resolved into factors
    
    Returns:
        list of tuples: factorize(220) returns [(2, 2), (5, 1), (11, 1)]
    """
    fct = []  # prime factor
    b, e = 2, 0  # base, exponent
    while b * b <= n:
        while n % b == 0:
            n = n // b
            e = e + 1
        if e > 0:
            fct.append((b, e))
        b, e = b + 1, 0
    if n > 1:
        fct.append((n, 1))
    return fct
def combinations_count(n, r):
    """Return the number of selecting r pieces of items from n kinds of items.
    
    Args:
        n (long): number
        r (long): number
    
    Raises:
        Exception: not defined when n or r is negative
    
    Returns:
        long: number
    """
    # TODO: How should I do when n - r is negative?
    if n < 0 or r < 0:
        raise Exception('combinations_count(n, r) not defined when n or r is negative')
    if n - r < r: r = n - r
    if r < 0: return 0
    if r == 0: return 1
    if r == 1: return n
    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]
    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot
    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])
    return result
def combinations_with_replacement_count(n, r):
    """Return the number of selecting r pieces of items from n kinds of items allowing individual elements to be repeated more than once.
    
    Args:
        n (long): number
        r (long): number
    
    Raises:
        Exception: not defined when n or r is negative
    
    Returns:
        long: number
    """
    if n < 0 or r < 0:
        raise Exception('combinations_with_replacement_count(n, r) not defined when n or r is negative')
    elif n == 0:
        return 1
    else:
        return combinations_count(n + r - 1, r)
from bisect import bisect_left, bisect_right
from collections import deque, Counter, defaultdict # https://docs.python.org/ja/3/library/collections.html#collections.deque
from heapq import heapify, heappop, heappush, heappushpop, heapreplace,nlargest,nsmallest # https://docs.python.org/ja/3/library/heapq.html
from copy import deepcopy, copy # https://docs.python.org/ja/3/library/copy.html
from operator import itemgetter
# ex1: List.sort(key=itemgetter(1))
# ex2: sorted(tuples, key=itemgetter(1,2))
from functools import reduce
def chmin(x, y):
    """change minimum
    if x > y, x = y and return (x, True).
    convenient when solving problems of dp[i]
    
    Args:
        x (long): current minimum value
        y (long): potential minimum value
    
    Returns:
        (x, bool): (x, True) when updated, else (x, False)
    """
    if x > y:
        x = y
        return (x, True)
    else:
        return (x, False)
def chmax(x, y):
    """change maximum
    if x < y, x = y and return (x, True).
    convenient when solving problems of dp[i]
    
    Args:
        x (long): current maximum value
        y (long): potential maximum value
    
    Returns:
        (x, bool): (x, True) when updated, else (x, False)
    """
    if x < y:
        x = y
        return (x, True)
    else:
        return (x, False)

from fractions import gcd # Deprecated since version 3.5: Use math.gcd() instead.
def gcds(numbers):
    return reduce(gcd, numbers)
def lcm(x, y):
    return (x * y) // gcd(x, y)
def lcms(numbers):
    return reduce(lcm, numbers, 1)

# first create factorial_list
# fac_list = mod_factorial_list(n)
INF = 10 ** 18
MOD = 10 ** 9 + 7
modpow = lambda a, n, p = MOD: pow(a, n, p) # Recursive function in python is slow!
def modinv(a, p = MOD):
    # evaluate reciprocal using Fermat's little theorem:
    # a**(p-1) is identical to 1 (mod p) when a and p is coprime
    return modpow(a, p-2, p)
def modinv_list(n, p = MOD):
    if n <= 1:
        return [0,1][:n+1]
    else:
        inv_t = [0,1]
        for i in range(2, n+1):
            inv_t += [inv_t[p % i] * (p - int(p / i)) % p]
        return inv_t
def modfactorial_list(n, p = MOD):
    if n == 0:
        return [1]
    else:
        l = [0] * (n+1)
        tmp = 1
        for i in range(1, n+1):
            tmp = tmp * i % p
            l[i] = tmp
        return l
def modcomb(n, k, fac_list = [], p = MOD):
    # fac_list = modfactorial_list(100)
    # print(modcomb(100, 5, modfactorial_list(100)))
    from math import factorial
    if n < 0 or k < 0 or n < k: return 0
    if n == 0 or k == 0: return 1
    if len(fac_list) <= n:
        a = factorial(n) % p
        b = factorial(k) % p
        c = factorial(n-k) % p
    else:
        a = fac_list[n]
        b = fac_list[k]
        c = fac_list[n-k]
    return (a * modpow(b, p-2, p) * modpow(c, p-2, p)) % p
def modadd(a, b, p = MOD):
    return (a + b) % MOD
def modsub(a, b, p = MOD):
    return (a - b) % p
def modmul(a, b, p = MOD):
    return ((a % p) * (b % p)) % p
def moddiv(a, b, p = MOD):
    return modmul(a, modpow(b, p-2, p))

""" initialize variables and set inputs
# initialize variables
    # to initialize list, use [0] * n
    # to initialize two dimentional array, use [[0] * N for _ in range(N)]
# set inputs
    # open(0).read() is a convenient method:
    # ex) n, m, *x = map(int, open(0).read().split())
    #     min(x[::2]) - max(x[1::2])
    # ex2) *x, = map(int, open(0).read().split())
    #     don't forget to add comma after *x if only one variable is used
# preprocessing
    # transpose = [x for x in zip(*data)]
    # ex) [[1, 2, 3], [4, 5, 6], [7, 8, 9]] => [(1, 4, 7), (2, 5, 8), (3, 6, 9)]
    # flat = [flatten for inner in data for flatten in inner]
    # ex) [[1, 2, 3], [4, 5, 6], [7, 8, 9]] => [1, 2, 3, 4, 5, 6, 7, 8, 9]
# calculate and output
    # output pattern
    # ex1) print(*l) => when l = [2, 5, 6], printed 2 5 6
"""

# functions used
r = lambda: sys.stdin.readline().strip()
r_int = lambda: int(r())
R = lambda: list(map(int, r().split()))
Rfloat = lambda: list(map(float, r().split()))
Rtuple = lambda: tuple(map(int, r().split()))
Rmap = lambda: map(int, r().split())

""" how to treat input
# single int: int(r())
# single string: r()
# single float: float(r())
# line int: R()
# line string: r().split()
# line (str, int, int): [j if i == 0 else int(j) for i, j in enumerate(r().split())]
# lines int: [R() for _ in range(n)]
"""

# main
N = int(r())
Dic = defaultdict(list)
ans = [-1] * N
task = []
for _ in range(N-1):
    u, v, w = R()
    Dic[u-1].append((v-1,w))
    Dic[v-1].append((u-1,w))

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

while task:
    s = task.pop()
    zeroone = ans[s]
    for (v, w) in Dic[s]:
        if ans[v] >= 0:
            continue
        elif w % 2 == 0:
            ans[v] = zeroone
        else:
            ans[v] = abs(zeroone-1)
        task.append(v)

for i in ans:
    print(i)

"""memo: how to use defaultdict of list
# initialize
Dic = defaultdict(list)
# append
Dic[x].append(y)
# for
for k, v in Dic.items():
"""

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

Submission status: Accepted

Solution code:
from collections import Counter
from collections import deque
from functools import reduce
from pprint import pprint
import bisect
import copy
import fractions
import itertools
import math
import queue
import random
import sys
import time
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def MI(): return map(int, sys.stdin.readline().split())
def II(): return int(sys.stdin.readline())
def IS(): return input()
def C(x): return Counter(x)
def GCD_LIST(numbers): return reduce(fractions.gcd, numbers)
def LCM_LIST(numbers): return reduce(LCM, numbers)
def LCM(m, n): return (m * n // fractions.gcd(m, n))


def f(v, c):
    for next_v, w in graph[v]:
        if seen[next_v] == -1:
            seen[next_v] = (c + w) & 1
            f(next_v, c + w)


n = II()
node = [LI() for _ in range(n - 1)]
graph = [[] for _ in range(n)]
seen = [-1] * n
for u, v, w in node:
    graph[u - 1].append((v - 1, w))
    graph[v - 1].append((u - 1, w))

seen[0] = 0
f(0, 0)
for i in seen:
    print(i)

Submission status: Accepted

Solution code:
from collections import deque
import sys

sys.setrecursionlimit(50000000)


ans = {1: 1}


def dfs(tree, nodes):
    for node in nodes:
        nexts = tree[node]
        for next, l in nexts.items():
            if l % 2 == 0:
                ans[next] = ans[node]
            else:
                ans[next] = 1 - ans[node]
            tree[next].pop(node)

        dfs(tree, nexts)

    return 0


if __name__ == "__main__":
    tree = {}
    N = int(input())
    if N == 1:
        u, v, w = list(map(int, input().split(" ")))
        if w % 2 == 1:
            print(1)
            print(0)
        else:
            print(0)
            print(0)
    else:
        for i in range(N - 1):
            u, v, w = list(map(int, input().split(" ")))

            if u not in tree:
                tree[u] = {}
            tree[u][v] = w

            if v not in tree:
                tree[v] = {}
            tree[v][u] = w
        dfs(tree, [1])
        for i in range(1, N + 1):
            print(ans[i])

Submission status: Accepted

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

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

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

H = deque()
H.append(a)
visited = [-1]*(N)
visited[a] = 0

while H:
  x = H.popleft()
  for y, z in A[x]:
    if visited[y] == -1:
      visited[y] = (visited[x] + z%2)%2
      H.append(y)
for i in visited:
  print(i)

Submission status: Accepted

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


def dfs(v, cur):
    color[v] = cur
    
    for next_v in Graph[v]:
        if color[next_v[0]] != -1:
            continue
        elif next_v[1] % 2 == 0:
            dfs(next_v[0], cur)
        else:
            dfs(next_v[0], 1-cur)


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

for i in uvw:
    Graph[i[0]-1].append([i[1]-1, i[2]])
    Graph[i[1]-1].append([i[0]-1, i[2]])

dfs(0, 0)

for i in color:
    print(i)

Submission status: Accepted

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

for i in range(N-1):
    inf = input().split()
    u = int(inf[0])
    v = int(inf[1])
    w = int(inf[2])
    dic[u-1] += [(v-1,w)]
    dic[v-1] += [(u-1,w)]


dist = [-1]*N
stack = []
dist[0] = 0

stack += [0]

while stack:
    u = stack.pop(-1)
    for i, w in dic[u]:
        if dist[i]==-1:
            dist[i] = dist[u]+w
            stack.append(i)

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

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.readline
N = int(input().strip())

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

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

is_visit = [False] * (N+1)
search_list = [(1, 0)]

while len(search_list) > 0:
    now, color = search_list.pop()
    ans[now] = color
    is_visit[now] = True

    for node, distance in path[now]:
        if not is_visit[node]:
            search_list.append((node, (distance+color) % 2))
for color in ans[1:]:
    print(color)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000)
 
N = int(input())
X = [[] for _ in range(N)]
for _ in range(N-1):
    u, v, w = map(int, input().split())
    X[u-1].append((v-1, w%2))
    X[v-1].append((u-1, w%2))
 

D = [-1] * N
def calc(i, c):
    D[i] = c
    for j, w in X[i]:
        if D[j] < 0:
            calc(j, D[i]^w)
 
calc(0, 0)
for d in D:
    print(d)

Submission status: Accepted

Solution code:
N = int(input())
G = [dict() for i in range(N)]
# グラフの表し方
for i in range(N-1):
    u,v,w = map(int,input().split())
    G[u-1][v-1] = w
    G[v-1][u-1] = w
color = [-1 for i in range(N)]
dist=[-1 for i in range(N)]
# 頂点1を根に根付き木を考える。頂点１からの距離
dist[0]=0
q=[0]
while(len(q)>0):
    r=q.pop()
    for p in G[r]:
        if dist[p]!=-1:
            continue
        dist[p]=dist[r]+G[r][p]
        q.append(p)

for i in range(N):
    print(dist[i]%2)

Submission status: Accepted

Solution code:
N = int(input())

dic = [[] for i in range(N)]
for i in range(N-1):
  inf = input().split()
  u = int(inf[0])
  v = int(inf[1])
  w = int(inf[2])
  dic[u-1] +=[(v-1, w)]
  dic[v-1] +=[(u-1, w)]

dist = [-1]*N
stack = []
stack.append(0)
dist[0] = 0

while stack:
  label = stack.pop(-1)
  for i, c in dic[label]:
    if dist[i] == -1:
      dist[i] = dist[label]+c
      stack += [i]

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**5+1)
N = int(input())
es = [[] for i in range(N+1)]
for i in range(N-1):
    u, v, w = map(int, input().split())
    es[u].append([v,w])
    es[v].append([u,w])
dfs_map = [1 for i in range(N+1)]
col = [None] * (N+1)
def dfs(v, c):
    col[v] = c
    for e in es[v]:
        if dfs_map[e[0]]:
            dfs_map[e[0]] = 0
            if e[1] % 2:
                dfs(e[0], c^1)
            else:
                dfs(e[0], c)
dfs_map[1] = 0
dfs(1, 0)
for i in range(1, N+1):
    print(col[i])

Submission status: Accepted

Solution code:
n = int(input())
dic = [[] for i in range(n)] 
for i in range(n-1):
    inf = input().split()
    u = int(inf[0])
    v = int(inf[1])
    w = int(inf[2])
    dic[u-1] += [(v-1, w)]
    dic[v-1] += [(u-1, w)] 
    
dist = [-1]*n
stack = []
stack.append(0)
dist[0] = 0 

while stack:
    label = stack.pop(-1) 
    #print(label, dic[label])
    for i, c in dic[label]: 
        if dist[i] == -1: 
            dist[i] = dist[label]+c
            stack += [i]
            
print(0)
for i in range(1,n):
    if dist[i]%2==0:
        print(0)
    else:
        print(1)

Submission status: Accepted

Solution code:
#!/usr/bin/env python
import bisect
from collections import defaultdict
import math

def main():
    #N = map(int, input().split())
    N = int(input())

    edges = defaultdict(list)
    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))

    colors = [None]*N
    colors[0] = 0
    colored = [(0, 0)]
    while colored:
        new_colored = []
        for n, d in colored:
            nodes = edges[n]
            for m, w in nodes:
                if colors[m] is None:
                    dist = d + w
                    if dist % 2 == 0:
                        colors[m] = 0
                    else:
                        colors[m] = 1
                    new_colored.append((m, dist))
        colored = new_colored

    for n in range(N):
        print(colors[n])

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N = int(input())

dic = [[] for i in range(N)]
for i in range(N-1):
  inf = input().split()
  u = int(inf[0])
  v = int(inf[1])
  w = int(inf[2])
  dic[u-1] +=[(v-1, w)]
  dic[v-1] +=[(u-1, w)]

dist = [-1]*N
stack = []
stack.append(0)
dist[0] = 0

while stack:
  label = stack.pop(-1)
  for i, c in dic[label]:
    if dist[i] == -1:
      dist[i] = dist[label]+c
      stack += [i]

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

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from collections import deque
N = int(input())
table = [[] for i in range(N)]
for i in range(N-1):
  u, v, w = map(int, input().split())
  u, v = u-1, v-1
  table[u].append((v, w))
  table[v].append((u, w))
H = deque()
H.append(0)
visit = [-1]*N
visit[0] = 0
while H:
  x = H.popleft()
  for y, w in table[x]:
    if visit[y] == -1:
      visit[y] = (visit[x]+w)%2
      H.append(y)
for i in range(N):
  print(visit[i])

Submission status: Accepted

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

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

dist = [None]*N
dist[0] = 0
comp = [0]*N
next_ptr = [0]
for ptr in next_ptr:
    comp[ptr] = 1
    edges = tree[ptr]
    for edge in edges:
        if comp[edge[0]] == 0:
            dist[edge[0]] = dist[ptr] + edge[1]
            next_ptr.append(edge[0])

for item in dist:
    print(item%2)

Submission status: Accepted

Solution code:
import sys

N=int(input())
sys.setrecursionlimit(100000)
u = [0]*(N-1)
v = [0]*(N-1)
w = [0]*(N-1)
for i in range(N-1):
    u[i], v[i], w[i] = map(int, input().split())
    u[i] -= 1
    v[i] -= 1

class Path:
    def __init__(self, next_node, length, num):
        self.next=next_node
        self.len=length
        self.num=num

class Node:
    def __init__(self, index):
        self.index = index
        self.paths = []

    def append(self, next_node, length, num):
        self.paths.append(Path(next_node, length, num))

nodes = [Node(i) for i in range(N)]
for i in range(N-1):
    nodes[u[i]].append(v[i], w[i], i)
    nodes[v[i]].append(u[i], w[i], i)

past_paths = [0]*(N-1)
paints = [-1]*N

def rec(pos, color):
    if paints[pos] == -1:
        paints[pos] = color
    for path in nodes[pos].paths:
        # まだ通ってない道を通る
        if past_paths[path.num] == 0:
            past_paths[path.num] = 1
            rec(path.next, (color + path.len) % 2)
        # さっきの道を戻ってくる

rec(0, 0)

for i in paints:
    print(i)

Submission status: Accepted

Solution code:
###template###
import sys
def input(): return sys.stdin.readline().rstrip()
def mi(): return map(int, input().split())
###template###

N = int(input())

adj = [set() for _ in range(N)] #adj[i] = (i_adj, 距離0or1)
for _ in range(N-1):
  u, v, w = mi()
  #0スタートに
  u -= 1
  v -= 1
  adj[u].add((v, w%2))
  adj[v].add((u, w%2))

from collections import deque
q = deque([])

seen = [-1] * N #色を兼ねる。0or1

#とりあえずノード0から探索をスタートすることにする
#0の距離は0としておく
q.append(0)
seen[0] = 0


while q:
  nownode = q.popleft()
  nowcolor = seen[nownode]

  #今のノードから隣接しているものを探索
  for adjidx, w in adj[nownode]:
    if seen[adjidx]==-1:
      q.append(adjidx)
      seen[adjidx]=(nowcolor+w)%2

for color in seen:
  print(color)

Submission status: Accepted

Solution code:
###template###
import sys
def input(): return sys.stdin.readline().rstrip()
def mi(): return map(int, input().split())
###template###
import sys
sys.setrecursionlimit(10000000)

N = int(input())

adj = [set() for _ in range(N)] #adj[i] = (i_adj, 距離0or1)
for _ in range(N-1):
  u, v, w = mi()
  #0スタートに
  u -= 1
  v -= 1
  adj[u].add((v, w%2))
  adj[v].add((u, w%2))

from collections import deque
q = deque([])

seen = [0] * N
bw = [0] * N

#とりあえずノード0から探索をスタートすることにする
#0の距離は0としておく
q.append(0)
bw[0] = 0 #必要無いが、分かりやすくするために
seen[0] = 1


def solve(): #前のノードまでの色（0or1）を引き継ぐ
  try: nownode = q.popleft()
  except: return
  nowcolor = bw[nownode]

  #今のノードから隣接しているものを探索
  for adjidx, w in adj[nownode]:
    if seen[adjidx]!=1:
      q.append(adjidx)
      seen[adjidx]=1
      bw[adjidx] = (nowcolor+w)%2

  solve()

solve()

for color in bw:
  print(color)

Submission status: Accepted

Solution code:
from collections import deque


n = int(input())
es = [[] for _ in range(n)]
for _ in range(n-1):
    u, v, w = map(int, input().split())
    u -= 1
    v -= 1
    es[u].append((v, w))
    es[v].append((u, w))
clr = [None]*n
clr[0] = 0
dq = deque()
dq.append(0)
while dq:
    v = dq.popleft()
    for nv, w in es[v]:
        if clr[nv] is not None:
            continue
        clr[nv] = (clr[v] + w)%2
        dq.append(nv)
print(*clr, sep='\n')

Submission status: Accepted

Solution code:
#ABC126D-EvenRelation.py

import sys
import collections
import numpy as np

def main():
    N = int(sys.stdin.readline())
    UVW = [[] for _ in range(N)]
    for _ in range(N-1):
        u, v, w = list(map(int, sys.stdin.readline().split()))
        UVW[u-1].append([v,w])
        UVW[v-1].append([u,w])
    answerList = [0] + [-1]*(N-1)
    edge = collections.deque([(1,0)])

    while edge:
        u, w1 = edge.pop()
        for v, w2 in UVW[u-1]:
            if answerList[v-1] == -1:
                answerList[v-1] = (w1 + w2) % 2
                edge.append((v,w1+w2))

    for answer in answerList:
        print(answer)



if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import deque

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

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

clr = [None] * N
clr[0] = 0

dq = deque()
dq.append(0)

while dq:
    v = dq.popleft()
    for nv, w in es[v]:
        if clr[nv] is not None:
            continue
        clr[nv] = (clr[v] + w) % 2
        dq.append(nv)
print(*clr, sep='\n')

Submission status: Accepted

Solution code:
N = int(input())
color = [ [] for i in range(N)]

def updateColor( color, i, from_i, c):
    if len(color[i]) == 1 and color[i][0][0] == from_i:
        color[i] = c
    else:
        for l in color[i]:
            if l[0] != from_i:
                if l[1] == 'Same':
                    updateColor( color, l[0], i, c)
                else:
                    updateColor( color, l[0], i, 1-c)
        color[i] = c
                    

for i in range(N-1):
    u, v, w = map(int, input().split())
    u -= 1
    v -= 1
    if i == 0:
        if w%2 == 0:
            color[u] = color[v] = 0
        else:
            color[u] = 0
            color[v] = 1
    else:
        if color[u] in (0,1):
            if w%2 == 0:
                temp = color[u]
            else:
                temp = 1-color[u]

            for l in color[v]:
                if l[1] == "Same":
                    updateColor( color, l[0], v, temp )
                else:
                    updateColor( color, l[0], v, 1-temp )
            color[v] = temp

        elif color[v] in (0,1):
            if w%2 == 0:
                temp = color[v]
            else:
                temp = 1-color[v]
                
            for l in color[u]:
                if l[1] == "Same":
                    updateColor( color, l[0], u, temp )
                else:
                    updateColor( color, l[0], u, 1-temp )
            color[u] = temp

        else:
            if w%2 == 0:
                color[u].append([v, "Same"])
                color[v].append([u, "Same"])
            else:
                color[u].append([v, "Diff"])
                color[v].append([u, "Diff"])
                    
for c in color:
    print(c)

Submission status: Accepted

Solution code:
#5888164
N = int(input())
edge = [[] for _ in range(N)]
ans = [-1 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))

stack = [(e,0) for e in edge[0]]
ans[0] = 0

while len(stack) > 0:
    e,c = stack.pop()
    n,w = e[0],e[1]
    if ans[n] >= 0:
        continue
    ans[n] = (c + w) % 2
    stack += [(e,ans[n]) for e in edge[n]]

for a in ans:
    print(a)