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:
class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n+1)]
        self.rank = [0] * (n+1)

    # 検索
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    # 併合
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
    def height(self, x):
        return self.rank[x]

    # 同じ集合に属するか判定
    def same_check(self, x, y):
        return self.find(x) == self.find(y)


def BFS(K,edges,N):
  roots=[ [] for i in range(N)]
  for a,b,c in edges:
    roots[a-1]+=[(b-1,c)]
    roots[b-1]+=[(a-1,c)]
  dist=[-1]*N
  stack=[]
  stack.append(K)
  dist[K]=0
  while stack:
    label=stack.pop(-1)
    for i,c in roots[label]:
      if dist[i]==-1:
        dist[i]=dist[label]+c
        stack+=[i]
  return dist

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

distance = BFS(0, edges, N)


ans = []
for i in range(N):
    if distance[i] % 2 == 0:
        ans.append(0)
    else:
        ans.append(1)

for c in ans:
    print(c)

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!

N = int(input())

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

for i in range(N-1):
    u, v, w = map(int, input().rstrip().split(' '))
    u = u - 1
    v = v - 1
    
    edges[u].append([v, w])
    edges[v].append([u, w])
    
from collections import deque

temp = deque([[0, 0]])

color = [-1] * N
while len(temp) > 0:
    a, b = temp.popleft()
    color[a] = b
    
    
    for edge in edges[a]:
        if edge[1] % 2 == 1 and color[edge[0]] == -1:
            temp.append([edge[0], 1 - b])
        elif color[edge[0]] == -1:
            temp.append([edge[0], b])

for c in color:
    print(c)

Submission status: Accepted

Solution code:
from collections import deque
N = int(input())
ans = [True]*(N+1)
already = [False] * (N+1)

td = {i:[] for i in range(1,N+1)}
for i in range(N-1):
	ut,vt,wt = map(int,input().split(' '))
	td[ut].append((vt,wt%2))
	td[vt].append((ut,wt%2))

q = deque([1])
while(q):
	i = q.popleft()
	already[i] = True
	for v,w in td[i]:
		if not already[v]:
			q.append(v)
			#print(i,v,w)
			if w:
				ans[v] = not ans[i]
			else:
				ans[v] = ans[i]

#print(td)

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

Submission status: Accepted

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

N = int(input())
        
G = [[] for i in range(N)]
for _ in range(N - 1):
    a, b, c = map(int, input().split())
    G[a - 1].append([b - 1, c])
    G[b - 1].append([a - 1, c])
    
color = [0] * N

def dfs(v, c):
    if color[v] == 0:
        color[v] = c
    for i in range(len(G[v])):
        if color[G[v][i][0]] == 0:
            if G[v][i][1] % 2 == 0:
                dfs(G[v][i][0], color[v])
            else:
                dfs(G[v][i][0] , -color[v])
                
for i in range(N):
    dfs(i, 1)
    # print(color)
    
for i in range(N):
    if color[i] == 1:
        print(0)
    else:
        print(1)

Submission status: Accepted

Solution code:
import array
import collections
import heapq

AdjacentVertex = collections.namedtuple("AdjacentVertex", "vertex cost")
INF = 2**31 - 1
NO_VERTEX = -1

ans = [0 for i in range(10**5)]


# Prim法で頂点0からの最小全域木を求める
def compute_mst_prim(max_v, adj_list):
    # pred[u]は頂点uの「ひとつ前」の頂点を表す
    pred = collections.defaultdict(lambda: NO_VERTEX)
    # uとpred[u]を結ぶ辺の重みがkey[u]に入る
    key = collections.defaultdict(lambda: INF)
    key[0] = 0
    # 二分ヒープを優先度付きキューとして用いる
    pq = [(key[v], v) for v in range(max_v)]
    heapq.heapify(pq)
    # 優先度付きキューに頂点が入っているかを示す配列
    in_pq = array.array("B", (True for _ in range(max_v)))
    while pq:
        _, u = heapq.heappop(pq)
        in_pq[u] = False
        for v, v_cost in adj_list[u]:
            if in_pq[v]:
                weight = v_cost
                if weight < key[v]:
                    pred[v] = u
                    key[v] = weight
                    ans[v] = ans[pred[v]] + key[v]
                    heapq.heappush(pq, (weight, v))
                    in_pq[v] = True
    return (pred, key)


