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=10**6):
    self.n = n
    self.root = [-1]*(n+1)
    self.rnk = [0]*(n+1)
  def find(self, x):
    if(self.root[x] < 0):
      return x
    else:
      self.root[x] = self.find(self.root[x])
      return self.root[x]
  def unite(self, x, y):
    x = self.find(x)
    y = self.find(y)
    if(x == y):return 
    elif(self.rnk[x] > self.rnk[y]):
      self.root[x] += self.root[y]
      self.root[y] = x
    else:
      self.root[y] += self.root[x]
      self.root[x] = y
      if(self.rnk[x] == self.rnk[y]):
        self.rnk[y] += 1
  def same(self, x, y):
    return self.find(x) == self.find(y)
  def count(self, x):
    return -self.root[self.find(x)]
uf=UnionFind()
n=int(input())
for _ in range(n-1):
  u,v,w=map(int,input().split())
  if w%2:
    uf.unite(2*u,2*v-1)
    uf.unite(2*u-1,2*v)
  else:
    uf.unite(2*u,2*v)
    uf.unite(2*u-1,2*v-1)
f=uf.find(2*1)
for i in range(1,n+1):
  print(int(uf.find(2*i)==f))

Submission status: Accepted

Solution code:
import sys,math,collections,itertools
input = sys.stdin.readline
#ダイクストラで頂点1と偶数距離を0として塗る
N=int(input())
road=[[] for i in range(N+1)]
for _ in range(N-1):
    u,v,w=list(map(int,input().split()))
    road[u].append((v,w))
    road[v].append((u,w))
dist = [float('inf')for i in range(N+1)]
ans = [0]*(N+1)

q = collections.deque([])
q.append(1)
dist[1]=0
while q:
    now = q.popleft()
    for goto,cost in road[now]:
        if dist[goto]>dist[now]+cost:
            dist[goto]=dist[now]+cost
            q.append(goto)

for a in dist[1:]:
    print(a%2)

Submission status: Accepted

Solution code:
from collections import deque

n=int(input())
ch=0
g=[[] for _ in range(n)]
k=[[] for _ in range(n)]
for i in range(n-1):
  u,v,w=map(int,input().split())
  if w%2==0:
    g[u-1].append(v-1)
    g[v-1].append(u-1)
  else:
    k[u-1].append(v-1)
    k[v-1].append(u-1)
    ch1=u-1
    ch2=v-1
    ch=1

## 0:White 1:Black
ans=[-1 for _ in range(n)]

if ch>0:
  ans[ch1]=0
  d=[ch1]
  qu=deque(d)
  while qu:
    p=qu.popleft()
    
    for gr in g[p]:
      if ans[gr]==-1:
        if ans[p]==0:
          ans[gr]=0
          qu.append(gr)
        else:
          ans[gr]=1
          qu.append(gr)
      
    for kr in k[p]:
      if ans[kr]==-1:
        if ans[p]==0:
          ans[kr]=1
          qu.append(kr)
        else:
          ans[kr]=0
          qu.append(kr)   
    
          
  for j in range(n):
    print(ans[j])
    
else:
  for j in range(n):
    print(0)

Submission status: Accepted

Solution code:
class UnionFindTree:
    def __init__(self, n):
        self.nodes = [-1] * n #根にサイズを負の値で格納する。
    def find(self, i):
        if self.nodes[i] < 0: #値が負の場合は根
            return i
        else:
            self.nodes[i] = self.find(self.nodes[i]) #縮約
            return self.nodes[i]

    def union(self, i, j):
        i = self.find(i)
        j = self.find(j)
        if i == j:
            return
        if self.nodes[i] > self.nodes[j]: #サイズ比較してiの方がサイズが大きいようにする
            i, j = j, i
        self.nodes[i] += self.nodes[j] #大きい方に小さい方を統合しサイズを登録する。
        self.nodes[j] = i # jの親はi
    
    def size(self, i): # 所属する集合の大きさを返す
        i = self.find(i)
        return -self.nodes[i]

n = int(input())
uft = UnionFindTree(2 * n)
for _ in range(n-1):
    u, v, w = map(int, input().split())
    u -= 1
    v -= 1
    if w % 2 == 0:
        uft.union(u, v)
        uft.union(u + n, v + n)
    else:
        uft.union(u + n, v)
        uft.union(u, v + n)

