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
from collections import deque
input = sys.stdin.readline

class Node:
    def __init__(self):
        self.color = 0
        self.check = False
        self.link = []

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

    nodes = [Node() for i in range(N)]
    
    for i in range(N-1):
        u, v, w = map(int, input().split())
        nodes[u-1].link.append((nodes[v-1], w&1))
        nodes[v-1].link.append((nodes[u-1], w&1))
    
    q = deque()
    q.append((nodes[0], 1))
    while len(q) > 0:
        node, color = q.popleft()
        node.color = color
        node.check = True
        for nex, weight in node.link:
            if not nex.check:
                if weight == 0:
                    q.append((nex, color))
                else:
                    q.append((nex, -color))
    
    for i in range(N):
        print((nodes[i].color + 1) // 2)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import deque
n = int(input())
l = [[] for i in range(n)]
for i in range(n-1):
    u,v,w = map(int,input().split())
    l[u-1].append([v-1,w])
    l[v-1].append([u-1,w])
l2 = [0 for i in range(n)]
ans = [0 for i in range(n)]
q = deque()
q.append([0,0])
while q:
    x,y = q.popleft()
    if l2[x] == 0:
        l2[x] = 1
        ans[x] = y
        for i,j in l[x]:
            if l2[i] == 0:
                q.append([i,y+j])
for i in range(n):
    print(ans[i]%2)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)
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=[None for i in range(n)]
def k(v,dis):
    b[v]=dis
    for next_v,w in a[v]:
        if b[next_v]!=None:
            continue
        if w%2==0:
            k(next_v,dis)
        else:
            k(next_v,1-dis)
k(0,0)
for i in range(n):
    print(b[i])

Submission status: Accepted

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

import sys
sys.setrecursionlimit(10**7)

def main(N,G):
    global ans
    ans = [-1]*N
    dfs(0,0)
    for i in ans:
        print(i)

def dfs(v,now):
    ans[v] = now
    for next_v, w in G[v]:
        if(ans[next_v]!=-1):
            continue
        if w:
            dfs(next_v,1-now)
        else:
            dfs(next_v,now) 
            
if __name__ == '__main__':
    N = int(input())
    G = [[]for i in range(N)]
    for i in range(N-1):
        u, v, w = map(int, input().split())
        u -= 1
        v -= 1
        G[u].append((v,w%2))
        G[v].append((u,w%2))
    main(N,G)

Submission status: Accepted

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

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

ans = [-1]*n

def dfs(v, now):
    ans[v] = now

    for next_v ,w in link[v]:
        if ans[next_v] != -1:
            continue
        if w % 2:
            dfs(next_v, 1-now)
        else:
            dfs(next_v, now)

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

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])
dist = [0]*(n +1)
visited = [0]*(n + 1)
que = deque([[1,0]])
while que:
    node,weight = que.popleft()
    if visited[node] == 1:
        continue
    else:
        visited[node] = 1
        dist[node] = weight
        for x,y in graph[node]:
            if visited[x] ==1:
                continue
            else:
                que.append([x,weight+y])
for i in range(1,n+1):
    print(dist[i]%2)

Submission status: Accepted

Solution code:
import collections
def main():
    N = int(input())
    edges = collections.defaultdict(dict)
    for _ in range(N-1):
        u, v, w = map(int, input().split())
        edges[u][v] = w
        edges[v][u] = w
    color = dict()
    color[1] = '0'
    cur = [[1, 0]]
    while cur:
        temp = []
        for i, d in cur:
            for j in edges[i]:
                if j not in color:
                    color[j] = str((d + edges[i][j]) % 2)
                    temp.append([j, d + edges[i][j]])
        cur = temp
    for i in range(1, N+1):
        print(color[i])

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
n = int(input())
lst = [list(map(int,input().split())) for _ in range(n-1)]
c = [[] for _ in range(n+1)]
for i in lst:
  c[i[0]].append([i[1],i[2]])
  c[i[1]].append([i[0],i[2]])
ans = [0]*(n+1)
pool = [1]
done = set()
done.add(1)
while pool:
  start = pool.pop()
  for l in c[start]:
    if l[0] not in done:
      ans[l[0]] = ans[start] + l[1]
      done.add(l[0])
      pool.append(l[0])