def main():
    max_v = int(input())
    max_e = max_v - 1
    adjacency_list = collections.defaultdict(set)
    for _ in range(max_e):
        s, t, w = map(int, input().split())
        s -= 1
        t -= 1
        adjacency_list[s].add(AdjacentVertex(t, w))
        adjacency_list[t].add(AdjacentVertex(s, w))
    (_, key) = compute_mst_prim(max_v, adjacency_list)
    for i in range(max_v):
        print(ans[i] % 2)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000)

nVertices = int(input())
edges = [[] for _ in range(nVertices + 1)]
length = {}
for _ in range(nVertices - 1):
    u, v, l = map(int, input().split())
    edges[u].append(v)
    edges[v].append(u)
    if u > v:
        u, v = v, u
    length[(u, v)] = l
color = [None] * (nVertices + 1)
color[1] = 0

def dfs(par, v):
    for child in edges[v]:
        if child != par:
            key = (min(v, child), max(v, child))
            if length[key] & 1 == 0:
                color[child] = color[v]
            else:
                color[child] = color[v] ^ 1
            dfs(v, child)

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

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(1000000)

n = int(input())
ans = [-1]*n
tree = [[] for i in range(n)]

def dfs(x,y):
  ans[x] = y
  for node in tree[x]:
    if ans[node[0]] == -1:
      if node[1] % 2 == 0:
        dfs(node[0],y)
      else:
        if y:
          dfs(node[0],0)
        else:
          dfs(node[0],1)

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

dfs(0,0)
for a in ans:
  print(a)

Submission status: Accepted

Solution code:
n = int(input())
route = {}

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

r = [-1] * n
q = [1]
r[0] = 0
while len(q) > 0:
    u = q.pop()
    vws = route[u]
    for (v, w) in vws:
        if r[v-1] != -1:
            continue
        r[v-1] = (w & 1) ^ r[u-1]
        q.append(v)

for i in r:
    print(i)

Submission status: Accepted

Solution code:
from collections import deque

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

adj = [[] for _ in range(N+1)]
for b in branch:
  adj[b[0]].append([b[1],b[2]])
  adj[b[1]].append([b[0],b[2]])

ans = [-1] * (N+1)
deq = deque()
deq.appendleft(1)
while len(deq) > 0:
  v = deq.pop()
  for u, w in adj[v]:
    if ans[u] == -1:
      deq.appendleft(u)
    if ans[v] == -1 and ans[u] == -1:
      if w % 2 == 0:
        ans[v] = 0
        ans[u] = 0
      else:
        ans[v] = 0
        ans[u] = 1
    elif ans[v] == 0:
      if w % 2 == 0:
        ans[u] = 0
      else:
        ans[u] = 1
    else:
      if w % 2 == 0:
        ans[u] = 1
      else:
        ans[u] = 0
if N == 1:
  print(0)
else:
  for i in range(1,N+1):
    print(ans[i])

Submission status: Accepted

Solution code:
N = int(input())

mpA = dict()
mpB = dict()
for n in range(N-1):
    u, v, w = list(map(int, input().split()))
    if u in mpA:
        mpA[u].append((v, w))
    else:
        mpA[u] = [(v, w)]
    if v in mpB:
        mpB[v].append((u, w))
    else:
        mpB[v] = [(u, w)]

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

A = 0
Z[1] = A

nxt = [(1, A)]
while(len(nxt) > 0):
    nxt2 = []
    for x in nxt:
        xx, xA = x[0], x[1]
        if xx in mpA:
            vA = mpA[xx]
            for wa in vA:
                v, w = wa[0], wa[1]
                if Z[v] == -1:
                    if w % 2 == 0:
                        Z[v] = xA
                        nxt2.append((v, Z[v]))
                    else:
                        Z[v] = 1 - xA
                        nxt2.append((v, Z[v]))
        if xx in mpB:
            vB = mpB[xx]
            for wb in vB:
                u, w = wb[0], wb[1]
                if Z[u] == -1:
                    if w % 2 == 0:
                        Z[u] = xA
                        nxt2.append((u, Z[u]))
                    else:
                        Z[u] = 1 - xA
                        nxt2.append((u, Z[u]))
    nxt = nxt2

for n in range(1, N+1):
    print(Z[n])

Submission status: Accepted