x = uft.find(0)
for i in range(n):
    print(0 if uft.find(i) == x else 1)

Submission status: Accepted

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

stack = [0]
color = [-1] * n
color[0] = 0
while stack:
    v = stack.pop()
    for child, w in tree[v]:
        if color[child] < 0:
            color[child] = (color[v] + w) % 2
            stack.append(child)
for i in color:
    print(i)

Submission status: Accepted

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

q = deque()
q.append(0)
color = [-1] * n
color[0] = 0

while q:
    v = q.popleft()
    for child, w in tree[v]:
        if color[child] < 0:
            color[child] = (color[v] + w) % 2
            q.append(child)

for i in color:
    print(i)

Submission status: Accepted

Solution code:
import sys
mod=10**9+7 ; inf=float("inf")
from math import sqrt, ceil
from collections import deque, Counter, defaultdict #すべてのkeyが用意されてる defaultdict(int)で初期化
input=lambda: sys.stdin.readline().strip()
sys.setrecursionlimit(11451419)
from decimal import ROUND_HALF_UP,Decimal  #変換後の末尾桁を0や0.01で指定
  #Decimal((str(0.5)).quantize(Decimal('0'), rounding=ROUND_HALF_UP))
from functools import lru_cache
from bisect import bisect_left as bileft, bisect_right as biright
#メモ化再帰defの冒頭に毎回 @lru_cache(maxsize=10**10)
#引数にlistはだめ
#######ここまでテンプレ#######
#ソート、"a"+"b"、再帰ならPython3の方がいい
#######ここから天ぷら########

n=int(input())
G=[[] for i in range(n)]
for i in range(n-1):
    a,b,w=map(int,input().split())
    a-=1;b-=1
    G[a].append((b,w))
    G[b].append((a,w))
C=[-1]*n 
C[0]=0
def dfs(x):
    for v,w in G[x]:
        if C[v]==-1:
            C[v]=1-C[x] if w%2==1 else C[x]
            dfs(v)

dfs(0)
# print(G)
for i in range(n):
    print(C[i])

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(500*500)


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

for node in nodes:
    a[node[0]].append([node[1],node[2]])
    a[node[1]].append([node[0],node[2]])

depth = [-1] * (n+1)
depth[1] = 0

def dfs(a,s):
    for v in a[s]:
        if depth[v[0]] == -1:
            depth[v[0]] = depth[s] + v[1]
            dfs(a,v[0])    
dfs(a,1)
for d in depth[1:]:
    if d % 2 == 0:
        print(0)
    else:
        print(1)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)
N = int(input())

Graph = [[] for _ in range(N+1)]
dist  = [1000000000000]*(N+1)

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


def func(fromE,now,length):
	dist[now] = length
	for i in range(len(Graph[now])):
		target = Graph[now][i][0]
		lengt  = Graph[now][i][1]

		if target == fromE:
			continue

		func(now,target,dist[now]+lengt)

func(-1,0,0)

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)
N = int(input())

Graph = [[] for _ in range(N+10)]
dist  = [10000000000000]*(N+10)

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

dist[0] = 0

def func(fromE,now,length):
	if fromE != -1:
		dist[now] = dist[fromE]+length
	for i in range(len(Graph[now])):
		target = Graph[now][i][0]
		lengt  = Graph[now][i][1]

		if target == fromE:
			continue

		func(now,target,lengt)

func(-1,0,0)

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

Submission status: Accepted

Solution code:
from collections import deque

N = int(input())
graph = [[] for _ in range(N)]
dist = [-1] * 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))
q = deque()

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

while len(q) != 0:
  v = q.popleft()
  for next_v, next_w in graph[v]:
    if dist[next_v] != -1:
      continue
    dist[next_v] = dist[v] + next_w
    q.append(next_v)

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

Submission status: Accepted

Solution code:
import sys
from collections import deque
input=sys.stdin.readline
N=int(input())
tree=[[] for _ in range(N)]
for _ in range(N-1):
  u,v,w=map(int,input().split())
  tree[u-1].append((v-1,w))
  tree[v-1].append((u-1,w))
ans=[-1]*N
ans[0]=0
d=deque([0])
while d:
  p=deque.popleft(d)
  color=ans[p]
  for v,w in tree[p]:
    if ans[v]==-1:
      deque.append(d,v)
      ans[v]=color^(w%2)
