Problem:


Score : 400 points

Problem Statement

We have a tree with N vertices numbered 1 to N.
The i-th edge in the tree connects Vertex u_i and Vertex v_i, and its length is w_i.
Your objective is to paint each vertex in the tree white or black (it is fine to paint all vertices the same color) so that the following condition is satisfied:

For any two vertices painted in the same color, the distance between them is an even number.

Find a coloring of the vertices that satisfies the condition and print it. It can be proved that at least one such coloring exists under the constraints of this problem.

Constraints

All values in input are integers.

1 \leq N \leq 10^5

1 \leq u_i < v_i \leq N

1 \leq w_i \leq 10^9

Input

Input is given from Standard Input in the following format:

N
u_1 v_1 w_1
u_2 v_2 w_2
.
.
.
u_{N - 1} v_{N - 1} w_{N - 1}

Output

Print a coloring of the vertices that satisfies the condition, in N lines.
The i-th line should contain 0 if Vertex i is painted white and 1 if it is painted black.

If there are multiple colorings that satisfy the condition, any of them will be accepted.

Sample Input 1

3
1 2 2
2 3 1

Sample Output 1

0
0
1

Sample Input 2

5
2 5 2
2 3 10
1 3 8
3 4 2

Sample Output 2

1
0
1
0
1



Sample input:
3
1 2 2
2 3 1


Sample output:
0
0
1

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)



n=int(input())

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

result=[-1]*n
#print(tree)
def DEF(x,dis):
    #print("x",x)
    global tree, uvw,result
    for nextNode in tree[x]:
        if result[nextNode]==-1:
            nextDis=dis+uvw[(min(x,nextNode),max(x,nextNode))]
            if (nextDis)%2==0:
                result[nextNode]=0
                DEF(nextNode,nextDis)
            else:
                result[nextNode]=1
                DEF(nextNode,nextDis)
result[0]=0
DEF(0,0)

for item in result:
    print(item)

Submission status: Accepted

Solution code:
#n=int(input())
#n,m=list(map(int,input().split()))
#a=list(map(int,input().split()))
input_list = lambda : list(map(int,input().split()))

from collections import Counter 
from collections import defaultdict
import itertools
import sys
sys.setrecursionlimit(10**6)

def sol(num,w,node,ans):
    now=node[num]
    
    for each in now:
        ne_n=each[0]
        ne_w=each[1]
        if ans[ne_n]!=-1:
            continue
        if ne_w==0:
            ans[ne_n]=ans[num]
        else:
            ans[ne_n]=1-ans[num]
        
        sol(ne_n,ne_w,node,ans)




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

ans=[-1 for _ in range(n)]
ans[0]=0
sol(0,0,node,ans)
for i in ans:
    print(i)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(100000)

class Graph():
    def __init__(self):
        self.adjacency_dict = {}

    def add_vertex(self, v):
        self.adjacency_dict[v] = []
    
    def add_edge(self, v1, v2, dist):
        self.adjacency_dict[v1].append([v2, dist])
        self.adjacency_dict[v2].append([v1, dist])
    
    def next_edges(self, v):
        return self.adjacency_dict[v]

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

graph = Graph()
for i in range(1, N+1):
    graph.add_vertex(i)
for v1, v2, dist in dists:
    graph.add_edge(v1, v2, dist)

def dfs(start, group):
    if visited[start] is not None:
        return
    visited[start] = group
    for v, dist in graph.next_edges(start):
        if dist % 2 == 0:
            dfs(v, group)
        else:
            dfs(v, 1-group)

visited = [None]*(N+1)
dfs(1, 0)
for i in visited[1:]:
    print(i)

Submission status: Accepted

Solution code:
from collections import defaultdict
n = int(input())
d = defaultdict(list)
for i in range(n-1):
    u, v, w = map(int, input().split())
    d[u-1].append([v-1, w])
    d[v-1].append([u-1, w])
color = [0] * n
q = [0]
seen = set()
while q:
    parent = q.pop()
    for child in d[parent]:
        j, w = child
        if j not in seen:
            color[j] = color[parent]+w
            seen.add(j)
            q.append(j)
