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:
n=int(input())
dis=[10**15]*n
dis[0]=0
pair=[[]for _ in range(n)]
for i in range(n-1):
	a,b,c=map(int,input().split())
	pair[a-1].append([b-1,c])
	pair[b-1].append([a-1,c])
now=0
stack=set()
cnt=n-1
while cnt!=0:
	for i in range(len(pair[now])):
		if dis[pair[now][i][0]]==10**15:
			dis[pair[now][i][0]]=dis[now]+pair[now][i][1]
			stack.add(pair[now][i][0])
	now=stack.pop()
	cnt-=1
for i in range(n):
	if dis[i]%2==0:
		print(0)
	else:
		print(1)

Submission status: Accepted

Solution code:
def p_d():
    from sys import stdin
    input = stdin.readline
    import sys
    sys.setrecursionlimit(10 ** 6)
    n = int(input())
    route = [[] for _ in range(n)]
    for _ in range(n - 1):
        u, v, w = map(int, input().split())
        w = 0 if w & 1 == 0 else 1
        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)

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

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(4100000)
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))

color_list = [-1]*(N+1)
color_list[1] = 0
'''
for i in range(1,N+1):
    for node in graph[i]:
        if node[1]%2 ==0:
            num =  color_list[i]
        else:
            num =  0 if color_list[i] == 1 else 1
        if color_list[node[0]] == -1:
            color_list[node[0]] = num
'''
def search(n):
    for node in graph[n]:
        if node[1]%2 ==0:
            num =  color_list[n]
        else:
            num =  0 if color_list[n] == 1 else 1
        if color_list[node[0]] == -1:
            color_list[node[0]] = num
            search(node[0]) 
search(1)
#print(color_list)
for i in range(1,N+1):
    print(color_list[i])

Submission status: Accepted

Solution code:
from collections import defaultdict
import sys

sys.setrecursionlimit(1000000)

G = defaultdict(list)

N = int(input())
C = [0 for i in range(N)]
last = N


def rec(pos, c):
    """ 2 色で塗ることができることが保証されている """
    global C
    C[pos] = c
    for to in G[pos]:
        if C[to] == 0:
            rec(to, -c)


for i in range(N-1):
    u, v, w = map(int, input().split())
    u -= 1; v -= 1
    # 無向グラフ
    if w%2 == 0:
        G[u].append(last)
        G[last].append(u)
        G[v].append(last)
        G[last].append(v)
        C.append(0)
        last += 1
    else:
        G[u].append(v)
        G[v].append(u)
rec(0, 1)
for i in range(N):
    print(0 if C[i] == -1 else 1)

Submission status: Accepted

Solution code:
#16:57
n = int(input())
peer = [[] for _ in range(n)]
for _ in range(n-1):
  a,b,w = map(int,input().split())
  a -= 1
  b -= 1
  peer[a].append([b,w%2])
  peer[b].append([a,w%2])
now = [0]
seen = [-1 for _ in range(n)]
seen[0] = 0
#print(peer)
while now:
  last = now
  now = []
  for x in last:
    for yw in peer[x]:
      y,w = yw
      if seen[y] == -1:
        seen[y] = (seen[x]+w)%2
        now.append(y)
for i in range(n):
  print(seen[i])

Submission status: Accepted

Solution code:
"""
dfs活用問題
- 2部グラフ作成
- https://atcoder.jp/contests/abc126/tasks/abc126_d
"""
from collections import deque
import sys
sys.setrecursionlimit(10 ** 9)

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


def dfs_recursive(n, graph):
    def dfs(graph, colors, cur, depth):
        colors[cur] = depth % 2
        for child in graph[cur]:
            child_index = child[0]
            if -1 != colors[child_index]:
                continue
            dfs(graph, colors, child_index, depth + child[1])
    colors = [-1 for _ in range(n)]
    dfs(graph, colors, 0, 0)
    for i in colors:
        print(i)


