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:
import math,itertools,fractions,heapq,collections,bisect,sys,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

visited=[False]*(10**5)
ans=[-1]*(10**5)

def f(n,edges,s):
  all_visited=True
  for i in range(n):
    if visited[i]==False:
      all_visited=False
      break
  if all_visited:
    return

  for x,c in edges[s]:
    if visited[x]:
      continue
    if ans[s]==0:
      if c%2==1:
        ans[x]=1
      else:
        ans[x]=0
    else:
      if c%2==1:
        ans[x]=0
      else:
        ans[x]=1
    visited[x]=True
    f(n,edges,x)

def main():
  n=I()

  edges=[[] for _ in range(n)]
  for _ in range(n-1):
    a,b,c=LI()
    a-=1
    b-=1
    edges[a].append([b,c])
    edges[b].append([a,c])

  ans[0]=0
  visited[0]=True

  f(n,edges,0)

  for x in ans[:n]:
    print(x)

main()
# print(main())

Submission status: Accepted

Solution code:
import sys
from collections import deque

rl = sys.stdin.readline


def solve():
    N = int(rl())
    graph = [[] for _ in range(N)]
    for _ in range(N - 1):
        u, v, w = map(int, rl().split())
        u -= 1
        v -= 1
        graph[u].append([v, w])
        graph[v].append([u, w])
    
    ans = [-1] * N
    stack = deque([[0, 0]])
    while stack:
        node, dist = stack.pop()
        for child, weight in graph[node]:
            if ans[child] != -1:
                continue
            nd = dist + weight
            if nd % 2 == 0:
                ans[child] = 0
            else:
                ans[child] = 1
            stack.append([child, nd])
    
    print('\n'.join(map(str, ans)))


if __name__ == '__main__':
    solve()

Submission status: Accepted

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

n=int(input())
G=[[] for i 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])

A=[0]*n
def dfs(s,p=-1):
    for g in G[s]:
        if g[0]!=p:
            A[g[0]]=A[s]+g[1]
            dfs(g[0],s)

dfs(0)
for a in A:
    if a%2==0:
        print(0)
    else:
        print(1)

Submission status: Accepted

Solution code:
from collections import deque


def main():

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

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

    dist = [-1] * N
    q = deque([0])
    dist[0] = 0

    while q:
        v = q.popleft()
        for n in G[v].keys():
            if dist[n] == -1:
                q.appendleft(n)
                dist[n] = dist[v] + G[v][n]

    print("\n".join([str(x % 2) for x in dist]))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys

N=int(input())
d=[-1 for _ in range(N)] #木の根から頂点i+1までの距離d[i]
d[0]=0 #根までの距離はゼロ
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]) #頂点u+1から伸びる辺の先v+1と辺の長さwをtree[u]に登録
    tree[v].append([u,w]) #逆からも登録

def dfs(u,D): #根からの距離Dである頂点u+1から先の分岐を探索
    sys.setrecursionlimit(10**6) #再帰回数の上限突破(N回ループのためN以上の数字を設定)
    for v,w in tree[u]: #木の頂点u+1から伸びる辺の先tree[u][0]と距離tree[u][1]をv,wとして取り出し全てについてforループ
        if d[v]==-1: #根から頂点v+1までのの距離d[v]が未記入だった場合(初期値-1)
            d[v]=(D+w) #根から頂点u+1までの距離Dに頂点u+1からv+1までの距離wを加えて根からの距離dのリストに格納
            dfs(v,D+w) #DFSなので次の頂点に移って探索続行、分岐は後回し。
            #木の末端に到達したらfor文中の変数で元の分岐に戻るが既にdが記入済みなのでif中の再帰を避けて次の頂点を探索

dfs(0,0) #(0,0)から始める、すなわち頂点1を根とした木を考える
for i in d:
    print(i%2) #解説にある通り、根からの距離の偶奇で色分けをすればよい

Submission status: Accepted

Solution code:
import sys

def dfs(u,D):
    sys.setrecursionlimit(10**6)
    for v,w in tree[u]:
        if d[v]==-1:
            d[v]=(D+w)%2
            dfs(v,D+w)

N=int(input())
d=[-1 for _ in range(N)]
d[0]=0
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])
    tree[v].append([u,w])

