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:
from collections import deque

N = int(input())

edge = [[] for _ in range(N)]
check = [False] * N
dist = [0] * N

for i 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))

q = deque([0])

while q :
    current = q.popleft()
    if check[current] :
        continue

    check[current] = True
    for ad , w in edge[current] :
        if not check[ad] :
            q.append(ad)
            dist[ad] = dist[current] + w

for w in dist :
    print(w % 2)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
import copy
import collections
from bisect import bisect_left
from bisect import bisect_right
from collections import defaultdict
from heapq import heappop, heappush
	
def main():
	N = int(input())
	MP = Graph()
	
	for i in range(N-1):
		u, v, w = map(int, input().split(" "))
		u -= 1
		v -= 1
		if w % 2 == 0:
			MP.add_edge(u, v, 0)
			MP.add_edge(v, u, 0)
		else:
			MP.add_edge(u, v, 1)
			MP.add_edge(v, u, 1)
	
	tmp = Dijkstra(MP, 0)
	
	for i in range(N):
		if i == 0:
			print(0)
			continue
			
		tmptmp = tmp.shortest_distance(i)
		if tmptmp % 2 == 0:
			print(0)
		else:
			print(1)
			
	#print("---")
	#print(tmp.shortest_distance(1))
	
class Graph(object):
    # 隣接リストによる有向グラフ
    def __init__(self):
        self.graph = defaultdict(list)

    def __len__(self):
        return len(self.graph)

    def add_edge(self, src, dst, weight=1):
        self.graph[src].append((dst, weight))

    def get_nodes(self):
        return self.graph.keys()


class Dijkstra(object):
    # ダイクストラ法（二分ヒープ）による最短経路探索
    def __init__(self, graph, start):
        self.g = graph.graph

        # startノードからの最短距離
        # startノードは0, それ以外は無限大で初期化
        self.dist = defaultdict(lambda: float('inf'))
        self.dist[start] = 0

        # 最短経路での1つ前のノード
        self.prev = defaultdict(lambda: None)

        # startノードをキューに入れる
        self.Q = []
        heappush(self.Q, (self.dist[start], start))

        while self.Q:
            # 優先度（距離）が最小であるキューを取り出す
            dist_u, u = heappop(self.Q)
            if self.dist[u] < dist_u:
                continue
            for v, weight in self.g[u]:
                alt = dist_u + weight
                if self.dist[v] > alt:
                    self.dist[v] = alt
                    self.prev[v] = u
                    heappush(self.Q, (alt, v))

    def shortest_distance(self, goal):
        # startノードからgoalノードまでの最短距離
        return self.dist[goal]

    def shortest_path(self, goal):
        # startノードからgoalノードまでの最短経路
        path = []
        node = goal
        while node is not None:
            path.append(node)
            node = self.prev[node]
        return path[::-1]
        
	
if __name__ == "__main__":
	main()

Submission status: Accepted

Solution code:
from collections import defaultdict
import sys
sys.setrecursionlimit(1000000)

n = int(input())
s = [list(map(int,input().split())) for i in range(n-1)]
t = defaultdict(list)
for i in range(n-1):
    p = [s[i][1],s[i][2]]
    q = [s[i][0],s[i][2]]
    t[s[i][0]] += [p]
    t[s[i][1]] += [q]

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

def Tree(dic,a,x,lo):
    for i in range(len(dic[x])):
        if a[dic[x][i][0]-1] != -1:
            continue
        else:
            save = lo
            lo += dic[x][i][1]
            a[dic[x][i][0]-1] = lo
            a = Tree(dic,a,dic[x][i][0],lo)
            lo = save
    return a

lis = Tree(t,a,1,0)
for i in range(n):
    if lis[i] % 2 == 0:
        print(0)
    else:
        print(1)

Submission status: Accepted

Solution code:
from collections import deque

n=int(input())
l=[[] for _ in range(n)]
cost=[[] for _ in range(n)]
ans=[-1 for _ in range(n)]
ans[0]=0
q=deque([])
q.append(0)
for iii in range(n-1):
  a,b,w=[int(_) for _ in input().split()]
  a-=1
  b-=1
  l[a].append(b)
  cost[a].append(w)
  l[b].append(a)
  cost[b].append(w)