def dfs_with_queue(n, grpah):
    q = deque()
    ans = [-1 for _ in range(n)]
    q.append(0)
    ans[0] = 0
    while 0 != len(q):
        v = q.popleft()
        for neigbhor in graph[v]:
            u = neigbhor[0]
            w = neigbhor[1]
            if -1 != ans[u]:
                continue
            ans[u] = (ans[v] + w) % 2
            q.append(u)
        for i in ans:
            print(i)


dfs_recursive(n, graph)

Submission status: Accepted

Solution code:
from collections import deque

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


q = deque()
ans = [-1 for _ in range(n)]
q.append(0)
ans[0] = 0
while 0 != len(q):
    v = q.popleft()
    for neigbhor in graph[v]:
        u = neigbhor[0]
        w = neigbhor[1]
        if -1 != ans[u]:
            continue
        ans[u] = (ans[v] + w) % 2
        q.append(u)

for i in ans:
    print(i)

Submission status: Accepted

Solution code:
import sys
from heapq import heappush, heappop, heapify

input = sys.stdin.readline

def main():
    INF = float('inf')
    N = int(input())
    dist = [INF] * N
    visited = [False] * N
    
    E = [[] for i in range(N)]
    V = None
    
    for i 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))
        
        if V is None: V = u-1
    
    q = E[V]
    heapify(q)
    dist[V] = 0
    visited[V] = True
    
    while q:
        v, w = heappop(q)
    
        if visited[v]: continue
    
        visited[v] = True
        dist[v] = w
        
        for u, c in E[v]:
            if visited[u] or dist[u] <= w+c: continue
            heappush(q, (u, w+c))
            
    for d in dist:
        if d % 2: print(0)
        else: print(1)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
from bisect import bisect_left
import heapq

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N = INT()
uvw = [LIST() for _ in range(N-1)]

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


color = [0] *  N
color[0] = 1
def DFS(node):
	for i, w in graph[node]:
		if not color[i]:
			if w % 2 == 0:
				color[i] = color[node]
			else:
				color[i] = color[node] * (-1)
			DFS(i)

DFS(0)
for c in color:
	if c == 1:
		print(0)
	elif c == -1:
		print(1)
	else:
		print("HOGE")

Submission status: Accepted

Solution code:
n = int(input())
T = [[] for _ in range(n+1)]
todo = []
seen = [-1 for _ in range(n+1)]
for i in range(n-1):
    u, v, w = [int(_) for _ in input().split()]
    T[u].append((v, w))
    T[v].append((u, w))
seen[1] = 1
todo.append(1)
while len(todo) != 0:
    t = todo.pop()
    for j in T[t]:
        v = j[0]
        w = j[1]
        color = seen[t]
        if seen[v] == -1:
            todo.append(v)
            if w % 2 == 0:
                seen[v] = color
            else:
                seen[v] = (color + 1) % 2
        else:
            continue
for i in range(1, n+1):
    print(seen[i])

Submission status: Accepted

Solution code:
# ABC126 D - Even Relation
import sys
sys.setrecursionlimit(20000000)

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

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

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

ans = [-1]*N
dfs(0,0)
print(*ans,sep='\n')

Submission status: Accepted

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

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

root = 1
dist = [-1 for _ in range(N+1)]
dist[root] = 0

stack = [root]
while stack:
  idx = stack.pop()
  for i, w in graph[idx]:
    if dist[i] == -1:
      dist[i] = dist[idx] + w
      stack.append(i)

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

Submission status: Accepted

Solution code:
N = int(input())
graph = [[] for _ 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])


root = 0
distances = [-1 for _ in range(N)]
distances[0] = 0

stack = [root]

while len(stack) != 0:
    src = stack.pop()
    for dst, w in graph[src]:
        if distances[dst] == -1:
            distances[dst] = distances[src] + w
            stack.append(dst)


root_color = 0
another_color = 1

for d in distances:
    if d%2==0: print(root_color)
    else: print(another_color)

Submission status: Accepted

Solution code:
import sys
import collections