Solution code:
N = int(input())
nodes = {}
for _ in range(N-1):
    l, r, d = map(int, input().split())
    if nodes.get(str(l)) is None:
        nodes[str(l)] = {'to': [], 'color': -1}
    if nodes.get(str(r)) is None:
        nodes[str(r)] = {'to': [], 'color': -1}

    nodes[str(l)]['to'].append((str(r), d))
    nodes[str(r)]['to'].append((str(l), d))

q = [('1', 0)]
while q:
    node, color = q.pop()

    nodes[node]['color'] = color
    for n, d in nodes[node]['to']:
        if nodes[n]['color'] != -1:
            continue

        if d % 2 == 0:
            q.append((n, color))
        else:
            q.append((n, (color+1) % 2))


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

Submission status: Accepted

Solution code:
def d_even_relation(N, Nodes):
    from collections import deque
    graph = [{} for _ in range(N)]
    for u, v, w in Nodes:
        graph[u - 1][v - 1] = w
        graph[v - 1][u - 1] = w

    ans = [0] * N
    queue = deque([(-1, -1, 0)])
    while queue:
        previous, parent, child = queue.pop()
        if parent == -1:
            ans[child] = 0
        elif previous != child:
            length = graph[parent][child]
            if length % 2 == 0:
                ans[child] = ans[parent]
            else:
                ans[child] = 1 if ans[parent] == 0 else 0
        for k in graph[child].keys():
            if parent != k:
                queue.appendleft((parent, child, k))
    return '\n'.join(map(str, ans))

N = int(input())
Nodes = [[int(i) for i in input().split()] for j in range(N - 1)]
print(d_even_relation(N, Nodes))

Submission status: Accepted

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

isChecked = [False for i in range(N)]
ans = [0 for i in range(N)]
for k in d:
    c = ans[k-1]
    q = [[0, k]]
    while q:
        l = q[-1][0]
        p = q[-1][1]
        q.pop()
        #print(l, p)
        if isChecked[p-1]:
            continue
        if l%2 == 0:
            ans[p-1] = c
        else:
            ans[p-1] = (c+1)%2
        isChecked[p-1] = True
        for e in d[p]:
            n = e[0]
            w = e[1]
            q.append([l+w, n])

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

Submission status: Accepted

Solution code:
import heapq
N = int(input())
L = []
edge = [[] for i in range(N)]
for i in range(N-1):
  x,y,z = map(int,input().split())
  edge[x-1].append([x-1,y-1,z])
  edge[y-1].append([x-1,y-1,z])
ans = ['TBD']*N
ans[0] = 0
edgelist = []
for i in edge[0]:
  heapq.heappush(edgelist,i)
while len(edgelist) != 0:
  ed = heapq.heappop(edgelist)
  if ans[ed[1]] == 'TBD':
    if ed[2]%2 == 0:
      if ans[ed[0]] == 0:
        ans[ed[1]] = 0
      else:
        ans[ed[1]] = 1
    else:
      if ans[ed[0]] == 0:
        ans[ed[1]] = 1
      else:
        ans[ed[1]] = 0
    for e in edge[ed[1]]:
      if ans[e[1]] == 'TBD':
        heapq.heappush(edgelist,e)
      elif ans[e[0]] == 'TBD':
        heapq.heappush(edgelist,e)
  elif ans[ed[0]] == 'TBD':
    if ed[2]%2 == 0:
      if ans[ed[1]] == 0:
        ans[ed[0]] = 0
      else:
        ans[ed[0]] = 1
    else:
      if ans[ed[1]] == 0:
        ans[ed[0]] = 1
      else:
        ans[ed[0]] = 0
    for e in edge[ed[0]]:
      if ans[e[1]] == 'TBD':
        heapq.heappush(edgelist,e)
      elif ans[e[0]] == 'TBD':
        heapq.heappush(edgelist,e)
for i in range(N):
  print(ans[i])

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(1000000)
n=int(input())
mat=[[] for i in range(n)]
group=[0]*n
group[0]=1
for i in range(n-1):
    u, v, w = map(int, input().split())
    mat[u-1].append((v-1, w))
    mat[v-1].append((u-1, w))
def C(kw, p, l):
    global group
    k, w = kw
    if w%2==1:
        p*=-1
    group[k]=p
    for kwi in mat[k]:
        if kwi[0]!=l:
            C(kwi, p, k)