print(*ans,sep='\n')

Submission status: Accepted

Solution code:
from collections import deque
import sys
sys.setrecursionlimit(10**7)
n = int(input())
ad_ls = [[] for _ in range(n)]
for _ in range(n-1):
    a,b,w = map(int,input().split())
    ad_ls[a-1].append([b-1,w])
    ad_ls[b-1].append([a-1,w])

cost_ls = [0] * n
done_ls = [0] * n
def dfs(v,c):
    for new,cost in ad_ls[v]:
        if not done_ls[new]:
            cost_ls[new] = c+cost
            done_ls[new] = 1
            dfs(new,c+cost)

dfs(0,0)

color_ls = [0] * n
for i in range(n):
    color_ls[i] = cost_ls[i] % 2

for color in color_ls:
    print(color)

Submission status: Accepted

Solution code:
from collections import deque
n = int(input())
ad_ls = [[] for _ in range(n)]
for _ in range(n-1):
    a,b,w = map(int,input().split())
    ad_ls[a-1].append([b-1,w])
    ad_ls[b-1].append([a-1,w])

cost_ls = [0] * n
done_ls = [0] * n
done_ls[0] = 1
q = deque()
q.append(0)

while q:
    now = q.pop()
    for new in ad_ls[now]:
        nex,cost = new[0],new[1]
        if not done_ls[nex]:
            cost_ls[nex] = cost + cost_ls[now]
            done_ls[nex] = 1
            q.append(nex)

color_ls = [0] * n
for i in range(n):
    color_ls[i] = cost_ls[i] % 2

for color in color_ls:
    print(color)

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

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

dq = deque([0])

# 各頂点について、根からの距離
# 頂点0を根とする
dist_list = [-1] * n
dist_list[0] = 0

# BFS
while dq:
    now = dq.popleft()
    # tと繋がっている各頂点について
    for info in g[now]:
        next = info[0]
        d = info[1]
        if dist_list[next] == -1:
            # 根からtまでの距離 + tから次への距離
            dist_list[next] = dist_list[now] + d
            dq.append(next)

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

Submission status: Accepted

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

visited = [-1]*n
stack = [0]
visited[0]=0
while stack:
    z = stack.pop()
    for v,w in e[z]:
        if visited[v-1]==-1:
            stack.append(v-1)
            if w%2==0:
                visited[v-1]=visited[z]
            else:
                visited[v-1]=1-visited[z]
        else:
            continue
print(*visited,sep="\n")

Submission status: Accepted

Solution code:
from collections import deque
N=int(input())
E={i:{} for i in range(1,N+1)}

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

inf=float("inf")
Dist=[inf]*(N+1)
Q=deque([1])
Dist[1]=0
while Q:
    u=Q.popleft()
    for v in E[u]:
        if Dist[v]==inf:
            Q.append(v)
            Dist[v]=Dist[u]^E[u][v]
print("\n".join(map(str,Dist[1:])))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from collections import deque

n = int(input())
g = [list() for _ in range(n)]
visited = [True] * n
coler = [0] * n
for _ in range(1, n):
    v1, v2, w = map(int, input().split())
    v1 -= 1
    v2 -= 1
    w %= 2
    g[v1].append((v2, w))
    g[v2].append((v1, w))

q = deque([0])
visited[0] = False
while q:
    a = q.pop()
    for v, w in g[a]:
        if visited[v]:
            visited[v] = False
            coler[v] = (coler[a] + w) % 2
            q.append(v)

print(*coler, sep="\n")

Submission status: Accepted

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

def f(x):
  for tmp in links[x]:
    if c[tmp[0]]<0:
      if tmp[1]%2==0:
        c[tmp[0]]=c[x]+0
      else:
        c[tmp[0]]=1-c[x]
      f(tmp[0])

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

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

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from collections import deque
N = int(input())
lis = [[] for i in range(N)]
for i in range(N-1):
    a,b,w = map(int,input().split())
    lis[a-1].append((b-1,w%2))#移動先、偶奇の順
    lis[b-1].append((a-1,w%2))