for i in ans[1:]:
  print(int(i%2))

Submission status: Accepted

Solution code:
import copy
import sys

sys.setrecursionlimit(10 ** 7)

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

# 適当に最初の色を決める
# その点を親として、
# 親からの距離が偶数だったら親と同じ色
# 親からの距離が奇数だったら親と違う色

children = [[] for _ in range(N + 1)]

for e in uvw:
    children[e[0]].append([e[1], e[2]])
    children[e[1]].append([e[0], e[2]])

pool = [1]
result = [0 for i in range(N + 1)]  # 頂点1は白くする

marked = set()
marked.add(1)

while pool:
    top = pool.pop()
    for child in children[top]:
        child_edge = child[0]
        length = child[1]

        if child_edge not in marked:
            pool.append(child_edge)
            marked.add(child_edge)
        if length % 2 == 0:
            result[child_edge] = 0 if result[top] == 0 else 1
        else:
            result[child_edge] = 1 if result[top] == 0 else 0

for i in result[1:]:
    print(i)

Submission status: Accepted

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

sys.setrecursionlimit(1000000)

def main(): 

    N=int(input())
    to=[[] for _ in range(N+1)]
    ans=[0]*(N+1)

    for i in range(N-1):
        u,v,w=map(int,input().split())
        to[u].append([v,w])
        to[v].append([u,w])
    
    def dfs(chil, par):
        for v,l in to[chil]:
            if v == par: continue
            if (ans[chil] == 1 and l%2==0) or (ans[chil] == 0 and l%2==1):
                ans[v]=1
            dfs(v,chil)
    
    #ans[1] = 1
    dfs(1,-1)
    for i in ans[1:]:
        print(i)
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def main():
    import sys
    from collections import defaultdict,deque
    input = sys.stdin.readline
    N = int(input())
    Tree = defaultdict(list)
    for _ in range(N-1):
        u,v,w = map(int, input().split())
        Tree[u].append([v,w])
        Tree[v].append([u,w])
        
    visited = {}
    answer = [0]*N
    que = deque()
    que.append([1,0])
    while que != deque():
        tmp = que.pop()
        visited[tmp[0]] = 1
        for i in Tree[tmp[0]]:
            if not i[0] in visited:
                if (tmp[1] + i[1])%2 == 1:
                    answer[i[0]-1] = 1
                que.append([i[0],tmp[1] + i[1]])
    print(*answer,sep="\n")
    
main()

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)


def dfs(v, p, c):
    colors[v] = c
    for next_v, d in g[v]:
        if next_v == p:
            continue
        if d % 2 == 0:
            dfs(next_v, v, c)
        else:
            dfs(next_v, v, 1 - c)


N = int(input())

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

dfs(0, -1, 0)
print(*colors, sep='\n')

Submission status: Accepted

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

N = int(input())
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))

#print(edge)

def dfs(u,v):
  for e,w in edge[u]:
    if e != v:
      ans[e] = (w + ans[u]) % 2
      # print(ans)
      dfs(e,u)

ans = [0] + [-1] * (N-1)
dfs(0,-1)
print(*ans)

Submission status: Accepted

Solution code:
from collections import deque
from collections import defaultdict
def main():
    n = int(input())
    # 隣接リスト 距離
    dc = defaultdict(list)
    for _ in range(n-1):
        a,b,c = map(int,input().split())
        dc[a].append([b,c])
        dc[b].append([a,c])


    que = deque([1])
    # 調べたか判定
    visited = [0]*(n+1)
    visited[0] = 1
    visited[1] = 1

    ans = [1]*(n+1)
    while len(que)>0:
        now = que.popleft()
        for ls in dc[now]:
            next_,_ = ls
            if visited[ls[0]]==0:
                if ls[1]%2==0:
                    ans[next_] = ans[now]
                else:
                    ans[next_] = -ans[now]
                
                visited[ls[0]]=1
                que.append(ls[0])
            else:
                pass
        
                    
    for i in range(1,n+1):
        if ans[i]==1:
            print(1)
        else:
            print(0)
if __name__ == "__main__":
    main()