def solve():
    readline = sys.stdin.buffer.readline
    mod = 10 ** 9 + 7
    tmd = collections.defaultdict(list)
    n = int(readline())
    start = -1
    cql = collections.defaultdict(int)
    for i in range(n-1):
        tma, tmb, tmc = list(map(int, input().rstrip('\n').split()))
        tmd[tma-1] += [tmb-1]
        cql[tma-1, tmb-1] = tmc
        tmd[tmb-1] += [tma-1]
        cql[tmb-1, tma-1] = tmc
        if start == -1:
            start = tma - 1

    ql = [[0, start]]
    ql = collections.deque(ql)
    fq = collections.defaultdict(int)
    fq[start]
    while True:
        if len(ql) != 0:
            cost, tmp = ql.popleft()
            for tmv in tmd[tmp]:
                if tmv not in fq:
                    ql.append([cost + cql[tmv, tmp], tmv])
                    fq[tmv] = (cost + cql[tmv, tmp]) % 2
        else:
            break
    for i in range(n):
        print(fq[i])


if __name__ == '__main__':
    solve()

Submission status: Accepted

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

#
N = int(input())

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

root = 0
distances = [-1 for _ in range(N)]
distances[root] = 0

stack = [root]
while len(stack) != 0:
    src = stack.pop()
    for dst, w in graph[src]:
        if distances[dst] == -1:
            distances[dst] = distances[src] + w
            stack.append(dst)

# print(distances)
#
root_color = 0
another_color = 1
for d in distances:
    if d % 2 == 0:
        print(root_color)
    else:
        print(another_color)

Submission status: Accepted

Solution code:
import math

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    # divisors.sort()
    return divisors

#a = list(map(int, input().split()))

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


#0:49
n = int(input())
nlist = [[]for i in range(n+1)]
for i in range(n-1):
    temp = list(map(int, input().split()))
    nlist[temp[0]].append([temp[1],temp[2]])
    nlist[temp[1]].append([temp[0],temp[2]])


queue = []    
for i in range(n+1):
    if(len(nlist[i])==1):
        queue.append([-1,i])
        break
        

searched = 0
color=[-1 for i in range(n+1)]
nowcol=0


color[queue[0][1]]=nowcol
queue.append([queue[0][1],nlist[queue[0][1]][0][0]])
if(nlist[queue[0][1]][0][1]%2==0):
    color[nlist[queue[0][1]][0][0]]=nowcol
else:
    nowcol=1-nowcol
    color[nlist[queue[0][1]][0][0]]=nowcol
searched+=1
    
while(True):
    nowpos = queue[searched][1]
    #print(queue[searched:])
    #print(nowpos)
    for k in nlist[nowpos]:
        if(k[0]!=queue[searched][0]):
            queue.append([nowpos,k[0]])
            #print("k",k[1])
            if(k[1]%2==0):
                color[k[0]]=color[nowpos]
                #print("a")
            else:
                color[k[0]]=1-color[nowpos]
                #print("b")
    searched+=1
    if(len(queue)==searched):
        break
print()
for i in range(n):
    print(color[i+1])

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(20000000)

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

N = int(input())

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

ans = [-1] * N
dfs(0, 0)
print(*ans, sep='\n')

Submission status: Accepted

Solution code:
from collections import deque

n = int(input())
uvw = [list(map(int, input().split())) for i in range(n-1)]
tree = [list() for i in range(n)]
queue = deque([0])
ans = [0] + [-1] * (n-1)
for u,v,w in uvw:
  u -= 1
  v -= 1
  w %= 2
  tree[u].append((v,w))
  tree[v].append((u,w))
while len(queue):
  i = queue.popleft()
  for NEXT,w in tree[i]:
    if ans[NEXT] == -1:
      if w % 2:
        ans[NEXT] = 1 if ans[i] == 0 else 0
      else:
        ans[NEXT] = ans[i]
      queue.append(NEXT)
print(*ans, sep="\n")

Submission status: Accepted

Solution code:
from collections import deque


