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:
from collections import deque
from heapq import heapify,heappop,heappush,heappushpop
from copy import copy,deepcopy
from itertools import permutations,combinations
from collections import defaultdict,Counter
from pprint import pprint

def myinput():
    return map(int,input().split())

def mycol(data,col):
    return [ row[col] for row in data ]

def mysort(data,col):
    data.sort(key=lambda x:x[col],reverse=False)
    return data

def mymax(data):
    M = -1*float("inf")
    for i in range(len(data)):
        m = max(data[i])
        M = max(M,m)
    return M

def mymin(data):
    m = float("inf")
    for i in range(len(data)):
        M = min(data[i])
        m = min(m,M)
    return m

n = int(input())
uvw = [ list(myinput()) for _ in range(n-1) ]

g = [ [] for _ in range(n) ]
for i in range(n-1):
    u = uvw[i][0] - 1
    v = uvw[i][1] - 1
    w = uvw[i][2]
    g[u].append([v,w])
    g[v].append([u,w])
# print(g)

def bfs(g):
    ls_ans = [-1] * n
    ls_ans[0] = 0
    q = deque()
    q.append(0)
    while q:
        node = q.popleft()
        ls = g[node]
        # print(ls)
        for i in range(len(ls)):
            child = ls[i][0]
            weight = ls[i][1]
            if ls_ans[child]!=-1:
                pass
            elif ls_ans[node]==0 and weight%2==0:
                ls_ans[child] = 0
                q.append(child)
            elif ls_ans[node]==0 and weight%2==1:
                ls_ans[child] = 1
                q.append(child)
            elif ls_ans[node]==1 and weight%2==0:
                ls_ans[child] = 1
                q.append(child)
            elif ls_ans[node]==1 and weight%2==1:
                ls_ans[child] = 0
                q.append(child)
            else:
                print("error")
        # print(ls_ans)
    return ls_ans

ls_ans = bfs(g)
# print(ls_ans)

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

Submission status: Accepted

Solution code:
import sys
stdin = sys.stdin
sys.setrecursionlimit(10**6)
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()

n = ni()
g = [[] for i in range(n)]

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

dp = [0]*n

def f(a,b,c):
    dp[b] = c
    for i,j in g[b]:
        if i != a:
            f(b,i,c+j)

f(0,0,0)

for k in dp:
    print(k%2)

Submission status: Accepted

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

q = deque([(0,0)])
reached = [True] + [False]*(n-1)
ans = [0]*n
while q:
  p,c = q.popleft()
  for i,d in path[p].items():
    if reached[i]:continue
    if d&1:
      ans[i] = 1 - c
    else:
      ans[i] = c
    reached[i] = True
    q.append((i,ans[i]))
for i in ans:
  print(i)

Submission status: Accepted

Solution code:
from collections import deque

N = int(input())
tree =   [[] for _ in range(N)]
color = [-1] * N
color[0] = 0
for n 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])

q = deque()
q.append((0,-1))

while q:
  index, parent = q.pop()
  for target, d in tree[index]:
    if target == parent: continue
    if d%2 == 0:
      color[target] = color[index]
    else:
      color[target] = (color[index] + 1)%2
    q.append((target,index))
print(*color, sep="\n")

Submission status: Accepted

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

g = [[] * n 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))

chk = [0]*n
chk[0] = 1

def dfs(now, prev):
    global chk
    # 今いる頂点から行ける頂点を順に next に入れてループ
    for next in g[now]:
        if next[0] != prev:
          if next[1]%2 == 0:
            chk[next[0]] = chk[now]
          elif next[1]%2 == 1:
            chk[next[0]] = (chk[now]*-1)
          
          dfs(next[0], now)
        
dfs(0,-1)
chk = tuple(chk)
for i in chk:
  if i == 1:
    print(1)
  else:
    print(0)

Submission status: Accepted

Solution code:
import sys, copy, math, heapq, bisect
from itertools import accumulate
from collections import deque, defaultdict, Counter
input = sys.stdin.readline # 文字列の入力のとき'/n'まで受け取るので注意!!!
sys.setrecursionlimit(500000)

N = int(input())
T = [defaultdict(int) for i in range(N)]
for i in range(N-1):
    u,v,w = map(int,input().split())
    T[u-1][v-1] = w
    T[v-1][u-1] = w
