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
from collections import deque
import bisect
import copy
import heapq
import itertools
import math
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
mod = 10 ** 9 + 7

def read_values(): return map(int, input().split())
def read_index(): return map(lambda x: int(x) - 1, input().split())
def read_list(): return list(read_values())
def read_lists(N): return [read_list() for n in range(N)]


def f(N):
    res = 0
    while N != 0:
        b = format(N, "b").count("1")
        N %= b
        res += 1
    return res


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

    for _ in range(N - 1):
        u, v, w = read_values()
        u -= 1
        v -= 1
        F[u].append((v, w % 2))
        F[v].append((u, w % 2))

    D = [0] * N
    stack = [(0, 0, -1)]

    while stack:
        a, d, p = stack.pop()
        D[a] = d % 2

        for b, w in F[a]:
            if b == p:
                continue
            stack.append((b, (d + w) % 2, a))
    
    for d in D:
        print(d)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# D - Even Relation
from typing import List, Tuple


def main():
    N, *X = map(int, open(0).read().split())
    tree: List[List[Tuple[int, int]]] = [[] for _ in range(N + 1)]
    for u, v, w in zip(*[iter(X)] * 3):
        w %= 2
        tree[u].append((v, w)), tree[v].append((u, w))

    color = [-1] * (N + 1)
    color[1] = 1
    stack = [1]
    while stack:
        u = stack.pop()
        cur = color[u]
        for v, w in tree[u]:
            if color[v] != -1:
                continue
            color[v] = cur ^ w
            stack.append(v)

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


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**9)
def dfs(i):
  if reached[i] == 1:
    return
  reached[i] = 1
  for dic in uv[i]:
    to = dic["to"]
    w = dic["weight"]
    if w % 2 == 0:
      color[to] = color[i]
    else:
      color[to] = int(not color[i])
    dfs(to)

n = int(input())
color = [0]*(n+1)
reached = [0]*(n+1)
uv = [[] * (n+1) for i in range(n+1)]
for i in range(n-1):
  u,v,w = map(int,input().split())
  uv[u].append({"to":v, "weight":w})
  uv[v].append({"to":u, "weight":w})
dfs(1)
for i in color[1:]:
  print(i)

Submission status: Accepted

Solution code:
import sys
from sys import stdin
input = stdin.readline
sys.setrecursionlimit(20000000)
 
 
def main():
  N = int(input())
  G = [[] for _ in range(N+1)]
  for i in range(N-1):
    u, v, w = map(int, input().split())
    G[u].append((v, w))
    G[v].append((u, w))
 
  color = [-1]*(N+1)
  color[1] = 0
  # S = [1]
  # while len(S):
  #   now = S[-1]
  #   for next_, w in G[now]:
  #     if color[next_] != -1:
  #       continue
  #     S.append(next_)
  #     color[next_] = (w % 2) ^ color[now]
  #     break
  #   else:
  #     S.pop()
 
  def dfs(now):
    for next_, w in G[now]:
      if color[next_] == -1:
        color[next_] = (w % 2) ^ color[now]
        dfs(next_)
  dfs(1)
 
  for i in range(1, N+1):
    print(color[i])
 
 
if(__name__ == '__main__'):
  main()

Submission status: Accepted

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


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

  color = [-1]*(N+1)
  color[1] = 0
  # S = [1]
  # while len(S):
  #   now = S[-1]
  #   for next_, w in G[now]:
  #     if color[next_] != -1:
  #       continue
  #     S.append(next_)
  #     color[next_] = (w % 2) ^ color[now]
  #     break
  #   else:
  #     S.pop()

  def dfs(now):
    for next_, w in G[now]:
      if color[next_] == -1:
        color[next_] = (w % 2) ^ color[now]
        dfs(next_)
  dfs(1)

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


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

Submission status: Accepted

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


n = int(input())
col = [0]*n
next = [[] for i in range(n)]
d = [float('INF')]*n
d[0]=0

