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:
def main():
    import sys
    input = sys.stdin.buffer.readline
    N = int(input())
    edge = [[] for _ in range(N)]
    for i in range(N-1):
        a, b, c = (int(i) for i in input().split())
        edge[a-1].append((c % 2, b-1))
        edge[b-1].append((c % 2, a-1))

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

    def dfs(v, G):
        todo = []
        dist[v] = 0
        color[v] = 0
        todo.append((v, 0)) #最初は0でappend
        while todo:
            u, s = todo.pop() #ここでpopしちゃう
            if s == 0:
                # s==0: 潜っていく時の処理
                todo.append((u, 1)) #1でappendして戻り処理の仕込み
                for c, next_v in G[u]:
                    if dist[next_v] != -1:
                        continue
                    dist[next_v] = dist[u] + c
                    if dist[next_v] % 2 == 1:
                        color[next_v] = 1
                    else:
                        color[next_v] = 0
                    todo.append((next_v, 0))
                    #break
            #else:
            #    s==1: 戻ってくる時の処理(この問題では特にやることなし)

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


if __name__ == '__main__':
    main()

Submission status: Accepted

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

def dfs(i):
    # if all([v != -1 for v in visited]):
    #     return
    color = visited[i]
    for nextIdx, wgt in graph[i]:
        if visited[nextIdx] == -1:
            if wgt % 2 == 0:
                visited[nextIdx] = color
            else:
                visited[nextIdx] = int(not color)
            dfs(nextIdx)

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

visited = [-1] * n
visited[0] = 0
dfs(0)
for v in visited:
    print(v)

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
stack = [0]
while stack:
    u = stack.pop()
    d = dist[u]

    for v,w in edge[u]:
        if dist[v] > 0:
            continue
        dist[v] = d + w
        stack.append(v)

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

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
que = [0]
while que:
    u = que.pop()
    d = dist[u]

    for v,w in edge[u]:
        if dist[v] > 0:
            continue
        dist[v] = d + w
        que.append(v)

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

Submission status: Accepted

Solution code:
def main():
    import sys
    from collections import deque
    input = sys.stdin.buffer.readline
    N = int(input())
    edge = [[] for _ in range(N)]
    for i in range(N-1):
        a, b, c = (int(i) for i in input().split())
        edge[a-1].append((c, b-1))
        edge[b-1].append((c, a-1))

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

    def dfs(v, G):
        todo = deque()
        dist[v] = 0
        color[v] = 0
        todo.append(v)
        while todo:
            u = todo.pop()
            for c, next_v in G[u]:
                if dist[next_v] != -1:
                    continue
                dist[next_v] = dist[u] + c
                if dist[next_v] % 2 == 1:
                    color[next_v] = 1
                else:
                    color[next_v] = 0
                todo.append(next_v)

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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.buffer.readline
    N = int(input())
    edge = [[] for _ in range(N)]
    for _ in [0]*(N-1):
        a, b, c = (int(i) for i in input().split())
        edge[a-1].append((c % 2, b-1))
        edge[b-1].append((c % 2, a-1))

    from collections import deque
    dist = [-1]*N
    color = [-1]*N

    def bfs(s, G):
        que = deque()
        dist[s] = 0
        color[s] = 0
        que.append(s)
        while que:
            u = que.popleft()
            for c, v in G[u]:
                if dist[v] != -1:
                    continue
                dist[v] = (dist[u] + c) % 2
                if dist[v] % 2 == 1:
                    color[v] = 1
                else:
                    color[v] = 0
                que.append(v)

    bfs(0, edge)
    print(*color, sep="\n")
    # print("\n", *dist, sep="\n")


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys

if sys.getrecursionlimit()<10**7:
    sys.setrecursionlimit(10**7)

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

def dfs(i,col):
    his[i]=col
    for j,w in ver[i]:
        if his[j]==-1:
            if w%2==0:
                dfs(j,col)
            else:
                dfs(j,(col+1)%2)

dfs(0,0)            
for i in range(N):
    print(his[i])

Submission status: Accepted

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

N = int(input())
INF = 10**18
edges = [[] for _ in range(N)]

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

dist = [INF] * N
que = deque([(0, 0)])

