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, 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 = []
# q.append((0, 0))

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

Submission status: Accepted

Solution code:
N = int(input())

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

distance = [-1] * N
distance[0] = 0
q = [0]
while q:
    p = q.pop()
    for n, w in links[p]:
        if distance[n] == -1:
            distance[n] = distance[p] + w
            q.append(n)

for i in distance:
    print(i % 2)

Submission status: Accepted

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

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N = int(readline())

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

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

COLOR = [None] * (N + 1)


def setColor(v, c):
    COLOR[v] = c
    for w, l in E[v]:
        if COLOR[w] == None:
            nc = c
            if l % 2 != 0:
                nc = int(not nc)
            setColor(w, nc)


setColor(1, 0)

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

Submission status: Accepted

Solution code:
from collections import deque

n=int(input())

tree=[[] for i in range(n)]
for i 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])

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

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

dq=deque()
dq.append(0)

while dq:
  x=dq.popleft()
  for vv,ww in tree[x]:
    if dist[vv]==-1:
      dq.append(vv)
      dist[vv]=dist[x]+ww
      if dist[vv]%2==0:
        ans[vv]=0
      else:
        ans[vv]=1

for i in ans:
  print(i)

Submission status: Accepted

Solution code:
from sys import stdin
from collections import deque
nii=lambda:map(int,stdin.readline().split())

n=int(input())

tree=[[] for i in range(n)]
for i in range(n-1):
  u,v,w=nii()
  u-=1
  v-=1
  tree[u].append([v,w])
  tree[v].append([u,w])

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

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

dq=deque()
dq.append(0)

while dq:
  x=dq.popleft()
  for vv,ww in tree[x]:
    if dist[vv]==-1:
      dq.append(vv)
      dist[vv]=dist[x]+ww
      if dist[vv]%2==0:
        ans[vv]=0
      else:
        ans[vv]=1

for i in ans:
  print(i)

Submission status: Accepted

Solution code:
#python3
from collections import deque
def main():
    n = int(input()) 
    #隣接リスト表現でグラフを管理する
    #v-uのcostはto[v]においてuが格納されている位置と同じcost[v]リスト位置に保存するような対応関係をとる
    to = [[] for _ in range(n)]
    cost = [[] for _ in range(n)]
    for _ in range(n-1):
        v, u, w  = map(int, input().split())
        v -= 1
        u -= 1
        to[v].append(u)
        cost[v].append(w)
        to[u].append(v)
        cost[u].append(w)

    
    #根からの距離を偶奇をBFSで求める    
    dist = [-1 for _ in range(n)]
    dist[0] = 0
    q = deque()
    q.append(0)
    while len(q) != 0:
        #訪問予定の頂点を取り出す
        val = q.popleft()
        #頂点vに連結している頂点を探索すして訪問予定に追加する
        for i in range(len(to[val])):
            wal = to[val][i]
            cos = cost[val][i]
            if dist[wal] != -1:
                continue
            dist[wal] = (dist[val] + cos)%2 
            q.append(wal)
    
    for i in range(n):
        print(dist[i])
main()

Submission status: Accepted

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

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

b = [[] for i in range(n)]

for i in range(n-1):
    b[a[i][0]-1].append((a[i][1]-1,a[i][2]))
    b[a[i][1]-1].append((a[i][0]-1,a[i][2]))

import collections
from collections import deque

INF = -10 ** 9
dis = [INF for i in range(n)]
ans = [-1]*n
def bfs(s):
    d = deque()
    d.append(s)
    dis[s]=0
    ans[s]=0
    flag = True

    while len(d):
        x = d.popleft()

        for i in range(len(b[x])):
            y=b[x][i][0]
            if dis[y] == INF:
                d.append(y)
                dis[y]=dis[x]+b[x][i][1]
                if dis[y]%2==0:
                    ans[y]=0
                else:
                    ans[y]=1
    return ans
z=bfs(0)

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

Submission status: Accepted

Solution code:
# import bisect
from collections import Counter, defaultdict, deque
# import copy
# from heapq import heappush, heappop, heapify
# from fractions import gcd
# import itertools
# from operator import attrgetter, itemgetter
# import math

import sys

# import numpy as np

ipti = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)

class Node:
    def __init__(self, node_id):
        self.color = -1
        self.id = node_id
        self.next = []