while not q==deque([]):
  v=q.popleft()
  for jjj in range(len(l[v])):
    u = l[v][jjj]
    w = cost[v][jjj]
    if not ans[u]==-1:
      continue
    ans[u]=(ans[v]+w)%2
    q.append(u)
for a in ans:
  print(a)

Submission status: Accepted

Solution code:
read = input
n = int(read())
v = [[] for i in range(n+1)] # 邻接
used = [0 for i in range(n+1)] # 节点 1~n
def add(f,t,w):
    v[f].append((t, w))
for i in range(n-1):
    f,t,w = map(int, read().split())
    add(f,t,w)
    add(t,f,w)
# 从1出发，贪心即可，1画1，理论不会有回环，总是能画成二分图
from queue import Queue
q = Queue() # 队列
#def dfs(f, s, fa=-1):
#    if s % 2 == 0: 
#        used[f] = 1
#    for t, w in v[f]:
##         print('%d->%d->%d'%(fa, f, t,), s, w)
#        if t == fa:continue
#        dfs(t, w + s, f)
#
#
#dfs(1,0)
q.put_nowait((1, 0, -1)) #(目标节点号，根节点到目标节点的距离，与目标节点相连的上一个节点号)
while not q.empty():
    f, s, fa = q.get_nowait()
    if s % 2 == 0: 
        used[f] = 1 #used数组从1开始填充颜色
    for t, w in v[f]:
#         print('%d->%d->%d'%(fa, f, t,), s, w)
        if t == fa:continue  #fa为与目标节点相连的上一个节点号，防止成环。2->3则，3->2不能再遍历一遍
        q.put_nowait(
            (t, w + s, f)
        )
    
for i in used[1:]: #球号从1开始，故used[0]无意义
    print(used[i])

Submission status: Accepted

Solution code:
import collections
N = int(input())
tree = [[] for i in range(N+1)]

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

for i in range(1, N+1):
    if len(tree[i]) == 1:
        start = i
        break
queue = collections.deque()
queue.append([start, 0])
ans = [-1] * (N+1)
ans[start] = 0


while len(queue) > 0:
    now = queue.popleft()
    for next in tree[now[0]]:
        if ans[next[0]] == -1:
            queue.append(next)
            ans[next[0]] = (ans[now[0]] + next[1])%2
for i in range(1, N+1):
    print(ans[i])

Submission status: Accepted

Solution code:
N = int(input())
uvw = [list(map(int,input().split())) for i in range(N-1)]
u = []
v = []
distance = []
for i in range(N-1):
    u.append(uvw[i][0])
    v.append(uvw[i][1])
    distance.append(uvw[i][2])
graph = [dict() for i in range(N)]
for i in range(N-1):
    graph[u[i]-1][v[i]-1] = distance[i]
    graph[v[i]-1][u[i]-1] = distance[i]

trav = [-1]*N
trav[0]=0
pos = [0]
while len(pos)>0:
    r = pos.pop()
    for i in graph[r]:
        if trav[i] != -1:
            continue
        else:
            trav[i] = trav[r]+graph[r][i]
            pos.append(i)

color = [0]*N
for i in range(N):
    color[i] = trav[i]%2
    print(color[i])

Submission status: Accepted

Solution code:
from collections import deque
N = int(input())
G = [[] for i in range(N)]
for i in range(N-1):    # 辺はN-1本
    u, v, w = map(int, input().split())
    G[u-1].append((v-1, w)) # GにGraph情報を格納(直接結合している頂点と距離)
    G[v-1].append((u-1, w))

used = [0] * N
used[0] = 1
q = deque([0])  # u=0 から開始
ans = [0] * N

while q:    # qがある間ループ
    u = q.popleft()
    color = ans[u]
    for v, w in G[u]:   # uに直接結合している頂点(v)と距離(w)
        if used[v]:
            continue
        if w % 2:   # 奇数ならuとvは別の色
            ans[v] = 1 - color
        else:       # 偶数ならuとvは同じ色
            ans[v] = color
        q.append(v) # 幅優先探索
        used[v] = 1

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

Submission status: Accepted

Solution code:
import sys
if sys.version_info[0] == 2:
    input = raw_input
sys.setrecursionlimit(2 ** 31 -1)

res = None
G = None