dfs(0,0)
for i in d:
    print(i%2)

Submission status: Accepted

Solution code:
N = int(input())

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

dist = [-1]*(N+1)
dist[1] = 0
q = [1]
while q:
    p = q.pop()
    for n, w in link[p]:
        if dist[n] == -1:
            dist[n] = dist[p] + w
            q.append(n)

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

Submission status: Accepted

Solution code:
import sys 
sys.setrecursionlimit(100000000)
n = int(input())
graph = [[] for _ in range(n)]
color = [-1]*n
dist = [-1]*n
dist[0] = 0
visited = [0]*n
for _ in range(n-1):
  u, v, w = map(int, input().split())
  u -= 1
  v -= 1 
  graph[u] += [[v, w]]
  graph[v] += [[u, w]]
  
def dfs(u, d):
  for v, w in graph[u]:
    if dist[v] == -1:
      dist[v] = (w + d) % 2
      dfs(v, d+w)
      
dfs(0, 0)
for i in dist:
  print(i)

Submission status: Accepted

Solution code:
import sys 
sys.setrecursionlimit(100000000)
n = int(input())
graph = [[] for _ in range(n)]
color = [-1]*n
visited = [0]*n
for _ in range(n-1):
  u, v, w = map(int, input().split())
  u -= 1
  v -= 1 
  graph[u] += [[v, w]]
  graph[v] += [[u, w]]
def dfs(u, c):
  color[u] = c 
  for v, w in graph[u]:
    if color[v] != -1:
      continue
    if color[v] == -1 and w % 2 == 0:
      dfs(v, c)
    if color[v] == -1 and w % 2 != 0:
      dfs(v, abs(1-c))
  return 

dfs(0, 1)
for i in range(n):
  if color[i] == 1:
    print(1)
  else:
    print(0)

Submission status: Accepted

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

import sys

def main():
    sys.setrecursionlimit(10 ** 6)
    n = int(input())
    adjs = [[] for i in range(n)]
    for i in range(n - 1):
        u, v, w = map(int, input().split())
        adjs[u - 1].append((v - 1, w))
        adjs[v - 1].append((u - 1, w))
    colors = [None for i in range(n)]
    colors[0] = 0
    dfs(0, adjs, -1, colors)
    for i in range(n):
        print(colors[i])

def dfs(i, adjs, p, colors):
    for v, w in adjs[i]:
        if v == p:
            continue
        colors[v] = (colors[i] + w) % 2
        dfs(v, adjs, i, colors)

if __name__ == "__main__":
    main()

Submission status: Accepted

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

import sys

def main():
    sys.setrecursionlimit(10 ** 6)
    n = int(input())
    adjs = [[] for i in range(n)]
    for i in range(n - 1):
        u, v, w = map(int, input().split())
        adjs[u - 1].append((v - 1, w))
        adjs[v - 1].append((u - 1, w))
    colors = [None for i in range(n)]
    visited = [False for i in range(n)]
    dfs(0, 0, adjs, visited, colors)
    for i in range(n):
        print(colors[i])

def dfs(i, color, adjs, visited, colors):
    visited[i] = True
    colors[i] = color
    for v, w in adjs[i]:
        if visited[v]:
            continue
        dfs(v, (color + w) % 2, adjs, visited, colors)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import deque

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

queue = deque([0])
while queue:
    now = queue.popleft()
    for u, w in g[now]:
        if ans[u] != -1:
            continue
        ans[u] = ans[now] + w
        queue.append(u)
for a in ans:
    if a % 2 == 0:
        print(1)
    else:
        print(0)

Submission status: Accepted

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

N = int(input())

def dfs(v, u, w):
    if w % 2 == 0:
        iro[v] = 0
    else:
        iro[v] = 1
    for i in ki[v]:
        if i[1] == u: continue
        dfs(i[1], v, w + i[0])
    return

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

iro = [0] * N
dfs(0, 0, 0)
for i in iro:
    print(i)

Submission status: Accepted

Solution code:
N = int(input())
edges = [[] for _ in range(N)]

