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 sys
sys.setrecursionlimit(10**6)
N = int(input())
edg = [list(map(int,input().split())) for _ in range(N-1)]
vtx = [[] for _ in range(N)]
for e in edg:
    v1,v2,w = e
    vtx[v1-1].append([v2-1,w])
    vtx[v2-1].append([v1-1,w])

colors = [1 for _ in range(N)]

def dfs(vtx,i=0,p=-1,c=1): # vertex and its parent
    colors[i] = c
    for v,w in vtx[i]:
        if v == p:
            continue
        dfs(vtx,v,i,1-c if w%2 != 0 else c)
dfs(vtx)

for v in colors:
    print(v)

Submission status: Accepted

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

from collections import deque

N = int(input())

distance = {}
edge = [[] for _ in range(N + 1)]

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

color = [0 for _ in range(N + 1)]
q = deque([1]) # root => 1
done = [0 for _ in range(N + 1)]
done[1] = 1

while q:
    parent = q.pop()
    for e in edge[parent]:
        if e != parent and done[e] == 0:
            d = distance[str(parent) + "_" + str(e)]
            if d % 2 == 0:
                color[e] = color[parent]
            else:
                color[e] = 0 if color[parent] == 1 else 1
            q.append(e)
            done[e] = 1

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

Submission status: Accepted

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

ans = [-1]*N
ans[0] = 0
q = deque()
q.append((0, 0))
while q:
    temp = q.popleft()
    u = temp[0]
    w = temp[1]
    for e in E[u]:
        if ans[e[0]] >= 0:
            continue
        if w+e[1] & 1 == 0:
            ans[e[0]] = 0
        else:
            ans[e[0]] = 1
        q.append((e[0], w+e[1]))

for a in ans:
    print(a)

Submission status: Accepted

Solution code:
from collections import deque
n=int(input())
v=tuple(tuple(map(lambda x: int(x)-1,input().split())) for _ in range(n-1))

node=[{} for _ in range(n)]
d=deque()
ans= [-1] * n
ans[0]=0
d.append(0)
for pair in v:
    node[pair[0]][pair[1]]=pair[2]
    node[pair[1]][pair[0]]=pair[2]
    
while True:
    if not d:
        break
    i=d.pop()
    for k in node[i].keys():
        if ans[k]!=-1:
          continue
        d.append(k)
        if node[i][k]%2==1:
            ans[k]=ans[i]
        else:
            ans[k]=1-ans[i]
print(*ans)

Submission status: Accepted

Solution code:
n=int(input())
node=[-1 for i in range(n)]
g=[[] for i in range(n)]
for i in range(n-1):
  u,v,w=map(int,input().split())
  u-=1
  v-=1
  w%=2
  g[u].append([v,w])
  g[v].append([u,w])
queue=[0]
node[0]=0
while len(queue)>0:
  t=queue.pop()
  for v,w in g[t]:
    if node[v]>-1:
      continue
    node[v]=node[t]^w
    queue.append(v)
for i in range(n):
  print(node[i])

Submission status: Accepted

Solution code:

import sys
sys.setrecursionlimit(10**6)
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))
vis = [False]*n
color = [0]*n

def dfs_rec(now):
    for node,w in tree[now]:
        if not vis[node]:
            vis[node] = True
            if w%2==0:
                color[node] = color[now]
            else:
                color[node] = 1-color[now]
            dfs_rec(node)
    return
vis[0] = True
dfs_rec(0)
for c in color:
    print(c)

Submission status: Accepted

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