for cnt in color:
    if cnt%2 == 0:
        print('0')
    else:
        print('1')

Submission status: Accepted

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

sys.setrecursionlimit(10 ** 7)

# 1 ✕ 1 (int)
N = int(input().rstrip())

# N ✕ M (2D array)
A = list(map(int, input().rstrip().split()) for _ in range(N - 1))

items = [[] for _ in range(N)]
colors = [-1 for _ in range(N)]

for i in range(N - 1):
    a, b, w = A[i]
    items[a - 1].append((b - 1, w))
    items[b - 1].append((a - 1, w))

queue = collections.deque()
queue.append(0)
colors[0] = 0
while queue:
    v = queue.popleft()
    c = colors[v]
    for k, w in items[v]:
        cc = colors[k]
        if cc == -1:
            nc = c if w % 2 == 0 else not c
            colors[k] = nc
            queue.append(k)

# def dfs(v, c):
#     colors[v] = c
#
#     cc = colors[k]
#
#     if cc == -1:
#         if not dfs(k, nc):
#             return False
#     else:
#         if colors[i] != nc:
#             return False
#
#
# return True
#
# dfs(0, True)
for c in colors:
    print(int(not c))

Submission status: Accepted

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

N = int(input())
G = [[] for i in range(N)]
temp = sys.stdin.readlines()
for line in temp:
    u, v, d = map(int, line.split())
    G[u-1].append([v-1, d])
    G[v-1].append([u-1, d])
    
def dfs(v, G, cur=0):
    # 色をメモ
    color[v] = cur
        
    # 隣接するノードの色を調べる
    for next_v in G[v]:
        # 隣接ノードが探索済みなら、色が正しいか確かめる
        if color[next_v[0]] != -1:
            continue
            
        # 隣接ノードが未探索なら、正しい色に更新して再帰的に探索
        if next_v[1] % 2 == 0:
            dfs(next_v[0], G, cur)
        else:
            dfs(next_v[0], G, 1-cur)

color = [-1 for i in range(N)]
dfs(0, G)
for i in range(N):
    print(color[i])

Submission status: Accepted

Solution code:
N = int(input())
link = [set() for i in range(N)]
for i in range(N-1):
    u, v, w = map(int,input().split())
    link[u-1] |= {(v-1,w)}
    link[v-1] |= {(u-1,w)}
check = [(0, 0, -1)]
ans = [-1 for i in range(N)]
while check:
    now, d, From = check.pop()
    ans[now] = d % 2
    for next, dist in link[now]:
        if next == From:
            continue
        else:
            check.append((next, d + dist, now))
print('\n'.join(map(str,ans)))

Submission status: Accepted

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

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

edge = [[] for _ in range(N)]

for i in range(N-1):
    v1, v2, w = map(int, input().split())
    edge[v1-1].append((v2-1, w))
    edge[v2-1].append((v1-1, w))

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

def dfs(x):
    for v, w in edge[x]:
        if color[v] == -1:
            color[v] = (w + color[x])%2
            dfs(v)



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

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.buffer.readline
sys.setrecursionlimit(10**9)
n=int(input())
edges=[[] for i in range(n)]
for i in range(n-1):
    a,s,w=map(int,input().split())
    edges[a-1].append([s-1,w]);edges[s-1].append([a-1,w])
colors=[-1]*n
colors[0]=1
def dfs(now):
    for to,cost in edges[now]:
        if colors[to]==-1:
            colors[to]=(cost+colors[now])%2
            dfs(to)

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import math
N = int(input())
graph = [{} for _ in range(N)]

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

d = [-1 for _ in range(N)]
src = 0
d[src] = 0
buf = [src]

while buf:
    src = buf.pop()
    for dst, w in graph[src].items():
        if d[dst] == -1:
            d[dst] = d[src] + w
            buf.append(dst)

for n in d:
    if n % 2:
        print(0)
    else:
        print(1)

Submission status: Accepted

Solution code:
n=int(input())
edges=[[] for i in range(n)]
import sys