for _ in range(N - 1):
    fr, to, d = map(int, input().split())
    fr -= 1
    to -= 1
    edges[fr].append((to, d))
    edges[to].append((fr, d))

minDist = [10**18] * N
st = [(0, 0)]
while st:
    now, dist = st.pop()

    if minDist[now] < dist:
        continue
    minDist[now] = dist

    for to, d in edges[now]:
        if minDist[to] > dist + d:
            st.append((to, dist + d))

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

Submission status: Accepted

Solution code:
N = int(input())
E = [[] for _ in range(N)]

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

color = [-1 for _ in range(N)]
stack = [u]
color[u] = 0
while stack:
	u = stack.pop()
	for v,w in E[u]:
		if color[v] == -1:
			stack.append(v)
		if w % 2 == 0:
			color[v] = color[u]
		else:
			color[v] = (color[u] + 1) % 2

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

Submission status: Accepted

Solution code:
from collections import deque
N=int(input())
numbers=[[] for _ in range(N)]
for _ in range(N-1):
    u,v,w=map(int,input().split())
    u-=1
    v-=1
    numbers[u].append((v,w%2))
    numbers[v].append((u,w%2))
inf=pow(10,9)
visited_point=[inf for _ in range(N)]
visited_point[0]=0
stack=deque([0])
while len(stack)>0:
    n=stack.pop()
    for v,w in numbers[n]:
        if visited_point[v]==inf:
            stack.appendleft(v)
            if w%2==0:
                visited_point[v]=visited_point[n]
            else:
                visited_point[v]=visited_point[n]^1
for a in visited_point:
    print(a)

Submission status: Accepted

Solution code:
from collections import deque
n=int(input())
G=[[]for i in range(n)]
U=[0]*(n-1)
V=[0]*(n-1)
A=[0]*(n-1)
D=[]
for i in range(n-1):
  U[i],V[i],w=map(int,input().split())
  U[i]=U[i]-1
  V[i]=V[i]-1
  A[i]=U[i]*10**5+V[i]
  w=w%2
  G[U[i]].append([V[i],w])
  G[V[i]].append([U[i],w])
  D.append([A[i],0])
C=[0]*n
VV=[0]*n
d=deque([0])
while len(d)>0:
  x=d[0]
  d.popleft()
  for i in range(len(G[x])):
    if VV[G[x][i][0]]==0:
      VV[G[x][i][0]]=1
      d.append(G[x][i][0])
      if G[x][i][1]==0:
        C[G[x][i][0]]=C[x]
      else:
        C[G[x][i][0]]=(C[x]+1)%2
for i in range(n):
  print(C[i])

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**9)                    #再帰の深さブースト

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

def bfsC(pre, now, nowc):
    for node, weight in edge[now]:
        if node != pre:
            if weight:
                ans[node] = 1-nowc
                bfsC(now, node, 1-nowc)
            else:
                ans[node] = nowc
                bfsC(now, node, nowc)
bfsC(-1, 0, 0)
for i in range(n):
    print(ans[i])

Submission status: Accepted

Solution code:
from collections import deque
N = int(input())
E = [[] for _ in range(N+1)]
for i in range(N-1):
    u,v,w = map(int,input().split())
    E[u].append([u,v,w])
    E[v].append([v,u,w])
color = [-1]*(N+1)
color[1] = 0
e = deque(E[1])
while(e):
    v = e.popleft()
    if(color[v[1]] == -1):
        if(v[2]%2 == 0):
            color[v[1]] = color[v[0]]
        else:
            color[v[1]] = color[v[0]]^1
        for p in E[v[1]]:
            e.append(p)
for i in range(1,N+1):
    print(color[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))
color=[-1]*n
color[0]=0
q=[0]
while q:
  x=q.pop()
  for t,cost in tree[x]:
    if color[t]>=0:
      continue
    if cost%2==0:
      color[t]=color[x]
    else:
      color[t]=1-color[x]
    q.append(t)
