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

n = int(input())
g = tuple(set() for _ in range(n))
for _ 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))

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

q = deque()
q.append(0)

while q:
    v = q.popleft()
    for u, w in g[v]:
        if d[u] != -1:
            continue
        d[u] = (d[v] + w) % 2
        q.append(u)

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

Submission status: Accepted

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

ed = [[] for _ in range(n)]

for _ in range(n-1):
    u,v,w = map(int, input().split( ))
    ed[u-1].append([v-1,w])
    ed[v-1].append([u-1,w])#こっちも必要

c = [0]*n
done = [0]*n#無向だから
Q = deque()

Q.append(0)
while Q:
    u = Q.popleft()
    for e in ed[u]:
        if not done[e[0]]:
            c[e[0]] = (e[1]&1) ^ c[u]
            Q.append(e[0])
            done[e[0]] = 1

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

Submission status: Accepted

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

que = [ (0, 0, -1) ]
while que:
    v, d, p = que.pop()
    if d%2 == 0:
        ans[v] = 0
    else:
        ans[v] = 1
    for u,w in links[v]:
        if u==p:
            continue
        que.append( (u, d+w, v) )

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N = INT()
nodes = tuple([] for i in range(N))
for i in range(N-1):
    a, b, c = MAP()
    a -= 1
    b -= 1
    nodes[a].append((b, c))
    nodes[b].append((a, c))

ans = [0] * N
def rec(u, prev, prevc):
    # 親への辺のコストによって塗り分け
    if prev == -1:
        ans[u] = 0
    elif prevc % 2 == 0:
        ans[u] = ans[prev]
    else:
        ans[u] = 1 - ans[prev]
    for v, c in nodes[u]:
        if v != prev:
            rec(v, u, c)
rec(0, -1, 0)

[print(a) for a in ans]

Submission status: Accepted

Solution code:
N = int(input())

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

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

for i in d:
    print(i % 2)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from collections import deque
def solve():
  n = int(input())
  treenode = [[] for _ in range(n)]
  treecolor = [-2]*n
  for i in range(n-1):
    u,v,w = (int(i) for i in input().split())
    u -= 1
    v -= 1
    treenode[u].append((v,w%2))
    treenode[v].append((u,w%2))
  query = deque([(0,0,0)])
  while query:
    a,b,c = query.popleft()
    if b%2 == 0:
      treecolor[a] = c
      nextc = c
    else:
      treecolor[a] = 1^c
      nextc = 1^c
    for nextnode,weight in treenode[a]:
      if treecolor[nextnode] != -2:
        continue
      else:
        query.append((nextnode,weight,nextc))  
        treecolor[nextnode] = -1
  for i in treecolor:
    print(i)
solve()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(100100)

n = int(input())
route = [[] for i in range(n)]
for i in range(n-1):
	u, v, w = map(int,input().split())
	route[u-1].append((v-1,w))
	route[v-1].append((u-1,w))
	
ans=[-1]*n
def dfs(p,d):
	ans[p] = d
	for i,j in route[p]:
		if ans[i] < 0:
		    dfs(i, (d+j) % 2)
dfs(0,0)

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

Submission status: Accepted

Solution code:
N = int(input())

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

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

for i in d:
  print(i % 2)

Submission status: Accepted

Solution code:
N = int(input())

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

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

for i in d:
  print(i % 2)

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
input = lambda: sys.stdin.readline()[:-1]
sys.setrecursionlimit(10**8)


n = int(input())
uvw = [list(map(int, input().split())) for i in range(n-1)]
graph = [[] for i in range(n+1)]
color = [-1]*(n+1)
for u, v, w in uvw:
    graph[u].append((v, w))
    graph[v].append((u, w))

color[1] = 1
ne = [1]
while ne:
    t = ne.pop()
    for v, w in graph[t]:
        if color[v] == -1:
            ne.append(v)
            color[v] = color[t] if w % 2 == 0 else (color[t]+1) % 2

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

Submission status: Accepted

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

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

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

deq = deque()
deq.append(1)
res = [-1]*(N+1)
res[1] = 0

while deq:
  x = deq.popleft()
  for e, w in G[x]:
    if res[e] == -1:
      res[e] = (res[x]+w)%2
      deq.append(e)
[print(r) for r in res[1:]]

Submission status: Accepted

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

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

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