sys.setrecursionlimit(10**7)
for i in range(n-1):
    a,s,w=map(int,input().split())
    edges[a-1].append([s-1,w]);edges[s-1].append([a-1,w])
colors=[-1]*n
colors[0]=1
def dfs(now):
    for to,cost in edges[now]:
        if colors[to]==-1:
            colors[to]=(cost+colors[now])%2
            dfs(to)

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

Submission status: Accepted

Solution code:
n=int(input())
edges=[[] for i in range(n)]
import sys

sys.setrecursionlimit(10**9)
for i in range(n-1):
    a,s,w=map(int,input().split())
    edges[a-1].append([s-1,w]);edges[s-1].append([a-1,w])
colors=[-1]*n
colors[0]=1
def dfs(now):
    for to,cost in edges[now]:
        if colors[to]==-1:
            colors[to]=(cost+colors[now])%2
            dfs(to)

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

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10**6)

n = int(input())
if n == 1:
    print(1)
else:
    edge=[[] for _ in range(n)]
    for _ in range(n-1):
        u,v,w = map(int,input().split())
        edge[u-1].append((v-1,w%2))
        edge[v-1].append((u-1,w%2))
 
    color =[-1]*n
    def dfs(node,edge):
        for next_node,w in edge[node]:
            if color[next_node] != -1:
                continue
            if w == 1:
                color[next_node] = color[node]^1
            elif w == 0:
                color[next_node] = color[node]
            dfs(next_node,edge)
        
        
    color[0] = 0
    dfs(0,edge)
    print(*color,sep="\n")

Submission status: Accepted

Solution code:
import sys
from collections import deque
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
n = int(input())
edges = [[]for _ in range(n)]
for _ in range(n-1):
    u, v, w = map(int, input().split())
    edges[u-1].append((w, v-1))
    edges[v-1].append((w, u-1))

next_v = deque([(0, 0)])
color = [-1]*n
while next_v:
    d, v = next_v.popleft()
    color[v] = d & 1
    for d2, v2 in edges[v]:
        if color[v2] != -1:
            continue
        next_v.append((d+d2, v2))
print(*color, sep='\n')

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
n = int(input())
edges = [[]for _ in range(n)]
for _ in range(n-1):
    u, v, w = map(int, input().split())
    edges[u-1].append((w, v-1))
    edges[v-1].append((w, u-1))


color = [-1]*n


def dfs(v, d, parent):
    color[v] = d & 1
    for d2, v2 in edges[v]:
        if v2 == parent:
            continue
        dfs(v2, d+d2, v)


dfs(0, 0, -1)
print(*color, sep='\n')

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N=int(readline())
m=map(int,read().split())
UVW=zip(m,m,m)

graph =[[] for i in range(N+1)]
for u,v,w in UVW:
    graph[u].append((v,w))
    graph[v].append((u,w))

color=[0]*(N+1)
parent=[0]*(N+1)
stack=[1]
while stack:
    x=stack.pop()
    for dst,w in graph[x]:
        if (dst==parent[x]):
            continue
        stack.append(dst)
        color[dst]=color[x]^(w&1)
        parent[dst]=x

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N=int(readline())
m=map(int,read().split())
UVW=zip(m,m,m)

graph =[[] for i in range(N+1)]
for u,v,w in UVW:
    graph[u].append((v,w))
    graph[v].append((u,w))
color=[0]*(N+1)

def dfs(cur,par,dist):
    color[cur]=dist
    for dst,w in graph[cur]:
        if (dst==par):
            continue
        dfs(dst,cur,dist^(w&1))
dfs(1,-1,0)
print('\n'.join(map(str,color[1:])))

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.readline
from heapq import heapify, heappush, heappop

def dijkstra(path, N, a):
    visited = [False] * N
    que = [(0, a)]
    heapify(que)  # 始点aから各頂点への(距離, 頂点ID)
    dist = [-1] * N  # 始点aから各頂点への距離
    dist[a] = 0  # 始点aからaへの距離は0
    while que:
        d, v = heappop(que)  # 始点から最短距離の頂点を(確定ノード)を取り出す
        visited[v] = True  # 確定フラグを立てる
        # 接続先ノードの情報を更新する
        for d, to in path[v]:
            cost = dist[v] + d
            if dist[to] < 0 or cost < dist[to]:
                dist[to] = cost
                if not visited[to]:
                    heappush(que, (cost, to))

    return dist