print(*color,sep='\n')

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations, accumulate
    #from itertools import product
    from bisect import bisect_left,bisect_right
    import heapq
    from math import floor, ceil
    #from operator import itemgetter

    inf = 10**17
    #mod = 10**9 + 7

    N = int(input())
    def dijkstra_heap(start,edge):
        #始点から各頂点への最短距離(頂点番号:0~N-1)
        d = [inf]*N
        used = [False]*N
        d[start] = 0
        used[start] = True
        edgelist = []
        #a:重み(//), b:次の頂点(%)
        for a,b in edge[start]:
            heapq.heappush(edgelist,a*(10**6)+b)

        while len(edgelist):
            #まだ最短距離が決まっていない頂点の中から最小の距離のものを探す
            minedge = heapq.heappop(edgelist)
            if used[minedge%(10**6)]:
                continue
            node = minedge%(10**6)
            d[node] = minedge//(10**6)
            used[node] = True

            for e in edge[node]:
                if not used[e[1]]:
                    heapq.heappush(edgelist,(e[0]+d[node])*(10**6)+e[1])
        return d

    #N:頂点数   W:辺数
    edge = [[] for i in range(N)]
    #edge[i] : iから出る道の[重み,行先]の配列
    for _ in range(N-1):
        x,y,z = map(int,input().split())
        edge[x-1].append((z,y-1))
        edge[y-1].append((z,x-1))
    d = dijkstra_heap(0, edge)

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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000)
n=int(input())
graph=[[] for i in range(n)]
color=[-1]*n
for i in range(n-1):
    a,b,c=map(int,input().split())
    graph[a-1].append([b-1,c%2])
    graph[b-1].append([a-1,c%2])
def coloring(pre,c):
  color[pre]=c
  for i,j in graph[pre]:
    if color[i]<0:
      coloring(i,color[pre]^j)
coloring(0,1)
for i in color:
  print(i)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(pow(10, 9))

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

def dfs(v, dist):
  for nv, e_dist in G[v]:
    if ans[nv] == -1:
      ans[nv] = (dist + e_dist) % 2
      dfs(nv, dist + e_dist)

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:
N=int(input())
E=[[] for _ in range(N)]
for i 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))
color=[-1]*N
color[0]=0
stack=[0]
while stack:
  u=stack.pop()
  for v,w in E[u]:
    if color[v]==-1:
      stack.append(v)
      if w%2==0:
        color[v]=color[u]
      else:
        color[v]=1 if color[u]==0 else 0
for i in range(N):
  print(color[i])

Submission status: Accepted

Solution code:
#abc126d
n=int(raw_input())
t=[[] for i in range(n+1)]
for i in range(n-1):
 u,v,w=map(int,raw_input().split())
 t[u].append([v,w])
 t[v].append([u,w])
d=[-1]*(n+1)
d[1]=0
q=[1]
while q:
 now=q.pop()
 for ni,nl in t[now]:
  if d[ni]==-1:
   d[ni]=d[now]+nl
   q.append(ni)
for l in d[1:]:
 print l%2

Submission status: Accepted

Solution code:
n=int(input())
X=[[] for _ in range(n)]
for i in range(n-1):
    u,v,w=map(int,input().split())
    X[u-1].append([v-1,w])
    X[v-1].append([u-1,w])
C=[-1]*n
q=[[0,0]]


while q:
    v,w=q.pop()
    if w%2==0:
        C[v]=0
    else:
        C[v]=1
    for pv,pw in X[v]:
        if C[pv]==-1:
            q.append([pv,pw+w])

for c in C:
    print(c)

Submission status: Accepted

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

while q:
    v,w=q.popleft()

    if visited[v]==1:
        continue
    visited[v]=1
    if w%2==0:
        C[v]=0
    else:
        C[v]=1
    for pv,pw in X[v]:
        q.append([pv,pw+w])

for c in C:
    print(c)

Submission status: Accepted

Solution code:
import queue

n = int(input())
go = [[]for _ in range(n)]
ge = [[]for _ in range(n)]
 
for _ in range(n-1):
    x,y,z = map(int, input().split())
    if z % 2 == 0:
        ge[x-1].append(y-1)
        ge[y-1].append(x-1)
    else:
        go[x-1].append(y-1)
        go[y-1].append(x-1)

color = [0] * n
color[0] = 1

q = queue.Queue()

q.put(0)

