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 getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
import heapq
import math
from fractions import gcd
import random
import string
import copy
from itertools import permutations
from operator import mul
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7


#############
# Main Code #
#############

N = getN()
edges = [[] for i in range(N)]
for i in range(N - 1):
    u, v, d = getNM()
    edges[u - 1].append([v - 1, d])
    edges[v - 1].append([u - 1, d])

def dij(start):
    dist = [float('inf') for i in range(N)]
    dist[start] = 0
    pq = [(0, start)]

    while len(pq) > 0:
        d, now = heapq.heappop(pq)
        if (d > dist[now]):
            continue
        for i in edges[now]:
            if dist[i[0]] > dist[now] + i[1]:
                dist[i[0]] = dist[now] + i[1]
                heapq.heappush(pq, (dist[i[0]], i[0]))
    return dist

ans = [0] * N
dij_list = dij(0)
for i in range(N):
    if dij_list[i] % 2 == 0:
        ans[i] = 0
    else:
        ans[i] = 1
for i in ans:
    print(i)

Submission status: Accepted

Solution code:
from collections import deque
n = int(input())
to = [[] for i in range(n)]
col = [0] + [-1] * (n - 1)

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

search = deque([0])
while search:
    v = search.popleft()
    for nv, nw in to[v]:
        if col[nv] != -1:
            continue
        col[nv] = (col[v] + nw) % 2
        search.append(nv)
print(*col, sep='\n')

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)
n=int(input())
path=[[] for i in range(n)]
for i in range(n-1):
    u,v,w=map(int,input().split())
    path[u-1].append((v-1,w%2))
    path[v-1].append((u-1,w%2))
ans=[0]+[-1]*(n-1)
def dfs(i):
    global n,path,ans
    for j in path[i]:
        if ans[j[0]]==-1:
            if j[1]:
                ans[j[0]]=1-ans[i]
                dfs(j[0])
            else:
                ans[j[0]]=ans[i]
                dfs(j[0])
dfs(0)
print("\n".join(map(str,ans)))

Submission status: Accepted

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

for i in range(n-1):
    a,b,c=map(int, input().split())
    edge[a-1].append([b-1,c])
    edge[b-1].append([a-1,c])
#任意の点から行ける偶数の距離で行けるところを同じ色で塗る。
col = [-1]*n
visited = [0]*n

def dfs(i,c):
    visited[i]=1
    col[i] = c
    for j in edge[i]:
        if not visited[j[0]]:
            if j[1]%2==0:
                dfs(j[0],c)
            else:
                dfs(j[0],-1*c)


def main():
    dfs(0,1)
    for i in range(n):
        print(max(col[i],0))



if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
import itertools
# import numpy as np
import time
import math

sys.setrecursionlimit(10 ** 7)

from collections import defaultdict

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

n = int(readline())

adj = [[] for i in range(n)]
for i in range(n - 1):
    u, v, w = map(int, readline().split())
    u -= 1
    v -= 1
    adj[u].append((w, v))
    adj[v].append((w, u))
# print(adj)

visited = [False for _ in range(n)]
dist = [0 for _ in range(n)]
def dfs(x, depth):
    if visited[x]:
        return
    visited[x] = True
    dist[x] = depth
    for y in adj[x]:
        dfs(y[1], depth + y[0])

dfs(0, 0)

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

Submission status: Accepted

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

import heapq
from collections import defaultdict

class Dijkstra:
    def __init__(self, rote_map, start_point, goal_point=None):
        self.rote_map = rote_map
        self.start_point = start_point
        self.goal_point = goal_point

    def execute(self):
        num_of_city = len(self.rote_map)
        dist = [float("inf") for _ in range(num_of_city)]
        prev = [float("inf") for _ in range(num_of_city)]

        dist[self.start_point] = 0
        heap_q = []
        heapq.heappush(heap_q, (0, self.start_point))
        while len(heap_q) > 0:
            prev_cost, src = heapq.heappop(heap_q)

            if dist[src] < prev_cost:
                continue

            for dest, cost in self.rote_map[src].items():
                if cost != float("inf") and dist[dest] > dist[src] + cost:
                    dist[dest] = dist[src] + cost
                    heapq.heappush(heap_q, (dist[dest], dest))
                    prev[dest] = src
        return dist

    def get_path(self, goal, prev):
        path = [goal]
        dest = goal
        while prev[dest] != float("inf"):
            path.append(prev[dest])
            dest = prev[dest]
        return list(reversed(path))