def main():
    N = int(input())
    path = [[] for _ in range(N)]
    for _ in range(N-1):
        u, v, w = map(int, readline().rstrip().split())
        path[u-1].append((w, v-1))
        path[v-1].append((w, u-1))
    
    G = dijkstra(path, N, 0)
    for i in range(N):
        if G[i] % 2 == 0:
            print(0)
        else:
            print(1)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

n = int(input())
G = [[] for _ in range(n)]
for i in range(n-1):
  uvw = list(map(int, input().split()))
  u = uvw[0]-1
  v = uvw[1]-1
  w = uvw[2]
  G[u].append([v, w])
  G[v].append([u, w])
  
color = [-1]*n
def dfs(G, v, cur = 0):
  if color[v] == -1:
    
    color[v] = cur
    for next_v, w in G[v]:
     
      if color[next_v]==-1:
        if (w % 2 != 0):
          dfs(G, next_v, 1-cur)
        if (w% 2 == 0):
          dfs(G, next_v, cur)
        continue
      


        

for v in range(n):
  if color[v] != -1:
    continue
  else:
    dfs(G, v)


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

Submission status: Accepted

Solution code:
"""
created 2020-05-11
"""
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

def main():
    N,*uvw = map(int, read().split())

    E = [[] for _ in range(N+1)]
    for u, v, w in zip(*[iter(uvw)]*3):
        E[u].append((v, w))
        E[v].append((u, w))
    
    color = [-1] * (N+1)
    color[1] = 0
    
    d = [-1] * (N+1)
    d[1] = 0
    def dfs(s):
        stack = [s]

        while stack:
            v = stack.pop()
            for e, w in E[v]:
                if d[e] == -1:
                    d[e] = d[v] + w
                    if d[e] % 2 == 0:
                        color[e] = 0
                    else:
                        color[e] = 1
                    stack.append(e)
    
    dfs(1)

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


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N = int(input())

u_list = []
v_list = []
w_list = []

for _ in range(N-1):
  u, v, w = map(int, input().split())
  u_list.append(u-1)
  v_list.append(v-1)
  w_list.append(w)
  
color_dict = dict()
uvw_list = list(zip(u_list, v_list, w_list))
color_dict[u_list[0]] = 1

def eval_single(u, v, w, color_dict):
  skip = True

  if u in color_dict:
    color_dict[v] = assign_color(color_dict[u], w)
    skip = False
    
  if v in color_dict:
    color_dict[u] = assign_color(color_dict[v], w)
    skip = False
    
  return skip, color_dict
  

def assign_color(color, w):
  if w%2==0:
    return color
  else:
    return color*(-1)+1
  
while True:
  ind_list = []
  for ind, (u, v, w) in enumerate(uvw_list):
    skip, color_dict = eval_single(u, v, w, color_dict)
    
    if skip:
      ind_list.append(ind)

  uvw_list = [uvw_list[ind] for ind in ind_list]
  
  if len(color_dict) == N:
    break

for i in range(N):
  print(color_dict[i])

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
def main():
  n=int(input())
  uvw=[list(map(int,input().split())) for _ in range(n-1)]
  ki=[[] for _ in range(n)]
  for u,v,w in uvw:
    ki[u-1].append((v-1,w))
    ki[v-1].append((u-1,w))
  todo=[0]
  seen=[-1]*n
  seen[0]=0
  while len(todo)>0:
    a=todo.pop()
    l=ki[a]
    for li in l:
      if seen[li[0]]==-1:
        seen[li[0]]=seen[a] if li[1]%2==0 else (seen[a]+1)%2
        todo.append(li[0])
  for s in seen:
    print(s)
if __name__=='__main__':
  main()

Submission status: Accepted

Solution code:
N = int(input())
uvw = [list(map(int,input().split())) for i in range(N-1)]