while not q.empty():
    v = q.get()
    for i in range(len(go[v])):
        if color[go[v][i]] == 0:
            color[go[v][i]] = - color[v]
            q.put(go[v][i])
    for i in range(len(ge[v])):
        if color[ge[v][i]] == 0:
            color[ge[v][i]] = color[v]
            q.put(ge[v][i])

for i in range(n):
    if color[i] == -1:
        print(0)
    else:
        print(1)

Submission status: Accepted

Solution code:
from collections import deque

def bfs(i):
    q = deque()
    q.append(i)
    c[i] = 1
    while q:
        p = q.popleft()
        f = G[p]
        z = W[p]
        for j in range(len(f)):
            if c[f[j]] == 0:
                q.append(f[j])
                c[f[j]] = 1
                d[f[j]] = d[p] + z[j]
    return

n = int(input())
G = [[] for _ in range(n)]
W = [[] for _ in range(n)]
c = [0] * n
d = [0] * n
for _ in range(n - 1):
    u, v, w = map(int, input().split())
    G[u - 1].append(v - 1)
    G[v - 1].append(u - 1)
    W[u - 1].append(w)
    W[v - 1].append(w)
bfs(0)
for i in d:
    print(i % 2)

Submission status: Accepted

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

N = int(input())
edge = [[] for _ in range(N+1)]
for i in range(N-1):
  u,v,w = map(int, input().split())
  edge[u].append([v,w%2])
  edge[v].append([u,w%2])
color = [0]*(N+1)
visited = [False]*(N+1)
def dfs(u):
  for v,w in edge[u]:
    if visited[v]==False:
      #print(v)
      visited[v]=True
      color[v]=color[u]^w
      dfs(v)
  return 0
visited[1]=True
dfs(1)
ans = color[1:]
print(*ans,sep='\n')

Submission status: Accepted

Solution code:
from itertools import product

def main():
    n = int(input())
    adj = [{} for i in range(n)]
    dist = [-1] * n
    for _ in range(n-1):
        u, v, w = [int(i) for i in input().split()]
        adj[u-1][v-1] = w
        adj[v-1][u-1] = w
    dist[0] = 0
    visited = 1
    cand = [0]
    while visited < n:
        pos = cand.pop()
        for i, v in adj[pos].items():
            if dist[i] < 0:
                dist[i] = (dist[pos] + v)%2
                visited += 1
                cand.append(i)
    for d in dist:
        print(d)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import defaultdict
from sys import stdin
def main():
    N = int(stdin.readline())
    edge = defaultdict(list)
    for _ in range(N-1):
        u,v,w = map(int,stdin.readline().split())
        u -= 1;v -= 1
        edge[u].append([v,w])
        edge[v].append([u,w])
    stack = [0]
    color = [-1 for _ in range(N)]
    color[0] = 0
    while stack:
        u = stack.pop()
        for e in edge[u]:
            v,dist = e
            if dist%2==0 and color[v] == -1:
                color[v] = color[u]
                stack.append(v)
            elif dist%2==1 and color[v] == -1:
                if color[u] == 1:
                    color[v] = 0
                else:
                    color[v] = 1
                stack.append(v)
            else:continue
    for c in color:
        print(c)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# https://juppy.hatenablog.com/entry/2019/02/18/%E8%9F%BB%E6%9C%AC_python_%E3%83%97%E3%83%A9%E3%82%A4%E3%82%AA%E3%83%AA%E3%83%86%E3%82%A3%E3%82%AD%E3%83%A5%E3%83%BC(heapq)%E3%82%92%E7%94%A8%E3%81%84%E3%81%9F%E3%83%97%E3%83%AA%E3%83%A0%E6%B3%95
# ↓
# http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4265763
# 頂点数10^5の時の高速化(🦍)
import heapq
import sys

input = sys.stdin.readline

def dijkstra_heap(s,edge):
    #始点sから各頂点への最短距離
    d = [10**20] * n
    used = [True] * n #True:未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    for a,b in edge[s]:
        heapq.heappush(edgelist,a*(10**6)+b)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if not used[minedge%(10**6)]:
            continue
        v = minedge%(10**6)
        d[v] = minedge//(10**6)
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,(e[0]+d[v])*(10**6)+e[1])
    return d

################################