Submission status: Accepted

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

def survey(now, mlist, clist):
    for ml in mlist[now]:
        if clist[ml[0]]==2:
            clist[ml[0]]=(clist[now]+ml[1])%2
            _, _=survey(ml[0], mlist, clist)
    return mlist, clist

n=int(input())
mlist=[]
clist=[]
for i in range(n):
    mlist.append([])
    clist.append(2)

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

clist[0]=0
now=0
mlist, clist = survey(now, mlist, clist)
for cl in clist:
    print(cl)

Submission status: Accepted

Solution code:
n = int(input())
data = [[] for _ in range(n)]
for _ in range(n-1):
    a,b,c = map(int,input().split())
    data[a-1].append([b-1,c % 2])
    data[b-1].append([a-1,c % 2])

que = []
color = [-1 for _ in range(n)]
def dfs(a,data):
    # pop last index
    #a : current state
    if color[a] == -1:
        color[a] = 0
        que.append(a)
    else:
        return 0
    while len(que):
        a = que.pop()
        for i in data[a]:
            #i[0] is edge
            #i[1] is cost
            if color[i[0]] != -1:continue
        
            if i[1] == 0:
                color[i[0]] = color[a]
            else:
                color[i[0]] = 1 - color[a]  
            que.append(i[0])

for i in range(n):
    dfs(i,data)
for i in range(n):
    print(color[i])

Submission status: Accepted

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

res = [0] * (N + 1)
visited = [0] * (N + 1)
Q = dq([])
Q.append((1, 0))
visited[1] = 1
while len(Q):
  q = Q.pop()
  for n in e[q[0]]:
    if visited[n[0]] == 1:
      continue
    if n[1] % 2 == 0:
      res[n[0]] = res[q[0]]
    else:
      res[n[0]] = (res[q[0]] + 1) % 2
    Q.append(n)
    visited[n[0]] = 1
  #print(res, q)
for i in range(1, N + 1):
  print(res[i])

Submission status: Accepted

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

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

ans = [-1] * (N)
ans[0] = 0
q = deque([])
q.append(0)

while len(q) > 0:
  u = q.pop()
  for v, w in D[u]:
    if ans[v] != -1:
      continue
    else:
      ans[v] = (ans[u] + w) % 2
    q.append(v)

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

Submission status: Accepted

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

N=int(input())

G = [[] for j in range(N)]

color = [0]*N

for _ in range(N-1):
    e,f,g = list(map(int, input().split()))
    heapq.heappush(G[e-1], [f-1,g%2])
    heapq.heappush(G[f-1], [e-1,g%2])

def dfs(v,p,c):
    color[v]=c
    for k in range(len(G[v])):
        i,j = heapq.heappop(G[v])
        if i==p:
            continue
        elif j ==0 :
            dfs(i,v,c)
        elif j ==1 :
            dfs(i,v,1-c)
        
dfs(0,-1,0)

for k in color:
    print(k)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**9)
 
def dfs(now, prev):
    # 今いる頂点から行ける頂点を順に next に入れてループ
    for next, w in g[now]:
        if ans[next] == -1:
            ans[next]=0
            if  w % 2 != 0:
                if ans[now]==0:
                    ans[next]=1
                    dfs(next,now)
                else:
                    ans[next]=0
                    dfs(next,now)
            else:
                ans[next]=ans[now]
                dfs(next,now)
    
 
#木構造の取り込み 
n=int(input())
g = [[] for i in range(n)]
for i in range(n-1):
    u, v , w= map(int, input().split())
    u -= 1
    v -= 1
    g[u].append([v,w])
    g[v].append([u,w])

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

Submission status: Accepted

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

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

def dfs(v, cur):
  color[v] = cur
  for next_v, w in G[v]:
    if color[next_v] != -1:
      continue
    if w % 2 == 0:
      dfs(next_v, cur)
    else:
      dfs(next_v, 1 - cur)
      
dfs(0, 0)
for i in range(N):
  print(color[i])

Submission status: Accepted

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

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

def dfs(v, cur):
  color[v] = cur
  for next_v, w in zip(G[v], W[v]):
    if color[next_v] != -1:
      continue
    if w % 2 == 0:
      dfs(next_v, cur)
    else:
      dfs(next_v, 1 - cur)
      