def main():
    # BLACK = 1
    WHITE = 0
    EDGE = 0
    WEIGHT = 1
    N = int(input())
    graph = [[] for i in range(N+1)]
    colors = [-1] * (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))

    q = deque()
    q.append(1)
    colors[1] = WHITE
    visited = [False] * (N + 1)
    while len(q) != 0:
        parentIdx = q.popleft()
        parent = graph[parentIdx]
        # print(u+1, [i + 1 for i in q])
        for v, e in enumerate(parent):
            if not visited[e[EDGE]]:
                q.append(e[EDGE])
                visited[e[EDGE]] = True
                if e[WEIGHT] % 2 == 0:
                    colors[e[EDGE]] = colors[parentIdx]
                else:
                    colors[e[EDGE]] = 1 - colors[parentIdx]
                # print(colors)

    for i in range(1, len(colors)):
        print(colors[i])


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N = int(input())

es = [[] for _ in range(N)]

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

    es[u-1].append((v-1,w))
    es[v-1].append((u-1,w))

ans = [-1] * N

ans[0] = 0

queue = [0]

while len(queue) > 0:
    next_queue = []
    for curr in queue:
        for next,w in es[curr]:
            if ans[next] == -1:
                    next_queue.append(next)
                    if w % 2 == 0:
                        ans[next] = ans[curr]
                    else:
                        ans[next] = 1 if ans[curr] == 0 else 0

    if len(next_queue) > 0:
        queue = next_queue
    else:
        queue = []

print(*ans, 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):
    a,b,c = map(int,input().split()); a-=1;b-=1
    g[a].append([b, c]); g[b].append([a, c])

fromzero = [0]*n

res = [0]*n
q = deque([0])
visited = [0]*n; visited[0] = 1
while q :
    now = q.popleft()
    for nxt, c in g[now] :
        if visited[nxt] : continue
        visited[nxt] = 1
        fromzero[nxt] = fromzero[now] + c
        d = fromzero[nxt]
        res[nxt] = (d % 2)
        q.append(nxt)

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

Submission status: Accepted

Solution code:
from collections import Counter,defaultdict,deque
import sys,bisect,math,itertools,string,queue,copy
from heapq import heappop, heappush
input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7

def inp(): # n=1
    return int(input())
def inpm(): # x=1,y=2
    return map(int,input().split())
def inpl(): # a=[1,2,3,4,5,...,n]
    return list(map(int, input().split()))
def inpls(): # a=['1','2','3',...,'n']
    return list(input().split())
def inplm(n): # x=[] 複数行
    return list(int(input()) for _ in range(n))
def inpll(n): # [[1,1,1,1],[2,2,2,2],[3,3,3,3]]
    return sorted([list(map(int, input().split())) for _ in range(n)])
def sortx(x,n,k):
    if k == 0:x.sort(key=lambda y:y[1,n])
    else:x.sort(reversed=True, key=lambda y:y[1,n])
def graph():
    n,m=inpm()
    g=[[] for _ in range(n)]
    for _ in range(n-1):
        a,b=inpm()
        a-=1
        b-=1
        g[a].append(b)
        g[b].append(a)
    return n,m,g

def graphm():
    n=inp()
    g=[[] for _ in range(n)]
    for _ in range(n-1):
        a,b,w=inpm()
        a-=1
        b-=1
        g[a].append((b,w))
        g[b].append((a,w))
    return n,g