while que:
    now, d = que.pop()

    if dist[now] <= d:
        continue
    dist[now] = d
    for to, w in edges[now]:
        que.append((to, d + w))

ans = [dist[i] % 2 for i in range(N)]
print(*ans, sep='\n')

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**9)
N = int(input())
edge = [[] for _ in range(N)]

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

ret = [0] * N
def dfs(pv, v, dist):
    ret[v] = dist
    for nv, w in edge[v]:
        if nv == pv:
            continue
        dfs(v, nv, (dist+w)%2)

dfs(-1,0,0)
print(*ret, sep="\n")

Submission status: Accepted

Solution code:
from collections import deque
n = int(input())
edge = []
for i in range(n+1):
    edge.append([])
for i in range(n-1):
    u,v,w = map(int,input().split())
    edge[u].append([v,w])
    edge[v].append([u,w])
ans = [0] * (n+1)


def breadth_first_search(edge):
    work_q = deque([1])
    visited = set()
    visited.add(1)
    while work_q:
        here = work_q.popleft()
        col = ans[here]
        for i in edge[here]:
            if i[0] not in visited:
                work_q.append(i[0])
                visited.add(i[0])
                if i[1] % 2 == 0 and col == 0:
                    ans[i[0]] = 0
                elif i[1] % 2 != 0 and col == 0:
                    ans[i[0]] = 1
                elif i[1] % 2 == 0 and col == 1:
                    ans[i[0]] = 1
                elif i[1] % 2 != 0 and col == 1:
                    ans[i[0]] = 0


breadth_first_search(edge)
for i in range(1,n+1):
    print(ans[i])

Submission status: Accepted

Solution code:
import sys
#sys.setrecursionlimit(10**6)
input = sys.stdin.readline

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

from collections import deque
s = deque()
s.append(0)
visit = [-1]*n
visit[0] = 0
while s:
    u = s.pop()
    for v, w in g[u]:
        if visit[v] == -1:
            if w%2 == 0:
                visit[v] = visit[u]
            else:
                visit[v] = 1 - visit[u]
            s.append(v)
for i in range(n):
    print(visit[i])

Submission status: Accepted

Solution code:
from collections import deque

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
que = deque([0])
while que:
    u = que.popleft()
    d = dist[u]

    for v,w in edge[u]:
        if dist[v] > 0:
            continue
        dist[v] = d + w
        que.append(v)

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

Submission status: Accepted

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

    ans = [-1] * N
    ans[0] = 0
    stack = [(0,0)]
    while stack:
        v, w = stack.pop()
        for to, to_w in G[v]:
            if ans[to] >= 0: continue
            ans[to] = 1 if (w + to_w) & 1 else 0
            stack.append((to, w + to_w))
    
    for a in ans: print(a)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
from collections import deque

def solve():
    input = sys.stdin.readline
    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))

    Col = [-1] * N
    q = deque()
    q.append((0, 0, 0)) #now, pre, dist
    while q:
        nn, pn, dist = q.pop()
        if Col[nn] == -1:
            Col[nn] = dist % 2
            for nextN, addW in Edge[nn]:
                if pn != nextN:
                    q.append((nextN, nn, dist + addW))
    print("\n".join(map(str, Col)))

    return 0

if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)
N = int(input())
UVW = [tuple(map(int,input().split())) for i in range(N-1)]
es = [[] for _ in range(N)]
for u,v,w in UVW:
    u,v = u-1,v-1
    es[u].append((v,w))
    es[v].append((u,w))

ans = [-1]*N
ans[0] = 0
def dfs(v,p=-1):
    for to,d in es[v]:
        if to==p: continue
        if d%2:
            ans[to] = 1 - ans[v]
        else:
            ans[to] = ans[v]
        dfs(to,v)
dfs(0)
print(*ans, sep='\n')

Submission status: Accepted

Solution code:
from collections import deque
from collections import Counter
from itertools import product, permutations,combinations
from operator import itemgetter
from heapq import heappop, heappush
import math
import sys
input = sys.stdin.readline
#文字列のときはうまく行かないのでコメントアウトすること
sys.setrecursionlimit(2147483647)