def dfs(jibun_v, p, jibun_c):
    global res
    global G

    res[jibun_v] = jibun_c
    #print(jibun_v, p, jibun_c)

    tonari_nodes = G[jibun_v]
    for tonari_v, w in tonari_nodes:
        #if tonari_v == p: # only no loop
        #if tonari_v == p or res[tonari_v] != -1:
        if res[tonari_v] != -1:
            continue

        else:
            if w % 2 == 0:
                tonari_c = jibun_c
            else:
                tonari_c = 1 - jibun_c

            dfs(tonari_v, jibun_v, tonari_c)
    

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

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

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

    global res
    res = [-1 for _ in range(N)]
    
    jibun_v = 0
    p = -1
    jibun_c = 0
    dfs(jibun_v, p, jibun_c)

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

main()

Submission status: Accepted

Solution code:
import sys
if sys.version_info[0] == 2:
    input = raw_input
sys.setrecursionlimit(2 ** 31 -1)

res = None
G = None

def dfs(jibun_v, p, jibun_c):
    global res
    global G

    res[jibun_v] = jibun_c
    #print(jibun_v, p, jibun_c)

    tonari_nodes = G[jibun_v]
    for tonari_v, w in tonari_nodes:
        #if tonari_v == p: # only no loop
        #if tonari_v == p or res[tonari_v] != -1:
        if res[tonari_v] != -1:
            continue

        else:
            if w % 2 == 0:
                tonari_c = jibun_c
            else:
                tonari_c = 1 - jibun_c

            dfs(tonari_v, jibun_v, tonari_c)
    

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

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

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

    global res
    res = [-1 for _ in range(N)]
    
    jibun_v = 0
    p = -1
    jibun_c = 0
    dfs(jibun_v, p, jibun_c)

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

main()

Submission status: Accepted

Solution code:
n=int(input())
edge=[]
node=[]
for i in range(n-1):
    u,v,w=map(int,input().split())
    edge.append([u,v,w])
    node.append([])
node.append([])
dist=[-1]*n
for i in range(n-1):
    [u,v,w]=edge[i]
    node[u-1].append([v-1,w])
    node[v-1].append([u-1,w])
#print(node)

def bfs(node,l):
    stack=[]
    for [v,w] in node[l]:
        stack.append([v,l,w])
    while stack:
        [v,l,w]=stack.pop()
        if(dist[v]==-1):
            dist[v]=(dist[l]+w)%2
            for [v1,w1] in node[v]:
                stack.append([v1,v,w1])
    
dist[0]=1
bfs(node,0)
for i in range(n):
    print(dist[i],end='\n')

Submission status: Accepted

Solution code:
N = int(input())

q = []
visited = [0] * N
ans = [0] * N
A = [[] for _ in range(N)]  # tree
W = [[] for _ in range(N)]  # weight

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

q.append(0)  # start
for _ in range(N):
    u = q.pop(0)
    visited[u] = 1
    k = 0
    for v in A[u]:
        if visited[v]==0:
            q.append(v)
            ans[v] = ans[u] + W[u][k]
        k += 1

for a in ans:
    print(a%2)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
'''
allinputs = iter(input().splitlines())
input = lambda : next(allinputs)
#'''

N = int(input())
q = []
c = [0] * N
l = [0] * N
A = [[] for i in range(N)]
W = [[] for i in range(N)]

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

q.append(0)
for _ in range(N):
	if len(q) == 0:
		break
	i = q.pop(0)
	c[i] = 1
	k = 0
	for j in A[i]:
		if c[j] == 0:
			q.append(j)
			l[j] = l[i] + W[i][k]
		k += 1

for i in l:
	print('{}'.format(i%2))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
'''
allinputs = iter(input().splitlines())
input = lambda : next(allinputs)
#'''

N = int(input())
q = []
c = [0] * N
l = [0] * N
A = [[] for i in range(N)]
W = [[] for i in range(N)]

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

q.append(0)
while len(q):
	i = q.pop(0)
	c[i] = 1
	k = 0
	for j in A[i]:
		if c[j] == 0:
			q.append(j)
			l[j] = l[i] + W[i][k]
		k += 1

for i in l:
	print('{}'.format(i%2))

Submission status: Accepted

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

n = int(input())
t = [[] for i in range(n + 1)]
r = [0 for i in range(n + 1)]

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

def s(f, i):
    for k in t[i]:
        v, w = k
        if v != f:
            if w % 2 == 0:
                r[v] = r[i]
            else:
                r[v] = 1 - r[i]
            s(i, v)
