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())
ans = [-1] * n
ans[0] = 0
d = [[] for _ in range(n)]

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

cnt = 0
queue = deque()
queue.append(0)
while queue:
    u = queue.pop()
    for v, w in d[u]:
        if ans[v] == -1:
            if w % 2 == 0:
                ans[v] = ans[u]
            else:
                ans[v] = ans[u] ^ 1
            queue.append(v)


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

Submission status: Accepted

Solution code:
N = int(input())
u, v, w = [0]*(N-1), [0]*(N-1), [0]*(N-1)
n = [-1] * N
# n[][0] 色　n[][1] 連結先一覧リスト n[][2] mod2 
for i in range(N):
    n[i] = [0]*4
    n[i][1] = []
    n[i][2] = []

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

stack = [u[0]-1]

while True:
    num = stack.pop()
    n[num][3] = 1
    for i in range(len(n[num][1])):
        if n[n[num][1][i]][3] == 0:
            stack.append(n[num][1][i])
            if n[num][2][i] == 0:
                n[n[num][1][i]][0] = n[num][0]
            else:
                n[n[num][1][i]][0] = -1 * n[num][0] + 1
    if len(stack) == 0:
        break

for i in n:
    print(i[0])

Submission status: Accepted

Solution code:
'''
研究室PCでの解答
'''
import math
#import numpy as np
import queue
import bisect
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)
mod = 10**9+7
dir = [(-1,0),(1,0),(0,-1),(0,1)]
alp = "abcdefghijklmnopqrstuvwxyz"


def main():
    n = int(ipt())
    way = [[] for i in range(n+1)]
    for i in range(n-1):
        u,v,w = map(int,ipt().split())
        way[u].append((v,w))
        way[v].append((u,w))

    col = [-1]*(n+1)
    q = [(1,0)]
    col[1] = 0
    while q:
        qi,ci = q.pop()
#        print(qi,ci)
        for j,lj in way[qi]:
            if col[j] == -1:
                cj = (ci+lj)%2
                col[j] = cj
                q.append((j,cj))

    for i in col[1::]:
        print(i)

    return None

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def f(G, not_searched, results={0: '0'}):
    stack = []
    while len(not_searched) > 0:
        if len(stack) > 0:
            i = stack.pop()
            not_searched.remove(i)
        else:
            i = not_searched.pop()

        for key, val in G[i].items():
            if not key in not_searched:
                continue

            if val % 2 == 1:
                if results[i] == '0':
                    results[key] = '1'
                else:
                    results[key] = '0'
            else:
                results[key] = results[i]

            stack.append(key)

    return results

N = int(input())
G = [{} for _ in range(N)]
not_searched = set([i for i in range(N)])

if N == 1:
    print(results[0])
else:
    for i in range(N-1):
        u, v, w = map(int, input().split())
        G[u-1][v-1] = w
        G[v-1][u-1] = w

    results = f(G, not_searched)
    for i in range(N):
        print(results[i])

Submission status: Accepted

Solution code:
from sys import setrecursionlimit

setrecursionlimit(10 ** 6)

def dfs(now, prev):
    for nxt, w in edge[now]:
        if nxt == prev:
            continue
        
        dist[nxt] = dist[now] + w
        dfs(nxt, now)


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 = [0] * n
dfs(0, -1)

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

Submission status: Accepted

Solution code:
N = int(input())
dist_from_1 = [0 for i in range(N+1)]

paths = [dict() for i in range(N+1)]
for i in range(N-1):
    a, b, dist = map(int, input().split())
    paths[a][b] = dist
    paths[b][a] = dist

queue = [(0, 1, 0)]
while len(queue) != 0:
    prev, now, dist = queue.pop()
    dist_from_1[now] = dist
    for next in paths[now]:
        if next == prev:
            continue
        queue.append((now, next, dist + paths[now][next]))

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

Submission status: Accepted