def main():
    n,g=graphm()
    que=[0]
    ans=[-1 for _ in range(n)]
    ans[0]=0
    while len(que)>0:
        x=que.pop(0)
        for i in range(len(g[x])):
            go=g[x][i][0]
            if ans[go]==-1:
                que.append(go)
                if g[x][i][1]%2==0:
                    ans[go]=ans[x]
                else:
                    ans[go]=1-ans[x]
    print(*ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import Counter,defaultdict,deque
import sys,bisect,math,itertools,string,queue,copy
from heapq import heappop, heappush
input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7

def inp(): # n=1
    return int(input())
def inpm(): # x=1,y=2
    return map(int,input().split())
def inpl(): # a=[1,2,3,4,5,...,n]
    return list(map(int, input().split()))
def inpls(): # a=['1','2','3',...,'n']
    return list(input().split())
def inplm(n): # x=[] 複数行
    return list(int(input()) for _ in range(n))
def inpll(n): # [[1,1,1,1],[2,2,2,2],[3,3,3,3]]
    return sorted([list(map(int, input().split())) for _ in range(n)])
def sortx(x,n,k):
    if k == 0:x.sort(key=lambda y:y[1,n])
    else:x.sort(reversed=True, key=lambda y:y[1,n])
def graph():
    n,m=inpm()
    g=[[] for _ in range(n)]
    for _ in range(n-1):
        a,b=inpm()
        a-=1
        b-=1
        g[a].append(b)
        g[b].append(a)
    return n,m,g

def graphm():
    n=inp()
    g=[[] for _ in range(n)]
    for _ in range(n-1):
        a,b,w=inpm()
        a-=1
        b-=1
        g[a].append([b,w])
        g[b].append([a,w])
    return n,g

def main():
    n,g=graphm()
    que=[0]
    ans=[-1 for _ in range(n)]
    ans[0]=0
    while len(que)>0:
        x=que.pop(0)
        for i in range(len(g[x])):
            go=g[x][i][0]
            if ans[go]==-1:
                que.append(go)
                if g[x][i][1]%2==0:
                    ans[go]=ans[x]
                else:
                    ans[go]=1-ans[x]
    print(*ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

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

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

while len(stack) > 0:
    x = stack.pop()
    p = ans[x-1]
    g = len(G[x-1])
    for i in range(g):
        y = G[x-1][i][0]
        z = G[x-1][i][1]
        a = ans[y-1]
        if a == -1:
            stack.append(y)
            if z == 0:
                ans[y-1] = p
            else:
                ans[y-1] = 1-p
for i in range(N):
    print(ans[i])

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)
n=int(input())
t=[[] for i in range(n)]
for i in range(n-1):
    a,b,l=map(int,input().split())
    t[a-1].append([b-1,l % 2])
    t[b-1].append([a-1,l % 2])

flag = [(-1) for _ in range(n)]

def dfs(s,l,c):
    global flag
    global t
    if l == 1:
        if c == 0:c = 1
        else:c = 0
    flag[s] = c
    for g in t[s]:
        if flag[g[0]] == -1:
            dfs(g[0],g[1],c)

dfs(0,0,0)

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

Submission status: Accepted

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

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

def dfs(v, color):
  seen[v] = color
  for nv, nw in G[v]:
    if seen[nv] == -1:
      dfs(nv, seen[v]^nw%2)

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

Submission status: Accepted

Solution code:
from collections import deque

N = int(input())
dic = {i + 1:[] for i in range(N)}
color = [-1 for i in range(N + 1)]

for i in range(N - 1):
    f, t, d = map(int, input().split())
    dic[f].append((t, d & 1)) #奇数だったら1
    dic[t].append((f, d & 1))

q = deque()
q.append(1)
color[1] = 0
while len(q) > 0:
    v = q.popleft()
    for t in dic[v]:
        if not color[t[0]] == -1:
            continue
        color[t[0]] = 1 - color[v] if t[1] == 1 else color[v]
        q.append(t[0])

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

Submission status: Accepted

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

n = int(input())

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

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

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

def dfs(now):
    for v,w in path[now]:
        if dist[v] == -1:
            dist[v] = w + dist[now]
            dfs(v)
    
dfs(0)

for i in dist:
    print(i%2)

Submission status: Accepted

Solution code:
n = int(input())
con = [-1] * n
g = [[] for i in range(n)]
for i in range(n-1):
  u,v,w = map(int,input().split())
  u-=1;v-=1;w%=2
  g[u].append([v,w])
  g[v].append([u,w])
con[0] = 0
stack = [0]
while stack:
  cur = stack.pop()
  for i,j in g[cur]:
    if con[i] == -1:
      con[i] = con[cur] + j
      stack.append(i)
for i in range(n):
  print('01'[con[i]%2::2])

Submission status: Accepted

Solution code:
n=int(input())
k=[[] for _ in range(n)]
for i in range(n-1):
  a,b,c=map(int,input().split())
  k[a-1].append([b-1,c])
  k[b-1].append([a-1,c])
s=[0]*n
from collections import deque
d=deque()
d.append(0)
v=[False]*n
v[0]=True
while d:
  g=d.popleft()
  for i in k[g]:
    if v[i[0]]:
      continue
    d.append(i[0])
    v[i[0]]=True
    if i[1]%2==0:
      s[i[0]]=s[g]
    else:
      s[i[0]]=[1,0][s[g]]
for i in s:
  print(i)

Submission status: Accepted

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

class Node:
    def __init__(self):
        self.val = None
        self.a = []

n = int(input())
nodes = []

for i in range(n):
    nodes.append(Node())

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

root = nodes[0]
root.val = True
nodeSet = set()

def traverse(node):
    if node in nodeSet:
        return
    else:
        nodeSet.add(node)

    for pair in node.a:
        adjNode = pair[0]
        dis = pair[1]
        if dis % 2 == 0:
            adjNode.val = node.val
        else:
            adjNode.val = not node.val
        traverse(adjNode)

traverse(root)

for i in range(n):
    node = nodes[i]
    if node.val:
        print(1)
    else:
        print(0)

Submission status: Accepted

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

class Node:
    # def __init__(self, val):
    def __init__(self):
        self.val = None
        self.color = None
        self.a = []

n = int(input())
nodes = []

for i in range(n):
    nodes.append(Node())
    # nodes.append(Node(i+1))

for i in range(n-1):
    u, v, w = map(int, input().split())
    node1 = nodes[u-1]
    node2 = nodes[v-1]
    node1.val = u
    node2.val = v
    node1.a.append([node2, w])
    node2.a.append([node1, w])

# for i in range(n):
#     node = nodes[i]
#     for pair in node.a:
#         print(pair[0])
#         print(pair[1])

root = nodes[0]
root.color = True
nodeSet = set()

def traverse(node, distance):
    if node in nodeSet:
        return
    else:
        nodeSet.add(node)
    # print('# traverse: ' + str(node.val))
    for pair in node.a:
        adjNode = pair[0]
        dis = pair[1]
        if (distance + dis) % 2 == 0:
            adjNode.color = root.color
        else:
            adjNode.color = not root.color
        traverse(adjNode, distance + dis)

traverse(root, 0)

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    n=int(input())
    E=[[] for _ in range(n)]
    for _ in range(n-1):
        u,v,w=map(int,input().split())
        u-=1; v-=1; w%=2
        E[u].append((v,w))
        E[v].append((u,w))

    d=[0]*n
    def dfs(v,p):
        for nv,w in E[v]:
            if(nv==p): continue
            d[nv]=d[v]^w
            dfs(nv,v)
    dfs(0,-1)
    print(*d,sep='\n')
resolve()

Submission status: Accepted

Solution code:
from collections import deque

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

dist = [-1 for _ in range(n)]
dist[0] = 0
q = deque()
q.append(0)
while q:
    v = q.popleft()
    for nv, w in edges[v]:
        if dist[nv] != -1: continue
        dist[nv] = dist[v] + w
        q.append(nv)

for i in range(n):
    if dist[i] % 2:
        print(1)
    else:
        print(0)

Submission status: Accepted

Solution code:
n = int(input())
A = [[] for i in range(n+1)]
CHK = [False for i in range(n+1)]
COL = [0 for i in range(n+1)]
for i in range(n-1):
  u,v,w = map(int,input().split())
  w = w%2
  A[u].append((v,w))
  A[v].append((u,w))
#print(A)
cnt=0
Q = [1]
while cnt<n:
  p = Q.pop()
  childs = A[p]
  for c in childs:
    u1 = c[0]
    w1 = c[1]
    if not CHK[u1]:
      Q.append(u1)
      if w1==0:
        COL[u1] = COL[p]
      else:
        COL[u1] = 0 if COL[p]==1 else 1
  CHK[p] = True
  cnt+=1
  #print(cnt)

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(100000)
input=sys.stdin.readline
n=int(input())
visitedlist=[-1 for  i in range(n)]
kilist=[[] for i in range(n)]
anslist=[0 for i in range(n)]
searchedlist=[-1 for i in range(n)]
for i in range(n-1):
        a,b,c=map(int,input().split())
        kilist[a-1].append((b,c))
        kilist[b-1].append((a,c))
def search(i):
        searchedlist[i-1]=1
        visitedlist[i-1]=1
        flag=0
        for j in kilist[i-1]:
            if visitedlist[j[0]-1]<0:
                visitedlist[j[0]-1]=1
                flag+=1
                anslist[j[0]-1]=anslist[i-1]+j[1]
        else:
            pass

        if flag>0:    
            for k in kilist[i-1]:
                if searchedlist[k[0]-1]==-1:
                    search(k[0])
search(2)
for i in anslist:
    print(i%2)

Submission status: Accepted

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

n = int(input())
tree = [list() for _ in range(n)]
ans = [0] * n

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

def dfs(v, p, dist):
    ans[v] = dist % 2
    for nv, w in tree[v]:
        if nv == p: continue
        dfs(nv, v, dist + w)

dfs(0, -1, 0)
print(*ans, sep="\n")

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(100000)

n=int(input())
visitedlist=[-1 for  i in range(n)]
kilist=[[] for i in range(n)]
anslist=[0 for i in range(n)]
searchedlist=[-1 for i in range(n)]
for i in range(n-1):
        a,b,c=map(int,input().split())
        kilist[a-1].append((b,c))
        kilist[b-1].append((a,c))
def search(i):
        searchedlist[i-1]=1
        visitedlist[i-1]=1
        flag=0
        for j in kilist[i-1]:
            if visitedlist[j[0]-1]<0:
                visitedlist[j[0]-1]=1
                flag+=1
                anslist[j[0]-1]=anslist[i-1]+j[1]
        else:
            pass

        if flag>0:    
            for k in kilist[i-1]:
                if searchedlist[k[0]-1]==-1:
                    search(k[0])
search(2)
for i in anslist:
    print(i%2)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
from collections import deque
def getN():
    return int(input())
def getList():
    return list(map(int, input().split()))
import math
from collections import deque

n = getN()
tree = [[] for i in range(n)]
visited = [0 for i in range(n)]
color = [0 for i in range(n)]

for i in range(n-1):
    a, b, c = getList()
    tree[a-1].append((b-1, c))
    tree[b-1].append((a-1, c))

for i, vert in enumerate(tree):
    if len(vert) == 1:
        root = i
        break

deq = deque()
deq.append(root)

while(len(deq) != 0):
    cur = deq.pop()
    for (target, dist) in tree[cur]:
        if visited[target] == 0:
            color[target] = (color[cur] + dist) % 2
            visited[target] = 1

            deq.append(target)



for c in color:
    print(c)

Submission status: Accepted

Solution code:
import sys
def dfs(n,c):
    if Ans[n] == -1:
        Ans[n] = c
        for m,w in Data[n]:
            if w % 2 == 0:
                dfs(m,c)
            else:
                dfs(m,1-c)
    elif Ans[n] == c:
        return
    else:
        return

sys.setrecursionlimit(100000)
N = int(input())
Data = []
Ans  = [-1] * N
for i in range(N):
    Data.append([])
for i in range(N-1):
    u,v,w = map(int,input().split())
    Data[u-1].append([v-1,w])
    Data[v-1].append([u-1,w])
dfs(0,0)

for a in Ans:
    print(a)

Submission status: Accepted

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

MOD = 10 ** 9 + 7

n = int(input())

graph = [[] for _ in range(n)]
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))

dist = [-1] * n
dist[0] = 0
que = [0]
while len(que) != 0:
    i = que.pop()
    for j, w in graph[i]:
        if dist[j] == -1:
            dist[j] = dist[i] + w
            que.append(j)

for d in dist:
    print(d % 2)