n = int(input())
route_map = [dict() for _ in range(n)]
for i in range(n - 1):
    u, v, wi = map(int, input().split())
    u, v = u - 1, v - 1
    route_map[u][v] = wi
    route_map[v][u] = wi

d = Dijkstra(route_map, 0).execute()
for k in range(n):
    if d[k] % 2 == 0:
        print(0)
    else:
        print(1)

Submission status: Accepted

Solution code:
n=int(input())
e=[[] for _ in range(n)]
for _ in range(n-1):
    xi,yi,wi=map(int, input().split())
    xi-=1;yi-=1
    e[yi].append((xi,wi))
    e[xi].append((yi,wi))

c=[0]*n
used=[0]*n

from collections import deque

q=deque()
q.append(0)
while q:
    u=q.popleft()
    for v,w in e[u]:
        if not used[v]:
            c[v]=(c[u]+w)%2
            used[v]=1
            q.append(v)
for i in c:
    print(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+1)]
    for _ in range(n-1):
        u,v,w=map(int,readline().split())
        G[u].append((v,w))
        G[v].append((u,w))

    d=[0]*(n+1)
    flags=[False]*(n+1)
    flags[1]=True
    q=deque([1])
    while len(q)>0:
        now=q.popleft()
        for nex in G[now]:
            if flags[nex[0]]==False:
                flags[nex[0]]=True
                q.append(nex[0])
                d[nex[0]]=d[now]+nex[1]

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

if __name__=="__main__":
    main()

Submission status: Accepted

Solution code:
import collections

N = int(input())

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


ans = [-1] * N

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


for u, v, w in UVW:
    A[u - 1].append([v - 1, w % 2])
    A[v - 1].append([u - 1, w % 2])

q = collections.deque()
q.append(0)

ans[0] = 0
while q:
    c = q.popleft()

    for ni, nd in A[c]:
        if ans[ni] != -1:
            continue

        if nd == 0:
            ans[ni] = ans[c]
        else:
            ans[ni] = ans[c] ^ 1

        q.append(ni)

if sum(ans) == 0:
    ans[0] = 1

for a in ans:
    print(a)

Submission status: Accepted

Solution code:
import unittest

import collections


def solve(n, tree):
    cl = [0] * n
    visited = [False]*n
    stack = []
    stack.append((0, 0))
    while stack:
        v, c = stack.pop()
        if visited[v]:
            continue
        cl[v] = c
        visited[v] = True
        for nv, w in tree[v]:
            if visited[nv]:
                continue
            stack.append((nv, (c + w) % 2))

    return '\n'.join([str(c) for c in cl])


def main():
    n = int(input())
    tree = [[] for i in range(n)]
    for _ in range(n-1):
        u, v, w = map(int, input().split())
        tree[v-1].append((u-1, w % 2))
        tree[u-1].append((v-1, w % 2))
    result = solve(n, tree)
    print(result)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from collections import deque
def main():
    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))
    V = [-1]*N
    V[0] = 0
    d = deque([(0,0)])
    while d:
        u, l = d.popleft()
        for v,w in E[u]:
            if V[v] == -1:
                V[v] = (l+w)%2
                d.append((v, (l+w)%2))
    print("\n".join( map( str, V)))
    
    
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**8)
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 = [None] * N
ans[0] = 0

def dfs(v,p=-1):
    for to,d in es[v]:
        if to==p: continue
        ans[to] = ans[v] ^ (d%2)
        dfs(to,v)
dfs(0)

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

Submission status: Accepted

Solution code:
from collections import deque

n = int(input())

u = [0] * n
v = [0] * n
w = [0] * n

dist = [-1] * n
adj_list = [[] for _ in range(n)]

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

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

q = deque()
dist[0] = 0
q.append(0)

while len(q) > 0:
    node = q.popleft()

    for next, d in adj_list[node]:
        if dist[next] > 0:
            continue

        if dist[next] == -1 or dist[next] > dist[node] + d:
            dist[next] = dist[node] + d
            q.append(next)

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

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

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

from heapq import heappush, heappop, heapify
INF = float('inf')

dist = [INF] * N
visited = [False] * N

q = g[0]
heapify(q)
dist[0] = 0
visited[0] = True

while q:
    c, v = heappop(q)

    if visited[v]: continue
    visited[v] = True
    dist[v] = c

    for w, u in g[v]:
        if visited[u]: continue
        heappush(q, (c+w, u))

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

Submission status: Accepted