def dijkstra(s,N,edge):
    d = [float('inf')] * N
    used = [False] * N
    d[s] = 0
    used[s] = True
    edgelist = []
    for w, i in edge[s]:
        heapq.heappush(edgelist, w * (10**6) + i)
        # (w * (10**6) + i) // 10 ** 6 => 距離 w　が求められる
        # (w * (10**6) + i) % 10 ** 6 => 頂点 i　が求められる
    
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        if used[minedge%(10**6)]:
            continue
        v = minedge % (10 ** 6)
        d[v] = minedge // (10 ** 6)
        used[v] = True
        for w, i in edge[v]:
            if not used[i]:
                heapq.heappush(edgelist,(w+d[v])*(10**6)+i)

    return d


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

    d = dijkstra(0,N,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(500*500)
N = int(input())
edges = [list(map(int,input().split())) for _ in range(N-1)]
A = [[] for _ in range(N+1)]

for edge in edges:
    A[edge[0]].append([edge[1],edge[2]])
    A[edge[1]].append([edge[0],edge[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
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

from collections import deque 
def main():
    N = int(readline())
    to = [[] for _ in range(N)]
    wight = [[] for i in range(N)]
    for _ in range(N-1):
        u, v, w = map(int, readline().split())
        u-=1
        v-=1
        to[u].append(v)
        to[v].append(u)
        wight[u].append(w)
        wight[v].append(w)

    dq = deque()
    dq.append(0)
    dist = [-1 for _ in range(N)]
    dist[0] = 0
    while len(dq)>0:
        v = dq.popleft()
        for i in range(len(to[v])):
            nx = to[v][i] 
            cost = wight[v][i]
            if dist[nx] != -1:
                continue
            dist[nx] = (dist[v]+cost)%2
            dq.append(nx)

    for i in dist:
        print(i)
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(1000000)


def dfs(g: {}, v: int, seen: [], current_color: int):
    seen[v] = current_color
    for (next_v, next_w) in g[v]:
        # next_v が探索済だったらスルー
        if seen[next_v] != -1:
            if current_color == seen[next_v] and next_w % 2 == 1:
                return False
            elif current_color != seen[next_v] and next_w % 2 == 0:
                return False
            continue
        next_color = current_color if next_w % 2 == 0 else 1 - current_color
        # 再帰的に探索
        if not dfs(g, next_v, seen, next_color):
            return False
    return True


def main():
    n = int(input())

    g = {}
    for i in range(n-1):
        u, v, w = map(int, input().split())
        dic_a = g.setdefault(u-1, [])
        dic_a.append((v-1, w))
        dic_b = g.setdefault(v-1, [])
        dic_b.append((u-1, w))
    # -1:not clear, 0:white, 1:black
    seen = [-1] * n

    is_bipartite = True

    for i in range(n):
        if seen[i] != -1:
            continue
        if not dfs(g, i, seen, 0):
            is_bipartite = False
            break

    if is_bipartite:
        for i in range(n):
            print(seen[i])
    else:
        print("is not bipartite")

main()

Submission status: Accepted

Solution code:
n=int(input())
g=[[] for _ in range(n)]
for _ in range(n-1):
  u,v,w=map(int,input().split())
  g[u-1]+=[(v-1,w%2)]
  g[v-1]+=[(u-1,w%2)]
l=[-1]*n
q=[(0,0)]
while q:
  a,b=q.pop(); l[a]=b
  for c,d in g[a]:
    if l[c]<0: q+=[(c,b^d)]
print(*l,sep='\n')

Submission status: Accepted

Solution code:
n=int(input())
g=[set() for _ in range(n)]
for _ in range(n-1):
  u,v,w=map(int,input().split())
  g[u-1].add((v-1,w%2))
  g[v-1].add((u-1,w%2))
l=[-1]*n
q=[(0,0)]
while q:
  a,b=q.pop()
  l[a]=b
  for c,d in g[a]:
    if l[c]>=0: continue
    q+=[(c,b^d)]
print(*l,sep='\n')

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)
n=int(input())
g=[set() for _ in range(n)]
for _ in range(n-1):
  u,v,w=map(int,input().split())
  g[u-1].add((v-1,w%2))
  g[v-1].add((u-1,w%2))
l=[-1]*n
def dfs(x,p=-1,s=0):
  l[x]=s
  for c,d in g[x]:
    if p==c: continue
    dfs(c,x,s^d)
dfs(0)
print(*l,sep='\n')

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().strip()


def main():
    N = int(input())
    repn = [[] for _ in range(N)]
    for _ in range(N - 1):
        u, v, w = map(int, input().split())
        repn[u - 1].append((v - 1, w))
        repn[v - 1].append((u - 1, w))
    
    """
    Greedyに隣接する頂点ごとに色を塗っていけばよい
    """

    color = [-1] * N
    color[0] = 0
    q = [0]
    while q:
        v = q.pop()
        for u, w in repn[v]:
            if color[u] != -1:
                continue
            if w % 2 == 0:
                color[u] = color[v]
            else:
                color[u] = (1 + color[v]) % 2
            q.append(u)
    for ans in color:
        print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
import heapq


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


def dijkstra(start, n_nodes, edge):
    dist = [float("inf")] * n_nodes
    dist[start] = 0
    # 優先度キューの準備
    q = [(dist[start], start)]
    heapq.heapify(q)
    while q:
        # スタートから最も最短距離のものを取り出す
        d, i = heapq.heappop(q)
        # 記録してある情報よりも，取り出した要素に入っている距離情報の方が大きければ
        # 打ち切り．次の要素を取り出す操作に戻る
        if dist[i] < d:
            continue
        # そこから移動できる頂点を探し，最短距離が更新できるものがあれば，
        # 距離を更新して，その頂点への距離と頂点の方法を優先度キューにpush
        for cost, j in edge[i]:
            if dist[j] > dist[i] + cost:
                dist[j] = dist[i] + cost
                heapq.heappush(q, (dist[j], j))
    return dist


def main():
    N = int(input())
    edge = [[] for _ in range(N)]
    for i in range(N - 1):
        u, v, w = map(int, input().split())
        edge[u - 1].append((w, v - 1))
        edge[v - 1].append((w, u - 1))
    D = dijkstra(0, N, edge)
    for d in D:
        if d % 2 == 0:
            print(0)
        else:
            print(1)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
import heapq


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


def dijkstra(start, n_nodes, edge):
    dist = [float("inf")] * n_nodes
    dist[start] = 0
    # 優先度キューの準備
    q = [(dist[start], start)]
    heapq.heapify(q)
    while q:
        # スタートから最も最短距離のものを取り出す
        d, i = heapq.heappop(q)
        # 記録してある情報よりも，取り出した要素に入っている距離情報の方が大きければ
        # 打ち切り．次の要素を取り出す操作に戻る
        if dist[i] < d:
            continue
        # そこから移動できる頂点を探し，最短距離が更新できるものがあれば，
        # 距離を更新して，その頂点への距離と頂点の方法を優先度キューにpush
        for cost, j in edge[i]:
            if dist[j] > dist[i] + cost:
                dist[j] = dist[i] + cost
                heapq.heappush(q, (dist[j], j))
    return dist


def main():
    N = int(input())
    edge = [[] for _ in range(N)]
    for i in range(N - 1):
        u, v, w = map(int, input().split())
        edge[u - 1].append([w, v - 1])
        edge[v - 1].append([w, u - 1])
    D = dijkstra(0, N, edge)
    for d in D:
        if d % 2 == 0:
            print(0)
        else:
            print(1)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import heapq
import sys

sys.setrecursionlimit(10 ** 6)
INF = float("inf")
MOD = 10 ** 9 + 7


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


def dijkstra(edges, n_nodes, start=0):
    dist = [float("inf")] * n_nodes
    dist[start] = 0

    # 優先度キュー
    q = [(dist[start], start)]
    heapq.heapify(q)

    while q:
        d, i = heapq.heappop(q)

        if dist[i] < d:
            continue

        for weight, j in edges[i]:
            tmp = dist[i] + weight
            if dist[j] > tmp:
                dist[j] = tmp
                heapq.heappush(q, (dist[j], j))

    return dist


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

    dist = dijkstra(edges, N)

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


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import defaultdict


def main():
    N = int(input())
    adj_nodes = defaultdict(list)
    edge_lengths = defaultdict(int)
    for _ in range(N - 1):
        u, v, w = list(map(int, input().split()))
        u -= 1
        v -= 1
        adj_nodes[u].append(v)
        adj_nodes[v].append(u)
        edge_lengths[(u, v)] = w
        edge_lengths[(v, u)] = w
    # Calculate distances from root node
    distances = [0 for _ in range(N)]
    explored = [0 for _ in range(N)]
    start_node = 0
    frontier = [(start_node, None)]  # (node, parent node)
    while len(frontier) > 0:
        node, parent_node = frontier.pop()
        if parent_node is not None:
            distances[node] = distances[parent_node] + edge_lengths[(node, parent_node)]
        explored[node] = 1
        next_nodes = adj_nodes[node]
        for next_node in next_nodes:
            if explored[next_node] == 1:
                continue
            frontier.append((next_node, node))
    # Coloring
    #   white: distance is odd
    #   black: distance is even
    for node in range(N):
        color = 0 if distances[node] % 2 == 1 else 1
        print(color)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n=int(input())
G=[[] for i in range(n)]
for i in range(n-1):
  u,v,w=map(int,input().split())
  G[u-1].append([v-1,w])
  G[v-1].append([u-1,w])
dist=[-1]*n
from collections import deque
q=deque()
q.append(0)
dist[0]=0
while q:
  cur=q.popleft()
  for nx,nd in G[cur]:
    if dist[nx]!=-1:continue
    dist[nx]=(dist[cur]+nd)%2
    q.append(nx)
print(*dist,sep='\n')

Submission status: Accepted

Solution code:
from _collections import deque
n = int(input())
edges = [[]for _ in range(n)]
for i in range(n-1):
    a, b, w = map(int, input().split())
    edges[a-1].append([b-1, w])
    edges[b-1].append([a-1, w])
color = [0]*n
color[0] = -1
q = deque()
q.append(0)
while q:
    a = q.popleft()
    for v, w in edges[a]:
        if color[v] != 0:
            continue
        else:
            q.append(v)
            if w % 2 == 0:
                color[v] = color[a]
            else:
                color[v] = (-1)*color[a]

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

Submission status: Accepted

Solution code:
import heapq
def dijkstra_heap(s):
  d=[float("inf")]*n
  used=[True]*n 
  d[s]=0
  used[s]=False
  edgelist=[]
  for e in edge[s]:
    heapq.heappush(edgelist,e)
  while len(edgelist):
    minedge=heapq.heappop(edgelist)
    if not used[minedge[1]]:
      continue
    v=minedge[1]
    d[v]=minedge[0]
    used[v]=False
    for e in edge[v]:
      if used[e[1]]:
        heapq.heappush(edgelist,[e[0]+d[v],e[1]])
  return d

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

ans=dijkstra_heap(0)
for i in range(n):
  print(ans[i]%2)

Submission status: Accepted

Solution code:
n=int(input())
l=[list(map(int,input().split())) for i in range(n-1)]
connection=[[] for i in range(n)]
for i in range(n-1):
  connection[l[i][0]-1].append(l[i][1]-1)
  connection[l[i][1]-1].append(l[i][0]-1)
d={}
for i in range(n-1):
  d[(l[i][0]-1,l[i][1]-1)]=l[i][2]
  d[(l[i][1]-1,l[i][0]-1)]=l[i][2]

def bfs(v):
  distance=[-1]*n
  distance[v]=0
  next=[v]
  next2=set()
  visited=[-1]*n
  visitct=0
  while len(next)!=0 and visitct!=n:
    for i in range(len(next)):
      if visited[next[i]]==-1:
        visited[next[i]]=1
        visitct+=1
        for j in range(len(connection[next[i]])):
          if visited[connection[next[i]][j]]==-1:
            distance[connection[next[i]][j]]=distance[next[i]]+d[(next[i],connection[next[i]][j])]
            next2.add(connection[next[i]][j])
    next=list(next2)
    next2=set()
  return distance

ans=bfs(0)
for i in range(n):
  print(ans[i]%2)

Submission status: Accepted

Solution code:
from heapq import heappush, heappop, heapify

N = int(input())
edge = [[] for i in range(N)]

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

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

dist = [float('inf')] * N
visited = [False] * N
dist[0] = 0
visited[0] = True

count = N-1
q = edge[0]
heapify(q)

while q and count:
    w, v = heappop(q)

    if visited[v]: continue
    visited[v] = True
    dist[v] = w
    count -= 1

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

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

Submission status: Accepted

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

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

check=[0]*N
ans=[0]*N
def solve(x):
  check[x]=1
  for i,d in graph[x]:
    if check[i]==0:
      ans[i]=(ans[x]+d)%2
      solve(i)
solve(0)
for i in range(N):
  print(ans[i])

Submission status: Accepted

Solution code:
N = int(input())
from collections import deque

tree = [{} for _ in range(N)]

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

queue = deque()
queue.append((0, 0))

while queue:
    v, w = queue.pop()
    color[v] = w%2
    for i in tree[v].keys():
        if color[i]==-1:
            queue.append((i, w+tree[v][i]))

for c in color:
    print(c)

Submission status: Accepted

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

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

s = [( 0, 0 )]
l = [ -1 ] * N
while s != []:
  a, w = s.pop()
  l[ a ] = w % 2
  for i, j in d[ a ]:
    if l[ i ] == -1:
      s.append( ( i , j + w ) )
for i in l:
  print( i )

Submission status: Accepted

Solution code:
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; w%=2
    G[u].append([v,w])
    G[v].append([u,w])
col=[-1 for i in range(N)]
col[0]=0
 
from collections import deque
dq=deque([0])
 
while len(dq)>0:
    p=dq.popleft()
    for i in range(len(G[p])):
        if col[G[p][i][0]]==-1: # 色がまだついていない場合
            dq.append(G[p][i][0]) # 頂点をキューに追加
            col[G[p][i][0]]=(col[p]+G[p][i][1])%2 # キューに追加された頂点と同じ偶奇かで色つけする
        
for i in col:
    print(i)

Submission status: Accepted

Solution code:
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; w%=2
    G[u].append([v,w])
    G[v].append([u,w])
col=[-1 for i in range(N)]
col[0]=0

from collections import deque
dq=deque([0])

while len(dq)>0:
    p=dq.popleft()
    for i in range(len(G[p])):
        if col[G[p][i][0]]==-1:
            dq.append(G[p][i][0])
            col[G[p][i][0]]=(col[p]+G[p][i][1])%2
        
for i in col:
    print(i)

Submission status: Accepted

Solution code:
import sys
import math  # noqa
import bisect  # noqa
import queue  # noqa


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


def main():
    N = int(input())

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

    state = [0 for _ in range(N)]
    visit = [False for _ in range(N)]
    que = queue.Queue()
    que.put((0, 0))
    while not que.empty():
        c, d = que.get()
        if d % 2 == 0:
            state[c] = 1
        visit[c] = True
        for pos, w in node[c]:
            if not visit[pos]:
                que.put((pos, d + w))

    for s in state:
        print(s)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

stack = [0]
d = [-1] * n
d[0] = 0

while stack:
    u = stack.pop()
    for v, w in adj[u]:
        if d[v] == -1:
            d[v] = d[u] + w
            d[v] %= 2
            stack.append(v)

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

Submission status: Accepted

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

import sys
# import math
# import re                                    # re.compile(pattern) => ptn obj; p.search(s), p.match(s), p.finditer(s) => match obj; p.sub(after, s)
# from collections import deque                # deque class. deque(L): dq.append(x), dq.appendleft(x), dq.pop(), dq.popleft(), dq.rotate()
# from collections import defaultdict          # subclass of dict. defaultdict(facroty)
# from collections import Counter              # subclass of dict. Counter(iter): c.elements(), c.most_common(n), c.subtract(iter)
# from heapq import heapify, heappush, heappop # built-in list. heapify(L) changes list in-place to min-heap in O(n), heappush(heapL, x) and heappop(heapL) in O(lgn).
# from heapq import nlargest, nsmallest        # nlargest(n, iter[, key]) returns k-largest-list in O(n+klgn).
# from itertools import count, cycle, repeat   # count(start[,step]), cycle(iter), repeat(elm[,n])
# from itertools import groupby                # [(k, list(g)) for k, g in groupby('000112')] returns [('0',['0','0','0']), ('1',['1','1']), ('2',['2'])]
# from itertools import starmap                # starmap(pow, [[2,5], [3,2]]) returns [32, 9]
# from itertools import product                # product(iter, repeat=n)
# from itertools import accumulate             # accumulate(iter[, f])
# from functools import reduce                 # reduce(f, iter[, init])
# from functools import lru_cache              # @lrucache ...arguments of functions should be able to be keys of dict
# from bisect import bisect_left, bisect_right # bisect_left(a, x, lo=0, hi=len(a)) returns i such that all(val<x for val in a[lo:i]) and all(val>-=x for val in a[i:hi]).
# from copy import deepcopy                    # to copy multi-dimentional matrix without reference
# from fractions import gcd                    # for Python 3.4


def main():
    mod = 1000000007                  # 10^9+7
    inf = float('inf')
    sys.setrecursionlimit(10**6)    # 1000 -> 1000000
    def input(): return sys.stdin.readline().rstrip()
    def ii():  return int(input())
    def mi():  return map(int, input().split())
    def mi_0(): return map(lambda x: int(x)-1, input().split())
    def lmi(): return list(map(int, input().split()))
    def lmi_0(): return list(map(lambda x: int(x)-1, input().split()))
    def li():  return list(input())

        
    n = ii()
    tree = [[] for _ in range(n+1)]    # 頂点 i (1-index) が隣接頂点 j と距離 d_j, k と 距離 d_k の時、tree[i] = [(j, d_j), (k, d_k)] と記録される
    for _ in range(n-1):
        u, v, w = mi()
        tree[u].append((v, w))
        tree[v].append((u, w))
    color = [None] * (n+1)
    root = 1
    def dfs(u=root, prev=-1, evenp=True):
        color[u] = evenp
        # print(u)
        for v, d in tree[u]:
            if v == prev:
                continue
            if d % 2 == 0:
                dfs(v, prev=u, evenp=evenp)
            else:
                dfs(v, prev=u, evenp=not evenp)
    dfs()
    for vertex_color in color[1:]:
        print('1') if vertex_color else print('0')





if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(20000000)

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

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

ans=[-1]*n
distn(0,0)
print(*ans,sep="\n")

Submission status: Accepted

Solution code:
import sys,queue,math,copy,itertools,bisect,collections
sys.setrecursionlimit(10**7)
LI = lambda : [int(x) for x in sys.stdin.readline().split()]
NI = lambda : int(sys.stdin.readline())

N = NI()
edge = [[] for _ in range(N+1)]
color = [-1] * (N+1)
for _ in range(N-1):
    u,v,w = LI()
    edge[u].append((v,w))
    edge[v].append((u,w))

def set_color(u,c):
    color[u] = c
    for v,w in edge[u]:
        if color[v] >= 0 : continue
        set_color(v,(w % 2) ^ c)
set_color(1,0)
print(*color[1:],sep='\n')

Submission status: Accepted

Solution code:
import sys,queue,math,copy,itertools,bisect,collections
sys.setrecursionlimit(10**7)
INF = 10**18
MOD = 10**9 + 7
LI = lambda : [int(x) for x in sys.stdin.readline().split()]
_LI = lambda : [int(x)-1 for x in sys.stdin.readline().split()]
NI = lambda : int(sys.stdin.readline())

N = NI()
edge = [[] for _ in range(N+1)]
color = [-1] * (N+1)
for _ in range(N-1):
    u,v,w = LI()
    edge[u].append((v,w))
    edge[v].append((u,w))

def set_color(u,c):
    color[u] = c
    for v,w in edge[u]:
        if color[v] >= 0 : continue
        set_color(v,(w % 2) ^ c)
set_color(1,0)
print(*color[1:],sep='\n')

Submission status: Accepted

Solution code:
import sys
import math
import fractions
from collections import deque
from collections import defaultdict
sys.setrecursionlimit(10**7)

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

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

ans = [0] * N


def dfs(cur, prev, dist):
    if dist % 2 == 0:
        ans[cur] = 1
    else:
        ans[cur] = 0
    for n, d in graph[cur]:
        if n != prev:
            dfs(n, cur, dist + d)


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

Submission status: Accepted

Solution code:
import heapq
def dijkstra_heap(s):
    d = [float("inf")] * n
    used = [True] * n
    d[s] = 0
    used[s] = False
    edgelist = []
    for e in edge[s]:
        heapq.heappush(edgelist,e)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        if not used[minedge[1]]:
            continue
        v = minedge[1]
        d[v] = minedge[0]
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,[e[0]+d[v],e[1]])
    return d
n = int(input())
edge = [[] for i in range(n+1)]
for i 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])
dist = dijkstra_heap(0)
for i in dist:
    print(i%2)