Solution code:
# distance between two nodes is dis(root, a)+dis(root, b)-2*(dis(lca(a,b),root))
# taking mod 2 last term is eliminated 
# all nodes having dis as odd parity from root will be white color
# all nodes having dis as even parity from root will be even color
import sys
import os
sys.setrecursionlimit(1000000)
from collections import defaultdict
adj = defaultdict(list)
dis =[0 for i in range(1000000)]
def dfs(u , p):
	for i , w in adj[u]:
		if i==p:
			continue
		dis[i]=dis[u]+w
		dis[i]=dis[i]%2
		dfs(i , u)
def main():
	n = int(input())
	for i in range(n-1):
		x, y , w = map(int , input().split())
		w = w%2
		adj[x].append([y , w])
		adj[y].append([x, w])
	dfs(1, 0)
	for i in range(1,n+1):
		print(dis[i])
if __name__ =="__main__":
	main()

Submission status: Accepted

Solution code:
import sys
import os
sys.setrecursionlimit(1000000)
from collections import defaultdict
adj = defaultdict(list)
dis =[0 for i in range(1000000)]
def dfs(u , p):
	for i , w in adj[u]:
		if i==p:
			continue
		dis[i]=dis[u]+w
		dis[i]=dis[i]%2
		dfs(i , u)
def main():
	n = int(input())
	for i in range(n-1):
		x, y , w = map(int , input().split())
		w = w%2
		adj[x].append([y , w])
		adj[y].append([x, w])
	dfs(1, 0)
	for i in range(1,n+1):
		print(dis[i])
if __name__ =="__main__":
	main()

Submission status: Accepted

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

n = int(readline())
node = [[] for i in range(n)]

for i in range(n-1):
    u,v,w = map(int,readline().split())
    node[u-1].append((v-1,w))
    node[v-1].append((u-1,w))
ans = [-1]*n
ans[0] = 0
def dfs(fro, to, dis):
    ans[to] = dis%2
    for nxt, dist in node[to]:
        if nxt == fro:
            continue
        dfs(to, nxt, (dis+dist)%2)

for to,dis in node[0]:
    dfs(0,to,dis)

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

Submission status: Accepted

Solution code:
#coding: utf-8
from collections import defaultdict, deque

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

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

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

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

while len(que) > 0:
    node, distance = que[0]
    que.popleft()

    ret[node] = distance % 2
    for next_node, next_distance in G[node]:
        if ret[next_node] == -1:
            que.append((next_node, distance + next_distance))

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

Submission status: Accepted

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

# 二分グラフ
N = int(input())
graph = [[] for _ in range(N)]
color = [-1]*N

# 隣接リストの作成
for i in range(N-1):
    a, b, w = map(int, input().split())
    a -= 1
    b -= 1
    w %= 2
    graph[a].append((b,w))
    graph[b].append((a,w))

next_q = [(0, 0)]
while len(next_q)>0:
    nw, nc = next_q.pop()
    color[nw] = nc
    for nxt, nl in graph[nw]:
        if color[nxt]==-1:
            next_q.append((nxt,(nl+nc)%2))
for i in color:
    print(i)

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict, deque

def main():
    input = sys.stdin.readline
    N = int(input())
    d = defaultdict(list)
    for _ 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))

    dist = [0] * N
    q = deque()
    q.append((0, 0))
    visited = set()

    while len(q) > 0:
        q_ = deque()
        while len(q) > 0:
            node1, cost1 = q.popleft()

            dist[node1] = cost1
            visited.add(node1)

            for node2, cost2 in d[node1]:
                if node2 in visited:
                    continue

                q_.append((node2, cost1 + cost2))

        q = q_

    for d in dist:
        print(d % 2)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n = int(input())
visited = [False] * (n + 1)
distance = [0] * (n + 1)
prev = [0] * (n + 1)

from collections import defaultdict, deque
d = defaultdict(list)

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

q = deque([1])
while q:
    node = q.popleft()
    visited[node] = True
    for next_node, next_dist in d[node]:
        if not visited[next_node]:
            q.append(next_node)
            # 距離を更新
            distance[next_node] = distance[node] + next_dist
    
# print(distance)
for dist in distance[1:]:
    print(dist%2)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(20000000)


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


N = int(input())

G = [[] for i 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])

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

Submission status: Accepted

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