graph = [[] for _ in range(N+1)]
for u,v,w in uvw:
    graph[u].append((v,w))
    graph[v].append((u,w))

ans = [0] * (N+1)

from collections import deque
todo = deque([(1,0)])
seen = [-1] * (N+1)

while todo:
    v,d = todo.pop()
    seen[v] = 0
    if d % 2 == 0:
        ans[v] = 0
    else:
        ans[v] = 1
    for u,w in graph[v]:
        if seen[u]== 0:
            continue
        todo.append((u,d+w))

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

Submission status: Accepted

Solution code:
from collections import deque

N = int(input())
connected = [[] for _ in range(N)]
for i in range(N-1):
    u,v,w = (int(x) for x in input().split())
    connected[u-1].append((v-1,w))
    connected[v-1].append((u-1,w))
colors = [None] * N
colors[0] = 0
d = deque()
parents = deque()
for edge in connected[0]:
    if edge[1] % 2 == 0:
        colors[edge[0]] = 0
        d.append((edge[0],0))
    else:
        colors[edge[0]] = 1
        d.append((edge[0],1))
    parents.append(0)
while d:
    temp = d.popleft()
    parent = parents.popleft()
    for edge in connected[temp[0]]:
        if edge[0] != parent:
            if edge[1] % 2 == 0:
                colors[edge[0]] = temp[1]
                d.append((edge[0],temp[1]))
            else:
                if temp[1] == 0:
                    colors[edge[0]] = 1
                    d.append((edge[0],1))
                else:
                    colors[edge[0]] = 0
                    d.append((edge[0],0))
            parents.append(temp[0])
for x in colors:
    print(x)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7) #再帰関数の呼び出し制限

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

def dfs(v, p, c): #pを親にもつvをcにする
    color[v] = c #vをcに着色
    for i in g[v]:
        nv, w = i[0], i[1]
        if nv == p: continue #次の点が親なら何もしない
        else:
            if w % 2 == 1: 
                dfs(nv, v, 1-c) #奇数なら違う色
            else:
                dfs(nv, v, c) #偶数なら同じ色
    

color = [-1]*(N+1) #1-index
dfs(1,-1,1) #どこでもいいが点１から開始。色は０

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

Submission status: Accepted

Solution code:
from collections import deque
# from fractions import gcd # >=Python3.5
# from math import gcd # <Python3.5

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

road = [[] for i in range(n)]
cost = [[] for i in range(n)]

for i in li:
  i[0]-=1
  i[1]-=1
  road[i[0]].append(i[1])
  road[i[1]].append(i[0])
  cost[i[0]].append(i[2]%2)
  cost[i[1]].append(i[2]%2)

dist = [-1]*n
que  = deque()
dist[0] = 0
que.append(0)

while(len(que)!=0):
  # BFS/DFS
  v = que.popleft()
  for i,r in enumerate(road[v]):
    if dist[r]!=-1:
      continue
    dist[r] = (dist[v]+cost[v][i])%2
    que.append(r)

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

Submission status: Accepted

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

def main():
    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])
    
    def dfs(x, co):
        if c[x] != -1:
            return
        c[x] = co
        directions = edge[x]
        for d in directions:
            t, w = d
            if w%2 != 0:
                nextco = abs(1-co)
            else:
                nextco = co
            dfs(t, nextco)
        
    c = [-1 for _ in range(N)]
    dfs(0, 0)
    for ans in c:
        print(ans)

main()

Submission status: Accepted

Solution code:
from collections import deque
def main():
    N = int(input())
    edge = [[] for _ in range(N)]
    for _ in range(N-1):
        u, v, w = map(int, input().split())
        edge[u-1].append([u-1, v-1, w])
        edge[v-1].append([v-1, u-1, w])
    
    
    c = [-1 for _ in range(N)]
    c[0] = 0
    que = deque(edge[0])
    while que:
        f, t, w = que.pop()
        if w%2 == 0:
            c[t] = c[f]
        else:
            c[t] = abs(1 - c[f])
        
        directions = edge[t]
        for d in directions:
            if c[d[1]] == -1:
                que.append(d)
            else:
                continue
    for ans in c:
        print(ans)