visited = [0]*N
ans = [0]*N
def dfs(now,col):
    visited[now] = 1
    for i in T[now].keys():
        if visited[i] == 1:
            continue
        if T[now][i]%2==1:
            ans[i] = col^1
            next = col^1
        else:
            ans[i] = col
            next = col
        dfs(i,next)
dfs(0,0)
for i in range(N):
    print(ans[i])

Submission status: Accepted

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

n = int(input())
g = [[] for _ in range(n)]
color = [-1] * n
for _ 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])


def dfs(u, c):
    color[u] = c
    for v, w in g[u]:
        if color[v] != -1:
            continue
        if w % 2 == 0:
            nc = c
        else:
            nc = 1 - c
        dfs(v, nc)


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

Submission status: Accepted

Solution code:
def bfs(n, g):
    from collections import deque
    color = [-1] * n
    q = deque([0])
    while q:
        tmp = q.popleft()
        for u, w in g[tmp]:
            if color[u] != -1:
                continue
            color[u] = color[tmp] + w
            q.append(u)
    for c in color:
        if c % 2 == 0:
            print(1)
        else:
            print(0)


def main():
    n = int(input())
    g = [[] for _ in range(n)]
    for _ 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])
    bfs(n, g)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import deque

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

q = deque([1])
while q:
  x = q.popleft()
  for y, w in graph[x]:
    if(y == parent[x]):
      continue
    parent[y] = x
    ans[y] = ans[x]^(w&1)
    q.append(y)
      
for i in range(1, n+1):
  print(ans[i])

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
sys.setrecursionlimit(10**5)
n = int(input())
uvw = [list(map(int, input().split())) for _ in range(n-1)]

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

res = [[] for _ in range(n)]
def dfs(v, p, c):
    res[v] = c
    for e in edges[v]:
        if e[0] == p: continue
        if e[1]%2==1: dfs(e[0], v, 1-c%2)
        else: dfs(e[0], v, c)

dfs(0, -1, 1)
print('\n'.join(list(map(str, res))))

Submission status: Accepted

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

used = [0]*N
Q = deque([0])
used[0] = 1
ans = [0]*N
while Q:
  i = Q.popleft()
  j = ans[i]
  for uv, w in Graph[i]:
    if used[uv]:
      continue
    if w%2 != 0:
      ans[uv] = j^1
    else:
      ans[uv] = j
    Q.append(uv)
    used[uv] = 1

print(*ans)

Submission status: Accepted

Solution code:
n = int(input())
node = {i:[] for i in range(1, n+1)}
ans = {i:0 for i in range(1, n+1)}

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

stack = [1]
memory = set()

while stack:
  x = stack.pop()
  memory.add(x)
  
  for node_i, len_i in node[x]:
    if node_i not in memory:
      if len_i%2==0:
        ans[node_i] = ans[x]
      else:
        ans[node_i] = 1-ans[x]
      stack.append(node_i)  
    
for v in ans.values():
  print(v)

Submission status: Accepted

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

def solve(N: int, u: "List[int]", v: "List[int]", w: "List[int]"):

    G=[dict() for i in range(N)]
    for i in range(N-1):
        ui,vi,wi=u[i],v[i],w[i]
        G[ui-1][vi-1]=wi
        G[vi-1][ui-1]=wi

    dist = [-1]*N
    p = [0]
    dist[0] = 0

    while (len(p)>0):
        k = p.pop()
        for n in G[k]:
            if dist[n]==-1:
                dist[n] = dist[k] + G[k][n]
                p.append(n)
    
    for x in dist:
        print(x%2)

    return


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

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque

N = int(input())
lines = [[] for _ in range(N+1)]
for _ in range(N-1):
    u, v, w = map(int, input().split())
    lines[u].append([v, w%2])
    lines[v].append([u, w%2])
q = deque([1])
color = [0]*(N+1)
d = [0]*(N+1)
parent = [0]*(N+1)
while q:
    x = q.popleft()
    dis = d[x]
    for y, w in lines[x]:
        if y == parent[x]:
            continue
        if (dis+w)%2 == 1:
            color[y] = 1
        parent[y] = x
        d[y] = (dis+w)%2
        q.append(y)
for i in range(1, N+1):
    print (color[i])

Submission status: Accepted

Solution code:
# coding: utf-8
import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N = ir()
graph = [[] for _ in range(N+1)] # 1-indexed
for _ in range(N-1):
    a, b, w = lr()
    graph[a].append((b, w&1))
    graph[b].append((a, w&1))