for i in range(N):
  if color[i] != -1:
    continue
  dfs(i, 0)
for i in range(N):
  print(color[i])

Submission status: Accepted

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

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

neighbor = [[] for _ in range(n+1)]
for edge in lst:
    neighbor[edge[0]].append((edge[1], edge[2]))
    neighbor[edge[1]].append((edge[0], edge[2]))

    
color = [-1] * (n+1)

#startをbwで塗る
def dfs(start, bw):
    color[start] = bw
    for pair in neighbor[start]:
        if color[pair[0]] != -1:
            continue
        elif pair[1] % 2 == 0:
            dfs(pair[0], bw)
        else:
            dfs(pair[0], (bw + 1) % 2)

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

Submission status: Accepted

Solution code:
from collections import defaultdict
import queue

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

ans = [-1] * N
ans[0] = 0
q = queue.Queue()
q.put(0)
while not q.empty():
    u = q.get()
    for v, w in to[u]:
        if ans[v] != -1:
            continue
        ans[v] = (ans[u] + w) % 2
        q.put(v)

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
# https://atcoder.jp/contests/abc126/tasks/abc126_d

import sys
sys.setrecursionlimit(100000)

def dfs(i):
  for v,w in V.get(i, []):
    if (w % 2) == 0:
      if color[v] == -1:
        color[v] = color[i]
      elif color[v] == color[i]:
        continue
      elif color[v] != color[i]:
        return False
    else:
      if color[v] == -1:
        color[v] = 0 if color[i] else 1
      elif color[v] == color[i]:
        return False
      elif color[v] != color[i]:
        continue
    dfs(v)
  return True

if __name__ == '__main__':
  n = int(input())
  V = {} # key:vertex, value:[[vertex opposited, wight]]
  color = {} # 0 or 1 or -1
  for i in range(1, n):
    u,v,w = map(int, input().split())
    if not V.get(u, False):
      V[u] = [[v,w]]
    else:
      V[u].append([v,w])

    if not V.get(v, False):
      V[v] = [[u,w]]
    else:
      V[v].append([u,w])
    # 同じ頂点間で複数の辺はないと仮定
  for i in range(1, n+1):
    color[i] = -1

  while True:
    i = 0
    for j in range(1, n+1):
      if color[j] == -1:
        i = j
        color[i] = 0
        break
    if i == 0:
      for j in range(1, n+1):
        print(color[j])
      break
    else:
      if not dfs(i):
        print('No')
        break

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(1000000)


n=int(input())

#ノードクラスの定義
class Node:
    def __init__(self,name):
        self.name=name
        self.near=[]
        self.length=[]
    def coloring(self,color):
        self.color=color


#ノードリストの作成
nodelist=[]
for i in range(n):
    nodelist.append(Node(i))
   
    
#辺の作成
for i in range(n-1):
    u,v,w=[int(i) for i in input().split()]
    w=w%2
    nodelist[u-1].near.append(nodelist[v-1])
    nodelist[u-1].length.append(w)
    nodelist[v-1].near.append(nodelist[u-1])
    nodelist[v-1].length.append(w)
    
#行ったかカラーでチェックリスト
color=[None for i in range(n)]
color[0]=0



def paint(node):
    nodecolor=node.color
    for j in range(len(node.near)):
        nearnode=node.near[j]
        if color[nearnode.name]!=None:
            continue
        if node.length[j]==0:
            nearnode.coloring(nodecolor)
        else:
            nearnode.coloring((nodecolor+1)%2)
        color[nearnode.name]=0
        paint(nearnode)

nodelist[0].coloring(0)
paint(nodelist[0])


for i in nodelist:
    print(i.color)

Submission status: Accepted

Solution code:
n = int(input())
L = [[] for _ in range(n+1)]
R = [[] for _ in range(n+1)]
for _ in range(n-1):
    u, v, w = map(int, input().split())
    w %= 2
    L[u] += [[u, v, w]]
    R[v] += [[v, u, w]]