flg = [True] * N
ans = [-1] * N
que = deque([ (0,0) ])
#flg[0] = False
ans[0] = 0
flg[0] = False
while len(que) != 0:
    p = que.popleft()
    #print(p)
    for i in lis[p[0]]:
        if flg[i[0]] == True:
            que.append(i)
            flg[i[0]] = False
            if i[1] == 0:
                ans[i[0]] = ans[p[0]]
            else:
                if ans[p[0]] == 1:
                    ans[i[0]] = 0
                else:
                    ans[i[0]] = 1
for i in ans:
    print(i)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
# 問題：https://atcoder.jp/contests/abc126/tasks/abc126_d


class Graph():

    def __init__(self):
        self.adjacency_dict = {}
        self.weight = []
    
    def add_vertex(self, v):
        self.adjacency_dict[v] = []
        self.weight.append([])

    def add_edge(self, v1, v2, w):
        self.adjacency_dict[v1].append(v2)
        self.adjacency_dict[v2].append(v1)
        self.weight[v1].append(w)
        self.weight[v2].append(w)

    def get_vertexes(self):
        return self.adjacency_dict.keys()

    def get_edges(self, v):
        return self.adjacency_dict[v], self.weight[v]

    def print_graph(self):
        print(self.adjacency_dict)

n = int(input())

res = []
g = Graph()
for i in range(n):
    res.append(-1)
    g.add_vertex(i)

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

q = []
res[0] = 0
q.append(0)
while(len(q) > 0):
    v = q.pop()
    u_l, w_l = g.get_edges(v)
    for u, w in zip(u_l, w_l):
        if res[u] != -1:
            continue
        res[u] = (res[v] + w) % 2
        q.append(u)

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

Submission status: Accepted

Solution code:
from collections import defaultdict, deque

N = int(input())
dic = defaultdict(list)
color = [-1]*N

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

queue = deque()
color[0]=0
for i in dic[1]:
    queue.append(i)

while queue:
    u, v, w =map(int, queue.popleft())
    if (color[u-1]+w)%2==0:
        color[v-1]=0
    else:
        color[v-1]=1
    for i in dic[v]:
        if color[i[1]-1]==-1:
            queue.append(i)
print(*color)

Submission status: Accepted

Solution code:
n=int(input())

#隣接リスト表現
es=[[] for i in range(n)]
for i in range(n-1):
  u,v,w=list(map(int,input().split()))
  es[u-1].append([v-1,w])
  es[v-1].append([u-1,w])


# 再帰の深さが1000を超えそうなときはこれをやっておく
import sys
sys.setrecursionlimit(10**7)

#頂点vから初めて白なら１、黒なら−１、未探索なら０
colors=[0 for i in range(n)]
def search(v,color):
  colors[v]=color
  #vから行ける辺について考える
  for to in es[v]:
    if colors[to[0]]==0 and to[1]%2==0:
      search(to[0],color)
    elif colors[to[0]]==0 and to[1]%2==1:
      search(to[0],-color)
  return colors

search(0,1)
for i in colors:
  if i==-1:
    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())
    u -= 1
    v -= 1
    g[u].append([v, w])
    g[v].append([u, w])
used = [0]*n
used[0] = 1
parity = [-1]*n
parity[0] = 0
que = deque()
que.append(0)
while que:
    # print(que)
    v = que.popleft()
    for nv, w in g[v]:
        if used[nv]:
            continue
        parity[nv] = (parity[v] + w)%2
        used[nv] = 1
        que.append(nv)

# print(used)
for i in range(n):
    print(parity[i])

Submission status: Accepted

Solution code:
n = int(input())
d = [[] for i 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])
  
ans = [[] for i in range(n)]
ans[0].append(0)
q = [0]

while q:
  x = q.pop()
  for u, w in d[x]:
    if not ans[u]:
      buf = ans[x][0]
      if w%2==1:
        buf = (buf+1)%2
      ans[u].append(buf)
      q.append(u)
    
for i in ans:
  print(*i)

Submission status: Accepted