color = [None] * (N+1)
color[1] = 0
root = 1
parent = [0] * (N+1)
stack = [(root, 0)]
while stack:
    cur, c = stack.pop()
    for next, weight in graph[cur]:
        if next == parent[cur]:
            continue
        parent[next] = cur
        color[next] = c^weight
        stack.append((next, color[next]))

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

Submission status: Accepted

Solution code:
from collections import deque, defaultdict

def main():
    n = int(input())
    UVW = [[int(e) for e in input().split()] for i in range(n - 1)]

    D = defaultdict(list)
    for uvw in UVW:
        u, v, w = uvw
        D[u].append([v, w])
        D[v].append([u, w])

    A = [''] * (n + 1)
    A[UVW[0][0]] = '0'

    Q = deque()
    Q.append(UVW[0][0])

    while True:
        if len(Q) == 0:
            break

        qe = Q.pop()
        for de in D[qe]:
            if A[de[0]] == '':
                Q.append(de[0])

            if de[1] % 2 == 0:
                A[de[0]] = A[qe]
            else:
                if A[qe] == '0':
                    A[de[0]] = '1'
                else:
                    A[de[0]] = '0'

    for i in range(n):
        print(A[i + 1])

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import deque
n = int(input())
graph = [[] for _ in range(n+1)]
for _ in range(n-1):
    u,v,w = map(int,input().split())
    graph[u].append((v,w))
    graph[v].append((u,w))
q = deque([1])
ans = [0] * (n+1)
parent = [0]*(n+1)
while q:
    x = q.popleft()
    for y,w in graph[x]:
        if y == parent[x]:
            continue
        parent[y] = x
        ans[y] = ans[x]^(w&1)
        q.append(y)
for i in range(1,n+1):
    print(ans[i])

Submission status: Accepted

Solution code:
from collections import deque, defaultdict

def search(g, v):
  visited = [False] * len(g)
  visited[v] = True
  ans = [False] * len(g) 
  
  q = deque([v])
  ans[v] = False
  while q:
    s = q.popleft()
    for t,w in g[s]:
      if not visited[t]:
        q.append(t)
        ans[t] = ans[s]^(True if w%2==1 else False)
        visited[t] = True
  return ans

N = int(input())
g = {i:[] 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))
print("\n".join(["1" if i else "0" for i in search(g,0)]))

Submission status: Accepted

Solution code:
# coding: utf-8
import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N = ir()
graph = [[] for _ in range(N+1)] # 1-indexed
for _ in range(N-1):
    a, b, w = lr()
    graph[a].append((b, w%2))
    graph[b].append((a, w%2))

color = [None] * (N+1)
color[1] = 0
root = 1
parent = [0] * (N+1)
stack = [(root, 0)]
while stack:
    cur, c = stack.pop()
    for next, weight in graph[cur]:
        if next == parent[cur]:
            continue
        parent[next] = cur
        if weight == 0:
            color[next] = c
        else:
            color[next] = 1 - c
        stack.append((next, color[next]))

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

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

import heapq


def dijkstra_heap(s):
    # 始点sから各頂点への最短距離
    d = [float("inf")] * n
    used = [True] * n  # True:未確定
    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(readline())
edge = [[] for i in range(n)]
for i in range(n - 1):
    u, v, w = map(int, readline().split())
    if i == 0:
        s = [u, v]
    edge[u - 1].append([w, v - 1])
    edge[v - 1].append([w, u - 1])
d = dijkstra_heap(0)
for k in d:
    if k % 2 == 0:
        print('0')
    else:
        print('1')

Submission status: Accepted

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


N = int(input())
#頂点iのindexは[i-1]
tree = []
for i in range(N):
    tree.append([])

#Wが0なら偶数、1なら奇数
for i in range(N-1):
    u, v, w = map(int,input().split())
    tree[v-1].append([u-1,w % 2])
    tree[u-1].append([v-1,w % 2])
    
#print(tree)

    
color = []
for i in range(N):
    color.append(0)
    color[0] = 1
#白=-1、黒=1、無色=0

distance = 0