for kwi in mat[0]:
    C(kwi, 1, 0)
for gi in group:
    if gi>0:
        print(1)
    else:
        print(0)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000)

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

col = [-1 for _ 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%2)%2)

dfs(1, 0)

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

Submission status: Accepted

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



ret = {}
done = [0 for x in range(N)]

queue = [0]

for i in range(N):
    curr = queue.pop()
    if curr == 0:
        ret[0] = 0

    for neigh in x[curr]:
        if done[neigh[0]] == 1:
            continue
        if neigh[1] % 2 == 0:
            ret[neigh[0]] = ret[curr]
        else:
            ret[neigh[0]] = 0 if ret[curr] == 1 else 1

        queue.append(neigh[0])
    done[curr] = 1


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

Submission status: Accepted

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


def solve(N: int, adjacent):
    color = [0] * N
    visited = [False] * N

    visited[0] = True
    
    Q = queue.Queue()
    Q.put(0)
    while not Q.empty():
        u = Q.get()
        for v, w in adjacent[u]:
            if visited[v]:
                continue
            visited[v] = True
            if w == 0:
                color[v] = color[u]
            else:
                color[v] = (color[u] + 1) % 2
            Q.put(v)
    for c in color:
        print(c)


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    adjacent = [[] for _ in range(N)]
    for i in range(N-1):
        u = int(next(tokens)) - 1
        v = int(next(tokens)) - 1
        w = int(next(tokens)) % 2
        adjacent[u].append((v, w))
        adjacent[v].append((u, w))
    solve(N, adjacent)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

def BFS(K,edges,N):
  roots=[ [] for i in range(N)]
  for a,b,c in edges:
    roots[a-1]+=[(b-1,c)]
    roots[b-1]+=[(a-1,c)]
  dist=[-1]*N
  stack=[]
  stack.append(K)
  dist[K]=0
  while stack:
    label=stack.pop(-1)
    for i,c in roots[label]:
      if dist[i]==-1:
        dist[i]=dist[label]+c
        stack+=[i]
  return dist
 

edges=[]
N = int(input())
K = 1
for i in range(N-1):
  edges += [list(map(int,input().split()))]
distance = BFS(K-1,edges,N)
for i in range(N):
  print(distance[i] % 2)

Submission status: Accepted

Solution code:
inpl = lambda: list(map(int,input().split()))
class ParityTree:
    def __init__(self,N):
        self.parent = [-1]*int(N)
        self.parity = [0]*int(N)

    def root(self, n):
        if self.parent[n] < 0:
            return n, 0
        else:
            m, p = self.root(self.parent[n])
            self.parent[n] = m
            self.parity[n] = (p + self.parity[n]) % 2
            return m, self.parity[n]

    def merge(self, m, n, parity):
        rm, pm = self.root(m)
        rn, pn = self.root(n)
        if rm != rn:
            if -self.parent[rm] < -self.parent[rn]:
                rm, rn = rn, rm
            self.parent[rm] += self.parent[rn]
            self.parent[rn] = rm
            self.parity[rn] = (pm + pn + parity) % 2

    def size(self, n):
        return -self.parent[self.root(n)]
    
    def aresame(self, m, n):
        return self.root(m) == self.root(n)

N = int(input())
pt = ParityTree(N)
for i in range(N-1):
    u, v, w = inpl()
    pt.merge(u-1,v-1,w)

for i in range(N):
    print(pt.root(i)[1])

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)
def dfs(s):
    visited[s]=1
    for v in adj[s]:
        if v not in visited:
            if (s,v) in we:
                y[v]=y[s]+we[(s,v)]
            elif (v,s) in we:
                y[v]=y[s]+we[(v,s)]
            dfs(v)
n=int(input())
adj={}
we={}
visited={}
y=[0]*(n+1)
for q in range(n-1):
    a,b,w=map(int,input().split())
    if a not in adj:
        adj[a]=[b]
    else:
        adj[a].append(b)
    if b not in adj:
        adj[b]=[a]
    else:
        adj[b].append(a)
    we[(a,b)]=w
if n>1:
	dfs(1)
for i in range(1,n+1):
    if y[i]%2==0:
        print(0)
    else:
        print(1)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
n=int(input())
E=[]
for i in range(n-1):
  u,v,w=map(int,input().split())
  E.append([u,v,w])