def main():
    n = int(input())
    nodes = [0] * (n+1)

    for i in range(1, n+1):
        nodes[i] = Node(i)

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

    que = deque()
    que.append((1,0))
    idx = 0

    while que:
        current_id, current_color = que.popleft()
        current_node = nodes[current_id]
        nodes[current_id].color = current_color

        while current_node.next:
            next_id, next_dist = current_node.next.pop()
            if nodes[next_id].color == -1:
                if next_dist % 2 == 0:
                    next_color = current_color
                else:
                    next_color = (current_color+1) % 2
                que.append((next_id, next_color))

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

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
from collections import namedtuple


sys.setrecursionlimit(10**5)

Edge = namedtuple('Edge', 'to cost')

N = int(input())

# index と頂点の番号を合わせたいのでサイズを N + 1 に
colors = [0] * (N + 1)
vertexes = [[] for _ in range(N + 1)]

for _ in range(N - 1):
  u, v, w = map(int, input().split())
  # 無向グラフなので双方向にリンクする
  vertexes[u].append(Edge(v, w))
  vertexes[v].append(Edge(u, w))


def dfs(id, color):
  colors[id] = color
  for edge in vertexes[id]:
    if edge.cost % 2 != 0:
      if colors[edge.to] == color:
        return False
      if colors[edge.to] == 0 and not dfs(edge.to, -color):
        return False
    elif colors[edge.to] == 0:
      dfs(edge.to, color)
  return True

if dfs(1, 1):
  for color in colors[1:]:
    print(1 if color == 1 else 0)

Submission status: Accepted

Solution code:
import sys
from collections import deque

n=int(input())
edge=[[] for i in range(n+1)]

color=[-1]*(n+1)

for i in range(n-1):
    u,v,w=list(map(int,sys.stdin.readline().strip().split()))
    w%=2

    edge[u].append([v,w])
    edge[v].append([u,w])

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

while len(q)>0:
    parent=q.popleft()
    pw=color[parent]

    for child,ew in edge[parent]:
        if color[child]!=-1:
            continue
        cw=(pw+ew)%2
        color[child]=cw
        q.append(child)

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

Submission status: Accepted

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

N = int(input())

ans = [-1] * N

G = [[[], []] for _ in range(N)]

for _ in range(N - 1):
    u, v, w = [int(x) for x in input().split()]
    if w % 2 == 0:
        G[u - 1][0].append(v - 1)
        G[v - 1][0].append(u - 1)
    else:
        G[u - 1][1].append(v - 1)
        G[v - 1][1].append(u - 1)

def dfs(x):
    ans[x] = 0
    stack = [x]
    while stack:
        y = stack.pop()
        for i in G[y][0]:
            if ans[i] < 0:
                ans[i] = ans[y]
                stack.append(i)
        for j in G[y][1]:
            if ans[j] < 0:
                ans[j] = int(not ans[y])
                stack.append(j)
    return ans

ans = dfs(0)

for i in ans:
    print(i)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)
N=int(input())
G=[[] for i in range(N)]
for _ in range(N-1):
    u,v,w=map(int,input().split())
    G[u-1].append([v-1,w%2])
    G[v-1].append([u-1,w%2])
color=[0 for i in range(N)]
seen=[False for i in range(N)]
color[0]=1
def dps(i):
    seen[i]=True
    for g in G[i]:
        if seen[g[0]]:
            continue
        else:
            if g[1]==0:
                color[g[0]]=color[i]
            else:
                color[g[0]]=color[i]*-1
            dps(g[0])
dps(0)
for i in range(N):
    print(1 if color[i]==1 else 0)

Submission status: Accepted

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

dist = [-1] * N
dist[0] = 0
q = [0]
while q:
  temp = q.pop()
  for u, v in edge[temp]:
    if dist[u] != -1:
      continue
    dist[u] = dist[temp] + v
    q.append(u)
  
for ans in dist:
  if ans % 2 == 0:
    print(1)
  else:
    print(0)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(4100000)

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

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

def dfs(index):
    if ans[index]==-1:
        ans[index] = 0
    for i in root[index]:
        if ans[i[0]] == -1:
            ans[i[0]] = (ans[index]+i[1])%2
            dfs(i[0])

for i in range(N):
    dfs(i)

for i in ans:
    print(i)