V = [-1]*n
V[0] = 0
que = deque([0])
while que:
    nw = que.popleft()
    for nx,d in G[nw]:
        if V[nx]!=-1: continue
        V[nx] = (V[nw]+d)%2
        que.append(nx)

for v in V:
    print(v)

Submission status: Accepted

Solution code:
g = {}
a = int(input())
for i in range(a - 1):
    c = [int(s) for s in input().split()]
    if c[0] not in g: g[c[0]] = [(c[1], c[2])]
    else: g[c[0]].append((c[1], c[2]))

    if c[1] not in g: g[c[1]] = [(c[0], c[2])]
    else: g[c[1]].append((c[0], c[2]))

c = {}
d = {i: False for i in range(1, a + 1)}
c[1], d[1] = 0, True
Q = [1]
while(Q != []):
    r = Q.pop(0)
    for i in g[r]:
        if d[i[0]] == False:
            d[i[0]] = True
            Q.append(i[0])
            if i[1] % 2 == 0: c[i[0]] = c[r]
            else: c[i[0]] = (c[r] + 1) % 2
for i in range(1, a + 1): print(c[i])

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc126/tasks/abc126_d

# ｄfsでやっていき、最初の点を黒か白かで固定する。偶数ならどんどん加えていく。
n = int(input())
tree = [[] for _ in range(n + 1)]
for _ in range(n - 1):
    u, v, w = map(int, input().split())
    u -= 1
    v -= 1
    tree[u].append((v, w))
    tree[v].append((u, w))


def dfs(tree, n):
    visited = [False] * n
    dis = [0] * n
    even = set([0])
    stack = [0]
    while stack:
        v = stack.pop()
        cur_dis = dis[v]
        for next_v, d in tree[v]:
            if not visited[next_v]:
                visited[next_v] = True
                stack.append(next_v)
                dis[next_v] = cur_dis + d
                if (cur_dis + d) % 2 == 0:
                    even.add(next_v)
    return even

even = dfs(tree, n)
for i in range(n):
    if i in even:
        print(0)
    else:
        print(1)

Submission status: Accepted

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

res = [-1]*N
res[0] = 0
q = [0]
while len(q):
  v = q.pop()
  for u,w in e[v]:
    if res[u]>=0:
      continue
    res[u] = res[v]+w
    q.append(u)

for r in res:
  print(r%2)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**7)
import bisect
import heapq
import itertools
import math
from collections import Counter, defaultdict, deque
from copy import deepcopy
from decimal import Decimal
from math import gcd
from operator import add, itemgetter, mul, xor
def cmb(n,r,mod):
  bunshi=1
  bunbo=1
  for i in range(r):
    bunbo = bunbo*(i+1)%mod
    bunshi = bunshi*(n-i)%mod
  return (bunshi*pow(bunbo,mod-2,mod))%mod
mod = 10**9+7
def I(): return int(input())
def LI(): return list(map(int,input().split()))
def MI(): return map(int,input().split())
def LLI(n): return [list(map(int, input().split())) for _ in range(n)]

n = I()
graph =[[]*(n+1) for i in range(n+1)]
ans = [0]*(n+1)
for i in range(n-1):
    u,v,w = map(int,input().split())
    w = w%2
    graph[u].append([v,w])
    graph[v].append([u,w])
#vをcに塗る。pはvの親
def dfs(v,p,c,ans):
    ans[v] = c
    for i in graph[v]:
        if i[0] == p:
            continue
        if i[1] == 1:
            dfs(i[0],v,1-c,ans)
        if i[1] == 0:
            dfs(i[0],v,c,ans)
dfs(1,0,0,ans)
for i in ans[1:]:
    print(i)

Submission status: Accepted

Solution code:
n=int(input())
L=[[] for i in range(n+1)]
for i in range(n-1):
    u,v,w=map(int,input().split())
    L[u].append((v,w%2))
    L[v].append((u,w%2))

V=[0 for i in range(n+1)]
V[1]=1
ans=[0 for i in range(n+1)]
que=[1]
head=0

while len(que)>head:
    now=que[head]
    head+=1
    for nex in L[now]:
        if V[nex[0]]==0:
            V[nex[0]]=1
            ans[nex[0]]=ans[now]^nex[1]
            que.append(nex[0])
    