P = [[] for _ in range(2*n+2)]
P[1] += (L[1]+R[1])
L[1] = R[1] = []
for i in range(1, 2*n):
    for _, v, w in P[i]:
        P[i+2-w] += (L[v]+R[v])
        L[v] = R[v] = []
A = []
for p in P[1::2]: A += p
B = set([u for u, *_ in A])
for i in range(1, n+1): print(1 if i in B else 0)

Submission status: Accepted

Solution code:
# 定数
INF = float("inf")
MOD = int(1e9 + 7)

# エントリーポイント
def main():
    N = int(input())
    g = [[] for _ in range(N)]
    for n in range(N - 1):
        u, v, w = map(int, input().split())
        u, v, w = u - 1, v - 1, w % 2
        g[u].append((v, w))
        g[v].append((u, w))
    rs, visited, que = [0] * N, [False] * N, [0]
    while que:
        c = que.pop(0)
        if visited[c]: continue
        visited[c] = True
        for n, w in g[c]:
            if visited[n]: continue
            rs[n] = (rs[c] + w) % 2
            que.append(n)
    for r in rs:
        print(r)

main()

Submission status: Accepted

Solution code:
n=int(input())
l=[[] for _ in range(n+1)]
q=[(1,0)]
ans=[-1]*n
while n>1:
    u,v,w=map(int,input().split())
    l[u]+=[(v,w)]
    l[v]+=[(u,w)]
    n-=1
while q:
    u,w=q.pop()
    ans[u-1]=w%2
    for v,d in l[u]:
        q+=[(v,w+d)]*(ans[v-1]<0)
print(*ans)

Submission status: Accepted

Solution code:
N = int(input())
import sys
sys.setrecursionlimit(90000)

graph = [[] for _ in range(N)]
for _ in range(N-1):
    a, b, c = map(int, input().split())
    graph[a-1].append((b-1, c))
    graph[b-1].append((a-1, c))

color = [-1 for _ in range(N)]
def dfs(p, c, color):
    color[p] = c
    cinv = 0 if c == 1 else 1
    for q, d in graph[p]:
        if color[q] != -1:
            continue
        if d % 2 == 1:
            color = dfs(q, cinv, color)
        else:
            color = dfs(q, c, color)
    return color

A = dfs(0, 0, color)
for a in A:
    print(a)

Submission status: Accepted

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

n = int(input())
seen = [-1]*(n+1)
path = defaultdict(dict)

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


def dfs(seen, pos, color):
    if seen[pos] != -1:
        return
    else:
        seen[pos] = color
        change_color = 1 - color
        for nx in path[pos].keys():
            check = path[pos][nx]
            if check % 2 == 1:
                dfs(seen, nx, change_color)
            dfs(seen, nx, color)


dfs(seen, 1, 0)
for i in range(1, n+1):
    print(seen[i])

Submission status: Accepted

Solution code:

import collections
import itertools

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

##* graph
##pre graph
m,lst,nxt,to=0,[],[],[]

def init_graph(node_count, edge_count):
    global lst,nxt,to
    lst = [-1 for _ in range(node_count)]
    nxt = [0  for _ in range(edge_count)]
    to  = [0  for _ in range(edge_count)]

# bidirection
def add_edge(u, v):
    global m
    nxt[m], lst[u], to[m], m = lst[u], m, v, m + 1
    nxt[m], lst[v], to[m], m = lst[v], m, u, m + 1

# bidirection weight
def add_edge(u, v, w):
    global m
    nxt[m], lst[u], to[m], m = lst[u], m, (v, w), m + 1
    nxt[m], lst[v], to[m], m = lst[v], m, (u, w), m + 1

def traverse(u):
    m = lst[u]
    while m != -1:
        yield m
        m = nxt[m]


n = getint()
init_graph(n, 2 * n)

for _ in range(n - 1):
    u, v, w = getints()
    add_edge(u - 1, v - 1, w)

def get_distance(u, dist):
    dist[u] = 0
    stk = [(u, 0)]
    while stk:
        v, d = stk[-1]
        stk.pop()
        for m in traverse(v):
            vv, w = to[m]
            if dist[vv] >= 0:
                continue
            dist[vv] = d + w
            stk.append((vv, d + w))


dist = [-1]*n
get_distance(0, dist)