def BFS(edges,N):
  roots=[[] for i in range(N)]
  for a,b,c in edges:
    roots[a-1]+=[(b-1,c)]
    roots[b-1]+=[(a-1,c)]
  dist=[-1]*N
  stack=[]
  stack.append(0)
  dist[0]=0
  while stack:
    label=stack.pop(-1)
    for i,c in roots[label]:
      if dist[i]==-1:
        dist[i]=dist[label]+c
        stack+=[i]
  return dist
D=BFS(E,n)
for i in range(n):
  print(0 if D[i]%2==0 else 1)

Submission status: Accepted

Solution code:
N = int(input())

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

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


stack = [0]
while len(stack) > 0:
    pos = stack.pop()
    for (p, w) in tree[pos]:
        if color[p] == -1:
            color[p] = color[pos] ^ w
            stack.append(p)

for c in color:
    print(c)

Submission status: Accepted

Solution code:
# AtCoder Beginner Contest 126
# https://atcoder.jp/contests/abc126
import sys
#import numpy as np

s2nn = lambda s: [int(c) for c in s.split(' ')]
ss2nn = lambda ss: [int(s) for s in ss]
ss2nnn = lambda ss: [s2nn(s) for s in ss]
i2s = lambda: sys.stdin.readline().rstrip()
i2n = lambda: int(i2s())
i2nn = lambda: s2nn(i2s())
ii2ss = lambda n: [sys.stdin.readline().rstrip() for _ in range(n)]
ii2nn = lambda n: ss2nn(ii2ss(n))
ii2nnn = lambda n: ss2nnn(ii2ss(n))

def main():
    N = i2n()
    d = [[] for _ in range(N)]
    #uvw = ii2nnn(N-1)
    #for u, v, w in uvw:
    for _ in range(N-1):
        u, v, w = i2nn()
        b = w % 2 == 0
        d[u-1].append((v-1, b))
        d[v-1].append((u-1, b))
    nn = [-1 for _ in range(N)]
    nn[0] = 0
    def main2(src):
        links = d[src]
        c = nn[src]
        for dst, b in links:
            if nn[dst] == -1:
                nn[dst] = c if b else 1-c
                main2(dst)
    #main2(0)
    que = [0]
    que2 = []
    while True:
        if len(que) == 0:
            break
        que2 = []
        for src in que:
            links = d[src]
            c = nn[src]
            for dst, b in links:
                if nn[dst] == -1:
                    nn[dst] = c if b else 1-c
                    que2.append(dst)
        que = que2
    for n in nn:
        print(n)

main()

Submission status: Accepted

Solution code:
from collections import deque
N = input()
A = [[] for i in range(N)]
for i in range(N-1):
	a2,b2,c2 = map(int, raw_input().split())
	A[a2-1].append([b2-1,c2])
	A[b2-1].append([a2-1,c2])
A2 = [-1]*N
A2[0] = 0
q = deque([0])
while q:
	c = q.popleft()
	l = A2[c]
	for c0,c1 in A[c]:
		if(A2[c0] != -1):
			continue
		else:
			A2[c0] = (l + c1)%2
			q.append(c0)
for t in A2:
	print(t)

Submission status: Accepted

Solution code:
from collections import deque

N = int(input())

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

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


color = [-1] * (N + 1)
Q = deque()
for n, p in node[1]:
    Q.append((n, p, 1))

color[1] = 0

while Q:
    a, b, cur = Q.popleft()
    if b:
        color[a] = color[cur]
    else:
        color[a] = 1 - color[cur]

    for n, p in node[a]:
        if color[n] == -1:
            Q.append((n, p, a))

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

Submission status: Accepted

Solution code:
from collections import deque

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

adj = [[] for _ in range(N+1)]
for b in branch:
  adj[b[0]].append([b[1],b[2]])
  adj[b[1]].append([b[0],b[2]])

ans = [-1] * (N+1)
deq = deque()
deq.appendleft(1)
while len(deq) > 0:
  v = deq.pop()
  for u, w in adj[v]:
    if ans[u] == -1:
      deq.appendleft(u)
    if ans[v] == -1 and ans[u] == -1:
      if w % 2 == 0:
        ans[v] = 0
        ans[u] = 0
      else:
        ans[v] = 0
        ans[u] = 1
    elif ans[v] == 0:
      if w % 2 == 0:
        ans[u] = 0
      else:
        ans[u] = 1
    else:
      if w % 2 == 0:
        ans[u] = 1
      else:
        ans[u] = 0