for pri in ans[1:]:
    print(pri)

Submission status: Accepted

Solution code:
N = int(input())
ans = [-1] * N
ans[0] = 0
root = [[] for i in range(N)]
for i in range(N - 1):
  u, v, w = map(int, input().split())
  root[u - 1].append([v - 1, w])
  root[v - 1].append([u - 1, w])
#print(root)

visited = [0] * N
visited[0] = 1
queue = [0]
while queue:
  x = queue.pop()
  for i, value in root[x]:
    if value % 2 == 0:
      ans[i] = ans[x]
    else:
      ans[i] = abs(1 - ans[x])
    if visited[i] == 0:
      visited[i] = 1
      queue.append(i)
      
#print(ans)      
for i in range(N):
  print(ans[i])

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10**7)


def dfs(s, to, color):
    for next_v, step in to[s]:
        if color[next_v] == -1:
            if step % 2 == 0:
                color[next_v] = color[s]
            else:
                color[next_v] = color[s] ^ 1
            dfs(next_v, to, color)


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

    color = [-1] * N #-1: 未探索、0: 白、1: 黒
    color[0] = 0
    dfs(0, to, color)
    print(*color, sep='\n')


if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
def abc126_d():
    import sys
    sys.setrecursionlimit(10010010)
    read = sys.stdin.buffer.read
    inp = iter(map(int, read().split()))

    N = next(inp)
    G = [[] for _ in range(N)]
    for _ in range(N-1):
        u = next(inp) - 1
        v = next(inp) - 1
        w = next(inp)
        G[u].append((v, w))
        G[v].append((u, w))

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

    def dfs(u):
        for v, w in G[u]:
            if color[v] != -1: continue
            if w % 2 == 0:
                color[v] = color[u]
            else:
                color[v] = abs(color[u] - 1)
            dfs(v)

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

if __name__ == '__main__':
    abc126_d()

Submission status: Accepted

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

done = {}
todo = [(0, 0, 0)]
while todo:
    i, c, d = todo.pop()
    for ni, dd in G[i]:
        if ni in done:
            continue
        nd = d + dd
        nc = nd % 2
        todo.append((ni, nc, nd))
    done[i] = c

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

Submission status: Accepted

Solution code:
from sys import setrecursionlimit
setrecursionlimit(10 ** 7)
n = int(input())
uvw = [list(map(int, input().split())) for i in range(n - 1)]
d = [-1 for i in range(n)]
edge = [[] for i in range(n)]
for u, v, w in uvw:
    edge[u - 1].append((v - 1, w))
    edge[v - 1].append((u - 1, w))
def dfs(now, D):
    d[now] = D
    for i, j in edge[now]:
        if d[i] == -1:
            dfs(i, D + j)
dfs(0, 0)
for i in d:
    print(i % 2)

Submission status: Accepted

Solution code:
import heapq

def dijkstra(G, s, dist):
    dist[s] = 0
    Q = [[0,s]]
    heapq.heapify(Q)

    while(len(Q) > 0):
        cur_d, cur_v = heapq.heappop(Q)
        cur_d *= -1
        
        if(cur_d > dist[cur_v]): continue

        for e in G[cur_v]:
            to, cost = e[0], e[1]
            if(dist[cur_v] + cost < dist[to]):
                dist[to] = dist[cur_v] + cost
                heapq.heappush(Q, [-dist[to], to])

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

dist = [1e18] * N
dijkstra(G,0,dist)

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

Submission status: Accepted

Solution code:

from collections import deque

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

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

colors = [-1] * (N + 1)
colors[1] = 0
q = deque([1])
while q:
    u = q.popleft()
    for v, w in graph[u]:
        if colors[v] >= 0:
            continue

        if w % 2 == 0:
            colors[v] = colors[u]
        else:
            colors[v] = 1 - colors[u]
        q.append(v)

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)
read = sys.stdin.read
readlines = sys.stdin.readlines
def main():
    def dfs(node):
        for adjnode in edges[node]:
            if colors[adjnode[0]] == -1:
                if adjnode[1] % 2 == 0:
                    colors[adjnode[0]] = colors[node]
                else:
                    colors[adjnode[0]] = colors[node] ^ 1
                dfs(adjnode[0])
    # input
    n = int(input())
    edges = {e: [] for e in range(n)}
    for _ in range(n - 1):
        u, v, w = map(int, input().split())
        u -= 1
        v -= 1
        edges[u].append((v, w))
        edges[v].append((u, w))
    # process
    colors = [-1] * n
    colors[0] = 0
    dfs(0)
    # output
    print(*colors, sep='\n')


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:

from copy import copy
N=int(input())
G=[[] for _ in range(N)]
di=[-1]*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])

di[0]=0

for i in range(1,N):
    if di[i]!=-1:continue
    seen=[0]*N
    stack=[[0,0]]
    while stack:
        y,d=stack.pop()
        if seen[y]==1:continue
        seen[y]=1
        for z, dist in G[y]:
            if seen[z] == 0:
                di[z] = d + dist
                stack.append([z, d + dist])

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

Submission status: Accepted

Solution code:
from collections import deque

N=int(input())
G=[{} for _ in range(N+1)]

for i in range(N-1):
  u,v,w=map(int,input().split())
  G[u][v]=w
  G[v][u]=w
  
for i in range(1,N+1):
  if len(G[i])==1:
    start=i
    break

def bfs(s):
    seen = [0 for i in range(N+1)]
    d = [0 for i in range(N+1)]
    todo = deque([])
    now = s
    seen[now]=1
    todo.append(now)
    while 1:
      if len(todo)==0:break
      a = todo.popleft()
      for b in G[a]:
        if seen[b] == 0:
          seen[b] = 1
          todo.append(b)
          d[b] += d[a] + G[a][b]
    return d

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

Submission status: Accepted

Solution code:
import collections
import heapq

def cin():
    in_ = list(map(int,input().split()))
    if len(in_) == 1:  return in_[0]
    else:  return in_

class Dijkstra():
    
    def __init__(self):  self.e = collections.defaultdict(list)

    def add(self, u, v, d, directed = False):
        self.e[u].append([v, d])
        self.e[v].append([u, d]) # 有向グラフの場合、コメントアウト

    def delete(self, u, v):
        self.e[u] = [_ for _ in self.e[u] if _[0] != v]
        self.e[v] = [_ for _ in self.e[v] if _[0] != u]

    def Dijkstra_search(self, s):

        d = collections.defaultdict(lambda: float('inf'))
        prev = collections.defaultdict(lambda: None)
        d[s] = 0
        q = []
        heapq.heappush(q, (0, s))
        v = collections.defaultdict(bool)
        while q:
        
            k, u = heapq.heappop(q)
            if v[u]:  continue
            v[u] = True

            for uv, ud in self.e[u]:
                if v[uv]:  continue
                vd = k + ud
                if d[uv] > vd:
                    d[uv] = vd
                    prev[uv] = u
                    heapq.heappush(q, (vd, uv))

        return d, prev

    def getDijkstraShortestPath(self, start, goal):
        _, prev = self.Dijkstra_search(start)
        shortestPath = []
        node = goal
        while node is not None:
            shortestPath.append(node)
            node = prev[node]
        return shortestPath[::-1]

graph = Dijkstra()
N = cin()
for i in range(N - 1): 
    in_ = cin()
    graph.add(in_[0] - 1, in_[1] - 1, in_[2])
min_w, prev = graph.Dijkstra_search(0)
ans = [0 for _ in range(N)]
for i in range(N):  print(min_w[i] % 2)

Submission status: Accepted

Solution code:
import queue
n=int(input())
e=[[] for _ in range(n)]
INF=10**18
d=[INF]*n
for _ in range(n-1):
  v,u,w=map(int,input().split())
  e[v-1]+=[(u-1,w)]
  e[u-1]+=[(v-1,w)]
q=queue.Queue()
q.put(0)
d[0]=0
while not q.empty():
  now=q.get()
  for to,dis in e[now]:
    if d[to]==INF:
      d[to]=d[now]+dis
      q.put(to)
for i in d:
  print(i%2)

Submission status: Accepted