Solution code:
import bisect, collections, copy, heapq, itertools, math, string, sys
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = float('inf')
def I(): return int(input())
def F(): return float(input())
def SS(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LSS(): return input().split()

def resolve():
    N = I()
    G = [[] for _ in range(N)]
    for _ in range(N - 1):
        u, v, w = LI()
        G[u-1].append((v - 1, w))
        G[v-1].append((u - 1, w))

    # print(G)

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

    def dfs(c):
        visited[c] = True
        for n, w in G[c]:
            if not visited[n]:
                if w % 2 == 0:
                    ans[n] = ans[c]
                else:
                    ans[n] = 1 - ans[c]
                dfs(n)

    dfs(0)

    for i in ans:
        print(i)

if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
# import itertools
# import math
import sys
sys.setrecursionlimit(500*500)
# import numpy as np

N = int(input())
# S = input()
# n, *a = map(int, open(0))
# H, W, K = map(int, input().split())
# A = list(map(int, input().split()))
# B = list(map(int, input().split()))
# S = input()

# d = sorted(d, reverse=True, key=lambda x:x[0])
# all_cases = list(itertools.permutations(P))
# a = list(itertools.combinations_with_replacement(range(1, M + 1), N))
# itertools.product((0,1), repeat=n)

# A = np.array(A)
# cum_A = np.cumsum(A)
# cum_A = np.insert(cum_A, 0, 0)

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

for edge in edges:
    tree[edge[0]].append([edge[1], edge[2]])
    tree[edge[1]].append([edge[0], edge[2]])

# print(tree)

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

def dfs(tree, s):
    for l in tree[s]:
        if depth[l[0]] == -1:
            depth[l[0]] = depth[s] + l[1]
            dfs(tree, l[0])

dfs(tree, 1)

# print(depth)

for l in depth[1:]:
    if l % 2 == 0:
        print(1)
    else:
        print(0)

Submission status: Accepted

Solution code:
N = int(input())
data = [[] for _ in range(N)]
for _ in range(N-1):
    p, q, w = map(int, input().split())
    p -= 1
    q -= 1
    data[p].append((q,w))
    data[q].append((p,w))

colors = [0]*N
visited = [0]*N
start = 0
next_set = [start]
while next_set:
    p = next_set.pop()
    visited[p] = 1
    color = colors[p]
    for q, w in data[p]:
        if visited[q]:
            continue
        colors[q] = (color + w%2)%2
        next_set.append(q)
print(*colors, sep="\n")

Submission status: Accepted

Solution code:
import heapq
inf=float("inf")


def prim():
    color=["white" for _ in range(n+1)]
    D=[inf for _ in range(n+1)]
    M=[[] for _ in range(n+1)]

    for u,v,w in UVW:
        M[u].append([w,v])
        M[v].append([w,u])

    queue=[[0,1]]
    heapq.heapify(queue)
    color[1]="gray"
    D[1]=1

    while len(queue)>0:
        num=heapq.heappop(queue)[1]
        if color[num]=="black":continue
        color[num]="black"

        for i,j in M[num]:
            if D[j]>i and color[j]!="black":
                if i%2==0:D[j]=D[num]
                else:D[j]=-D[num]
                color[j]="gray"
                heapq.heappush(queue,[i,j])

    return D[1:]


n=int(input())
UVW=[list(map(int,input().split())) for _ in range(n-1)]
for i in prim():
    if i==1:print(i)
    else:print(0)

Submission status: Accepted

Solution code:
import _heapq
inf=float("inf")


def prim():
    color=["white" for _ in range(n+1)]
    D=[inf for _ in range(n+1)]
    M=[[] for _ in range(n+1)]

    for u,v,w in UVW:
        M[u].append([w,v])
        M[v].append([w,u])

    queue=[[0,1]]
    _heapq.heapify(queue)
    color[1]="gray"
    D[1]=1

    while len(queue)>0:
        num=_heapq.heappop(queue)[1]
        if color[num]=="black":continue
        color[num]="black"

        for i,j in M[num]:
            if D[j]>i and color[j]!="black":
                if i%2==0:D[j]=D[num]
                else:D[j]=-D[num]
                color[j]="gray"
                _heapq.heappush(queue,[i,j])

    return D[1:]


n=int(input())
UVW=[list(map(int,input().split())) for _ in range(n-1)]
for i in prim():
    if i==1:print(i)
    else:print(0)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
Created on Sat Aug 15 08:50:44 2020

@author: naoki
"""
from collections import deque

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

routes = [[] for _ in range(N)]
for uvw in uvws:
    u = uvw[0]-1
    v = uvw[1]-1
    w = uvw[2]
    
    routes[u].append([v,w])
    routes[v].append([u,w])
    
    
colors = [-1 for _ in range(N)]
todo = deque()
todo.append(0)
colors[0] = 0


while len(todo)>0:
    checking = todo.pop()
    for route in routes[checking]:
        destination = route[0]
        weight = route[1]
        
        if colors[destination] == -1:
            if weight%2 == 0:
                colors[destination] = colors[checking]
            else:
                colors[destination] = 1 - colors[checking]
            todo.append(destination)

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

Submission status: Accepted

Solution code:
N=int(input())
tree=[[] for i in range(N)]
for i in range(N-1):
  u,v,w=map(int,input().split())
  tree[u-1].append((v-1,w))
  tree[v-1].append((u-1,w))
h=[]
h.append(0)
distance=[-1 for i in range(N)]
distance[0]=0
while h:
  k=h.pop(0)
  for v in tree[k]:
    x=v[0]
    y=v[1]
    if distance[x]==-1:
      distance[x]=distance[k]+y
      h.append(x)
for i in range(N):
  if distance[i]%2==0:
    print(0)
  else:
    print(1)

Submission status: Accepted

Solution code:
def main():
    N = int(input())
    G = [[] for _ in range(N)]
    for _ in range(N-1):
        a, b, c = (int(i) for i in input().split())
        G[a-1].append((b-1, c % 2))
        G[b-1].append((a-1, c % 2))

    color = [-1]*N

    def dfs(s):
        seen = [False]*N
        stack = [s]
        seen[s] = True
        color[0] = 0
        while stack:
            v = stack.pop()
            for u, dist in G[v]:
                if seen[u]:
                    continue
                if dist == 1:
                    color[u] = color[v] ^ 1
                else:
                    color[u] = color[v]
                stack.append(u)
                seen[u] = True

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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().rstrip()
def ii(): return int(input())
def mi(): return map(int, input().split())
def li(): return list(mi())

from collections import deque
def main():
    n = ii()
    edge = [[] for _ in range(n)]
    for i in range(n-1):
        u, v, w = mi()
        u -= 1
        v -= 1
        edge[u].append((v, w))
        edge[v].append((u, w))
    dist = [0]*n
    parent = [-1]*n
    que = deque([0])
    while que:
        v = que.pop()
        for nv, nx in edge[v]:
            if parent[v] == nv:
                continue
            parent[nv] = v
            dist[nv] = dist[v]+nx%2
            dist[nv]%= 2
            que.append(nv)
    print(*dist, sep='\n')
    


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
from collections import deque

input = sys.stdin.readline


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

    ans = [-1] * N
    ans[0] = 0
    stack = deque([(-1, 0)])
    while stack:
        p, u = stack.pop()
        for v, w in G[u]:
            if v == p:
                continue
            if w % 2 == 0:
                ans[v] = ans[u]
            else:
                ans[v] = (ans[u] + 1) % 2
            stack.append((u, v))

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


if __name__ == "__main__":
    main()

Submission status: Accepted

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

def bfs():
    q = deque([0])
    dist = [-1]*N
    dist[0] = 0
    
    while q:
        v = q.popleft()
        
        for nv, w in G[v]:
            if dist[nv]==-1:
                dist[nv] = dist[v]+w
                q.append(nv)
        
    return dist

N = int(input())
G = [[] for _ in range(N)]

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

dist = bfs()
ans = [0]*N

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

for ans_i in ans:
    print(ans_i)

Submission status: Accepted

Solution code:
from collections import deque

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

adj = [[] for _ in range(n+1)]

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

q = deque([1])

dist = [0] * (n+1)
visited = [False] * (n+1)

while len(q) > 0:
    v = q.popleft()
    for w, d in adj[v]:
        if not visited[w]:
            visited[w] = True
            dist[w] = dist[v] + d
            q.append(w)

#print(dist)

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

Submission status: Accepted

Solution code:
from math import ceil,floor,factorial,gcd,sqrt,log2,cos,sin,tan,acos,asin,atan,degrees,radians,pi,inf,comb
from itertools import accumulate,groupby,permutations,combinations,product,combinations_with_replacement
from collections import deque,defaultdict,Counter
from bisect import bisect_left,bisect_right
from operator import itemgetter
from heapq import heapify,heappop,heappush
from queue import Queue,LifoQueue,PriorityQueue
from copy import deepcopy
from time import time
from functools import reduce
import string
import sys
sys.setrecursionlimit(10 ** 7)
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def LIST()  : return list(MAP())

def bfs():
    dist = [-1]*n
    que = deque([0])
    dist[0] = 0
    while que:
        v = que.popleft()
        d = dist[v]
        for w in g[v]:
            if dist[w[0]] > -1:
                continue
            dist[w[0]] = d + w[1]
            que.append(w[0])
    return dist

n = INT()
g = [[] for i in range(n)]
for i in range(n-1):
    x, y, z = MAP()
    g[x-1].append([y-1, z])
    g[y-1].append([x-1, z])
for k in bfs():
    print(0 if k%2 == 0 else 1)

Submission status: Accepted

Solution code:
# 再帰の深さが1000を超えそうなときはこれをやっておく
import sys
sys.setrecursionlimit(10**7)
#二部グラフになっている時の色の塗り分けを聞いている
n=int(input())
es=[[] for i in range(n)]
for i in range(n-1):
  u,v,w=list(map(int,input().split()))
  es[u-1].append([v,w])
  es[v-1].append([u,w])

colors=[0 for i in range(n)]
#深さ優先探索　頂点vをcolorで塗ることを考える
def dfs(v,color):
  colors[v-1]=color
  for i in es[v-1]:
    if i[1]%2==0 and colors[i[0]-1]==0:
      dfs(i[0],color)
    elif i[1]%2==1 and colors[i[0]-1]==0:
      dfs(i[0],(-1)*color)
  return colors

    
a=dfs(1,-1)
for i in a:
  if i==-1:
    print(0)
  else:
    print(1)

Submission status: Accepted

Solution code:
from collections import deque
n=int(input())
e=[[]for _ in range(n+1)]
c=[-1]*(n+1)
for _ in range(n-1):
  a,b,w=map(int,input().split())
  e[a]+=[(b,w)]
  e[b]+=[(a,w)]
q=deque([1])
c[1]=0
while q:
  now=q.popleft()
  for to,w in e[now]:
    if c[to]==-1:
      c[to]=(c[now]+w)%2
      q.append(to)
print(*c[1:],sep='\n')

Submission status: Accepted

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

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    mod=10**9+7
    N=I()
    adj=[[]for _ in range(N)]
    for i in range(N-1):
        u,v,w=MI()
        u-=1
        v-=1
        adj[u].append((v,w))
        adj[v].append((u,w))
        
    
    ans=[-1]*N
    import queue
    
    q=queue.Queue()
    q.put(0)
    ans[0]=0
    
    while not q.empty():
        v=q.get()
        for nv,w in adj[v]:
            if ans[nv]==-1:
                if ans[v]==0 and w%2==0:
                    ans[nv]=0
                elif ans[v]==0 and w%2==1:
                    ans[nv]=1
                elif ans[v]==1 and w%2==0:
                    ans[nv]=1
                else:
                    ans[nv]=0
                q.put(nv)
                
    for i in range(N):
        print(ans[i])
    
    

main()

Submission status: Accepted

Solution code:
n = int(input())
uv = [[] for _ in range(n+1)]
for i in range(n-1):
    u,v,w = map(int, input().split())
    uv[u].append([v,w])
    uv[v].append([u,w])
stack = [1]
ans = [-1]*(n+1)
ans[1]=0
while stack:
    x = stack.pop()
    for j,k in uv[x]:
        if ans[j] == -1:
            if k % 2 ==0:
                ans[j] = ans[x]
            else:
                ans[j] = (ans[x]+1)%2
            stack.append(j)
for m in range(n):
    print(ans[m+1])

Submission status: Accepted

Solution code:
from collections import deque
n=int(input())
uv=[[] for _ in range(n+1)]
for i in range(n-1):
    u,v,w=map(int,input().split())
    uv[u].append([v,w])
    uv[v].append([u,w])
stack=[1]
ans=[-1]*(n+1)
ans[1]=0
while stack:
    x=stack.pop()
    for j in uv[x]:
        if ans[j[0]]==-1:
            if j[1]%2==0:
                ans[j[0]]=ans[x]
            else:
                ans[j[0]]=(ans[x]+1)%2
            stack.append(j[0])

for k in range(1,n+1):
    print(ans[k])