for i in range(1,N+1):
  print(ans[i])

Submission status: Accepted

Solution code:
from queue import Queue

N = int(input())

BLACK = -1
GRAY = 0
WHITE = 1
nodes = [GRAY] * N
nodes[0] = BLACK
neighbors = [[] for _ in range(N)]

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


def bfs():
    q = Queue()
    q.put(0)
    while not q.empty():
        u = q.get()

        neiss = neighbors[u]
        for neis in neiss:
            v, w = neis
            if nodes[v] == GRAY:
                if w % 2 == 0:
                    nodes[v] = nodes[u]
                else:
                    nodes[v] = -nodes[u]
                q.put(v)


bfs()

for n in nodes:
    if n == BLACK:
        print(0)
    else:
        print(1)

Submission status: Accepted

Solution code:
from collections import defaultdict, deque

def main():
    n = int(input())
    edges = defaultdict(list)

    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))
    
    vertexes = solve(edges, n)
    for v in vertexes:
        print(v)

def solve(edges, n):
    vertexes = [None for _ in range(n)]
    vertexes[0] = 0

    q = deque()
    q.append(0)

    while q:
        u = q.popleft()

        for v, w in edges[u]:
            if vertexes[v] is not None:
                continue
            if w % 2 == 0:
                vertexes[v] = vertexes[u]
            else:
                vertexes[v] = 1 - vertexes[u]
            q.append(v)
    
    return vertexes
    
main()

Submission status: Accepted

Solution code:

import sys
input = sys.stdin.readline

N = int(input())
lis = [[0,True]for _ in range(N)]
adj =[{}for _ in range(N)]
for i in range(N-1):
    i,j,w = map(int,input().split())
    i -= 1
    j -= 1
    w = w%2
    adj[i][j]=w
    adj[j][i]=w

lis[0][1] =False
tsugi =[0]
while len(tsugi)!=0:
    foo = []
    for i in tsugi:
        for j in adj[i].keys():
            if lis[j][1]:
                lis[j][0]=lis[i][0]+adj[i][j]
                foo.append(j)
            adj[j].pop(i)
        adj[i].clear()
    tsugi = foo

ans = [str(i[0]%2) for i in lis]
print("\n".join(ans))

Submission status: Accepted

Solution code:
import numpy as np
import math
import sys

sys.setrecursionlimit(1000000)

def contrary_bit(bit):
    if (bit == 1):
        return 0
    elif (bit == 0):
        return 1
    else:
        print("error")

def dfs(adj_lists, nodes, node):
    # nodeから出発して，深さ優先探索
    neighbors = adj_lists[node]
    for neighbor in neighbors:
        if (nodes[neighbor[0]] != -1):
            #訪問済み
            continue
        else:
            if neighbor[1] % 2 == 0:
                # 同じbit  
                nodes[neighbor[0]] = nodes[node]
                nodes = dfs(adj_lists, nodes, neighbor[0])
            else:
                nodes[neighbor[0]] = contrary_bit(nodes[node])
                nodes = dfs(adj_lists, nodes, neighbor[0])
    return nodes

def main():
    N = int(input())
    adj_lists = {}
    for i in range(1, N + 1):
        adj_lists[i] = []
    nodes = [-1] * (N + 1)
    for _ in range(N - 1):
        u, v, w = map(int, input().split())
        adj_lists[u].append((v, w))
        adj_lists[v].append((u, w))
    nodes[1] = 1
    nodes = dfs(adj_lists, nodes, 1)
    ans = nodes[1:]
    for color in ans:
        print(color)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

g_list = [[] for _ in range(n)]
for gi in g:
    g_list[gi[0] - 1].append([gi[1] - 1, gi[2] % 2])
    g_list[gi[1] - 1].append([gi[0] - 1, gi[2] % 2])


color = [-1] * n

from collections import deque

q = deque()

color[0] = 0
q.append(0)
while q:
    v = q.popleft()
    for i, j in g_list[v]:
        if color[i] == -1:
            color[i] = (color[v] + j) % 2
            q.append(i)

[print(c) for c in color]

Submission status: Accepted

Solution code:
from collections import deque