s(0, 1)
print(" ".join(map(str, r[1:])))

Submission status: Accepted

Solution code:
from collections import deque
n = int(input())
path = {u:[] for u in range(1, n+1)}
for i in range(1, n):
    u, v, w = map(int, input().split())
    path[u].append((v,w))
    path[v].append((u,w))

queue = deque()
queue.append(1) # (parent , child, distance)
distance_li = [-1] * (n+1)
distance_li[1] = 0

# for i in range(1,n):
#     print(i, path[i])

while len(queue) > 0:
    u = queue.popleft()
    for v,w in path[u]:
        if distance_li[v] != -1:
            continue
        distance_li[v] = (distance_li[u] + w) % 2
        queue.append(v)
for i in range(1,n+1):
    print(distance_li[i])

Submission status: Accepted

Solution code:
from collections import deque
N=int(input()) 
Graph=[[] for _ in range(N)]
for _ in range(N-1):
  u,v,w=map(int,input().split())
  Graph[u-1].append((v-1,w))
  Graph[v-1].append((u-1,w))
used=[0]*N
ans=[0]*N
used[0]=1
que=deque([0])
while que:
  node=que.popleft()
  color=ans[node]
  for point,dist in Graph[node]:
    if used[point]:
      continue;
    if dist%2==0:
      ans[point]=color
    else:
      ans[point]=color^1
    que.append(point)
    used[point]=1
print(*ans, sep='\n')

Submission status: Accepted

Solution code:
from sys import setrecursionlimit
setrecursionlimit(10**8)


def dfs(i, d):
    # print(i, d)
    for j, w in node_array[i]:
        if color_array[j] == -1:
            color_array[j] = (d + w) % 2
            dfs(j, d + w)


N = int(input())
node_array = [[] for i in range(N)]
color_array = [-1] * N

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

color_array[0] = 0
dfs(0, 0)

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

Submission status: Accepted

Solution code:
N, = list(map(int, input().split()))
a = [{} for i in range(N)]
for i in range(N-1):
  u, v, w = list(map(int, input().split()))
  u -= 1
  v -= 1
  a[u][v] = w%2
  a[v][u] = w%2
r = [-1 for i in range(N)]
r[0] = 0
q = [0]
while q:
  i = q.pop(0)
  for aj in a[i].keys():
    if r[aj]==-1:
      r[aj] = (r[i]+a[i][aj])%2
      q.append(aj)
for i in range(N):
  print(r[i])

Submission status: Accepted

Solution code:
N = int(input())
node_array = [list(map(int, input().split())) for i in range(N - 1)]
# print(node_array)
tree_num_array = [-1] * N
# print(tree_num_array)

tree_num_max = -1
tree = {}
last_tree_num = -1
for node in node_array:
    # print(tree)
    i, j, w = node
    i = i - 1
    j = j - 1
    if tree_num_array[i] == -1 and tree_num_array[j] == -1:
        # print(i, j, "added")
        tree_num_max += 1
        tree[tree_num_max] = {i: 0, j: w}
        tree_num_array[i] = tree_num_max
        tree_num_array[j] = tree_num_max
        last_tree_num = tree_num_max
        continue
    elif tree_num_array[i] == -1:
        # print(i, "added")
        tree_num_added = tree_num_array[j]
        tree[tree_num_added][i] = tree[tree_num_added][j] + w
        tree_num_array[i] = tree_num_added
        last_tree_num = tree_num_added
    elif tree_num_array[j] == -1:
        # print(j, "added")
        tree_num_added = tree_num_array[i]
        tree[tree_num_added][j] = tree[tree_num_added][i] + w
        tree_num_array[j] = tree_num_added
        last_tree_num = tree_num_added
    else:
        tree_num_i = tree_num_array[i]
        tree_num_j = tree_num_array[j]
        # print(tree_num_i, tree_num_j, "unite")
        if len(tree[tree_num_i]) > len(tree[tree_num_j]):
            tree_main_num = tree_num_i
            tree_main_value = tree[tree_main_num][i]
            tree_sub_num = tree_num_j
            tree_sub_value = tree[tree_sub_num][j]
        else:
            tree_main_num = tree_num_j
            tree_main_value = tree[tree_main_num][j]
            tree_sub_num = tree_num_i
            tree_sub_value = tree[tree_sub_num][i]

        for key, value in tree[tree_sub_num].items():
            tree[tree_main_num][
                key] = tree_main_value + w + abs(value - tree_sub_value)
            tree_num_array[int(key)] = tree_main_num
        last_tree_num = tree_main_num