Submission status: Accepted

Solution code:
from collections import deque

n = int(input())
color = [-1] * n
g = [[] for _ in range(n)]
l = [[] for _ in range(n)]

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

for i in range(n-1):
    u,v,w = map(int,input().split()) 
    g[u-1].append(v-1)
    g[v-1].append(u-1)
    l[u-1].append(w)
    l[v-1].append(w)
    
while que:
    s = que.pop()
    for i in range(len(g[s])):
        x = g[s][i]
        y = l[s][i]
        
        if color[x] != -1:
            continue
        elif y % 2 == 0:
            color[x] = color[s]
        else:
            color[x] = (color[s]+1) % 2
            
        que.append(g[s][i])
        
for i in range(n):
    print(color[i])

Submission status: Accepted

Solution code:
N=int(input())
uvw=[[] for _ in range(N)]
for i in range(N-1):
    u,v,w=map(int,input().split())
    uvw[u-1].append((v-1,w))
    uvw[v-1].append((u-1,w))
# print(uvw)
color=[-1]*N 
color[0]=0
now=0
nex=[0]
from copy import deepcopy
while nex:
    now=nex.pop()
    stack=deepcopy(uvw[now])
    uvw[now]=[]
    while stack:
        a=stack.pop()
        if a[1]%2==0:
            color[a[0]]=color[now]
        else:
            color[a[0]]=color[now]^1
        nex.append(a[0])
for c in color:
    print(c)

Submission status: Accepted

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

def main():
    n=int(input())
    l=[[] for _ in range(n+1)]
    for _ 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]*n
    chk=[(0,0,-1)]
    while chk:
        v,d,p=chk.pop()
        if d%2==0:
            ans[v]=0
        else:
            ans[v]=1
        for u,w in l[v]:
            if u==p:
                continue
            chk.append((u,d+w,v))
    [print(i) for i in ans]

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque

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

dq = deque()
dq.append(1)
Visited = [-1 for _ in range(n+1)]
Visited[1] = 0

while dq:
    now = dq.popleft()
    Adjs = Adj_dict[now]
    for adj in Adjs:
        if Visited[adj[0]] != -1:
            continue
        else:
            dq.append(adj[0])
            Visited[adj[0]] = Visited[now] + adj[1]

for i in range(1,n+1):
    print(Visited[i]%2)

Submission status: Accepted

Solution code:
from collections import deque
n=int(input())
A=[[[] for j in range(2)] for i in range(n)]
for i in range(n-1):
  u,v,w=map(int,input().split())
  w=w%2
  A[u-1][0].append(v-1)
  A[u-1][1].append(w)
  A[v-1][0].append(u-1)
  A[v-1][1].append(w)
B=deque([0])
C=[0]*n
C[0]=1
ans=[0]*n
while len(B)>0:
  s=B[0]
  B.popleft()
  for i in range(len(A[s][0])):
    if C[A[s][0][i]]==0:
      B.append(A[s][0][i])
      C[A[s][0][i]]=1
      ans[A[s][0][i]]=(ans[s]+A[s][1][i])%2
for i in range(n):
  print(ans[i])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 7)
N = int(input())
edge = [[] for _ in range(N + 1)]
for _ in range(N - 1):
    a, b, c = map(int, input().split())
    edge[a].append((b, c % 2))
    edge[b].append((a, c % 2))

root = 1
dist = [-1] * (N + 1)
dist[root] = 0
node = [root]

while node:
    s = node.pop()
    d = dist[s]
    for t, c in edge[s]:
        if dist[t] != -1:
            continue
        dist[t] = (d + c) % 2
        node.append(t)

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

Submission status: Accepted

Solution code:
from collections import deque

n = int(input())
to = [[0] for _ in range(n)]
cost = [[0] for _ in range(n)]
for i in range(n - 1):
    a, b, w = map(int, input().split())
    a -= 1
    b -= 1
    to[a].append(b)
    to[b].append(a)
    cost[a].append(w)
    cost[b].append(w)

q = deque()
q.append(0)
ans = [-1] * n
ans[0] = 0

while len(q):
    v = q.pop()
    for i in range(len(to[v])):
        u = to[v][i]
        w = cost[v][i]

        if ans[u] != -1:
            continue
        ans[u] = (ans[v] + w) % 2
        q.append(u)