res = [0]*(N+1)
# 現在頂点v を c に塗る。p は v の親
def dfs(v, p, c):
  res[v] = c
  for e, w in G[v]:   
    if e == p:
      continue    
    if w&1:
      # エッジの重みが奇数だったら、次のノードは異色 1-c で塗る
      dfs(e, v, 1-c)
    else:
      #エッジの重みが偶数だったら、次のノードも同色 c で塗る
      dfs(e, v, c)
# res:start[1:] even:cor==0   
dfs(1, 0, 0)      
[print(r) for r in res[1:]]

Submission status: Accepted

Solution code:
import collections

n=int(input())
g=[[] for _ in range(n+1)] 
for _ in range(n-1):
  a,b,w=map(int,input().split())
  g[a].append((b,w))
  g[b].append((a,w))
q=collections.deque()
q.append(1)
checked=[0]*(n+1)
ans=[0]*(n+1)
ans[1]=0
while len(q)!=0:
  v=q.popleft()
  checked[v]=1
  for u,w in g[v]:
    if checked[u]==0:
      if w%2==0:
        ans[u]=ans[v]
      else:
        ans[u]=ans[v]^1
      q.append(u)
for i in range(1,n+1):
  print(ans[i])

Submission status: Accepted

Solution code:
# 2019/10/10
# 解答かんにんぐ
# 前回WAの原因は、u,vのいずれかが訪問済みである必要があった。
# edge参照順序によっては、u,vのいずれも未訪問となり、このときWAとなる。

import sys
sys.setrecursionlimit(10**7)

n=int(input())
node=[None]*n
edge=[[] for _ in range(n)]


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


def dfs(v,p,c):
    node[v]=c
    for vv,w in edge[v]:
        if vv==p:continue
        dfs(vv,v,1-c) if w%2 else dfs(vv,v,c)


dfs(0,-1,0)

for e in node:
    print(e)

Submission status: Accepted

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

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

color = [-1] * N

def dfs(v=0, pv=-1, d=0):
    color[v] = d % 2
    for nv, nw in ad[v]:
        if nv == pv:
            continue
        nd = d + nw
        dfs(nv, v, nd)
        
dfs()
for c in color:
    print(c)

Submission status: Accepted

Solution code:
def is_bipartite(graph, start, n):
    stack = [start]
    visited = [-1] * (n+1)
    visited[start] = 0
    while stack:
        u = stack.pop()
        for v,w in graph[u].items():
            if visited[v] != -1:
                continue
            visited[v] = (visited[u] ^ 1) if w % 2 else visited[u]
            stack.append(v)
    return visited

n = int(input())
graph = {}

for i in range(n-1):
    u,v,w = map(int , input().split())
    if u not in graph:
        graph[u] = {}
    if v not in graph:
        graph[v] = {}
    graph[u][v] = w
    graph[v][u] = w

[print(color) for color in is_bipartite(graph, 1, n) if color > -1]

Submission status: Accepted

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

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

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

colors = [None] * N

def set_color(x, c):
    colors[x] = c
    for y, sgn in edges[x]:
        if colors[y] == None:
            set_color(y, c*sgn)