def dfs(now,parent):
    for next1,w1 in next[now]:
        if next1 == parent:
            continue
        elif d[next1]==float('INF'):
            d[next1]=d[now]+w1
            dfs(next1,now)

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

dfs(0,-1)

for i in range(n):
    if d[i]%2==0:
        print('0')
    else:
        print('1')

Submission status: Accepted

Solution code:
from collections import deque

n = int (input())
roots = [[] for _ in range(2*n)]
color = [0] * 2 * n

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

    if (w % 2 == 1):
        roots[u].append(v)
        roots[v].append(u)
    else:
        roots[u].append(u+n)
        roots[u+n].append(v)
        roots[v].append(v+n)
        roots[v+n].append(u)

d = deque()
d.append(0)
color[0] = 1

while(len(d)):
    temp = d.popleft()
    for i in roots[temp]:
        if(color[i] == 0):
            color[i] = color[temp] * (-1)
            d.append(i)

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from collections import deque, Counter
from heapq import heappop, heappush
from bisect import bisect_right
import sys
sys.setrecursionlimit(10**6)

# 入力
N = int(input())
adj = [[] for _ in range(N)]
ans = [None] * N

# グラフ探索で解いてみる
# c: 頂点vの色(0or1)
def dfs(v,parent,c):
    ans[v] = c
    for u,w in adj[v]:
        if u == parent:
            continue
        dfs(u,v,1-c) if w & 1 else dfs(u,v,c)

def main():
    for i in range(N-1):
        u, v, w = map(int, input().split())
        adj[u-1].append((v-1,w))
        adj[v-1].append((u-1,w))
    
    dfs(0,-1,1)
    [print(v) for v in ans]

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from collections import deque, Counter
from heapq import heappop, heappush
from bisect import bisect_right

def main():
    N = int(input())
    adj = [[] for _ in range(N)]
    for i in range(N-1):
        u, v, w = map(int, input().split())
        adj[u-1].append((v-1,w))
        adj[v-1].append((u-1,w))
    
    queue = deque([0])
    visit = [-1] * N
    visit[0] = 1
    
    while queue:
        now = queue.popleft()
        for u,w in adj[now]:
            if visit[u] < 0:
                queue.append(u)
                if w % 2 == 0:
                    visit[u] = visit[now]
                else:
                    visit[u] = (visit[now]+1) % 2
    [print(v) for v in visit]


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)
n=int(input())
edge=[[] for _ in range(n)]
dist=[-1]*n
for i in range(n-1):
    x,y,z=map(int,input().split())
    edge[x-1].append([y-1,z])
    edge[y-1].append([x-1,z])
def dfs(node,d):
    dist[node]=d
    for i in edge[node]:
        if dist[i[0]]==-1:
            dfs(i[0],d+i[1])
dfs(0,0)
print(*[i%2 for i in dist],sep='\n')

Submission status: Accepted

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

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

import queue
q = queue.Queue()
q.put(0)
while not q.empty():
    v = q.get()
    for c, w in G[v]:
        if color[c] >= 0: continue
        color[c] = (color[v] + w)%2
        q.put(c)

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

Submission status: Accepted

Solution code:
import sys
INFTY=sys.maxsize
sys.setrecursionlimit(100000)

def readinput():
    n=int(input())
    nList=[]
    for _ in range(n+1):
        nList.append([])
    for _ in range(1,n):
        u,v,w=map(int,input().split())
        nList[u].append((v,w))
        nList[v].append((u,w))

    return n,nList

WHITE=0
GRAY=1
BLACK=2
status=[]
color=[]

def dfs(s,nList):
    for u,w in nList[s]:
        if status[u]==WHITE:
            if w%2==0:
                color[u]=color[s]
            else:
                color[u]=(color[s]+1)%2
            status[u]=GRAY
            dfs(u,nList)
    status[s]=BLACK