def main():
  N = int(input())
  G = [[] for i in range(N)]
  C = [-1] * N
  C[0] = 0
  for i in range(N-1):
    u, v, w = map(int, input().split())
    u, v = u-1, v-1
    G[u].append((v,w))
    G[v].append((u,w))
  def dfs(now):
    for ne_xt, w in G[now]:
      if C[ne_xt]==-1:
        C[ne_xt]=(C[now]+w)%2
        dfs(ne_xt)
  dfs(0)
  for i in range(N):
    print(C[i])
  
  
if __name__ == '__main__':
  main()

Submission status: Accepted

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

readline = sys.stdin.readline
n = int(readline())
G = [[] for _ in range(n)]
ans = [-1] * n
for _ in range(n-1):
    u, v, w = map(int, readline().split())
    u -= 1
    v -= 1
    G[u].append((v, w))
    G[v].append((u, w))
q = [0]
ans[0] = 1
while q:
    x = q.pop()
    for i, d in G[x]:
        if ans[i] != -1:
            continue
        if d % 2:
            ans[i] = int(not ans[x])
        else:
            ans[i] = ans[x]
        q.append(i)
print(*ans, sep='\n')

Submission status: Accepted

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

def dfs(v, p, c):
    color[v] = c
    for vi, wi in g[v]:
        if vi == p: continue
        if wi % 2: dfs(vi, v, 1-c)
        else: dfs(vi, v, c)
    return color

n = int(input())
g = [[] for _ in range(n)]
for _ 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))

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

Submission status: Accepted

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

def dfs(v, p, c):
    color[v] = c
    for vi, wi in g[v]:
        if vi == p: continue
        if wi % 2 == 0: dfs(vi, v, c)
        else: dfs(vi, v, 1-c)
    return color

n = int(input())
g = [[] for _ in range(n)]
for _ 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))

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

Submission status: Accepted

Solution code:
import sys

input_methods=['clipboard','file','key']
using_method=0
input_method=input_methods[using_method]

IN=lambda : map(int, input().split())
mod=1000000007

#+++++

def main():
	n = int(input())
	dd=[[] for i in range(n)]
	
	
	for i in range(n-1):
		na, nb , dist = IN()
		dd[na-1].append((nb-1, dist))
		dd[nb-1].append((na-1, dist))
	#parent, parent_color, current, dist
	
	stock=[(0,0,0)]
	ret=[0]*n
	
	while len(stock)>0:
		(pn, cn, cc) = stock.pop()
		#pa(len(stock))
		#print(pn,pc,cn,di)
		for next_n, dist in dd[cn]:
			if next_n==pn:
				continue
				
			paint_color = cc
			if dist % 2 == 1:
				paint_color = (cc + 1)%2
			ret[next_n] = paint_color
			stock.append((cn, next_n,paint_color))
			
	for color in ret:
		print(color)
	
	
	
	
#+++++
isTest=False

def pa(v):
	if isTest:
		print(v)
		
def input_clipboard():
	import clipboard
	input_text=clipboard.get()
	input_l=input_text.splitlines()
	for l in input_l:
		yield l

if __name__ == "__main__":
	if sys.platform =='ios':
		if input_method==input_methods[0]:
			ic=input_clipboard()
			input = lambda : ic.__next__()
		elif input_method==input_methods[1]:
			sys.stdin=open('inputFile.txt')
		else:
			pass
		isTest=True
	else:
		pass
		#input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)

Submission status: Accepted

Solution code:
inputs = open(0).readlines()
n = int(inputs[0])
uvw = [list(map(int, uvw.split())) for uvw in inputs[1:]]

def dfs(root, option):
    nodes, stack = {}, [(root, 0)]
    while stack:
        current_node, color = stack.pop()
        if current_node in nodes:
            continue
        nodes[current_node] = color
        for n, w in get_next_nodes(current_node):
            if n not in nodes:
                stack.append((n, (color + w) % 2))
    return nodes

def get_next_nodes(node):
    return lst[node].items()

lst = [{} for _ in range(n)]
for u, v, w in uvw:
    lst[u-1][v-1] = lst[v-1][u-1] = w