for i in range(n):
    print(ans[i])

Submission status: Accepted

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

class Node:
    def __init__(self):
        self.children = []
        self.color = -1
    
    def append(self,target,weight):
        self.children.append((target,weight))
        target.children.append((self,weight))
 
    def setColor(self,color):
        self.color = color
        for child in self.children:
            if child[0].color != -1:
                continue
            if child[1] % 2 == 0:
                child[0].setColor(self.color)
            else:
                child[0].setColor(0 if self.color == 1 else 1)

def solve(N: int, u: "List[int]", v: "List[int]", w: "List[int]"):
    nodes = [Node() for i in range(N)]
    # print(u)
    for i in range(N-1):
        nodes[u[i]-1].append(nodes[v[i]-1],w[i])
    colorQueue = [(nodes[0],0)]
    while True:
        if len(colorQueue) == 0:
            break
        next = colorQueue.pop()
        next[0].color = next[1]
        for child in next[0].children:
            if child[0].color != -1:
                continue
            if child[1] % 2 == 0:
                colorQueue.append((child[0],next[0].color))
            else:
                colorQueue.append((child[0],0 if next[0].color == 1 else 1))

    for n in nodes:
        print(n.color)
    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    u = [int()] * (N - 1)  # type: "List[int]"
    v = [int()] * (N - 1)  # type: "List[int]"
    w = [int()] * (N - 1)  # type: "List[int]"
    for i in range(N - 1):
        u[i] = int(next(tokens))
        v[i] = int(next(tokens))
        w[i] = int(next(tokens))
    solve(N, u, v, w)

if __name__ == '__main__':
    main()

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

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
color[0] = 1

def dfs(node):
    for i, w in graph[node]:
        if color[i] == 0: # not visited
            if w % 2 == 0: # guusuu        
                color[i] = color[node]
            else:
                color[i] = color[node] * (-1)
            dfs(i)

dfs(0)
for c in color:
    if c == 1:
        print(0)
    else:
        print(1)

Submission status: Accepted

Solution code:
#126_D
import sys
sys.setrecursionlimit(500000)

n=int(input())
edges=[[] for _ in range(n)]
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))
visit=[False for _ in range(n)]
d=[0 for i in range(n)]

def dfs(i):
    visit[i]=True
    for v,w in edges[i]:
        if visit[v]==False:
            d[v]=(d[i]+w)%2
            dfs(v)
            
dfs(0)
print(*d,sep='\n')

Submission status: Accepted

Solution code:
#126_D
import sys
sys.setrecursionlimit(500000)

n=int(input())
edges=[[] for _ in range(n)]
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))
visit=[False for _ in range(n)]
d=[0 for i in range(n)]

def dfs(i):
    visit[i]=True
    if all(visit[i] for i in range(n)):
        print(*d,sep='\n')
        exit()
    for v,w in edges[i]:
        if visit[v]==False:
            d[v]=(d[i]+w)%2
            dfs(v)
            
dfs(0)

Submission status: Accepted

Solution code:
from collections import deque

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

q = deque([1])
visit[1] = 0
while q:
    position = q.popleft()
    for i, cost in friends[position]:
        if visit[i] < 0:
            visit[i] = visit[position] + cost
            q.append(i)

for i in visit[1:]:
    print(i%2)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(9**9)
n=int(input())
C=[0 for _ in range(n)]
L=[[] for _ in range(n)]
for j 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])
def a(n,v,d):
  for i in L[n]:
    if d%2==1:C[n]=1
    if v!=i[0]:a(i[0],n,d+i[1])
a(0,0,0)
for c in C:print(c)

Submission status: Accepted

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

def main():
    N = int(input())

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

    depth = [-1] * (N)
    depth[0] = 0
    def dfs(x):
        for i, g in graph[x].items():
            if depth[i] > -1:
                continue
            depth[i] = depth[x] + g
            dfs(i)
    dfs(0)
    print("\n".join(['1' if d % 2 == 0 else '0' for d in depth]))

if __name__ == '__main__':
    main()

Submission status: Accepted

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

N=int(input())
A=[list(map(int,input().split())) for _ in range(N-1)]
C=[0]*N
D=[[] for i in range(N)]
for u,v,w in A:
  u-=1
  v-=1
  D[u].append((v,w))
  D[v].append((u,w))