def main(n,nList):
    global status
    global color

    status=[WHITE]*(n+1)
    color=[WHITE]*(n+1)
    dfs(1,nList)

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

if __name__=='__main__':
    n,nList=readinput()
    main(n,nList)
    #print(ans)

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
#mod = 998244353
INF = 10**18
eps = 10**-7

N = int(readline())
ver = [[] for i in range(N+1)]
for i in range(N-1):
    u,v,w = map(int,readline().split())
    ver[u].append((v,w))
    ver[v].append((u,w))
color = [-1]*(N+1)
color[1] = 0
def dfs(fro,to,d):
    color[to] = d%2
    for v in ver[to]:
        if v[0] == fro:
            continue
        dfs(to,v[0],d+v[1])


for v in ver[1]:
    dfs(1,v[0],v[1])

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

Submission status: Accepted

Solution code:
import math,itertools,fractions,heapq,collections,bisect,sys,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

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 I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

color=[-1]*100100
G=[[] for _ in range(100100)]

def f(st):
  st_c=color[st]
  for v,d in G[st]:
    if color[v]!=-1:
      continue

    if d%2==0:
      color[v]=st_c
    else:
      color[v]=abs(st_c-1)

    f(v)

def main():
  n=I()
  for _ in range(n-1):
    a,b,c=LI()
    a-=1
    b-=1
    G[a].append((b,c))
    G[b].append((a,c))

  color[0]=0
  f(0)

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

main()
# print(main())

Submission status: Accepted

Solution code:
from collections import deque
n = int(input())
g = [[]for i in range(n)]
for _ in range(n-1):
  a, b, c = map(int, input().split())
  g[a-1].append([b-1,c])
  g[b-1].append([a-1,c])
ans = [0 for i in range(n)]
v = [-1 for i in range(n)]
v[0] = 0
d = deque([0])
while len(d):
  x = d.popleft()
  for i,j in g[x]:
    if v[i] == -1:
      d.append(i)
      b = ans[x] +j
      ans[i] = b
      if b%2 ==1:
        v[i] = 1
      else:
        v[i] = 0
print("\n".join(map(str,v)))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(20000000)

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

def dfs(node, dist):
    for nxt_node, edge_size in G[node]:
        if ans[nxt_node] == -1:
            ans[nxt_node] = ((dist + edge_size) % 2)
            dfs(nxt_node, dist + edge_size)

ans = [-1] * n
dfs(0, 0)
print(*ans, sep='\n')

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(1000000)

num_node = int(input())
relation = [[[], []] for i in range(num_node + 1)]
for i in range(num_node - 1):
    u, v, w = map(int, input().split())
    if w % 2 == 0:
        relation[u][0].append(v)
        relation[v][0].append(u)
    else:
        relation[u][1].append(v)
        relation[v][1].append(u)
colors = [None] * (num_node + 1)


def dfs(n: int, c: int):
    colors[n] = c
    # 偶数
    for even_idx in relation[n][0]:
        if colors[even_idx] is not None:
            continue
        else:
            dfs(even_idx, colors[n])
    # 奇数
    for odd_idx in relation[n][1]:
        if colors[odd_idx] is not None:
            continue
        else:
            dfs(odd_idx, 1 - colors[n])


if __name__ == '__main__':
    dfs(1, 0)
    for ans in list(map(int, colors[1:])):
        print(ans)

Submission status: Accepted

Solution code:
from collections import deque
N=int(input())
lst=[[] for i in range(N)]
for i in range(N-1):
    U,V,W=map(int,input().split())
    lst[U-1].append([U-1,V-1,W])
    lst[V-1].append([V-1,U-1,W])

ans_lst=[-1]*N
queue=deque([])
for i in lst[0]:
    queue.append(i)
ans_lst[0]=0
while queue:
    u,v,w=queue.popleft()
    if ans_lst[v]==-1:
        ans_lst[v]=(ans_lst[u]+w)%2
        for i in lst[v]:
            queue.append(i)