def poyo(x):
    global tree
    global color
    for i in tree[x]:#その頂点から行ける頂点を一覧
        if color[i[0]] == 0:#iもリスト([0]が行ける頂点、[1]が距離)
            if i[1] == 0:
                color[i[0]] = color[x]
            else:
                color[i[0]] = color[x] * (-1)
            
            poyo(i[0])


poyo(0)

for i in color:
    if i == -1:
        i = 0
        
    print(i)

Submission status: Accepted

Solution code:
from collections import deque
N=int(input())
tree=[[] for _ 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])
#print(tree)
dist=[-1]*N
v=0
d=deque()
d.append(v)
dist[0]=0
determined=[0]
while len(determined)<N:
    v=d.popleft()
    for i in tree[v]:
        if dist[i[0]]==-1:
            #print(dist[i[0]],dist[v],i[1])
            dist[i[0]]=dist[v]+i[1]
            d.append(i[0])
            determined.append(i[0])
    #print(dist,d,determined)
    #input()
for i in range(N):
    print(dist[i]%2)

Submission status: Accepted

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


def BFS():
    color=["white" for _ in range(n)]
    D=[0]*n
    M=[[] for _ in range(n)]

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

    D[0]=1
    color[0]="gray"
    queue=deque([0])

    while len(queue)>0:
        u=queue.popleft()
        for i,j in M[u]:
            if color[i]=="white":
                if j%2==0:D[i]=D[u]
                elif j%2==1:D[i]=-D[u]
                color[i]="gray"
                queue.append(i)
        color[u]="black"

    return D


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

Submission status: Accepted

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


def BFS():
    color=["white" for _ in range(n)]
    D=[0]*n
    M=[[] for _ in range(n)]

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

    D[0]=1
    color[0]="gray"
    queue=deque([0])

    while len(queue)>0:
        u=queue.popleft()
        for i,j in M[u]:
            if color[i]=="white":
                if j%2==0:D[i]=D[u]
                elif j%2==1:D[i]=-D[u]
                color[i]="gray"
                queue.append(i)
        color[u]="black"

    return D


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

Submission status: Accepted

Solution code:
n = int(input())
my_dict = dict()

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

    if v in my_dict:
        my_dict[v].append((u, w))
    else:
        my_dict[v] = [(u, w)]

visited = set()
white = set()
black = set()
candidate = [1]

white.add(1)

while candidate:
    item = candidate.pop()

    for val in my_dict[item]:
        if val[0] not in visited:
            if item in white:
                if val[1] % 2 == 0:
                    white.add(val[0])
                else:
                    black.add(val[0])
            else:
                if val[1] % 2 == 0:
                    black.add(val[0])
                else:
                    white.add(val[0])
        if val[0] not in visited:
            candidate.append(val[0])

    visited.add(item)

for i in range(n):
    if (i + 1) in white:
        print(0)
    else:
        print(1)

Submission status: Accepted

Solution code:
from collections import deque


def BFS():
    color=["white" for _ in range(n)]
    D=[0]*n
    M=[[] for _ in range(n)]

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

    D[0]=1
    color[0]="gray"
    queue=deque([0])

    while len(queue)>0:
        u=queue.popleft()
        for i,j in M[u]:
            if color[i]=="white":
                if j%2==0:D[i]=D[u]
                elif j%2==1:D[i]=-D[u]
                color[i]="gray"
                queue.append(i)
        color[u]="black"

    return D


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

Submission status: Accepted

Solution code:
import heapq
import sys

N = int(input())
a = [[] for i in range(N)]
for i in range(N - 1):
	u, v, w = map(int, input().split())
	a[u - 1].append([v - 1, w])
	a[v - 1].append([u - 1, w])
b = [[0, 0]]
c = [False] * N
d = [sys.maxsize] * N
d[0] = 0
while len(b):
	e = heapq.heappop(b)
	c[e[1]] = True
	for i in a[e[1]]:
		if c[i[0]]:
			continue
		if d[e[1]] + i[1] < d[i[0]]:
			d[i[0]] = d[e[1]] + i[1]
			heapq.heappush(b, [d[i[0]], i[0]])
for i in d:
	print(i % 2)

Submission status: Accepted

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

N = int(input())
uvw = []
for _ in range(N-1):
    uvw.append(tuple(map(int, input().split())))


H=[[] for _ in range(N+1)]
for el in uvw:
    H[el[0]].append((el[1], el[2]))
    H[el[1]].append((el[0], el[2]))
#print(H)

seen=[False]*(N+1)