# print(dist)


for i in range(n):
    print(dist[i] % 2)

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([0])
while q:
    next = q.popleft()
    for (u, w) in E[next]:
        if ans[u] < 0:
            q.append(u)
            ans[u] = int(ans[next]) if w % 2 == 0 else int(not ans[next])
print(*ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000)
 
def dfs(l,d,k):
  for i in l[k]:
    if d[i[0]]==-1:
      d[i[0]]=d[k]+i[1]
      dfs(l,d,i[0])

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,l[i][2]])
  connection[l[i][1]-1].append([l[i][0]-1,l[i][2]])
distance=[-1 for i in range(n)]
x=-1
for i in range(n-1):
  if len(connection[i])==1:
    x=i
    break
distance[x]=0
dfs(connection,distance,x)
for i in range(n):
  print(distance[i]%2)

Submission status: Accepted

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

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

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

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

queue = deque([0])

while queue:
  x = queue.popleft()
  for x_, w_ in g[x]:
    if c[x_] == -1:
      if w_%2 == 0:
        c[x_] = c[x]
      else:
        c[x_] = 1-c[x]
      queue.append(x_)
    else:
      continue

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

Submission status: Accepted

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

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

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

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

queue = deque([0])

while queue:
  x = queue.popleft()
  for x_, w_ in g[x]:
    if c[x_] == -1:
      if w_%2 == 0:
        c[x_] = c[x]
      else:
        c[x_] = 1-c[x]
      queue.append(x_)
    else:
      continue
for x in c:
  print(x)

Submission status: Accepted

Solution code:

N = int(input())

uvw = []
Nlis = [-1] * N
Ndic = {}

for i in range(N-1):

    u,v,w = map(int,input().split())
    
    if u not in Ndic:
        Ndic[u] = [[v,w]]

    else:
        Ndic[u].append([v,w])

    if v not in Ndic:
        Ndic[v] = [[u,w]]

    else:
        Ndic[v].append([u,w])


ends = set([1])
Q = [1]
Q_cnt = 0
Nlis[0] = 0

while len(Q) > Q_cnt and N != 1:

    now = Q[Q_cnt]
    Q_cnt += 1

    for nw in Ndic[now]:

        if nw[0] not in ends:

            Q.append(nw[0])
            ends.add(nw[0])

            if nw[1] % 2 == 0:
                Nlis[nw[0]-1] =  Nlis[now-1]

            else:
                Nlis[nw[0]-1] = (Nlis[now-1] + 1) % 2

            #Ndic[nw[0]].remove([now,nw[1]])

for i in Nlis:
    print(i)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(200000)

n = int(input())
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))


visited = [0] * n
ans = [0] * n
def dfs(u, d):
    for i in range(len(edge[u])):
        v, w = edge[u][i]
        if visited[v] == 0:
            ans[v] = (d + w) % 2
            visited[v] = 1
            dfs(v, d + w)


visited[0] = 1
dfs(0, 0)
for a in ans:
    print(a)

Submission status: Accepted

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

n = int(input())
roots = [[] for _ in range(n)]

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

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

while stack:
    label = stack.pop(-1)
    for i,w in roots[label]:
        if dis[i] == -1:
            dis[i] = dis[label] + w
            stack.append(i)

for i in dis:
    if i % 2 == 0:
        print(0)
    else:
        print(1)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000)

n = int(input())
graph = [[] for _ in range(n)]
for _ in range(n - 1):
    u, v, w = map(int, input().split())
    u -= 1
    v -= 1
    if w % 2 == 0:
        graph[u].append((v, 1))
        graph[v].append((u, 1))
    else:
        graph[u].append((v, -1))
        graph[v].append((u, -1))
            
color = [None for i in range(n)]
def set_color(v, c):
    color[v] = c
    for next_v, d in graph[v]:
        if color[next_v] is None:
            set_color(next_v, d * c)

set_color(0, 1)
for c in color:
    if c != 1:
        print(0)
    else:
        print(1)

Submission status: Accepted