main()

Submission status: Accepted

Solution code:
from collections import deque
import sys
input = sys.stdin.readline
N=int(input())
ki=[[] for f in range(N)]
for i in range(N-1):
 u,v,w = map(int,input().split())
 ki[u-1].append([v-1,w%2])
 ki[v-1].append([u-1,w%2])
stack = deque([[0,0]])
check = [0]*N #チェック済みリスト
ans=[2]*N
ans[0]=0
while stack != deque([]) :
 a=stack.pop()
 ne=a[0]
 if check[ne]==0:
  check[ne]=1
  for i in range(len(ki[ne])):
   eda=ki[ne][i][0]
   edanum=ki[ne][i][1]
   edaans=(edanum+ans[ne])%2
   if check[eda]==0:
    stack.append([eda,edaans])
    ans[eda]=edaans
for i in ans:
 print(i)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
N=int(input())
ki=[[] for f in range(N)]
for i in range(N-1):
 u,v,w = map(int,input().split())
 ki[u-1].append([v-1,w%2])
 ki[v-1].append([u-1,w%2])
stack = [[0,0]]
check = [0]*N #チェック済みリスト
ans=[2]*N
ans[0]=0
while stack != [] :
 a=stack.pop()
 ne=a[0]
 if check[ne]==0:
  check[ne]=1
  for i in range(len(ki[ne])):
   eda=ki[ne][i][0]
   edanum=ki[ne][i][1]
   edaans=(edanum+ans[ne])%2
   if check[eda]==0:
    stack.append([eda,edaans])
    ans[eda]=edaans
for i in ans:
 print(i)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
N=int(input())
ki=[[] for f in range(N)]
for i in range(N-1):
 u,v,w = map(int,input().split())
 ki[u-1].append([v-1,w%2])
 ki[v-1].append([u-1,w%2])
stack = [[0,0]]
check = [0]*N #チェック済みリスト
ans=[2]*N
ans[0]=0
while stack != [] :
 a=stack.pop()
 ne=a[0]
 if check[ne]==0:
  check[ne]=1
  for i in range(len(ki[ne])):
   if check[ki[ne][i][0]]==0:
    stack.append([ki[ne][i][0],(ki[ne][i][1]+ans[ne])%2])
    ans[ki[ne][i][0]]=(ki[ne][i][1]+ans[ne])%2
for i in ans:
 print(i)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
N=int(input())
ki=[[] for f in range(N)]
for i in range(N-1):
 u,v,w = map(int,input().split())
 ki[u-1].append([v-1,w%2])
 ki[v-1].append([u-1,w%2])
stack = [[0,0]]
check = [0]*N #チェック済みリスト
ans=[2]*N
ans[0]=0
while stack != [] :
 a=stack.pop()
 if check[a[0]]==0:
  check[a[0]]=1
  for i in range(len(ki[a[0]])):
   if check[ki[a[0]][i][0]]==0:
    stack.append([ki[a[0]][i][0],(ki[a[0]][i][1]+ans[a[0]])%2])
    ans[ki[a[0]][i][0]]=(ki[a[0]][i][1]+ans[a[0]])%2
for i in ans:
 print(i)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(200000)
n = int(input())
graph = {i: [] for i in range(1, n + 1)}
for _ in range(n - 1):
    u, v, ww = map(int, input().split())
    graph[u].append([v,ww])
    graph[v].append([u,ww])
color = [-1] * n

def dfs(x):
    for sub in graph[x]:
        next = sub[0]
        lon = sub[1]
        if color[next - 1] != -1:
            continue
        if lon % 2 == 0:
            color[next - 1] = color[x - 1]
        else:
            if color[x - 1] == 1:
                color[next - 1] = 0
            else:
                color[next - 1] = 1
        dfs(next)

color[0] = 0
dfs(1)
for i in color:
    print(i)

Submission status: Accepted