distance=[0]*(N+1)
def dfs(n):
    seen[n]=True
    for nxt in H[n]:
        if seen[nxt[0]] == False:
            distance[nxt[0]]=distance[n]+nxt[1]
            dfs(nxt[0])

dfs(1)
#print(distance)
#print(seen)

for val in distance[1:]:
    if val % 2 == 0:
        print(0)
    else:
        print(1)

Submission status: Accepted

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

N = int(input())
uvw = []
for _ in range(N-1):
    uvw.append(tuple(map(int, input().split())))


H=[[] for _ in range(N+1)]
for el in uvw:
    H[el[0]].append((el[1], el[2]))
    H[el[1]].append((el[0], el[2]))
#print(H)

seen=[False]*(N+1)
color=[0]*(N+1)
def dfs(n):
    seen[n]=True
    for nxt in H[n]:
        if seen[nxt[0]] == False:
            if nxt[1] % 2 == 0:
                color[nxt[0]]=color[n]
            else:
                color[nxt[0]]=color[n] ^ 1
            dfs(nxt[0])

dfs(1)
#print(distance)
#print(seen)

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

Submission status: Accepted

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

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

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

color = [-1]*N
#print(edge)
def dfs(s,col):
  #print(s,col)
  for w,v in edge[s]:
    if color[v]==-1:
      color[v] = col^w
      dfs(v,color[v])
  return

color[0] = 0
dfs(0,0)
ans = color

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

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self,n):
        super().__init__()
        self.par = [-1]*n
        self.rank = [0]*n
        self.tsize = [1]*n
    
    def root(self,x):
        if self.par[x] == -1:
            return x 
        else:
            self.par[x] = self.root(self.par[x])
            return self.par[x]

    def unite(self, x, y):
        x_r = self.root(x)
        y_r = self.root(y)
        
        if self.rank[x_r]>self.rank[y_r]:
            self.par[y_r] = x_r

        elif self.rank[x_r]<self.rank[y_r]:
            self.par[x_r] = y_r

        elif x_r != y_r:
            self.par[y_r] = x_r
            self.rank[x_r] += 1

        if x_r != y_r:
            size = self.tsize[x_r]+self.tsize[y_r]
            self.tsize[x_r] = size
            self.tsize[y_r] = size

    def isSame(self,x,y):
        return self.root(x) == self.root(y)

    def size(self,x):
        return self.tsize[self.root(x)]

def main():

    n= int(input())
    uf = UnionFind(2*(n+1))
    
    for _ in range(n-1):
      x,y,w = tuple([int(t)for t in input().split()])
      if w%2==0:
        uf.unite(2*x,2*y)
        uf.unite(2*x+1,2*y+1)
      else:
        uf.unite(2*x+1,2*y)
        uf.unite(2*x,2*y+1)

    w = uf.root(2)

    for i in range(1,n+1):
      if w == uf.root(2*i):
        print(1)
      else:
        print(0)

if __name__ == "__main__":
    main()

Submission status: Accepted

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

N = int(input())
G = [[] for _ in range(N)]
for _ 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))

C = [-1] * N


def dfs(pos, color):
    C[pos] = color
    for e in G[pos]:
        if C[e[0]] != -1:
            continue
        # odd
        if e[1] & 1:
            c = 1 - color
            dfs(e[0], c)
        # even
        else:
            c = color
            dfs(e[0], c)


dfs(0, 0)
for c in C:
    print(c)

Submission status: Accepted

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

N = int(input())
G = [[] for _ in range(N)]
for _ 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))

C = [-1 for _ in range(N)]


def dfs(pos, color):
    C[pos] = color
    for e in G[pos]:
        if C[e[0]] != -1:
            continue
        # odd
        if e[1] & 1:
            c = 1 - color
            dfs(e[0], c)
        # even
        else:
            c = color
            dfs(e[0], c)


dfs(0, 0)
for i in range(N):
    print(C[i])

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(100000)

N = int(input())
G = [[] for _ in range(N)]
for _ 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))

C = [-1 for _ in range(N)]


def dfs(pos, color):
    C[pos] = color
    for e in G[pos]:
        if C[e[0]] != -1:
            continue
        # odd
        if e[1] & 1:
            c = 1 - color
            dfs(e[0], c)
        # even
        else:
            c = color
            dfs(e[0], c)


dfs(0, 0)
for i in range(N):
    print(C[i])