# print(tree)
ans_dict = sorted(tree[last_tree_num].items(), key=lambda x: int(x[0]))
# print(ans_dict)
for distance in ans_dict:
    print(distance[1] % 2)

Submission status: Accepted

Solution code:
from collections import deque

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

color = {}
queue = deque()
queue.append((0, 1, 0))  # (parent-color, child, distance)

while len(queue) > 0:
    pc, c, d = queue.popleft()
    if c in color:
        continue
    color[c] = pc if d % 2 == 0 else 1 - pc
    for v, w in adj[c]:
        queue.append((color[c], v, w))

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-


def main():
    from collections import deque

    n = int(input())
    graph = [[] for _ in range(n)]

    # See:
    # https://www.youtube.com/watch?v=26AWkQNRb-A
    # https://atcoder.jp/contests/abc126/submissions/5456359
    for i in range(n - 1):
        ui, vi, wi = map(int, input().split())
        ui -= 1
        vi -= 1
        graph[ui].append((vi, wi))
        graph[vi].append((ui, wi))

    ans = [-1 for _ in range(n)]
    q = deque()
    ans[0] = 0
    q.append(0)

    while q:
        vj = q.popleft()

        for uj, wj in graph[vj]:
            if ans[uj] != -1:
                continue

            ans[uj] = (ans[vj] + wj) % 2
            q.append(uj)

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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-


def main():
    from collections import deque

    n = int(input())
    to = [[] for _ in range(n)]
    cost = [[] for _ in range(n)]

    for i in range(n - 1):
        ui, vi, wi = map(int, input().split())
        ui -= 1
        vi -= 1
        to[ui].append(vi)
        to[vi].append(ui)
        cost[ui].append(wi)
        cost[vi].append(wi)

    ans = [-1 for _ in range(n)]
    q = deque()
    ans[0] = 0
    q.append(0)

    while q:
        vj = q.popleft()

        for j in range(len(to[vj])):
            uj = to[vj][j]
            wj = cost[vj][j]

            if ans[uj] != -1:
                continue

            ans[uj] = (ans[vj] + wj) % 2
            q.append(uj)

    for a in ans:
        print(a)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#coding:utf-8
from collections import defaultdict
import sys
from Queue import Queue
N=input()
U=[];V=[];W=[]
G=defaultdict(list)
Dist={}
for _ in range(N-1):
    u,v,w=map(int,raw_input().split())
    u,v=min(u,v),max(u,v)
    U.append(u);V.append(v);W.append(w)    
    G[u].append(v)
    G[v].append(u)
    Dist[(u,v)]=Dist[(v,u)]=w

vis=[False]*(10**5+1)
color=[None]*(10**5+1)
q=Queue()
vis[1]=True
color[1]=0
curCol=1
for u in G[1]:q.put(u)
while not q.empty():
    child=q.get()
    vis[child]=True
    par=None
    for n in G[child]:
        if vis[n]: 
            par=n;break
    dist=Dist[(par,child)]
    if dist%2==0: color[child]=color[par]
    else: color[child]=color[par]^1
    for ch in G[child]:
        if not vis[ch]: q.put(ch)

for c in color[1:N+1]:print(c)

Submission status: Accepted

Solution code:
N = int(input())
q = []
c = [0 for i in range(N)]
l = [0 for i in range(N)]
A = [[] for i in range(N)]
W = [[] for i in range(N)]

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

q.append(0)
while len(q):
	i = q.pop(0)
	c[i] = 1
	k = 0
	for j in A[i]:
		if c[j] == 0:
			q.append(j)
			l[j] = l[i] + W[i][k]
		k = k + 1

for i in l:
	print('{}'.format(i%2))

Submission status: Accepted

Solution code:
import heapq

def dijkstra(graph,node,start):
    dist = [float("inf") for _ in range(node)]
    dist[start] = 0
    q = []
    heapq.heappush(q,[0,start])

    while(q):
        cost, cur_node = heapq.heappop(q)
        if dist[cur_node] < cost:
            continue
        for next_cost, next_node in graph[cur_node]:
            dist_cand = dist[cur_node]+next_cost
            if dist_cand < dist[next_node]:
                dist[next_node] = dist_cand
                heapq.heappush(q,(dist[next_node],next_node))
    return dist
    