Solution code:
from collections import deque
N = int(input())
E = [[] for i in range(N + 1)]
ans = [-1]*(N+1)
ans[1] = 0
for i in range(N - 1):
    u, v, w = map(int, input().split((' ')))
    E[u].append((u, v, w % 2))
    E[v].append((v, u, w % 2))
dfs = deque(E[1])
while dfs:
    p = (dfs.popleft())
    f, t, w = p
    if ans[t] != -1:
        continue
    if w == 0:
        ans[t] = ans[f]
    else:
        ans[t] = 0 if ans[f] else 1
    for i in E[t]:
        dfs.append(i)
for i in ans[1:]:
    print(i)

Submission status: Accepted

Solution code:
import collections
def resolve():
    N = int(input())
    VVW = [list(map(int, input().split())) for _ in range(N-1)]
    adjs = [[] for _ in range(N)]
    for vvw in VVW:
        adjs[vvw[0]-1].append([vvw[1]-1, vvw[2]])
        adjs[vvw[1]-1].append([vvw[0]-1, vvw[2]])

    result = [None for _ in range(N)]
    deq = collections.deque([[0, 0]])
    result[0] = "0"

    while deq:
        node, cost = deq.popleft()
        for adj in adjs[node]:
            nextnode, nextcost = adj[0], adj[1]
            if result[nextnode] is not None:
                continue
            if nextcost%2 == 0:
                result[nextnode] = result[node]
            else:
                result[nextnode] = "1" if result[node] == "0" else "0"
            deq.append([nextnode, nextcost])
    
    [print(r) for r in result]



if '__main__' == __name__:
    resolve()

Submission status: Accepted

Solution code:
# input
n = int(input())
graph = [[] for i in range(n+1)]
for i in range(n-1):
  a, b, c = map(int, input().split())
  graph[a].append([b, c])
  graph[b].append([a, c])
color = [-1 for i in range(n+1)]

# main
que = [1]
color[1] = 0
while len(que) != 0:
  nowv = que.pop(0)
  nowc = color[nowv]
  
  for nx in graph[nowv]:
    if color[nx[0]] != -1:
      continue
    que.append(nx[0])
    if nx[1] % 2 == 1:
      color[nx[0]] = 1 - nowc
    else:
      color[nx[0]] = nowc

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

Submission status: Accepted

Solution code:
import sys
from collections import Counter
from collections import deque
import heapq
import math
import fractions
import bisect
import itertools
def input(): return sys.stdin.readline().strip()
def mp(): return map(int,input().split())
def lmp(): return list(map(int,input().split()))

n=int(input())
tree=[[] for i in range(n+1)]
for i in range(n-1):
    a,b,c=mp()
    tree[a].append([a,b,c])
    tree[b].append([b,a,c])
ans=[-1]*(n+1)
ans[1]=0
que=deque()
que.append(tree[1])
while len(que):
    q=que.popleft()
    for x,y,z in q:
        if ans[y]==-1:
            ans[y]=(ans[x]+z)%2
            que.append(tree[y])
print(*ans[1:],sep="\n")

Submission status: Accepted

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()

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

# O(ElogV)
import heapq
def dijkstra(s):
    # 始点sから各頂点への最短距離
    d = [float('inf')]*n
    d[s] = 0
    # 各頂点が訪問済みかどうか
    used = [False]*n
    used[s] = True
    # 仮の距離を記録するヒープ
    que = []
    for e in edge[s]:
        heapq.heappush(que, e)
    while que:
        minedge = heapq.heappop(que)
        if used[minedge[1]]:
            continue
        v = minedge[1]
        d[v] = minedge[0]
        used[v] = True
        for e in edge[v]:
            if not used[e[1]]:
                heapq.heappush(que, [e[0] + d[v], e[1]])
    return d

d = dijkstra(0)
ans = [0]*n

for i in range(n):
    if d[i] % 2 == 1:
        ans[i] = 1

for i in ans:
    print(i)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(100000000)

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

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

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)
from collections import defaultdict
def dfs(node_i, oe):
    if ans[node_i] != -1:
        return
    next_nodes = graph[node_i]
    ans[node_i] = oe
    for next_i, cost in next_nodes:
        dfs(next_i, (oe+cost)%2)
        

N = int(input())
ans = [-1 for i in range(N+1)]
graph = defaultdict(list)
for i in range(N-1):
    u, v, w = map(int, input().split())
    graph[u] += [(v, w)]
    graph[v] += [(u, w)]

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

Submission status: Accepted

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