def dfs(n,v,k):
  for i in D[n]:
    if k%2!=0:
      C[n]=1
    if v!=i[0]:
      dfs(i[0],n,k+i[1])       
        
dfs(0,0,0)

for i in C:
  print(i)

Submission status: Accepted

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

N = int(input())
visited = [False] * N
colors = [-1] * N
dist = [float('inf')] * N

def dfs(u):
    if visited[u]:
        return

    visited[u] = True
    for (v, w) in edges[u]:
        if visited[v]:
            continue
        if colors[v] != -1:
            continue

        dist[v] = dist[u] + w
        if dist[v] % 2 == 0:
            colors[v] = 0
        else:
            colors[v] = 1
        dfs(v)


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


colors[0] = 0
dist[0] = 0
dfs(0)
for c in colors:
    print(c)

Submission status: Accepted

Solution code:
#!/usr/bin/python3
# -*- coding:utf-8 -*-

from collections import defaultdict, deque

def main():
  tree = defaultdict(list)
  weights = dict()
  n = int(input())
  colors = dict()
  
  for _ in range(n-1):
    u, v, w = map(int, input().strip().split())
    tree[u].append(v)
    tree[v].append(u)
    weights[(u, v)] = weights[(v, u)] = w%2
  
  def bs(iroot=1):
    visited = set()
    dq = deque()
    dq.append((iroot, 0))
    colors[iroot] = 0
    while dq:
      inode, sw = dq.popleft()
      visited |= set([inode])
      
      for ichild in tree[inode]:
        if ichild in visited:
          continue
        colors[ichild] = (sw + weights[(inode, ichild)])%2
        dq.append((ichild, (sw + weights[(inode, ichild)]%2)))
    return colors
  
  colors = bs()
  for i in range(1, len(colors)+1):
    print(colors[i])

if __name__=='__main__':
  main()

Submission status: Accepted

Solution code:
import heapq
import sys

N = int(input())
a = [[] for i in range(N)]
for i in range(N - 1):
	u, v, w = map(int, input().split())
	a[u - 1].append((v - 1, w))
	a[v - 1].append((u - 1, w))
b = [(0, 0)]
c = [False] * N
d = [sys.maxsize] * N
d[0] = 0
while len(b) != 0:
	e = heapq.heappop(b)
	c[e[1]] = True
	for i in a[e[1]]:
		if c[i[0]]:
			continue
		if d[e[1]] + i[1] < d[i[0]]:
			d[i[0]] = d[e[1]] + i[1]
			heapq.heappush(b, (d[i[0]], i[0]))
for i in d:
	print(i % 2)

Submission status: Accepted

Solution code:
from collections import deque
n=int(input())
edges=[[] for _ in range(n)]
visited=[-1 for _ in range(n)]
for i in range(n-1):
  u,v,w=map(int,input().split())
  edges[u-1].append((v-1,w))
  edges[v-1].append((u-1,w))
def dfs(edges,visited):
  stack=deque([0])
  visited[0]=0
  while stack:
    x=stack.pop()
    for newx,w in edges[x]:
      if visited[newx]==-1:
        if w%2:
          visited[newx]=1-visited[x]
        else:
          visited[newx]=visited[x]
        stack.append(newx)
  return visited
for i in dfs(edges,visited):
  print(i)

Submission status: Accepted

Solution code:
import math
import copy
from copy import deepcopy
import sys
import fractions
import numpy as np
from functools import reduce
# import statistics
import heapq
sys.setrecursionlimit(100001)

# input = sys.stdin.readline
# sys.setrecursionlimit(10**6)

# ===FUNCTION===

def getInputInt():
    inputNum = int(input())
    return inputNum


def getInputListInt():
    outputData = []
    inputData = input().split()
    outputData = [int(n) for n in inputData]

    return outputData


def getSomeInputInt(n):
    outputDataList = []
    for i in range(n):
        inputData = int(input())
        outputDataList.append(inputData)

    return outputDataList


def getSomeInputListInt(n):
    inputDataList = []
    outputDataList = []
    for i in range(n):
        inputData = input().split()
        inputDataList = [int(n) for n in inputData]
        outputDataList.append(inputDataList)

    return outputDataList


# ===CODE===

n = int(input())