dct = dfs(0, get_next_nodes)
for i in range(max(dct)+1):
    print(dct[i])

Submission status: Accepted

Solution code:
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))
distance = [-1]*n
distance[0] = 0
q = [0]
while q:
  p = q.pop()
  for a,b in g[p]:
    if distance[a] == -1:
      distance[a] = distance[p]+b
      q.append(a)
for i in range(n):
  print((distance[i])%2)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
n = int(input())
d = {}
graph = {i:[] for i in range(n)}
for _ in range(n-1):
  u,v,w = map(int,input().split())
  d[(u-1,v-1)] = w
  graph[u-1].append(v-1)
  graph[v-1].append(u-1)
  
  
color = [-1 for i in range(n)] 
color[0] = 0
from collections import deque
queue =deque([0])

while queue:
  p = queue.popleft()
  color_p = color[p]
  for i in graph[p]:
    if color[i] != -1:
      continue
    else:
      if d[(min(i,p),max(i,p))] %2:
        color[i] = 1 - color_p
      else:
        color[i] = color_p
      queue.append(i)

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

Submission status: Accepted

Solution code:
from sys import stdin
from collections import deque
def main():
    #入力
    readline=stdin.readline
    N=int(readline())
    g=[[] for _ in range(N)]
    for _ in range(N-1):
        u,v,w=map(int,readline().split())
        u-=1
        v-=1
        g[u].append((v,w))
        g[v].append((u,w))

    #0からの距離を幅優先探索
    d=[0]*N
    is_searched=[False]*N
    is_searched[0]=True
    que=deque([0])
    while len(que)>=1:
        now=que.popleft()
        for x in g[now]:
            if is_searched[x[0]]==False:
                is_searched[x[0]]=True
                d[x[0]]=d[now]+x[1]
                que.append(x[0])

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

if __name__=="__main__":
    main()

Submission status: Accepted

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

def dfs(v,p,dist):
    for u,w in tree[v]:
        if u==p:
            continue
        else:
            dist[u]=dist[v]+w
            dfs(u,v,dist)
    
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,dist)

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

Submission status: Accepted

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

def dfs(v, p, dist):
    for u, w in tree[v]:
        if u == p:
            continue
        else:
            dist[u] = dist[v] + w
            dfs(u, v, dist)
 
 
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 for _ in range(n)]
dfs(0, -1, dist)
 
for i in dist:
    if i % 2 == 0:
        print(0)
    else:
        print(1)

Submission status: Accepted

Solution code:
import sys
from collections import deque

sys.setrecursionlimit(100000000)
n = int(input())
G = [[] for _ in range(n)]  # 頂点の個数分準備
for i in range(n - 1):  # 辺の数は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
ans[0] = 0
que = deque([0])
while que:
    tmp = que.popleft()  # 幅優先探索
    for u, w in G[tmp]:
        if ans[u] != -1:  # すでに訪問済みの時
            continue
        ans[u] = ans[tmp] + w  # 辺の長さを追加
        que.append(u)  # queに追加

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

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(100000000)


def dfs(u, c):  # 引数には頂点の番号と色を入れる
    ans[u] = c  # 探索済みにする
    for v, w in G[u]:
        if ans[v] != -1:  # 探索していた時はスルー
            continue
        if ans[v] != c and w % 2 == 0:  # 距離が偶数で、未訪問あるいは色が違う時は同じ色にする
            dfs(v, c)
        elif ans[v] != c and w % 2 != 0:  # 距離が奇数で、未訪問あるいは色が違う時、違う色にする。
            dfs(v, 1-c)


n = int(input())
G = [[] for _ in range(n)]  # 頂点の個数分準備
for i in range(n-1):  # 辺の数は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
dfs(0, 0)
for a in ans:
    print(a)

Submission status: Accepted

Solution code:
from collections import deque
n = int(input())

mapping = [[] for i in range(n)]
#入力の受け取り
for i in range(n-1):
    u, v, w = map(int, input().split())
    mapping[u-1].append([u-1, v-1, w])
    mapping[v-1].append([v-1, u-1, w])

#壁の検出
already = [False]*n

depth = [0]*n