def dfs(curr_v, pare_v, curr_sum, visited, g):
    if curr_sum%2 == 0:
        visited[curr_v] = 0
    else:
        visited[curr_v] = 1
    for neib_vw in g[curr_v]:
        if neib_vw[0] == pare_v: continue
        dfs(neib_vw[0], curr_v, curr_sum+neib_vw[1], visited, g)
    

N = int(input())
g = [ [] for _ in range(N+1)]
visited = [-1] * (N+1)

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

dfs(1, -1, 0, visited, g)
for p in visited[1:]:
    print(p)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2000000)

N = int(input())
edges = [[] for _ in range(N+1)]
for _ in range(N-1):
    u,v,w = map(int,input().split())
    edges[u].append((v,w))
    edges[v].append((u,w))
color = [-1]*(N+1)
def dfs(n,p,c):
    color[n]=c
    for nx,w in edges[n]:
        if nx != p:
            if w % 2 == 0:
                nxC = c
            else:
                nxC = (c+1)%2
            dfs(nx,n,nxC)

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

Submission status: Accepted

Solution code:
from collections import deque

N = int(input())

edge = [[int(s) - 1 for s in input().split()] for _ in range(N-1)]
graph = [[] for _ in range(N)]
weight_odd = {}

for i, j, w in edge:
    graph[i].append(j)
    graph[j].append(i)
    weight_odd[(i, j)] = (w % 2 != 0)
    weight_odd[(j, i)] = (w % 2 != 0)

dq = deque([0])
visited = [False] * N
color = [1] * N
while(dq):
    search_obj = dq.pop()
    col1 = color[search_obj]
    col2 = 0 if col1 == 1 else 1
    for candidate_obj in graph[search_obj]:
        if not visited[candidate_obj]:
            if weight_odd[(candidate_obj, search_obj)]:
                color[candidate_obj] = col1
            else:
                color[candidate_obj] = col2
            dq.appendleft(candidate_obj)
            visited[candidate_obj] = True

for c in color:
    print(c)

Submission status: Accepted

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

# スタートを0で塗り、行先が奇数であれば違う色で塗る、を繰り返せばよい
N = int(readline())
G = [[] for i in range(N)]

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

ans = [-1] * N

stack = []
# 頂点, 色
stack.append([0,0])
while stack:
  v,color = stack.pop()
  if ans[v] != -1:
    continue
  ans[v] = color
  for child in G[v]:
    col = color
    if child[1] % 2 == 1:
      col ^= 1
    stack.append([child[0], col])

for a in ans:
  print(a)

Submission status: Accepted

Solution code:
import sys
n = int(input())
sys.setrecursionlimit(2*n)
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))
colors = [None]*n
colors[0] = 0
def DFS(node):
    for c_node, l in graph[node]:
        if colors[c_node] is not None:
            continue
        colors[c_node] = (l+colors[node])%2
        DFS(c_node)
DFS(0)
for i in colors:
    print(i)

Submission status: Accepted

Solution code:
def main():
    from collections import deque, defaultdict
    n, *uvw = map(int, open(0).read().split())
    l = defaultdict(dict)
    g = [[] for _ in range(n + 1)]

    for u, v, w in zip(uvw[::3], uvw[1::3], uvw[2::3]):
        g[u].append(v)
        g[v].append(u)
        l[u].update({v: w % 2})

    l[0].update({1: 0})

    vis = [False] * (n + 1)
    col = [0] * (n + 1)

    q = deque()
    q.append([0, 1, 0])

    while q:
        i, j, k = q.popleft()
        if vis[j]:
            continue
        vis[j] = True
        c = k if l[min(i, j)][max(i, j)] == 0 else 1 - k
        col[j] = c

        for x in g[j]:
            q.appendleft([j, x, c])

    print(*col[1:], sep='\n')


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    from collections import deque, defaultdict
    n, *uvw = map(int, open(0).read().split())
    l = defaultdict(dict)
    g = [[] for _ in range(n + 1)]

    for u, v, w in zip(uvw[::3], uvw[1::3], uvw[2::3]):
        g[u].append(v)
        g[v].append(u)
        l[u].update({v: w % 2})
        l[v].update({u: w % 2})

    l[0].update({1: 0})

    vis = [False] * (n + 1)
    col = [0] * (n + 1)

    q = deque()
    q.append([0, 1, 0])

    while q:
        i, j, k = q.popleft()
        if vis[j]:
            continue
        vis[j] = True
        c = k if l[i][j] == 0 else 1 - k
        col[j] = c

        for x in g[j]:
            q.appendleft([j, x, c])

    ans = '\n'.join(map(str, col[1:]))
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    from collections import deque, defaultdict
    n, *uvw = map(int, open(0).read().split())
    l = defaultdict(dict)
    g = [[] for _ in range(n + 1)]

    for u, v, w in zip(uvw[::3], uvw[1::3], uvw[2::3]):
        g[u].append(v)
        g[v].append(u)
        l[u].update({v: w % 2})

    l[0].update({1: 0})

    vis = [False] * (n + 1)
    col = [0] * (n + 1)

    q = deque()
    q.append([0, 1, 0])

    while q:
        i, j, k = q.popleft()
        if vis[j]:
            continue
        vis[j] = True
        c = k if l[min(i, j)][max(i, j)] == 0 else 1 - k
        col[j] = c

        for x in g[j]:
            q.appendleft([j, x, c])

    ans = '\n'.join(map(str, col[1:]))
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