def bfs(li,f,n):
    queue = deque([1])
    f[1] = 1
    count = 0
    ans = [0 for i in range(n+1)]
    while queue:
        point = queue.popleft()
        # print(point)
        for i in li[point]:
            if f[i[0]] == -1:
                f[i[0]] = 1
                if ans[point] == 0 and i[1]%2 != 0:
                    ans[i[0]] = 1
                elif ans[point] == 1 and i[1]%2 == 0:
                    ans[i[0]] = 1
                queue.append(i[0])
    for i in ans[1:]:
        print(i)


n=int(input())
li=[[] for i in range(n+1)]
for i in range(n-1):
    f,t,w = map(int,input().split())
    li[f].append((t,w))
    li[t].append((f,w))
f=[-1 for i in range(n+1)]
bfs(li,f,n)

Submission status: Accepted

Solution code:
from collections import defaultdict
from queue import Queue
N = int(input())
e_dict = {}

num_e_count = defaultdict(int)
edge_dict = defaultdict(list)
for _ in range(N-1):
    u, v, w = tuple(map(int, input().split()))
    e_dict[(u, v)] = not bool(w%2)
    e_dict[(v, u)] = not bool(w%2)
    num_e_count[v]+=1
    num_e_count[u]+=1
    edge_dict[v].append(u)
    edge_dict[u].append(v)

start_point = None
for k, v in num_e_count.items():
    if v == 1:
        start_point = k
        break


result = [None] * N

result[start_point-1] = 1

done_set = set()
next_points = Queue(maxsize=N)
next_points.put(start_point)

while len(done_set) < N:
    u = next_points.get()
    for v in edge_dict[u]:
        if v not in done_set:
            next_points.put(v)
            if e_dict[(u, v)]:
                result[v-1] = result[u-1]
            else:
                result[v-1] = 1 - result[u-1]
        done_set.add(u)

for r in result:
    print(r)

Submission status: Accepted

Solution code:
from heapq import heappush, heappop
def dijkstra(graph:list, node:int, start:int) -> list:
    # graph[node] = [(cost, to)]
    inf = float('inf')
    dist = [inf]*node

    dist[start] = 0
    heap = [(0,start)]
    while heap:
        cost,thisNode = heappop(heap)
        for NextCost,NextNode in graph[thisNode]:
            dist_cand = dist[thisNode]+NextCost
            if dist_cand < dist[NextNode]:
                dist[NextNode] = dist_cand
                heappush(heap,(dist[NextNode],NextNode))
    return dist
    # dist = [costs to nodes]



from collections import defaultdict
from heapq import heappop, heappush

class Graph(object):

    def __init__(self):
        self.graph = defaultdict(list)

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

    def add_edge(self, From, To, cost=1):
        self.graph[From].append((To,cost))

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

class Dijkstra(object):

    def __init__(self, graph, start):
        self.g = graph.graph
        self.dist = defaultdict(lambda:float('inf'))
        self.dist[start] = 0
        self.prev = defaultdict(lambda: None)
        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, cost in self.g[u]:
                alt = dist_u + cost
                if self.dist[v] > alt:
                    self.dist[v] = alt
                    self.prev[v] = u
                    heappush(self.Q,(alt, v))

    def shortest_distance(self, goal):
        return self.dist[goal]

    def shortest_path(self, goal):
        path = []
        node = goal
        while node is not None:
            path.append(node)
            node = self.prev[node]

        return path[::-1]

g = Graph()
N = int(input())
for i in range(N-1):
    u,v,w = map(int,input().split())
    g.add_edge(u-1,v-1,w)
    g.add_edge(v-1,u-1,w)

dijkstra = Dijkstra(g,0)
for i in range(N):
    print(dijkstra.shortest_distance(i)%2)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**5+1)
n = int(input())
if n==1:
  print(0)
  exit()
from collections import defaultdict
edge = defaultdict(list)
for i in range(n-1):
  u, v, w = list(map(int, input().split()))
  edge[u].append((v, w))
  edge[v].append((u, w))
graph = [-1 for i in range(n+1)]

def dfs(x, c):
  nexts = edge.get(x)
  if nexts is None:
    return
  if graph[x]!=-1:
    return
  else:
    graph[x] = c
  for y, w in nexts:
    if w%2:
      dfs(y, not c)
    else:
      dfs(y, c)

dfs(1, 0)
for i in range(1, n+1):
  print(int(graph[i]))