ans = [-1]*n

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])
ans = [-1]*n
def dfs(x,y):
    for i,j in g[x]:
        if ans[i] == -1:
            ans[i] = (y+j)%2
            dfs(i,y+j)
dfs(0,0)
for i in ans:
    print(i)

Submission status: Accepted

Solution code:
from collections import deque

def bfs(colors, links):
    q = deque([(0, 0)])
    
    while q:
        v, current = q.popleft()

        for next_v, distance in links[v]:
            if colors[next_v] != -1: continue
        
            if (current+distance) % 2 == 0:
                colors[next_v] = 0
            else:
                colors[next_v] = 1

            q.append((next_v, current + distance))
        
def solve():
    N = int(input())
    A = [list(map(int, input().split())) for _ in range(N-1)]
    cs = [-1] * N
    cs[0] = 0

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

    bfs(cs, links)

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

solve()

Submission status: Accepted

Solution code:
from collections import deque

def bfs(colors, links):
    q = deque([(0, 0)])
    
    while q:
        v, current = q.popleft()

        if current % 2 == 0:
            colors[v] = 0
        else:
            colors[v] = 1

        for next_v, distance in links[v]:
            if colors[next_v] != -1: continue

            q.append((next_v, current + distance))
        
def solve():
    N = int(input())
    A = [list(map(int, input().split())) for _ in range(N-1)]
    cs = [-1] * N
    cs[0] = 0

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

    bfs(cs, links)

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

solve()

Submission status: Accepted

Solution code:
import sys
from collections import deque
sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline
N = int(input())
L = [deque([]) for _ in range(N)]
ans = [-1] * N

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

def dfs(x, w):
    if ans[x-1] >= 0:
        return
    ans[x-1] = w % 2
    for nx, w_ in L[x-1]:
        dfs(nx, (w + w_) % 2)
    return

dfs(1, 0)

for a in ans:
    print(a)

Submission status: Accepted

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

N = int(input())
d = [[] for _ in range(N)]
iro = [0] * (N)

def dfs(n, v, k):
    for i in d[n]:
        if k % 2 != 0:
            iro[n] = 1
        if v == i[0]:
            continue
        dfs(i[0], n, k + i[1])

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

dfs(0, 0, 0)
for i in iro:
    print(i)

Submission status: Accepted

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

N = int(input())

G = []
for i in range(N):
    G.append([])

color = [None] * N

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

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

def dfs(v, c):
    color[v] = c

    # vと隣接する点
    for p, d in G[v]:
        # 訪問済み
        if color[p] is not None:
            continue
        if d % 2 == 0:
            dfs(p, c)
        else:
            dfs(p, c ^ 1)  # 排他的論理和で0, 1をひっくり返す

# 0の頂点を0で塗る
dfs(0, 0)

# print(color)
for col in color:
    print(col)

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
import sys
 
sys.setrecursionlimit(10**7)

def dfs(num,hiyo):
    ans[num]=hiyo
    for to,cos in way[num]:
        if ans[to]==-1:
            dfs(to,hiyo+cos)
    
    return 

N=int(input())

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

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

#lis.sort(key=lambda x:(x[0],x[1]))

dfs(0,0)
#print(ans)
for item in ans:
    print(item%2)

Submission status: Accepted

Solution code:
import copy ; import sys ; sys.setrecursionlimit(11451419)
n=int(input())
color=[-1 for i in range(n)]
color[0]=1
G=[[] for i in range(n)]
for i in range(n-1):
  a,b,d=map(int,input().split())
  G[a-1].append([b-1,d])
  G[b-1].append([a-1,d])
  
def dfs(x):
  
  for i,dis in G[x]:
    
    if color[i] != -1: continue
    if dis %2==1:
      color[i]=1-color[x]
    else:
      color[i]=color[x]
    dfs(i)
dfs(0)
for i in range(n):
  print(color[i])

Submission status: Accepted

Solution code:
from collections import defaultdict, deque

N = int(input())

edges = defaultdict(list)

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


colors = [None] * N
colors[0] = 0
que = deque([0])

while que:
    u = que.popleft()
    for v, w in edges[u]:
        if colors[v] != None:
            continue
        if edges[v] != []:
            que.append(v)

        if w % 2 == 0:
            colors[v] = colors[u]
        else:
            colors[v] = 1 ^ colors[u]

for c in colors:
    print(c)