for i in ans_lst:
    print(i)

Submission status: Accepted

Solution code:
from collections import deque
n = int(input())
V = [[] for i in range(n+1)]
for i in range(n-1):
    u,v,w = map(int,input().split())
    V[u].append([v,w])
    V[v].append([u,w])
q = deque([])
dis = [-1]*(n+1)
q.append(1)
dis[1] = 0
while q:
    x = q.popleft()
    for y,z in V[x]:
        if dis[y] == -1:
            q.append(y)
            dis[y] = dis[x] + z
for i in range(1,n+1):
    if dis[i]%2 == 0:
        print(0)
    else:
        print(1)

Submission status: Accepted

Solution code:
#import sys
MOD = 10 ** 9 + 7
INFI = 10**10
#input = sys.stdin.readline
import math
from collections import deque
import itertools
import heapq
#import bisect
from fractions import Fraction
import copy
from functools import lru_cache
from collections import defaultdict
import pprint

#oo=list("ABCDEFGHIJKLMNOPQRSTUVWXYZ")
# ko=list("abcdefghijklmnopqrstuvwxyz")

def sosuhante(n):
    for k in range(2, int(math.sqrt(n))+1):
        if n% k ==0:
            return False
    return True
def cmb(n, r):
    if n - r < r: r = n - r
    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 kingaku(a,b,n):
    keta=len(str(n))
    return a*n+b*keta

def my_index(l, x, default=False):
    if x in l:
        return l.index(x)
    else:
        return default

#    h,w,a,b = map(int, input().split())
#    c = [[0 for j in range(n)] for i in range(n)]

def ret(a):
    c=[None]*(len(a)-1)
    if len(a)==1:
        return a[0]
    elif len(a)==0:
        return 0
    for i in range(1,len(a)):
        c[i-1]=abs(a[i]-a[i-1])
    return ret(c)

def soinsubunkai(n):
    a = []
    i = 1
    while i*i <= n:
        if n % i == 0 and i!=1:
            a.append(i)
            n=n//i

        if n% i !=0 or i==1:
            i += 1
    nokori=[n]
    return a + nokori