not_yet = deque(mapping[0])
already[0] = True
#始点の情報をnot_yetに入れる    
for u, v, w in mapping[0]:
    already[v] = True
#本番   
while not_yet:
    key = not_yet.popleft()
    u, v, w = key[0], key[1], key[2]
    depth[v] = (depth[u]+w)%2  
    
    for key in mapping[v]:
        if already[key[1]]:
            continue
        not_yet.append(key)
        already[key[1]] = True
    
for i in range(n):
    print(depth[i])

Submission status: Accepted

Solution code:
N = int(input())
g = [[[]for i in range(2)] for j in range(N)]

for i in range(N-1):
    u,v,d = map(int,input().split())
    if d%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)

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

stack = [0]
not_visit = [True for i in range(N)]
not_visit[0] = False

while stack:
    now = stack.pop()
    for h in range(2):
        if h == 0: #距離が偶数ならば
            for i in range(len(g[now][h])):
                if not_visit[g[now][h][i]]:
                    not_visit[g[now][h][i]] = False
                    ans[g[now][h][i]] = ans[now]
                    stack.append(g[now][h][i])
        if h == 1: #距離が奇数ならば
            for i in range(len(g[now][h])):
                if not_visit[g[now][h][i]]:
                    not_visit[g[now][h][i]] = False
                    ans[g[now][h][i]] = (ans[now] + 1)%2
                    stack.append(g[now][h][i])

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

Submission status: Accepted

Solution code:

import sys
sys.setrecursionlimit(100000000)
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]] 

color = [-1]*n 
def dfs(u, c):
  color[u] = c 
  for v, w in graph[u]:
    if color[v] != -1:
      continue
    if color[v] != c and w % 2 == 0:
      dfs(v, c)
    elif color[v] != c and w % 2 != 0:
      dfs(v, abs(1-c))

  return

dfs(0, 0)
for c in color:
  print(c)

Submission status: Accepted

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

import sys
#import numpy
#from collections import deque
sys.setrecursionlimit(10**5)

def input():
    return sys.stdin.readline().rstrip('\n')

N = int(input())

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

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

distances = [-1]*(N+1)
distances[1] = 0

def dfs(i):
    childs = childsof[i]

    for c in childs:
        j = c[0]
        if distances[j] == -1:
            distances[j] = distances[i] + c[1]
            dfs(j)

dfs(1)

for d in distances[1:]:
    if d % 2 == 0: #even
        print(0)
    else:
        print(1)

Submission status: Accepted

Solution code:
N = int(input())

checked = [False]*(N+1)
edges = [[] for i in range(N+1)]
ans = [0]*(N+1)
for i in range(N-1):
    u,v,w = list(map(int,input().split()))
    edges[u].append((v,w))
    edges[v].append((u,w))

stack = [(1,0)]
while stack:
    p = stack.pop()
    checked[p[0]] = True
    for np in edges[p[0]]:
        if not checked[np[0]]:
            stack.append((np[0],p[1]+np[1]))
            if (p[1]+np[1])%2:
                ans[np[0]] = 1

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

Submission status: Accepted

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


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


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 for _ in range(n)]
dfs(0, -1, dist)

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

Submission status: Accepted

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

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

for _ in range(N-1):
    a,b,c=map(int,input().split())
    a-=1
    b-=1
    Graph[a].append((b,c))
    Graph[b].append((a,c))

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

#探索
for v in range(N):
    if color[v]==-1:
        dfs(Graph,v)
for i in color:
    print(i)

Submission status: Accepted

Solution code:
from collections import deque

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

que = deque([1])
seen = [-1]*(N+1)
seen[1] = 0
cnt = 1
while cnt < N:
    cur = que.pop()
    for item in data[cur]:
        if seen[item[0]] == -1:
            seen[item[0]] = (seen[cur]+item[1]%2)%2
            cnt += 1
            que.append(item[0])

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

Submission status: Accepted

Solution code:
from collections import deque

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

que = deque([1])
seen = [-1]*(N+1)
seen[1] = 0
cnt = 1
while cnt < N:
    cur = que.popleft()
    for item in data[cur]:
        if seen[item[0]] == -1:
            seen[item[0]] = (seen[cur]+item[1]%2)%2
            cnt += 1
            que.append(item[0])

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