Solution code:
N = int(input())
uvw = [list(map(int,input().split())) for _ in range(N-1)]
import sys
sys.setrecursionlimit(10000000)
#testcase = open('testcase_04','r')
#contents = testcase.read()
#contents = contents.split("\n")
#N = int(contents[0])
#uvw = [[0,0,0] for _ in range(N-1)]
#for i in range(N-1):
#    uvw[i] = [int(j) for j in contents[i+1].split()]
        


ans = [0] * N
adj_list = [[] for _ in range(N+1)]

for u,v,w in uvw:
    adj_list[u-1].append([v-1,w])
    adj_list[v-1].append([u-1,w])
    
memo = [True] * N
def dfs(s,cnt): 
    memo[s] = False
    if cnt % 2 == 1:
        ans[s] = 1
    nxt = adj_list[s]
    for v,w in nxt:
        if memo[v]:
            dfs(v,cnt+w)
    return
    
dfs(0,0)
for a in ans:
    print(a)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000)


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

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

color = [None for i in range(N)]


def set_color(v, c):
    color[v] = c
    for next_v, d in G[v]:
        if color[next_v] is None:
            set_color(next_v, d*c)


set_color(0, 1)

for c in color:
    if c == 1:
        print(1)
    else:
        print(0)

Submission status: Accepted

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

lst = [[] for _ in range(N + 1)]
for _ in range(N - 1):
    u, v, w = map(int, input().split())
    w = w%2
    lst[u].append([v, w])
    lst[v].append([u, w])
# print (lst)
ans = [-1] * (N + 1)
def dfs(x): #xについてつながりを見る
    # if ans[x] != -1: #既に見ているとき
    #     return ans[x]
    for i in lst[x]: #xからのつながりを見る
        # print (i)
        if ans[i[0]] == -1: #移動先をまだ見ていないとき
            if i[1] == 0: #距離が偶数のとき
                ans[i[0]] = ans[x] #移動先と移動前は同じ
                dfs(i[0])
            else: #距離が奇数のとき
                ans[i[0]] = (ans[x] + 1) % 2
                dfs(i[0])
    return 

ans[1] = 0
dfs(1)
for i in ans[1:]:
    print (i)

Submission status: Accepted

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

lst = [[] for _ in range(N + 1)]
for _ in range(N - 1):
    u, v, w = map(int, input().split())
    w = w%2
    lst[u].append([v, w])
    lst[v].append([u, w])
# print (lst)
ans = [-1] * (N + 1)
def dfs(x): #xについてつながりを見る
    # if ans[x] != -1: #既に見ているとき
    #     return ans[x]
    for i in lst[x]: #xからのつながりを見る
        # print (i)
        if ans[i[0]] == -1: #移動先をまだ見ていないとき
            if i[1] == 0: #距離が偶数のとき
                ans[i[0]] = ans[x] #移動先と移動前は同じ
                dfs(i[0])
            else: #距離が奇数のとき
                ans[i[0]] = (ans[x] + 1) % 2
                dfs(i[0])
    return 

ans[1] = 0
dfs(1)
for i in ans[1:]:
    print (i)

Submission status: Accepted

Solution code:
from collections import deque
N = int(input())
table = [[] for i in range(N)]
for i in range(N-1):
  u,v,w = map(int, input().split())
  u -= 1
  v -= 1
  table[u].append((v,w))
  table[v].append((u,w))
dist = [-1]*N
dist[0] = 0
H = deque()
H.append(0)
while H:
  u = H.popleft()
  for v,w in table[u]:
    if dist[v] == -1:
      dist[v] = dist[u] if w%2 == 0 else 1 - dist[u]
      H.append(v)
for i in range(N):
  print(dist[i])

Submission status: Accepted

Solution code:
import sys

N = int(input())
nodes = [set() for _ in range(N)]
for line in sys.stdin:
    u, v, w = map(int, line.split())
    u, v = (u - 1, v - 1)
    nodes[u].add((v, w))
    nodes[v].add((u, w))


ans = [-1 for _ in range(N)]
q = [(0, 0, -1)]

while q:
    v, dist, parent = q.pop()

    if dist % 2 == 0:
        ans[v] = 0
    else:
        ans[v] = 1

    for u, w in nodes[v]:
        if u == parent:
            continue

        q.append((u, dist + w, v))

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