Solution code:
from collections import defaultdict
import sys
sys.setrecursionlimit(10**5)
def solve():
    N = int(input())
    G = defaultdict(list)
    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))

    res = [0] * N
    dfs(0,-1,1,G,res)

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

def dfs(v,p,c,G,res):
    res[v] = c

    for e in G[v]:
        if e[0] == p:
            continue
        if e[1] % 2 == 0:
            dfs(e[0],v,c,G,res)
        else:
            dfs(e[0],v,1-c,G,res)
        
if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
from collections import defaultdict
import sys
sys.setrecursionlimit(10**5)
def solve():
    N = int(input())
    G = defaultdict(list)
    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))

    res = [0] * N

    dfs(0,-1,1,G,res)

    print(*res, sep='\n')
def dfs(v,p,c,G,res):
    res[v] = c
    for e in G[v]:
        if e[0] == p:
            continue
        if e[1] % 2 != 0:
            dfs(e[0], v, 1-c,G,res)
        else:
            dfs(e[0],v,c,G,res)
        
if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**9)
n = int(input())
graph = [[]for i in range(n)]
for i in range(n-1):
    pre = list(map(int,input().split()))
    graph[pre[0]-1].extend([pre[1]-1,pre[2]])
    graph[pre[1]-1].extend([pre[0]-1,pre[2]])
seen = [0 for i in range(n)]
color = [-1 for i in range(n)]

def DFS(x):
    if seen[x] == 1:
        return 0
    else:
        pass
    seen[x] = 1
    for i in range(len((graph[x]))//2):
        if graph[x][2*i+1] % 2 == 0:
            color[graph[x][2*i]] = color[x]
        else:
            color[graph[x][2*i]] = not color[x]

    for i in range(len((graph[x]))//2):
        DFS(graph[x][2*i])

color[0] = True
DFS(0)
for i in range(n):
    print(int(color[i]))

Submission status: Accepted

Solution code:
printn = lambda x: print(x,end='')
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True # and False
BIG = 10**18
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)

n = inn()
dst = [{} for i in range(n+1)]
for i in range(n-1):
    u,v,w = inm()
    dst[u][v] = dst[v][u] = w
q = [1]
d = [BIG]*(n+1)
d[1] = 0
while len(q)>0:
    x = q.pop()
    for y in dst[x]:
        if d[y]==BIG:
            d[y] = d[x]+dst[x][y]
            q.append(y)
for i in range(1,n+1):
    print(d[i]%2)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(500*500)

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

nbors = [[] for _ in range(N+1)]
for uvw in UVW:
    u,v,w = uvw[0], uvw[1], uvw[2]
    nbors[u].append((v, w))
    nbors[v].append((u, w))

dist = [-1] * (N+1)
dist[1] = 0
def dfs(now, nxt, w):
    if dist[nxt] >= 0:
        return
    dist[nxt] = dist[now] + w
    for nbor in nbors[nxt]:
        nxt2, w = nbor[0], nbor[1]
        dfs(nxt, nxt2, w)

for nbor in nbors[1]:
    nxt, w = nbor[0], nbor[1]
    dfs(1, nxt, w)

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(500*500)
N = int(sys.stdin.readline())
edges = [list(map(int,sys.stdin.readline().split())) for _ in range(N - 1)]
A = [[] for _ in range(N + 1)]
 
for edge in edges:
    A[edge[0]].append([edge[1],edge[2]])
    A[edge[1]].append([edge[0],edge[2]])
 
depth = [-1] * (N + 1)
depth[1] = 0
 
def dfs(A,s):
    for v in A[s]:
        if depth[v[0]] == -1:
            depth[v[0]] = depth[s] + v[1]
            dfs(A,v[0])    
dfs(A,1)
for d in depth[1:]:
    if d % 2 == 0:
        print(0)
    else:
        print(1)

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    import heapq

    N = int(input())
    edges = [[] for _ in range(N+1)]
    for _ in range(N-1):
        u,v,w = map(int,input().split())
        edges[u].append((v,w))
        edges[v].append((u,w))
    
    colors = [-1]*(N+1)
    que = [(0,1)]
    heapq.heapify(que)
    while que:
        c,n = heapq.heappop(que)
        if colors[n] == -1:
            colors[n] = c
            for nx,w in edges[n]:
                if w%2==0:
                    nxC = c
                else:
                    nxC = (c+1)%2
                heapq.heappush(que,(nxC,nx))

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

main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.buffer.readline
from collections import deque

def main():
    N = int(input())
    edge = [[] for _ in range(N)]
    dist = [-1]*N
    dist[0] = 0
    
    for _ in range(N-1):
        a,b,c = map(int,input().split())
        edge[a-1].append((b-1,c))
        edge[b-1].append((a-1,c))
        
    que = deque([0])
    while que:
        now = que.pop()
        for fol,d in edge[now]:
            if dist[fol] != -1:
                continue
            dist[fol] = dist[now]+d
            que.append(fol)
            
    for i in range(N):
        print(dist[i]%2)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**9)