#n = map(int,input().split()) #n:頂点数　w:辺の数  s:始点
n = int(input()); w = n - 1;s = 0 # in case that graph is tree

edge = [[] for i in range(n)]
#edge[i] : iから出る道の[重み,行先]の配列
for i in range(w):
    x,y,z = map(int,input().split())
    x -= 1
    y -= 1
    edge[x].append([z,y])
    edge[y].append([z,x]) 

d = dijkstra_heap(s,edge)
# for i in range(len(ans)):
#     if d[i] == 10**20:
#         d[i] = "INF"

# print("\n".join([ for a in d]))
print("\n".join([str(t%2) for t in d]))

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

def main():
    N = int(readline())
    m = map(int, read().split())
    UVW = zip(m, m, m)

    # 木が保証されているので、必ず実現できる

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

    color = [0] * (N + 1)
    stack = [1]
    parent = [0] * (N + 1)
    while stack:
        x = stack.pop()
        for y, w in graph[x]:
            if y == parent[x]:
                continue
            parent[y] = x
            color[y] = color[x] ^ (w & 1)
            stack.append(y)

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

if __name__ == '__main__':
    main()

Submission status: Accepted

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

d = [-1 for _ in range(N+1)]
d[1] = 0
q = [1]

while q:
    cur = q.pop()
    for n,l in tree[cur]:
        if d[n] == -1:
            d[n] = d[cur] + l
            q.append(n)

for l in d[1:]:
    print(l%2)

Submission status: Accepted

Solution code:
n=int(input())
tree=[[]for _ in range(n+1)]
for _ in range(n-1):
    u,v,w=map(int,input().split())
    tree[u].append([v,w])
    tree[v].append([u,w])
d=[-1]*(n+1)
d[1]=0
q=[1]
while q:
    now=q.pop()
    for n_i,n_l in tree[now]:
        if d[n_i]==-1:
            d[n_i]=d[now]+n_l
            q.append(n_i)
for l in d[1:]:
    print(l%2)

Submission status: Accepted

Solution code:
from collections import deque

N = int(input())
S = [[]for i in range(N)]
for i in range(N-1):
    u,v,w = map(int,input().split())
    S[u-1].append([v-1,w])
    S[v-1].append([u-1,w])
Node = [None]*N
Node[0] = True
queue = deque([0])
while queue != deque([]):
    p = queue.popleft()
    for u,w in S[p]:
        if Node[u] == None:
            queue.append(u)
            Node[u] = (Node[p])^(w%2==1)
for i in range(N):
    print([0,1][Node[i]])

Submission status: Accepted

Solution code:
n = int(input())

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

#print(tree)
d = [-1]*(n+1)
d[1] = 0
q = [1]
while q:
  now = q.pop()
  for n_i,n_l in tree[now]:
    if d[n_i] == -1:
      d[n_i] = d[now] + n_l
      q.append(n_i)

for l in d[1:]:
  print(l%2)

Submission status: Accepted

Solution code:
from collections import deque
def bfs(cur):
    q=deque()
    q.append(cur)
    while q:
        cur=q.popleft()
        for nx,e_dist in G[cur]:
            if ans[nx]!=-1:continue
            ans[nx]=(ans[cur]+e_dist)%2
            q.append(nx)

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
bfs(0)
print(*ans,sep='\n')

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(100000000)

def dfs(node,dist):
    for nx_node,e_dist in G[node]:
        if ans[nx_node]==-1:
            ans[nx_node]=(dist+e_dist)%2
            dfs(nx_node,dist+e_dist)

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, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
 
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
 
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N = INT()
uvw = [LIST() for i in range(N-1)]
color = [0] * N

graph = defaultdict(list)

for u, v, w in uvw:
    graph[u-1].append((v-1, w))
    graph[v-1].append((u-1, w))

color[0] = 1
q = [0]

while q:
    a = q.pop()
    # if color[a]

    ## from here
    # if color[a] != 0:
        # not yet
    for node, w in graph[a]:
        if color[node] == 0:
            # next_nodeはまだ塗られていない
            if w % 2 == 0:
                color[node] = color[a]
            else:
                color[node] = color[a] * (-1)
            q.append(node)