def make_divisors(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[::-1]

def main():
    n=int(input())
    dis=[INFI for _ in range(n+1)]
    graph=[[] for _ in range(n+1)]
    for i in range(n-1):
        a,b,c=map(int,input().split())
        graph[a].append([b,c])
        graph[b].append([a,c])
    stack=[]
    visited=[0 for _ in range(n+1)]
    dis[0]=0
    dis[1]=0
    for i in graph[1]:
        stack.append(i[0])
        dis[i[0]]=i[1]
    while True:
        s=stack.pop()
        for i in graph[s]:
            if visited[i[0]]==0:
                stack.append(i[0])
                dis[i[0]]=dis[s]+i[1]
                visited[i[0]]=1
        if len(stack)==0:
            break
#    print(dis)
    for i in range(1,n+1):
        if dis[i]%2==0:
            print(0)
        else:
            print(1)




if __name__ == "__main__":

    main()

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    def dfs(v, p):
        for u, w in tree[v]:
            if u == p:
                continue
            else:
                dist[u] = dist[v] + w
                dfs(u, v)

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

    dist = [0] * n
    dfs(0, -1)
    res = []
    for d in dist:
        res.append(0 if d % 2 == 0 else 1)
    print(*res, sep="\n")


if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
from collections import defaultdict, deque


def bfs(start):
    q = deque([start])
    dist = [-1] * N
    dist[start] = 0
    while q:
        v = q.popleft()
        for nv, nw in g[v]:
            if dist[nv] >= 0:
                continue
            dist[nv] = (dist[v] + nw) % 2
            q.append(nv)
    return dist


N, *UVW = map(int, open(0).read().split())
g = defaultdict(set)

ans = [0] * N
for u, v, w in zip(*[iter(UVW)] * 3):
    u -= 1
    v -= 1
    g[u].add((v, w))
    g[v].add((u, w))
print("\n".join(map(str, bfs(0))))

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict


sys.setrecursionlimit(1_000_000)


def dfs(v):
    for nv, nw in g[v]:
        if visited[nv]:
            continue
        if nw % 2:
            ans[nv] = ans[v] ^ 1
        else:
            ans[nv] = ans[v]
        visited[nv] = True
        dfs(nv)


N, *UVW = map(int, open(0).read().split())
g = defaultdict(set)

ans = [0] * N
for u, v, w in zip(*[iter(UVW)] * 3):
    u -= 1
    v -= 1
    g[u].add((v, w))
    g[v].add((u, w))
visited = [False] * N
visited[0] = True
dfs(0)
print("\n".join(map(str, ans)))

Submission status: Accepted

Solution code:
from collections import defaultdict


N, *UVW = map(int, open(0).read().split())
g = defaultdict(set)

ans = [0] * N
for u, v, w in zip(*[iter(UVW)] * 3):
    u -= 1
    v -= 1
    g[u].add((v, w))
    g[v].add((u, w))
visited = {0}
stack = [0]
while stack:
    v = stack.pop()
    for nv, nw in g[v]:
        if nv in visited:
            continue
        if nw % 2:
            ans[nv] = ans[v] ^ 1
        else:
            ans[nv] = ans[v]
        stack.append(nv)
        visited.add(v)
print("\n".join(map(str, ans)))

Submission status: Accepted

Solution code:
import sys
import heapq
import re
from itertools import permutations
from bisect import bisect_left, bisect_right
from collections import Counter, deque
from math import factorial, sqrt, ceil, gcd
from functools import lru_cache, reduce
from decimal import Decimal
from operator import mul

INF = 1 << 60
MOD = 1000000007
sys.setrecursionlimit(10 ** 7)


# UnionFind
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

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

# 素因数分解
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr

# 組合せnCr
def combinations_count(n, r):
    if n < r:
        return 0
    r = min(r, n - r)
    numer = reduce(mul, range(n, n - r, -1), 1)
    denom = reduce(mul, range(1, r + 1), 1)
    return numer // denom

# 2数の最小公倍数
def lcm(x, y):
    return (x * y) // gcd(x, y)

# リストの要素の最小公倍数
def lcm_list(numbers):
    return reduce(lcm, numbers, 1)

# リストの要素の最大公約数
def gcd_list(numbers):
    return reduce(gcd, numbers)

# 素数判定
def is_prime(n):
    if n <= 1:
        return False
    p = 2
    while True:
        if p ** 2 > n:
            break
        if n % p == 0:
            return False
        p += 1
    return True


# limit以下の素数を列挙
def eratosthenes(limit):
    A = [i for i in range(2, limit+1)]
    P = []

    while True:
        prime = min(A)
        
        if prime > sqrt(limit):
            break
            
        P.append(prime)
            
        i = 0
        while i < len(A):
            if A[i] % prime == 0:
                A.pop(i)
                continue
            i += 1
            
    for a in A:
        P.append(a)
            
    return P

# 同じものを含む順列
def permutation_with_duplicates(L):

    if L == []:
        return [[]]

    else:
        ret = []

        # set（集合）型で重複を削除、ソート
        S = sorted(set(L))

        for i in S:

            data = L[:]
            data.remove(i)

            for j in permutation_with_duplicates(data):
                ret.append([i] + j)

        return ret

def make_divisors(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[::-1]

# ここから書き始める
n = int(input())
u = [0 for i in range(n - 1)]
v = [0 for i in range(n - 1)]
w = [0 for i in range(n - 1)]
tree = [[] for i in range(n)]
for i in range(n - 1):
    u[i], v[i], w[i] = map(int, input().split())
    tree[u[i] - 1].append([v[i] - 1, w[i]])
    tree[v[i] - 1].append([u[i] - 1, w[i]])
# print(tree)
ans = [-1 for i in range(n)]
queue = deque([0])
while queue:
    now = queue.popleft()
    if ans[now] != -1:
        continue
    ans[now] = 0
    for i in tree[now]:
        if ans[i[0]] == -1:
            continue
        if ans[i[0]] == 0:
            if i[1] % 2 == 0:
                ans[now] = 0
            else:
                ans[now] = 1
        elif ans[i[0]] == 1:
            if i[1] % 2 == 0:
                ans[now] = 1
            else:
                ans[now] = 0
        break
    for i in tree[now]:
        queue.append(i[0])
# print(ans)
for i in ans:
    print(i)

Submission status: Accepted

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

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

node_colors = [-1] * (N+1)

def route(last, now, dist):
    for next_node, next_distance in paths[now].items():
        node_colors[next_node] = (dist + next_distance) % 2
        if next_node != last:
            route(now, next_node, dist + next_distance)

node_colors[1] = 0

route(0, 1, 0)

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

Submission status: Accepted

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

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

node_colors = [-1] * (N+1)

def route(last, now, dist):
    for next_node, next_distance in zip(paths[now].keys(), paths[now].values()):
        node_colors[next_node] = (dist + next_distance) % 2
        if next_node != last:
            route(now, next_node, dist + next_distance)

node_colors[1] = 0

route(0, 1, 0)

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

Submission status: Accepted

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

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

node_colors = [-1] * (N+1)

def route(last, now, dist):
    for next_node, next_distance in zip(paths[now].keys(), paths[now].values()):
        node_colors[next_node] = (dist + next_distance) % 2
        if next_node != last:
            route(now, next_node, dist + next_distance)

node_colors[1] = 0

route(0, 1, 0)

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

Submission status: Accepted

Solution code:
from collections import deque

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

M = N-1
G = [deque([]) for i in range(N+1)]

for i in range(M):
    G[tree[i][0]].append([tree[i][1], tree[i][2]])
    G[tree[i][1]].append([tree[i][0], tree[i][2]])
    
distance = [-1] * (N+1)     

def dfs(v):
    stack = deque([v])
    distance[v] = 0
    
    while stack:   
        tmp = stack[0]
        if G[tmp]:
            w = G[tmp].popleft() 
            if distance[w[0]] < 0:
                distance[w[0]] = (distance[tmp] + w[1]) % 2
                stack.append(w[0])
        else:
            stack.popleft()
    return distance

distance = dfs(1)
for i in range(N):
    print(distance[i+1])

Submission status: Accepted

Solution code:
from collections import deque

N = int(input())
dic = {i:[] for i in range(1,N+1)}

for _ in range(N-1):
  u, v, w = map(int, input().split())
  dic[u].append((v,w))
  dic[v].append((u,w))
  
s1 = set([1])
s2 = set([])
h = deque([(1,0)])

while h:
  p = h.popleft()
  for t in dic[p[0]]:
    if t[0] == p[1]:
      continue
    if t[1]%2 == 0:
      if p[0] in s1:
        s1.add(t[0])
      else:
        s2.add(t[0])
    else:
      if p[0] in s1:
        s2.add(t[0])
      else:
        s1.add(t[0])
    h.append((t[0],p[0]))

for i in range(1,N+1):
  if i in s1:
    print(0)
  elif i in s2:
    print(1)

Submission status: Accepted

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

n = int(input())
uvw = [[] for _ in range(n)]
for _ in range(n - 1):
    u, v, w = map(int, input().split())
    u -= 1
    v -= 1
    uvw[u].append([v, w])
    uvw[v].append([u, w])
color = [-1 for _ in range(n)]
color[0] = 0
def dfs(before_pos, pos, w):
    color[pos] = w
    for next_pos, next_w in uvw[pos]:
        if next_pos == before_pos:
            continue
        dfs(pos, next_pos, (w + next_w) % 2)
    
dfs(-1, 0, 0)
for c in color:
    print(c)