n = int(input())
T = [[] for _ in range(n)]
for _ in range(n-1):
    u,v,w = map(int,input().split())
    u -= 1
    v -= 1
    w %= 2
    T[u].append((v,w))
    T[v].append((u,w))

ans = [0]*n
def dfs(u,p=-1,c=0):
    for v,w in T[u]:
        if v == p: continue
        nc = (c+1)%2 if w else c 
        ans[v] = nc
        dfs(v,u,nc)
dfs(0)

print("\n".join(map(str,ans)))

Submission status: Accepted

Solution code:
# D
n = int(input())
tree = [[] for _ in range(n)]

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

# 白:0 黒:1 未定:-1
color = [-1] * n
q = [(0, 0)]

while q:  # qが存在する間
    a, b = q.pop()
    color[a] = b  # a番目をb色に染める
    for c, d in tree[a]:
        if color[c] == -1:  # 行き先が捜索済みでない
            q += [(c, b ^ d)] #(行き先ｃ ,和が奇数の時１ 偶数 0)
print(*color, sep='\n')

Submission status: Accepted

Solution code:
from collections import defaultdict


def main():
    N = int(input())
    adj_nodes = defaultdict(list)
    weights = defaultdict(int)
    for _ in range(N - 1):
        u, v, w = list(map(int, input().split(' ')))
        u -= 1
        v -= 1
        adj_nodes[u].append(v)
        adj_nodes[v].append(u)
        weights[(u, v)] = w
        weights[(v, u)] = w
    # calculate distance from node 0
    frontier = [0]
    dist = [0 for _ in range(N)]
    explored = [0 for _ in range(N)]
    while len(frontier) > 0:
        node = frontier.pop()
        explored[node] = 1
        for next_node in adj_nodes[node]:
            if explored[next_node] == 1:
                continue
            frontier.append(next_node)
            dist[next_node] = dist[node] + weights[(node, next_node)]
    # color: 0 = dist is even / 1 = dist is odd
    for node in range(N):
        print(dist[node] % 2)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque

N = int(input())

A = []
while True:
    try:
        temp=list(map(int,input().split()))
        A.append(temp)
    except:
        break;
#print(A)
To = [[] for i in range(N)]
Cost = [[] for i in range(N)]
for i in range(len(A)):
  #print(A[i])
  To[A[i][0]-1].append(A[i][1]-1)
  To[A[i][1]-1].append(A[i][0]-1)
  Cost[A[i][0]-1].append(A[i][2])
  Cost[A[i][1]-1].append(A[i][2])
#print(To,Cost)

ans = [-1]*N #到達未到達を判定するために-1を初期値として与える。
ans[0] = 0  #0を根にして、0とパリティが一致する場合には0とする。
Queue = deque([])
Queue.append(0) #0を根にする

while Queue:
  v = Queue.popleft() #vは点
  for i in range(len(To[v])): #vから行けるリストつまりToの中にある点の数だけ回す。
    u = To[v][i] #vから行ける点
    w = Cost[v][i] #その点に行くためのコスト
    if ans[u] != -1: #すでに訪れていたらスキップ
      continue
    ans[u] = (ans[v]+w)%2
    Queue.append(u)
print(*ans, sep="\n")