Submission status: Accepted

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

def dfs(i,j):
    color[i] = j
    for w,l in E[i]:
        if color[w] == -1:
            tj = j
            if l % 2 != 0:
                tj = int(not tj)
            dfs(w,tj)

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

Submission status: Accepted

Solution code:
import math
import fractions
import bisect
import collections
import itertools
import heapq
import string
import sys
import copy
from collections import deque
sys.setrecursionlimit(10**7)
MOD = 10**9+7
INF = float('inf') #無限大
def gcd(a,b):return fractions.gcd(a,b) #最大公約数
def lcm(a,b):return (a*b) // fractions.gcd(a,b) #最小公倍数
def iin(): return int(sys.stdin.readline()) #整数読み込み
def ifn(): return float(sys.stdin.readline()) #浮動小数点読み込み
def isn(): return sys.stdin.readline().split() #文字列読み込み
def imn(): return map(int, sys.stdin.readline().split()) #整数map取得
def imnn(): return map(lambda x:int(x)-1, sys.stdin.readline().split()) #整数-1map取得
def fmn(): return map(float, sys.stdin.readline().split()) #浮動小数点map取得
def iln(): return list(map(int, sys.stdin.readline().split())) #整数リスト取得
def iln_s(): return sorted(iln()) # 昇順の整数リスト取得
def iln_r(): return sorted(iln(), reverse=True) # 降順の整数リスト取得
def fln(): return list(map(float, sys.stdin.readline().split())) # 浮動小数点リスト取得
def join(l, s=''): return s.join(l) #リストを文字列に変換
def perm(l, n): return itertools.permutations(l, n) # 順列取得
def perm_count(n, r): return math.factorial(n) // math.factorial(n-r) # 順列の総数
def comb(l, n): return itertools.combinations(l, n) # 組み合わせ取得
def comb_count(n, r): return math.factorial(n) // (math.factorial(n-r) * math.factorial(r)) #組み合わせの総数
def two_distance(a, b, c, d): return ((c-a)**2 + (d-b)**2)**.5 # 2点間の距離
def m_add(a,b): return (a+b) % MOD

def sieves_of_e(n):
    is_prime = [True] * (n+1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5)+1):
        if not is_prime[i]: continue
        for j in range(i * 2, n+1, i): is_prime[j] = False
    return is_prime

N = iin()

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

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

colors = [None] * (N)

def set_color(vertex, color):
    colors[vertex] = color
    for v, w in edges[vertex]:
        if colors[v] == None:
            next_color = color
            if w % 2 == 1:
                next_color = (next_color+1)%2
            set_color(v, next_color)
set_color(0, 0)

for c in colors:
    print(c)

Submission status: Accepted

Solution code:
from collections import deque
n = int(input())
l = [-1]*n
dis = [[] for i in range(n)]
for i in range(n-1):
    a,b,c = map(int,input().split())
    dis[a-1].append([b-1,c])
    dis[b-1].append([a-1,c])

q = deque([])
l[0] = 0
q.append((0,0))
while q:
    bef,di = q.popleft()
    for i,j in dis[bef]:
        if l[i] == -1:
            if (di+j)%2==0:
                l[i] = 0
            else:
                l[i] = 1
            q.append((i,(di+j)%2))
for i in l:
    print(i)

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7


N = INT()
e = [[] for _ in range(N)]

for _ in range(N-1):
    t = LIST()
    e[t[0]-1].append([t[1]-1, t[2]%2])
    e[t[1]-1].append([t[0]-1, t[2]%2])

a = [0] * N
f = [0] * N

"""
for edge in G:
    if edge[2]%2 == 1:
        a[edge[1]-1] = 1 - a[edge[0]-1]
    else:
        a[edge[1]-1] = a[edge[0]-1]
"""
def r(n):
    f[n] = 1
    for nn in e[n]:
        if f[nn[0]] == 0:
            if nn[1] == 0:
                a[nn[0]] = a[n]
                r(nn[0])
            else:
                a[nn[0]] = 1 - a[n]
                r(nn[0])

r(0)
for item in a:
    print(item)