Submission status: Accepted

Solution code:
#グラフの連結成分を調べる
def Graph(ab):
    G=[[] for i in range(n)]
    #up_G=[0]*n#up_G[i]=頂点iの親
    for a,b,c in ab:
        G[a-1].append((b,c%2))
        G[b-1].append((a,c%2))
        #up_G[b-1]=a
    return G #,up_G
from collections import deque
def dfs(G,v,p):
    q=deque()
    q.append((v,p,0))
    ans=[0]*n
    while q:
        V,P,S=q.pop()
        if S==0:
            #下に遷移していくときの処理
            #q.append((V,1))
            for new_v,dis in G[V-1]:
                if new_v==P:continue
                ans[new_v-1]=(ans[V-1]+dis)%2
                q.append((new_v,V,0))
    return ans
n=int(input())
uvw=[list(map(int,input().split())) for i in range(n-1)]
G=Graph(uvw)
#print(G)
ans=dfs(G,1,-1)
print(*ans,sep='\n')

Submission status: Accepted

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

def dfs(s):
    stack = [(s, -1, 1)]
    while(len(stack)):
        v, p, c = stack[-1]
        stack.pop()
        color[v] = c
        for e in graph[v]:
            if e[0] == p: continue
            stack.append((e[0], v, abs(c - e[1] % 2)))


n = int(input())
color = [-1] * n
graph = [[] for _ in range(n)]

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

dfs(0)
for c in color: print(c)

Submission status: Accepted

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

def dfs(v, p, c):
    color[v] = c
    for e in graph[v]:
        if e[0] == p: continue
        if e[1] % 2: dfs(e[0], v, 1-c)
        else: dfs(e[0], v, c)


n = int(input())
color = [-1] * n
graph = [[] for _ in range(n)]

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

dfs(0, -1, 1)
for c in color: print(c)

Submission status: Accepted

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

def dfs(v, p, c):
    color[v] = c
    for e in graph[v]:
        if e[0] == p: continue
        if e[1] % 2: dfs(e[0], v, 1-c)
        else: dfs(e[0], v, c)


n = int(input())
color = [-1 for _ in range(n)]
graph = [[] for _ in range(n)]

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

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

Submission status: Accepted

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

def dfs(v, p, c):
    color[v] = c
    for e in graph[v]:
        if e[0] == p: continue
        if e[1] % 2: dfs(e[0], v, 1-c)
        else: dfs(e[0], v, c)


n = int(input())
color = [-1 for _ in range(n)]
graph = [[] for _ in range(n)]

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

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

Submission status: Accepted

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

color = []
graph = []

def dfs(v, p, c):
    color[v] = c
    for e in graph[v]:
        if e[0] == p: continue
        if e[1] % 2: dfs(e[0], v, 1-c)
        else: dfs(e[0], v, c)


def main():
    n = int(input())
    color.extend(-1 for _ in range(n))
    graph.extend([] for _ in range(n))
    for i in range(n-1):
        u, v, w = [int(x) for x in input().split()]
        u, v = u - 1, v - 1
        graph[u].append((v, w))
        graph[v].append((u, w))

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

if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

color = [-1]*N
color[0] = 0
stack = [0]

while stack:
    u = stack.pop()
    for v,w in A[u]:
        if color[v] != -1:
            continue
        color[v] = color[u]^(w&1)
        stack.append(v)

for c in color:
    print(c)

Submission status: Accepted

Solution code:
N=int(input())
import sys
sys.setrecursionlimit(10**6)
#頂点の色
colors=[0]*(N)
L=[[] for _ in range(N)]
for i in range(N-1):
  #u,vを長さwでつなぐ
  u,v,w=map(int, input().split())
  L[u-1].append((v-1,w,i))
  L[v-1].append((u-1,w,i))
  
def dfs(start_node, pre_node,is_even, ):
  for next_node,l,i in L[start_node]:
    if next_node==pre_node:
      continue
    if is_even:
      if l%2==0:
        colors[next_node]=0
        is_even_next=True
      else:
        colors[next_node]=1
        is_even_next=False
    else:
      if l%2==0:
        colors[next_node]=1
        is_even_next=False
      else:
        colors[next_node]=0
        is_even_next=True
    dfs(next_node, start_node, is_even_next)
    
dfs(0,-1,True)
for color in colors:
  print(color)