for c in color:
    if c == -1:
        print(1)
    else:
        print(0) 
            # if color[a] != 0:
                # kuro
            #     if w % 2 == 0:
            #         color[node] = color[a]
            #     else:
            #         color[node] = color[a] * (-1)
            # else:
            #     if w % 2 == 1:
            #         color[node] = color[a] 
            #     else:
            #         color[node] = color[a] * (-1)
            #     q.append(node)

Submission status: Accepted

Solution code:
import heapq
import sys

input = sys.stdin.readline

def dijkstra_heap(s,edge):
    #始点sから各頂点への最短距離
    d = [10**20] * n
    used = [True] * n #True:未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    for a,b in edge[s]:
        heapq.heappush(edgelist,a*(10**6)+b)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if not used[minedge%(10**6)]:
            continue
        v = minedge%(10**6)
        d[v] = minedge//(10**6)
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,(e[0]+d[v])*(10**6)+e[1])
    return d
################################
n=int(input()) #:頂点数　w:辺の数
w=n-1
edge = [[] for i in range(n)]
#edge[i] : iから出る道の[重み,行先]の配列
for i in range(w):
    x,y,z = map(int,input().split())
    edge[x-1].append([z,y-1])
    edge[y-1].append([z,x-1]) 

for i in dijkstra_heap(0,edge):
    if i%2==0:
        print(0)
    else:
        print(1)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)
n = int(input())
B = [[] for _ in range(n+1)]
for i in range(n-1):
    v,w,dist = map(int, input().split())
    B[v].append((w,dist))
    B[w].append((v,dist))
color = [-1]*(n+1)
def dfs(a, col):
    if color[a] == -1:
        color[a] = col
    for next_V, dis in B[a]:
        if color[next_V] == -1:
            tmp = col
            if dis%2 != 0:
                tmp = 1-col
            dfs(next_V, tmp)
dfs(1,0)
[print(color[i]) for i in range(1,n+1)]

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)
n = int(input())
G = [[] for _ in range(n+1)]
for i in range(n-1):
    v,w,dist = map(int, input().split())
    G[v].append((w,dist))
    G[w].append((v,dist))
color = [-1]*(n+1)


def dfs(a, col):
    tmp = -1
    if color[a] == -1:
        color[a] = col

    for next_V,dis in G[a]:
        if color[next_V] == -1:
            tmp = col
            if dis%2 !=0:
                tmp = 1-col
            dfs(next_V, tmp)
dfs(1,0)
[print(color[i]) for i in range(1,n+1)]

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
n=int(input())

#グラフの連結成分を調べる
def Graph():
    G=[[] for i in range(n)]
    #up_G=[0]*n#up_G[i]=頂点iの親
    for i in range(n-1):
        a,b,c=map(int,input().split())
        c=0 if c%2==0 else 1
        G[a-1].append((b,c))
        G[b-1].append((a,c))
    return G

#木上のDFSテンプレ
from collections import deque
def dfs(G,v,p):
    q=deque()
    q.append((v,p))
    dis=0
    dis_l=[-1]*n
    dis_l[0]=0
    while q:
        V,P=q.pop()
        for new_v in G[V-1]:
            v0,v1=new_v
            #new_vが頂点の時はアウト
            if v0==P:continue
            if dis_l[v0-1]>=0:continue
            dis=(dis_l[V-1]+v1)%2
            dis_l[v0-1]=dis
            q.append((v0,V))

    return dis_l


log=Graph()
ans=dfs(log,1,-1)
print(*ans,sep='\n')

Submission status: Accepted

Solution code:
import collections


def main():
    import sys
    input = sys.stdin.readline
    N = int(input())
    color = [-1]*N
    G = [set() for i in range(N)]
    for i in range(N-1):
        u, v, w = map(int, input().split())
        u -= 1
        v -= 1
        G[u].add((v, w))
        G[v].add((u, w))
    root = 0

    color[0] = 0
    q = collections.deque()
    q.append((root, 0))
    while(q):
        x, W = q.popleft()
        for y, w in G[x]:
            if color[y] < 0:
                if (W+w) % 2 == 0:
                    color[y] = 0
                else:
                    color[y] = 1
                q.append((y, W+w))
            else:
                continue
    print(*color, sep="\n")


main()