n  = int(input())
adj = [[] for _ in range(n)]
for i in range(n-1):
    u,v,w = map(int,input().split())
    u -= 1
    v -= 1
    adj[u].append((w,v))
    adj[v].append((w,u))
shortest = dijkstra(adj,n,0)
for i in shortest:
    print(i%2)

Submission status: Accepted

Solution code:
import heapq

def dijkstra(graph, node, start):
    dist = [float("inf") for _ in range(node)]

    dist[start] = 0
    q = []
    heapq.heappush(q, (0, start))

    while q:
        cost, cur_node = heapq.heappop(q)

        if dist[cur_node] < cost:
            continue

        for nex_cost, nex_node in graph[cur_node]:
            dist_cand = dist[cur_node] + nex_cost
            if dist_cand < dist[nex_node]:
                dist[nex_node] = dist_cand
                heapq.heappush(q, (dist[nex_node], nex_node))

    return dist


n = int(input())
adj = [[] for _ in range(n)]
for i in range(n - 1):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    adj[a].append((c, b))
    adj[b].append((c, a))
shortest = dijkstra(adj, n, 0)
for i in shortest:
    print(i % 2)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(1000000)

n = int(input())

ulist = []

for _ in range(n+1):
    ulist.append([])

vlist = [False]*(n+1)

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

def check(checkV, fromV):
    for data in ulist[checkV]:
        if data[0] != fromV:
            vlist[data[0]] = vlist[checkV] if data[1] % 2 == 0 else not vlist[checkV]
            check(data[0], checkV)

check(1, 0)

for i in range(1,n+1):
    print(1 if vlist[i] else 0)

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:
def solve(n, u, v, w):
    res = [-1] * (n+1)
    res[1] = 0
    E = {_: [] for _ in (set(u) | set(v))}
    W = {}
    for u_i, v_i, w_i in zip(u, v, w):
        E[u_i].append(v_i)
        E[v_i].append(u_i)
        W[(u_i, v_i)] = w_i
        W[(v_i, u_i)] = w_i
    que = [1]
    while que:
        s = que.pop(0)
        for t in E[s]:
            if res[t] != -1:
                continue
            d = W[s,t]
            que.append(t)
            if d % 2 == 0:
                res[t] = res[s]
            else:
                res[t] = 1 - res[s]
    return "\n".join(map(str, res[1:]))

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10000000)
N = int(input())
JU = [-1 for _ in range(N)]

LI = [[] for _ in range(N)]
for _ in range(N-1):
    u,v,w = map(int,input().split())
    W = w%2
    LI[u-1].append([v-1,W])
    LI[v-1].append([u-1,W])
def dfs(x):
    for i in range(len(LI[x])):
        j = LI[x][i][0]
        k = LI[x][i][1]
        if JU[j] == -1:
            if JU[x] == 0:
                if k == 0:
                    JU[j] = 0
                    dfs(j)
                else:
                    JU[j] = 1
                    dfs(j)
            else:
                if k == 0:
                    JU[j] = 1
                    dfs(j)
                else:
                    JU[j] = 0
                    dfs(j)

JU[0] = 0
dfs(0)
for i in range(N):
    print(JU[i])

Submission status: Accepted

Solution code:
n = int(input())
gr = [dict() for _ in range(n)]
l = [10*6]*n
l[0]= 0
for _ in range(n-1):
  x,y,w = map(int, input().split())
  w %= 2
  gr[x-1][y-1] = w
  gr[y-1][x-1] = w
  
seen = set()
q = [0]
while q:
  cur = q.pop()
  seen.add(cur)
  for x in set(gr[cur].keys())-seen:
    l[x] = l[cur] + gr[cur][x]
    q.append(x)
for i in range(n):
  print(l[i]%2)

Submission status: Accepted

Solution code:
N = int(input())
G = [[] for i in range(N)]
for i in range(N-1):
  u, v, w = list(map(int, input().split()))
  u -= 1
  v -= 1
  w = w % 2
  G[u].append([v, w])
  G[v].append([u, w])
  