Submission status: Accepted

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

G = [[] for i in range(N+1)]
for i in range(N-1):
    G[data[i][0]].append((data[i][1],data[i][2]))
    G[data[i][1]].append((data[i][0],data[i][2]))

from collections import deque

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

q = deque([1])

while q:
    n = q.pop()
    for d,e in G[n]:
        if D[d] != -1:
            continue
        elif e % 2 == 1:
            D[d] = 1-D[n]
            q.append(d)
        else:
            D[d] = D[n]
            q.append(d)

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

Submission status: Accepted

Solution code:
from collections import deque

N = int(input())
tree = [dict() for _ in range(N+1)]
color = [0]*(N+1)
parent = [0]*(N+1)
for _ in range(N-1):
    u, v, w = map(int, input().split())
    w %= 2
    tree[u][v] = w
    tree[v][u] = w

que = deque([1])
while len(que) != 0:
    u = que.pop()
    Rel, c, p = tree[u], color[u], parent[u]
    for v in Rel.keys():
        if v == p:
            continue
        elif Rel[v] == 0:
            color[v] = c
        else:
            color[v] = c^1
        parent[v] = u
        que.append(v)

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

Submission status: Accepted

Solution code:
from collections import deque


def main():
    vertices = int(input())
    tree = [[] for _ in range(vertices)]
    for _ in range(vertices - 1):
        u, v, length = map(int, input().split())
        u -= 1
        v -= 1
        tree[u].append([v, length])
        tree[v].append([u, length])
    root_index = 0
    max_deg = 0
    for i in range(vertices):
        if max_deg < len(tree[i]):
            root_index = i
            max_deg = len(tree[i])
    queue = deque([[root_index, 0]])
    is_checked = [False for _ in range(vertices)]
    is_checked[root_index] = True
    answer = ["0" for _ in range(vertices)]
    while queue:
        now_v, dist_from_root = queue.pop()
        for next_v, length in tree[now_v]:
            if not is_checked[next_v]:
                is_checked[next_v] = True
                if (dist_from_root + length) % 2:
                    answer[next_v] = "1"
                queue.append([next_v, dist_from_root + length])
    print("\n".join(answer))


if __name__ == '__main__':
    main()