set_color(0, 1)
for z in colors:
    print((z+1)//2)

Submission status: Accepted

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

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

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

colors = [None] * N
def set_color(x, c):
    colors[x] = c
    for y, sgn in edges[x]:
        if colors[y] == None:
            set_color(y, c*sgn)
set_color(0, 1)
for z in colors:
    print((z+1)//2)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)
n=int(input())
edge=[[]for i in range(n+1)]
for i in range(n-1):
    a,b,c=map(int,input().split())
    if c%2==0:
        edge[a].append((b,1))
        edge[b].append((a,1))
    else:
        edge[a].append((b,-1))
        edge[b].append((a,-1))
        

ans=[None]*(n+1)


def set_color(x,col):
    ans[x]=col
    for i,j in edge[x]:
        if ans[i] is None:
            set_color(i,j*col)
    
    
set_color(1,1)
            
for i in ans[1:]:
    print((i+1)//2)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)


def dfs(v):
    for u, w in e[v]:
        if c[u] != -1:
            continue
        c[u] = (c[v] + w) % 2
        dfs(u)


n = int(input())
e = tuple(set() for _ in range(n))
for _ in range(n - 1):
    u, v, w = map(int, input().split())
    u -= 1
    v -= 1
    e[u].add((v, w))
    e[v].add((u, w))

c = [-1] * n
c[0] = 0

dfs(0)

print(*c, sep='\n')

Submission status: Accepted

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

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

g = [[] for _ in range(n)]

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


WHITE = 0
GRAY = 1
BLACK = 2

ds = [0] * n
colors = [WHITE] * n


def dfs(u):
    if colors[u] == BLACK:
        return

    colors[u] = GRAY

    for v, w in g[u]:
        if colors[v] == WHITE:
            ds[v] = ds[u] + w
            dfs(v)

    colors[u] = BLACK


dfs(0)

for d in ds:
    print(d % 2)

Submission status: Accepted

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

g = [[] for _ in range(n)]

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


WHITE = 0
GRAY = 1
BLACK = 2

ds = [0] * n
colors = [WHITE] * n
ps = [-1] * n


def dfs(s):
    stack = []

    ds[s] = 0
    colors[s] = BLACK
    ps[s] = -1
    stack.append(ds[s])

    while stack:
        u = stack[-1]
        colors[u] = GRAY

        for v, w in g[u]:
            if colors[v] == WHITE:
                stack.append(v)
                ds[v] = ds[u] + w
                ps[v] = u
                g[u].remove([v, w])
                g[v].remove([u, w])
                break

        else:
            stack.pop()
            colors[u] = BLACK

    return ds, ps


dfs(0)

for d in ds:
    print(d % 2)

Submission status: Accepted

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

g = [[] for _ in range(n)]

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


WHITE = 0
GRAY = 1
BLACK = 2

ds = [0] * n
colors = [WHITE] * n
ps = [-1] * n


def dfs(s):
    global ds, colors, ps

    stack = []

    ds[s] = 0
    colors[s] = BLACK
    ps[s] = -1
    stack.append(ds[s])

    while stack:
        u = stack[-1]
        colors[u] = GRAY

        for v, w in g[u]:
            if colors[v] == WHITE:
                stack.append(v)
                ds[v] = ds[u] + w
                ps[v] = u
                g[u].remove([v, w])
                g[v].remove([u, w])
                break

        else:
            stack.pop()
            colors[u] = BLACK

    return ds, ps


dfs(0)

for d in ds:
    print(d % 2)

Submission status: Accepted

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

def solve(M: list, d: list, visited: list, u: int = 0):
    global N
    visited[u] = True
    for m in M[u]:
        i = m[0]
        w = m[1]
        if not visited[i]:
            d[i] = d[u] + w
            solve(M, d, visited, i)


def main():
    global N
    N = int(input())
    M = [[] for _ in range(N)]
    for _ in range(N-1):
        u, v, w = map(int, input().split())
        M[u-1].append((v-1, w))
        M[v-1].append((u-1, w))
    visited = [False] * N
    d = [0] * N
    solve(M, d, visited)
    for i in d:
        if i%2 == 0:
            print(0)
        else:
            print(1)

if __name__ == '__main__': main()

Submission status: Accepted

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

n=int(input())
edge=[[]for i in range(n+1)]

for i in range(n-1):
    u,v,w=map(int,input().split())
    if w%2==0:
        edge[u].append((v,1))
        edge[v].append((u,1))
    else:
        edge[u].append((v,-1))
        edge[v].append((u,-1))
        
color=[None]*(n+1)

def set_color(x,col):
    color[x]=col
    
    for i,j in edge[x]:
        if color[i] is None:
            set_color(i,j*col)

set_color(1,1)
for i in color[1:]:
    print((i+1)//2)

Submission status: Accepted

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

n=int(input())
edge=[[]for i in range(n+1)]

for i in range(n-1):
    u,v,w=map(int,input().split())
    if w%2==0:
        edge[u].append((v,1))
        edge[v].append((u,1))
    else:
        edge[u].append((v,-1))
        edge[v].append((u,-1))
        
color=[None]*(n+1)

def set_color(x,col):
    color[x]=col
    
    for i,j in edge[x]:
        if color[i] is None:
            set_color(i,j*col)

set_color(1,1)
for i in color[1:]:
    print((i+1)//2)

Submission status: Accepted

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

n=int(input())

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

for i in range(n-1):
    v1,v2,w=map(int,input().split())
    if w%2!=0:
        edge[v1].append((v2,-1))
        edge[v2].append((v1,-1))
    else:
        edge[v1].append((v2,1))
        edge[v2].append((v1,1))

color=[None]*(n+1)        
def set_color(x,col):
    color[x]=col
    
    for i,j in edge[x]:
        if color[i] is None:
            set_color(i,j*col)
set_color(1,1)

for x in color[1:]:
    print((x+1)//2)

Submission status: Accepted

Solution code:
import heapq
import sys

input = sys.stdin.readline

def dijkstra_heap(s,edge,N):
    d = [float('inf')] * N
    used = [True] * N
    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

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

    for i 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_heap(0,edge,N)
    first = D[0]
    for d in D:
        if abs(d - first) % 2 == 0:
            print(0)
        else:
            print(1)

main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)
N=int(input())
L=[[] for _ in range(N)]
for i in range(N-1):
  u,v,w=map(int,input().split())
  w=w%2
  L[u-1].append([v,w])
  L[v-1].append([u,w])
  

col=[-1]*N
def dfs(p):
  for i in L[p-1]:
    if col[i[0]-1]!=-1:
      pass
    else:
      col[i[0]-1]=abs(i[1]-col[p-1])
      dfs(i[0])

col[0]=0
dfs(1)

for i in col:
  print(i)

Submission status: Accepted

Solution code:
import math
import collections
import itertools
import sys
import bisect
from heapq import heappop,heappush,heapify
sys.setrecursionlimit(10**6)
def MAP(): return list(map(int,input().split()))
def INT(): return int(input())
def FLOAT(): return float(input())
MOD = 10**9+7


N = INT()
G = [dict() for _ in range(N)]
for i in range(N-1):
    u,v,w=map(int,input().split())
    G[u-1][v-1]=w
    G[v-1][u-1]=w
color=[-1 for _ in range(N)]
dist=[-1 for _ in range(N)]
dist[0]=0
q=[0]
while q:
    r=q.pop()
    for p in G[r]:
        if dist[p]!=-1:
            continue
        dist[p]=dist[r]+G[r][p]
        q.append(p)
for i in range(N):
    color[i]=dist[i]%2
for ans in color:
    print(ans)

Submission status: Accepted

Solution code:
#https://oneminutepython.com/atcoder/abc126_d.html

from collections import deque
N = int(input())
S = [[] for _ in range(N)]  #indexとu（繋がってる点）とwを格納する
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) #それ（繋がってる点）をqueueに追加
            Node[u] = Node[p]^(w%2==1)  #黒白の判定

#普通にfor i in range(N)でも可能

for i in range(N):
    print([0,1][Node[i]])   #これで片方のみ出力できるらしい

Submission status: Accepted

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

global color 
global adlist
color = [0 for _ in range(100001)] 

def make_adlist(N, uvw):
  global adlist
  adlist = [[] for _ in range(N)]
  for u, v, w in uvw:
    adlist[u-1] += [[v-1, w%2]]
    adlist[v-1] += [[u-1, w%2]]
  return adlist 

def dfs(v, c):
  global color
  global adlist
  color[v] = c
  for next_v, w in adlist[v]:
    if color[next_v] != 0:
      continue
    if color[next_v] == 0 and w % 2 != 0:
      dfs(next_v, -c)
    elif color[next_v] == 0 and w % 2 == 0:
      dfs(next_v, c)

  return 


def main():
  N = int(input())
  uvw = [list(map(int, input().split())) for _ in range(N-1)]
  adlist = make_adlist(N, uvw)
  dfs(0, 1)
  for c in color[:N]:
    if c == 1:
      print(1)
    else:
      print(0)


if __name__ == "__main__":
  main()

Submission status: Accepted

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

def main():
    def dfs(i=0,oi=-1):
        for ki,w in to[i]:
            if ki==oi:continue
            ans[ki]=(ans[i]+w)%2
            dfs(ki,i)

    n=int(input())
    to=defaultdict(list)
    for _ in range(n-1):
        u,v,w=map(int,input().split())
        u,v=u-1,v-1
        to[u].append([v,w])
        to[v].append([u, w])
    ans=[-1]*n
    ans[0]=0
    dfs()
    for x in ans:
        print(x)
main()

Submission status: Accepted

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

n = int(input())
edges = [[int(i) for i in input().split()] for _ in range(n - 1)]

BLACK = 1
WHITE = 0
UNKNOWN = -1

import sys
if n == 1:
    print(BLACK)
    sys.exit(0)

colors = [UNKNOWN] * (n + 1)

graph = [[] for _ in range(n + 1)]
for e in edges:
    graph[e[0]].append((e[1], e[2]))
    graph[e[1]].append((e[0], e[2]))

def dfs(graph, colors, current_point, current_color):
    colors[current_point] = current_color

    for next_point_info in graph[current_point]:
        if colors[next_point_info[0]] != UNKNOWN:
            continue
        if (next_point_info[1] % 2 == 0):
            next_color = current_color
        else:
            next_color = 1 - current_color
        dfs(graph, colors, next_point_info[0], next_color)

dfs(graph, colors, 1, BLACK)
for c in colors[1:]:
    print(c)

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict, deque

def dfs():
  queue = deque()
  queue.append([0,0])
  done = set([0])
  ans =[0] + [-1]*(N-1)
  while len(queue) != 0:
    prv_node, prv_edge = queue.pop()
    for node, edge in graph[prv_node]:
      if node in done: continue
      if (prv_edge + edge)%2==0:ans[node] = '0'
      else:ans[node] = '1'
      
      queue.append([node, prv_edge+edge])
      done.add(node)
  [print(a) for a in ans]
    
input = sys.stdin.readline

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

dfs()

Submission status: Accepted

Solution code:
n = int(input())
Edges = [list(map(int,input().split())) for i in range(n-1)]
for edge in Edges:
    edge[0] -= 1
    edge[1] -= 1
    edge[2] %= 2

Graph = [[] for i in range(n)]
for edge in Edges:
    Graph[edge[0]].append([edge[1],edge[2]])
    Graph[edge[1]].append([edge[0],edge[2]])

Color = [-1 for i in range(n)]
Color[0] = 0

stack = [0]

while stack:
    node = stack.pop()
    for adj in Graph[node]:
        if Color[adj[0]] == -1:
            if adj[1] == 0:
                Color[adj[0]] = Color[node]
            elif Color[node] == 0:
                Color[adj[0]] = 1
            else:
                Color[adj[0]] = 0
            stack.append(adj[0])

for color in Color:
    print(color)

Submission status: Accepted

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

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

rem = {}

for i in range(n):
  rem[i] = 1
  
ans = [0 for _ in range(n)]

def check(p, tmp):
  rem.pop(p)
  for n, w in d[p]:
    if n in rem:
      ntmp = (tmp + w) % 2
      ans[n] = ntmp
      check(n, ntmp)
      
check(0, 0)

for res in ans:
  print(res)

Submission status: Accepted

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

for i in range(N-1):
    VW[i][0] -= 1
    VW[i][1] -= 1

edges = [list() for _ in range(N)]
for i in range(N-1):
    edges[VW[i][0]].append((VW[i][1],VW[i][2]))
    edges[VW[i][1]].append((VW[i][0],VW[i][2]))

D = [-1 for _ in range(N)]
D[VW[0][0]] = 0
stack = [VW[0][0]]

while stack:
    s = stack.pop(-1)
    for (i,c) in edges[s]:
        if D[i] == -1:
            D[i] = D[s] +c
            stack.append(i)

for e in D:
    if e % 2:
        print(0)
    else:
        print(1)

Submission status: Accepted

Solution code:
from collections import deque
N = int(input())
A = [list(map(int, input().split())) for _ in range(N-1)]

T = [[] for _ in range(N)]
for i in range(N-1):
    u, v = A[i][0] - 1, A[i][1] - 1
    d = A[i][2] % 2 
    T[u].append([v, d])
    T[v].append([u, d])

visited = [True] + [False] * (N-1)
ans = [0] * N
que = deque([0]) 
while len(que) > 0:
    q = que.popleft()
    for v, d in T[q]:
        if visited[v]:
            pass
        else:
            que.append(v)
            visited[v] = True
            ans[v] = (ans[q] + d) % 2
            
for a in ans:
    print(a)

Submission status: Accepted

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


def dfs(v, c, C, visited, G):
    visited[v] = True
    C[v] = c

    for nv, w in G[v]:
        if visited[nv]:
            continue
        dfs(nv, c^w, C, visited, G)


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

    C = [0]*N
    visited = [False]*N
    dfs(0, 0, C, visited, G)
    for c in C:
        print(c)
    
        


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:

n = int(input())
nodes = [[] for _ in range(n)]
length = [-1]*n
for _ in range(n-1):
    ui, vi, wi = list(map(int, input().split()))
    nodes[ui-1].append((vi-1, wi%2))
    nodes[vi-1].append((ui-1, wi%2))

stack = []
stack.append(nodes[0][0])
while stack:
    current = stack.pop(-1)
    if length[current[0]] != -1:
        continue
    length[current[0]] = current[1]
    for nextnode in nodes[current[0]]:
        if length[nextnode[0]] != -1:
            continue
        stack.append([nextnode[0],(current[1]+nextnode[1])%2])
for i in length:
    print(i)

Submission status: Accepted

Solution code:
from collections import defaultdict
import queue

def getlist():
	return list(map(int, input().split()))

class Graph(object):
    def __init__(self):
        self.graph = defaultdict(list)

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

    def add_edge(self, a, b, w):
        self.graph[a].append([b, w])

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

class BFS(object):
    def __init__(self, graph, N):
        self.g = graph.graph
        self.dist = [0] * (N + 1)
        self.visit = [0] * (N + 1)
        self.Q = queue.Queue()
        self.Q.put(1)

        while not self.Q.empty():
            v = self.Q.get()
            for i, w in self.g[v]:
            	if self.visit[i] == 0:
            		self.dist[i] = self.dist[v] + w
            		self.Q.put(i)
            		self.visit[i] = 1

    def weight(self):
        return self.dist

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

XX = BFS(G, N)
ans = XX.weight()
for i in range(1, N + 1):
	if ans[i] % 2 == 0:
		print(0)
	else:
		print(1)

Submission status: Accepted

Solution code:
def solve():
	from collections import deque
	n,*l=map(int,open(0).read().split())
	con=[[] for _ in range(n)]
	dist=[-1]*n
	dist[0]=0
	for a,b,c in zip(*[iter(l)]*3):
		con[a-1].append((b-1,c%2))
		con[b-1].append((a-1,c%2))
 
	stk=deque([0])
	while stk:
		cur=stk.pop()
		for nxt,d in con[cur]:
			if dist[nxt]<0:
				stk.append(nxt)
				dist[nxt]=(dist[cur]+d)%2

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

if __name__=="__main__":
	solve()

Submission status: Accepted

Solution code:
def solve():
	from collections import deque
	n,*l=map(int,open(0).read().split())
	con=[[] for _ in range(n)]
	dist=[None]*n
	dist[0]=0
	for a,b,c in zip(*[iter(l)]*3):
		con[a-1]+=[(b-1,c%2)]
		con[b-1]+=[(a-1,c%2)]
 
	stk=deque([0])
	while stk:
		cur=stk.pop()
		for nxt,d in con[cur]:
			if dist[nxt]==None:
				stk.append(nxt)
				dist[nxt]=(dist[cur]+d)%2

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

if __name__=="__main__":
	solve()

Submission status: Accepted

Solution code:
def solve():
	n,*l=map(int,open(0).read().split())
	con=[[] for _ in range(n)]
	dist=[None]*n
	dist[0]=0
	for a,b,c in zip(*[iter(l)]*3):
		con[a-1].append((b-1,c%2))
		con[b-1].append((a-1,c%2))
 
	stk=[0]
	while stk:
		cur=stk.pop()
		for nxt,d in con[cur]:
			if dist[nxt]==None:
				stk.append(nxt)
				dist[nxt]=(dist[cur]+d)%2

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

if __name__=="__main__":
	solve()

Submission status: Accepted

Solution code:
def solve():
	from collections import deque
	n,*l=map(int,open(0).read().split())
	con=[[] for _ in range(n)]
	dist=[None]*n
	dist[0]=0
	for a,b,c in zip(*[iter(l)]*3):
		con[a-1].append((b-1,c%2))
		con[b-1].append((a-1,c%2))
 
	stk=deque([0])
	while stk:
		cur=stk.pop()
		for nxt,d in con[cur]:
			if dist[nxt]==None:
				stk.append(nxt)
				dist[nxt]=(dist[cur]+d)%2

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

if __name__=="__main__":
	solve()

Submission status: Accepted

Solution code:
def solve():
	from collections import deque
	n,*l=map(int,open(0).read().split())
	con=[[] for _ in range(n)]
	dist=[None]*n
	dist[0]=0
	for a,b,c in zip(*[iter(l)]*3):
		con[a-1].append((b-1,c%2))
		con[b-1].append((a-1,c%2))
 
	que=deque([0])
	while que:
		cur=que.popleft()
		for nxt,d in con[cur]:
			if dist[nxt]==None:
				que.append(nxt)
				dist[nxt]=(dist[cur]+d)%2

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

if __name__=="__main__":
	solve()

Submission status: Accepted

Solution code:
from collections import deque
n,*l=map(int,open(0).read().split())
con=[[] for _ in range(n)]
dist=[None]*n
dist[0]=0
for a,b,c in zip(*[iter(l)]*3):
	con[a-1].append((b-1,c%2))
	con[b-1].append((a-1,c%2))

que=deque([0])
while que:
	cur=que.popleft()
	for nxt,d in con[cur]:
		if dist[nxt]==None:
			que.append(nxt)
			dist[nxt]=dist[cur]^d

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