res = [-1] * N
"""
def dfs(u, p, c):
  res[u] = c
  for n in G[u]:
    if n[0] == p or res[n[0]] != -1:
      continue
    if n[1] == 1:
      dfs(n[0], u, 1-c)
    else:
      dfs(n[0], u, c)
"""
from collections import deque
q = deque()
# 再帰はメモリ的に厳しい？？
def search(q):
  while q:
    u, p, c = q.popleft()
    if res[u] == -1:
      for n in G[u]:
        if n[0] == p or res[n[0]] != -1:
          continue
        if n[1] == 1:
          q.append((n[0], u, 1-c))
        else:
          q.append((n[0], u, c))
    res[u] = c
  
  
def main():
  q.append((0, -1, 1))
  search(q)
  for i in res:
    print(i)
  
  
if __name__ == "__main__":
  main()

Submission status: Accepted

Solution code:

import sys
sys.setrecursionlimit(1000000)
def dfs(now,color):
    col[now]=color
    for n,w in nodes[now]:
        if col[n]!=-1:
            continue
        if w%2==0:
            dfs(n,color)
        else:
            dfs(n,1-color)

n=int(input())

nodes=[]
for i in range(n+1):
    nodes.append([])
for i in range(n-1):
    s,e,w = map(int,input().split())
    nodes[s].append((e,w))
    nodes[e].append((s,w))

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

dfs(1,1)

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

Submission status: Accepted

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

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

def dfs(x,c):
    col[x] = c
    for v,w in e[x]:
        if col[v] == -1:
            dfs(v , c+w)

dfs(1,0)



for i in range(1,N+1):
    print(col[i] % 2)

Submission status: Accepted

Solution code:
from collections import deque
n=int(input())
v=[0 for i in range(n-1)]
u=[0 for i in range(n-1)]
w=[0 for i in range(n-1)]
da=[[] for i in range(n)]
for i in range(n-1):
  u[i],v[i],w[i]=map(int,input().split())
  da[u[i]-1].append(i)
  da[v[i]-1].append(i)
  u[i]-=1
  v[i]-=1
que=[0]
co=0
ans=[-1 for i in range(n)]
di=[0 for i in range(n)]
ans[0]=0
while co<n:
  x=que.pop()
  if di[x]%2==0:
    ans[x]=0
  else:
    ans[x]=1
  for i in da[x]:
    if ans[u[i]]<0:
      di[u[i]]=di[x]+w[i]
      que.append(u[i])
    if ans[v[i]]<0:
      di[v[i]]=di[x]+w[i]
      que.append(v[i])
  co+=1
for i in ans:
  print(i)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(100000)

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

dist=[-1 for _ in range(N)]
def measure(src):
    for v,w in edges[src]:
        if dist[v]==-1:
            dist[v]=dist[src]+w
            measure(v)

dist[0]=0
measure(0)

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

Submission status: Accepted

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

from collections import defaultdict

uv = defaultdict(dict)

for u, v, w in uvw:
    uv[u][v] = w
    uv[v][u] = w
    
l = {1: 0}

s = [1]

while s:
    ns = []
    for i in s:
        for j in uv[i]:
            if not j in l:
                l[j] = l[i] + uv[i][j]
                ns.append(j)
    s = ns

for i in range(1, N + 1):
    print(l[i] % 2)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(1000000000)

n = int(input())

ulist = []

for _ in range(n):
    ulist.append([])

vlist = [True] * n

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


def check(checkV, fromV):
    for data in ulist[checkV]:
        if data[0] != fromV:
            vlist[data[0]] = vlist[checkV] if data[1] % 2 == 0 else not vlist[checkV]
            check(data[0], checkV)

check(0, -1)

for i in range(n):
    print(1 if vlist[i] else 0)

Submission status: Accepted

Solution code:
import queue

N = int(input())

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

q = queue.Queue()
q.put((1, 0))
while(not q.empty()):
    v, w = q.get()
    dist[v-1] = w
    for nv, nw in adj[v]:
        if(dist[nv-1]!=-1):
            continue
        q.put((nv, dist[v-1]+nw))

for c in dist:
    print(c%2)

Submission status: Accepted

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

dist = {i+1: -1 for i in range(N)}
stack = [1]
dist[1] = 0

while len(stack) != 0:
    prev = stack.pop()
    prev_d = dist[prev]
    for v, w in d[prev]:
        if dist[v] == -1:
            stack.append(v)
            dist[v] = prev_d + w

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