from collections import defaultdict, deque
g = defaultdict(list)
for u, v, w in uvw:
    g[u-1].append((v - 1, w))
    g[v-1].append((u - 1, w))

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

while q:
    cur = q.popleft()
    for target, w in g[cur]:
        if ans[target] == -1:
            if w % 2 == 0:
                ans[target] = ans[cur]
            else:
                ans[target] = 1 - ans[cur]
            q.append(target)

for a in ans:
    print(a)

Submission status: Accepted

Solution code:

from collections import deque

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

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


queue = deque([0])
ans = [0]*n
checked = [0]*n

while queue:
    x =queue.popleft()
    checked[x] = -1
    dis = ans[x]
    for tup in arr[x]:
        if checked[tup[0]]> -1:
            ans[tup[0]]=(dis+tup[1])%2
            queue.append(tup[0])
print(*ans,sep='\n')

Submission status: Accepted

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

que=deque([0])
ans=[0]*n
visited=[0]*n

while que:
    x=que.popleft()
    visited[x]=-1
    dis=ans[x]
    for tup in arr[x]:
        if visited[tup[0]]>-1:
            ans[tup[0]]=(dis+tup[1])%2
            que.append(tup[0])
print(*ans,sep='\n')

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(100000)

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

color = [None] * N
def dfs(n,l):
  if l%2==0:
    color[n] = 1
  else:
    color[n] = 0

  for nei, nl in adj[n]:
    if color[nei] is not None:
      if (l+nl) % 2 == 0 and color[nei] != 1:
        return False
      if (l+nl) % 2 == 1 and color[nei] != 0:
        return False
    else:
      dfs(nei, l+nl)

  return True

for i in range(N):
  if color[i] is None:
    if not dfs(i,0):
      print(-1)
      exit()

for c in color: print(c)

Submission status: Accepted

Solution code:
from collections import deque

n = int(input())

color = [-1]*(n+1)
rel = [{} for i in range(n+1)]

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

def f(n):
    color[n] = 0
    stack = deque()
    stack.append(n)
    while stack:
        new = stack.pop()
        for ver in rel[new]:
            if color[ver] == -1:
                color[ver] = 1-color[new] if rel[new][ver]&1 else color[new]
                stack.append(ver)

for i in range(1, n+1):
    if color[i] != -1: continue
    f(n)

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

Submission status: Accepted

Solution code:
import sys
from collections import deque
readline = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7

def main():
    N = int(readline())
    tree = [[] for _ in range(N)]
    for i in range(N-1):
        u, v, w = map(int, readline().split())
        u, v = u-1, v-1
        tree[u].append((v,w))
        tree[v].append((u,w))
    color = [-1]*N
    color[0]=0

    que = deque([0])
    while que:
        index = que.popleft()
        for next_, weight in tree[index]:
            if color[next_]==-1:
                if weight%2==0:
                    color[next_] = color[index]
                else:
                    color[next_] = color[index]^1
                que.append(next_)
    for c in color:
        print(c)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

n = int(input())

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

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

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


queue = [0]
while(len(queue) > 0):
    index = queue.pop()
    tree_tmp = tree[index]
    for next_, weight in tree_tmp:
        # print(color)
        if color[next_] == -1:
            if weight % 2 == 0:
                color[next_] = color[index]
            else:
                color[next_] = (color[index]+1) % 2
            queue.append(next_)


[print(i) for i in color]

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(20000000)

n = int(input())