Solution code:
from collections import deque
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))
ds = [-1]*n
dq = deque([0])
ds[0] = 0
while dq:
  t = dq.popleft()
  for i in g[t]:
    if ds[i[0]] == -1:
      ds[i[0]] = ds[t] + i[1]
      dq.append((i[0]))
for i in ds:
  if i%2 == 0:
    print(0)
  else:
    print(1)

Submission status: Accepted

Solution code:
def main():
    n = int(input())
    ki = {}
    for i in range(1,n+1):
        ki[i] = []
    for i in range(n-1):
        u,v,w = map(int,input().split())
        ki[u] += [[v,w%2]]
        ki[v] += [[u,w%2]]
    cl = [-1 for i in range(n)]
    cl[0] = 0
    que = [0]
    while len(que)>0:
        q = que.pop(0)
        for v in ki[q+1]:
            if cl[v[0]-1] != -1:
                continue
            if v[1]==1:
                cl[v[0]-1] = (cl[q]+1)%2
                que.append(v[0]-1)
            else:
                cl[v[0]-1] = cl[q]
                que.append(v[0]-1)
    for i in range(n):
        print(cl[i])

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import deque
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))
ds = [-1]*n
dq = deque([0])
ds[0] = 0
while dq:
  t = dq.popleft()
  for i in g[t]:
    if ds[i[0]] == -1:
      ds[i[0]] = ds[t] + i[1]
      dq.append((i[0]))
for i in ds:
  if i%2 == 0:
    print(0)
  else:
    print(1)

Submission status: Accepted

Solution code:
from collections import deque

n = int(input())
tree = {i: set() for i in range(n)}
cost = {}
for _ in range(n-1):
    u, v, w = map(lambda x: int(x)-1, input().split())
    tree[u].add(v)
    tree[v].add(u)
    cost[(u, v)] = w + 1

color = [-1] * n
color[0] = 0
que = deque([0])
while que:
    now = que.popleft()
    for i in tree[now]:
        if color[i] != -1:
            continue
        if cost[(min(now, i), max(now, i))] % 2 == 0:
            color[i] = color[now]
        else:
            color[i] = color[now] ^ 1
        que.append(i)
print('\n'.join(map(str, color)))

Submission status: Accepted

Solution code:
import queue
n = int(input())

node = [[] for _ in range(n)]
color = [-1] * n
color[0] = 0

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

q = queue.Queue()
q.put(0)

while not q.empty():
    i = q.get()
    c = color[i]
    for j, w in node[i]:
        if color[j] < 0:
            color[j] = c if w % 2 == 0 else (c + 1) % 2
            q.put(j)

for c in color:
    print(c)

Submission status: Accepted

Solution code:
import sys
from collections import deque


def input():
    return sys.stdin.readline().rstrip()


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

    color = [False] * N
    color[0] = 0
    q = deque([1])

    while q:
        u = q.popleft()
        c1 = color[u - 1]
        for c, w in edge[u]:
            if color[c - 1] is False:
                q.append(c)
                color[c - 1] = (c1 + w) % 2

    print(*color)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
from collections import deque


def input():
    return sys.stdin.readline().rstrip()


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

    color = [False] * (N + 1)
    color[1] = 0
    q = deque([1])
    pass
    while q:
        u= q.popleft()
        c1 = color[u]
        for c,w in edge[u]:
            if color[c] is False:
                q.append(c)
                color[c] = (c1+w)%2

    color.pop(0)
    print(*color)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import deque

n = int(input())

g = [[] for _ in range(n)]
# 0indexに直している
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))

"""
ex.
3
1 2 2
2 3 1
の場合、g = [[(1, 2)], [(0, 2), (2, 1)], [(1, 1)]]
"""

#print(g)

"""
根から各頂点への距離をd_iとする
u,vという2頂点について、その最小共通祖先をwとすると
uとvの距離=d_u+d_v-2d_w
第3項は常に偶数
d_uとd_vの偶奇が等しければ全体は偶数、偶奇が異なれば全体は奇数
例えば、d_iが偶数なら白に、奇数なら黒に塗るとすれば条件を満たす
"""

dq = deque([0])
#  各頂点について、根からの距離
# 頂点0を根とする（別にどれを選んでも良い）
ds = [-1] * n
ds[0] = 0

# BFS(幅優先探索)
while dq:
    t = dq.popleft()
    # tと繋がっている各頂点について
    for i in g[t]:
        # まだ調べていない場合
        if ds[i[0]] == -1:
            # 根からtまでの距離+tから次への距離
            ds[i[0]] = ds[t] + i[1]
            # 今調べた頂点をdequeに追加
            dq.append((i[0]))

# 偶数なら白、奇数なら黒とした。逆でも良い。
for i in ds:
    if i % 2 == 0:
        print(0)
    else:
        print(1)

Submission status: Accepted

Solution code:
from collections import deque
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))
ds = [-1]*n
dq = deque([0])
ds[0] = 0
while dq:
    t = dq.popleft()
    for i in g[t]:
        if ds[i[0]] == -1:
            ds[i[0]] = ds[t] + i[1]
            dq.append((i[0]))
for i in ds:
    if i%2 == 0:
        print(0)
    else:
        print(1)

Submission status: Accepted

Solution code:
from collections import defaultdict, deque
 
 
def bfs(start):
    q = deque([start])
    dist = [-1] * N
    dist[start] = 0
    while q:
        v = q.popleft()
        for nv, nw in g[v]:
            if dist[nv] >= 0:
                continue
            dist[nv] = (dist[v] + nw) % 2
            q.append(nv)
    return dist
 
 
N, *UVW = map(int, open(0).read().split())
g = defaultdict(set)
 
ans = [0] * N
for u, v, w in zip(*[iter(UVW)] * 3):
    u -= 1
    v -= 1
    g[u].add((v, w))
    g[v].add((u, w))
print("\n".join(map(str, bfs(0))))

Submission status: Accepted

Solution code:
from collections import deque

def nearlist(N, LIST):  # 隣接リスト
    NEAR = [set([]) for _ in range(N)]
    DIST = {}
    for a, b, c in LIST:
        NEAR[a - 1].add(b - 1)
        NEAR[b - 1].add(a - 1)
        DIST[(a - 1, b - 1)], DIST[(b - 1, a - 1)] = c, c
    return NEAR, DIST


def bfs(NEAR, N):  # 幅優先探索  # キュー
    ANS = [-1 for _ in range(N)]
    ANS[0] = 0
    que, frag = deque([0]), set([0])

    while len(que) > 0:
        q = que.popleft()
        for i in NEAR[q]:  # 移動先の候補
            if i in frag:  # 処理済みか否か
                continue
            if dist[(q, i)] % 2 == 0:
                ANS[i] = ANS[q]
            elif dist[(q, i)] % 2 == 1:
                ANS[i] = -ANS[q] + 1
            que.append(i), frag.add(i)
    return ANS


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

near, dist = nearlist(n, uvw)
ans = bfs(near, n)
print(*ans, sep='\n')

Submission status: Accepted

Solution code:
N = int(input())
Tree = [[] for _ in range(N+1)]
UVW = []

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

root = 1
parent = [0] * (N+1)
order = []
stack = [root]

while stack:
    x = stack.pop()
    order.append(x)
    for y in Tree[x]:
        if y == parent[x]:
            continue
        parent[y] = x
        stack.append(y)

dis = [0] * (N+1)

for u, v, w in UVW:
  if parent[u] == v:
    dis[u] = w
  else:
    dis[v] = w

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

for x in order:
  for y in Tree[x]:
    if y == parent[x]:
      continue
    if dis[y]%2 == 0:
      color[y] = color[x]
    else:
      color[y] = color[x] ^ 1

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

Submission status: Accepted

Solution code:
from collections import deque

N = int(input())
adj = [ [] for _ in range(N)]
clr = [-1 for _ in range(N)]

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

vis = [0 for _ in range(N)]
q = deque([(0,0)])
#print(clr)
while q:
  p, c = q.popleft()
  clr[p] = c
  vis[p] = 1
  for x, w in adj[p]:
    if vis[x] == 0:
      q.append((x,(w+c)%2))
      #print((x,(w+c)%2))

for c in clr:
  print(c)