graph = [[] for _ in range(n)]
for i 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])
# print(graph)

ans = [-1]*n

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


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

Submission status: Accepted

Solution code:
import sys
## io ##
def IS(): return sys.stdin.readline().rstrip()
def II(): return int(IS())
def MII(): return list(map(int, IS().split()))
def MIIZ(): return list(map(lambda x: x-1, MII()))
from collections import deque
#======================================================#
def main():
    n = II()
    graph = [[] for _ in range(n)]
    for i in range(n-1):
        u,v,w = MII()
        graph[u-1].append((w, v-1))
        graph[v-1].append((w, u-1))
    dq = deque()
    color = [-1]*n
    dist = [-1]*n
    dq.append((0,0))
    color[0] = 0
    dist[0] = 0
    while dq:
        prev_cost, src = dq.popleft()
        for cost, dst in graph[src]:
            if dist[dst] != -1:
                continue
            if prev_cost%2 == cost%2:
                color[dst] = 0
            else:
                color[dst] = 1
            dist[dst] = dist[src] + cost
            dq.append((dist[dst], dst))
    print(*color, sep='\n')

if __name__ == '__main__':
    main()

Submission status: Accepted

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

n=int(input())

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

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

que=deque()
que.append(0)

while que:
  x=que.popleft()
  for i in tree[x]:
    nx=i[0]
    nw=i[1]
    if ans[nx]==-1:
      que.append(nx)
      if nw%2==0:
        ans[nx]=ans[x]
      else:
        ans[nx]=(ans[x]+1)%2

for i in ans:
  print(i)

Submission status: Accepted

Solution code:
from collections import deque
N = int(input())
UVW = [list(map(int, input().split())) for _ in range(N-1)]
G = [{} for _ in range(N+1)]
for u, v, w in UVW:
    G[u-1][v-1] = w
    G[v-1][u-1] = w
# print(G)


distance = [-1] * N

que = deque([(0, 0)])
while que:
    c, d = que.popleft()
    distance[c] = d

    for n, w in G[c].items():
        if distance[n] == -1:
            que.append((n, d+w))

# print(distance)
print(*[d % 2 for d in distance], sep='\n')

Submission status: Accepted

Solution code:
import sys

def tree_path():
    def walk(i,c):
        if d[i] == -1:
            d[i] = c
            for node, dist in path[i]:
                walk(node, c+dist)
    sys.setrecursionlimit(100007)
    n = int(input())
    path = [[] for _ in range(n+1)]
    for _ in range(n-1):
        u , v , w = map(int,input().split())
        path[u].append([v,w])
        path[v].append([u,w])
    
    d = [-1] * (n+1)
    walk(1,0)
    for item in d[1:]:
        print(item % 2)
tree_path()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from collections import deque
def bfs(now):
    plan = deque()
    plan.append(now)
    while plan:
        now = plan.popleft()
        color = COLOR[now]
        for bady, l in LINK[now]:
            if COLOR[bady] != -1:
                continue
            plan.append(bady)
            if l%2:
                COLOR[bady] = 1 - color
            else:
                COLOR[bady] = color

if __name__ == '__main__':
    N = int(input())
    LINK = [[]*(N+1) for i in range(N+1)]
    # LINK = [deque()*(N+1) for i in range(N+1)]
    for i in range(N-1):
        a, b, l = map(int, input().split())
        LINK[a].append([b, l])
        LINK[b].append([a, l])
    # print(LINK)
    # print(LINK[1])
    # print(LINK[1][0])
    COLOR= [-1]*(N+1)
    COLOR[1] = 1
    bfs(1)
    for i in range(1,N+1):
        print(COLOR[i])

Submission status: Accepted

Solution code:
import queue
N = int(input())
ans = [-1]*N
odd = [[] for _ in range(N)]
even = [[] for _ in range(N)]
for i in range(N-1):
    u,v,w = map(int,input().split())
    if w % 2 == 0:
        even[u-1].append(v-1)
        even[v-1].append(u-1)
    else:
        odd[u-1].append(v-1)
        odd[v-1].append(u-1)

q = queue.Queue()
q.put(0)
ans[0] = 0

while (not q.empty()):
    now = q.get()
    nowa = ans[now]
    for i in odd[now]:
        if ans[i] == -1:
            if nowa == 0:
                ans[i] = 1
            else:
                ans[i] = 0
            q.put(i)
    for j in even[now]:
        if ans[j] == -1:
            ans[j] = nowa
            q.put(j)

for i in ans:
    print(i)