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: Time Limit Exceeded

Solution code:
import sys
from collections import deque

N = int(input())

edges = [[-1] * N for _ in range(N)]
for _ in range(N - 1):
    u, v, w = map(int, input().split())
    #インデックスの操作のしやすさのため番号を1減らす
    u -= 1
    v -= 1

    dist = w % 2
    #edges[from][to] = dist
    edges[u][v] = dist
    edges[v][u] = dist

paint_list = [-1] * N

queue = deque()
queue.append(0)
paint_list[0] = 0
is_visited = [0]

while len(queue) > 0:
    node = queue.popleft()
    for target in range(N):
        dist = edges[node][target]
        if dist != -1 and target not in is_visited:
            paint_list[target] = paint_list[node] ^ dist
            is_visited.append(target)
            queue.append(target)
print("\n".join(map(str, paint_list)))

Submission status: Time Limit Exceeded

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

ver = [-1] * N
known = [1]

def paint(a, b):
    if b == 0:
        known.append(a[1])
        if a[2] % 2 == 0:
            if ver[a[0]-1] == 0:
                ver[a[1]-1] = 0
            elif ver[a[0]-1] == 1:
                ver[a[1]-1] = 1
            else:
                ver[a[0]-1] = 0
                ver[a[1]-1] = 0
        else:
            if ver[a[0]-1] == 0:
                ver[a[1]-1] = 1
            elif ver[a[0]-1] == 1:
                ver[a[1]-1] = 0
            else:
                ver[a[0]-1] = 0
                ver[a[1]-1] = 1
    else:
        known.append(a[0])
        if a[2] % 2 == 0:
            if ver[a[1]-1] == 0:
                ver[a[0]-1] = 0
            elif ver[a[1]-1] == 1:
                ver[a[0]-1] = 1
            else:
                ver[a[1]-1] = 0
                ver[a[0]-1] = 0
        else:
            if ver[a[1]-1] == 0:
                ver[a[0]-1] = 1
            elif ver[a[1]-1] == 1:
                ver[a[0]-1] = 0
            else:
                ver[a[1]-1] = 0
                ver[a[0]-1] = 1

            
    
    
while array:
    tmp = []
    for a in array:
        if a[0] == known[0]:
            paint(a, 0)
            tmp.append(a)
            #print("0")
        elif a[1] == known[0]:
            paint(a, 1)
            tmp.append(a)
            #print("1")
    for c in tmp:
        array.remove(c)
    del known[0]

for color in ver:
    print(color)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
q = []
c = [0 for i in range(N)]
l = [0 for i in range(N)]
A = [[] for i in range(N)]
W = [[0 for i in range(N)] for i in range(N)]

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

q.append(0)
while len(q):
	i = q.pop(0)
	c[i] = 1
	for j in A[i]:
		if c[j] == 0:
			q.append(j)
			l[j] = l[i] + W[i][j]

for i in l:
	print('{}'.format(i%2))

Submission status: Time Limit Exceeded

Solution code:
from queue import Queue

'''
allinputs = iter(input().splitlines())
input = lambda : next(allinputs)
#'''

N = int(input())
q = Queue()
c = [0 for i in range(N)]
l = [0 for i in range(N)]
A = [[] for i in range(N)]
W = [[0 for i in range(N)] for i in range(N)]

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

q.put(0)
while not q.empty():
	i = q.get()
	c[i] = 1
	for j in A[i]:
		if c[j] == 0:
			q.put(j)
			l[j] = l[i] + W[i][j]

for i in l:
	print('{}'.format(i%2))

Submission status: Time Limit Exceeded

Solution code:
from queue import Queue

'''
allinputs = iter(input().splitlines())
input = lambda : next(allinputs)
#'''

N = int(input())
q = Queue()
c = [0 for i in range(N)]
l = [0 for i in range(N)]

u, v, w = map(int,input().split())
c[u-1] = 1
l[u-1] = 0
c[v-1] = 1
l[v-1] = w
		
for i in range(1,N-1):
	u, v, w = map(int,input().split())
	u = u - 1
	v = v - 1
	if c[u] == 0 and c[v] == 0:
		q.put([u,v,w])
	elif c[u] == 0 and c[v] == 1:
		c[u] = 1
		l[u] = l[v] + w
	elif c[u] == 1 and c[v] == 0:
		c[v] = 1
		l[v] = l[u] + w

while not q.empty():
	u, v, w = q.get()
	if c[u] == 0 and c[v] == 0:
		q.put([u,v,w])
	elif c[u] == 0 and c[v] == 1:
		c[u] = 1
		l[u] = l[v] + w
	elif c[u] == 1 and c[v] == 0:
		c[v] = 1
		l[v] = l[u] + w

for i in l:
	print('{}'.format(i%2))

Submission status: Time Limit Exceeded

Solution code:
from queue import LifoQueue

'''
allinputs = iter(input().splitlines())
input = lambda : next(allinputs)
#'''

N = int(input())
A =  [[0 for i in range(N)] for j in range(N)]
q = LifoQueue()
#b = [-1 for i in range(N)]
c = [0 for i in range(N)]
l = [0 for i in range(N)]

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

q.put(0)
while not q.empty():
	i = q.get()
	c[i] = 1
	for j in range(N):
		if A[i][j] > 0 and c[j] == 0:
			q.put(j)
			#b[j] = i
			l[j] = l[i] + A[i][j]

for i in l:
	print('{}'.format(i%2))

Submission status: Time Limit Exceeded

Solution code:
from queue import LifoQueue

'''
allinputs = iter(input().splitlines())
input = lambda : next(allinputs)
#'''

N = int(input())
A =  [[0 for i in range(N)] for j in range(N)]
q = LifoQueue()
b = [-1 for i in range(N)]
c = [0 for i in range(N)]
l = [0 for i in range(N)]

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

q.put(0)
while not q.empty():
	i = q.get()
	c[i] = 1
	for j in range(N):
		if A[i][j] > 0 and c[j] == 0:
			q.put(j)
			b[j] = i
			l[j] = l[i] + A[i][j]

for i in l:
	print('{}'.format(i%2))

Submission status: Time Limit Exceeded

Solution code:
import heapq

def dijkstra(graph, node, start):
    dist = [float("inf") for _ in range(node)]

    dist[start] = 0
    q = []
    heapq.heappush(q, (0, start))

    while q:
        cost, cur_node = heapq.heappop(q)

        if dist[cur_node] < cost:
            continue

        for nex_cost, nex_node in graph[cur_node]:
            dist_cand = dist[cur_node] + nex_cost
            if dist_cand < dist[nex_node]:
                dist[nex_node] = dist_cand
                heapq.heappush(q, (dist[nex_node], nex_node))

    return dist


n = int(input())
adj = [[] for _ in range(n)]
for i in range(n - 1):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    adj[a].append((c, b))
    adj[b].append((c, a))
shortest = []
for i in range(n):
    print(dijkstra(adj, n, i)[0] % 2)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
u = [0] * (N - 1)
v = [0] * (N - 1)
w = [0] * (N - 1)
for i in range(N - 1):
    u[i], v[i], w[i] = map(int, input().strip().split())
    u[i] -= 1
    v[i] -= 1

node = [-1] * N

node[0] = 0


def dfs(x):
    for i in range(N - 1):
        if u[i] == x and node[v[i]] == -1:
            if w[i] % 2 == 0:
                node[v[i]] = node[u[i]]
            else:
                node[v[i]] = abs(node[u[i]] - 1)
            dfs(v[i])
        if v[i] == x and node[u[i]] == -1:
            if w[i] % 2 == 0:
                node[u[i]] = node[v[i]]
            else:
                node[u[i]] = abs(node[v[i]] - 1)
            dfs(u[i])


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

Submission status: Time Limit Exceeded

Solution code:
n = int(input())

array = []
vArray = [-1] * n

for _ in range(n):
    array.append([-1] * n)

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

def check(checkV, color):
    if vArray[checkV] >= 0:
        return
    vArray[checkV] = color
    for i in range(n):
        if array[checkV][i] >= 0:
            if array[checkV][i] % 2 == 0:
                check(i, color)
            else:
                check(i, not color)


check(0, True)

for i in range(n):
    print(0 if vArray[i] == True else 1)

Submission status: Time Limit Exceeded

Solution code:
# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math

mod = 10**9+7

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

# v は今見ている頂点，p はｖの親
def dfs(node,p,color): # Depth First Serch
    res[node] = color
    index_num = [n for n, value in enumerate(u) if value == node]
    # print(index_num)
    for index in index_num:
        new_node = v[index]
        if new_node == p:
            continue
        if w[index] % 2 == 1:dfs(new_node,node,1-color)
        else:dfs(new_node,node,color)

    index_num = [n for n, value in enumerate(v) if value == node]
    # print(index_num)
    for index in index_num:
        new_node = u[index]
        if new_node == p:
            continue
        if w[index] % 2 == 1:dfs(new_node,node,1-color)
        else:dfs(new_node,node,color)

#tree 探索　
# vは頂点，ｐは親
dfs(1,-1,1)

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

Submission status: Time Limit Exceeded

Solution code:
from scipy.sparse import coo_matrix
from scipy.sparse.csgraph import dijkstra

N=int(input())
R=[]
C=[]
W=[]

for i in range(N-1):
    u, v, w = [int(i) for i in input().split()]
    R.append(u-1)
    C.append(v-1)
    W.append(w)
    R.append(v-1)
    C.append(u-1)
    W.append(w)
g = coo_matrix((W, (R, C)), shape=(N, N)).tocsr()
d = dijkstra(g, indices=0 ,directed=1, unweighted=False)
for i in d:
    print(int(i) % 2)

Submission status: Time Limit Exceeded

Solution code:
from scipy.sparse import coo_matrix
from scipy.sparse.csgraph import dijkstra

N=int(input())
R=[]
C=[]
W=[]

for i in range(N-1):
    u, v, w = [int(i) for i in input().split()]
    R.append(u-1)
    C.append(v-1)
    W.append(w)
g = coo_matrix((W, (R, C)), shape=(N, N)).tocsr()
d = dijkstra(g, indices=0 ,directed=False, unweighted=False)

for i in d:
    print(int(i) % 2)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
t = []

for i in range(n - 1):
    t.append(list(map(int, input().split())))

t.sort(key=lambda x:(x[0], x[1]))

color_list = {1: 1}

for e in t:
    if e[2] % 2 == 0:
        if color_list.get(e[0]) == 1 or color_list.get(e[1]) == 1:
            color_list[e[0]] = 1
            color_list[e[1]] = 1
        elif color_list.get(e[0]) == 0 or color_list.get(e[1]) == 0:
            color_list[e[0]] = 0
            color_list[e[1]] = 0
        else:
            t.append(e)
    else:
        if color_list.get(e[0]) == 1 or color_list.get(e[1]) == 0:
            color_list[e[0]] = 1
            color_list[e[1]] = 0
        elif color_list.get(e[0]) == 0 or color_list.get(e[1]) == 1:
            color_list[e[0]] = 0
            color_list[e[1]] = 1
        else:
            t.append(e)

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

Submission status: Time Limit Exceeded

Solution code:
import numpy as np


def read():
    N = int(input().strip())  # N <= 10**5
    edges = dict()
    for i in range(N-1):
        # u[i] < v[i] は保証されている
        u, v, w = list(map(int, input().strip().split()))
        if u - 1 in edges.keys():
            edges[u - 1].update({v - 1: w % 2})
        else:
            edges.update({u - 1: {v - 1: w % 2}})
        if v - 1 in edges.keys():
            edges[v - 1].update({u - 1: w % 2})
        else:
            edges.update({v - 1: {u - 1: w % 2}})
    return N, edges


def solve(N, edges):
    c = np.empty((N, ), dtype=np.int32)
    c.fill(-1)
    stack = list()
    c[0] = 0
    stack.append(0)
    while len(stack) > 0:
        s = stack.pop()
        for t in edges[s].keys():
            if c[t] == -1:
                if edges[s][t]:
                    c[t] = 1 - c[s]
                else:
                    c[t] = c[s]
                stack.append(t)
    return c


if __name__ == '__main__':
    inputs = read()
    colors = solve(*inputs)
    for col in colors:
        print("%d" % col)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np


def read():
    N = int(input().strip())  # N <= 10**5
    edges = dict()
    for i in range(N-1):
        # u[i] < v[i] は保証されている
        u, v, w = list(map(int, input().strip().split()))
        if u - 1 in edges.keys():
            edges[u - 1].update({v - 1: w % 2})
        else:
            edges.update({u - 1: {v - 1: w % 2}})
        if v - 1 in edges.keys():
            edges[v - 1].update({u - 1: w % 2})
        else:
            edges.update({v - 1: {u - 1: w % 2}})
    return N, edges


def solve(N, edges):
    c = np.empty((N, ), dtype=np.int32)  # -1: unvisited, 0: white, 1: black
    c[:] = -1
    stack = list()
    c[0] = 0
    stack.append(0)
    while len(stack) > 0:
        s = stack.pop()
        for t in edges[s].keys():
            if c[t] == -1:
                if edges[s][t]:
                    c[t] = 1 - c[s]
                else:
                    c[t] = c[s]
                stack.append(t)
    return c


if __name__ == '__main__':
    inputs = read()
    colors = solve(*inputs)
    for col in colors:
        print("%d" % col)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np


def read():
    N = int(input().strip())  # N <= 10**5
    edges = dict()
    for i in range(N-1):
        # u[i] < v[i] は保証されている
        u, v, w = list(map(int, input().strip().split()))
        if u - 1 in edges.keys():
            edges[u - 1].update({v - 1: w % 2})
        else:
            edges.update({u - 1: {v - 1: w % 2}})
        if v - 1 in edges.keys():
            edges[v - 1].update({u - 1: w % 2})
        else:
            edges.update({v - 1: {u - 1: w % 2}})
    return N, edges


def solve(N, edges):
    c = np.full((N, ), -1, dtype=np.int32)  # -1: unvisited, 0: white, 1: black
    stack = list()
    c[0] = 0
    stack.append(0)
    while len(stack) > 0:
        s = stack.pop()
        for t in edges[s].keys():
            if c[t] == -1:
                if edges[s][t]:
                    c[t] = 1 - c[s]
                else:
                    c[t] = c[s]
                stack.append(t)
    return c


if __name__ == '__main__':
    inputs = read()
    colors = solve(*inputs)
    for col in colors:
        print("%d" % col)

Submission status: Time Limit Exceeded

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

color = [2 for _ in range(N+1)]
color[0] = 0
color[1] = 0
bi = []
if N > 2:
    for i in range(1,N+1):
        n1 = None
        n2 = None
        l1 = 0
        l2 = 0
        for x in weights:
            if x[0]==i:
                if n1 == None:
                    n1 = x[1]
                    l1 = x[2]
                else:
                    n2 = x[1]
                    l2 = x[2]
            if x[1]==i:
                if n1 == None:
                    n1 = x[1]
                    l1 = x[2]
                else:
                    n2 = x[1]
                    l2 = x[2]
        if n1 != None and n2 != None:
            bi.append([n1,n2,l1+l2])
            
w2 = weights + bi           
while 2 in color:
    for x in w2:
        if x[2]%2 == 0:
            if color[x[0]] != 2:
                color[x[1]] = color[x[0]]
            if color[x[1]] != 2:
                color[x[0]] = color[x[1]]
for x in color[1:]:
    print(x)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
n = int(input())
q = deque(maxlen=n-1)

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

cllist = [-1] * n
a, b, c = q.popleft()
cllist[a] = 0
cllist[b] = c
while q:
    a, b, c = q.popleft()
    if cllist[a] != -1:
        cllist[b] = (cllist[a] + c) % 2
    elif cllist[b] != -1:
        cllist[a] = (cllist[b] + c) % 2
    else:
        q.append([a, b, c])
print(*cllist)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
n = int(input())
q = deque(maxlen=n-1)

for i in range(n - 1):
    a, b, c = map(int, input().split())
    q.append([a-1, b-1, c])

cllist = [-1] * n
a, b, c = q.popleft()
cllist[a] = 0
cllist[b] = c % 2
while q:
    a, b, c = q.popleft()
    if cllist[a] != -1:
        cllist[b] = (cllist[a] + c) % 2
    elif cllist[b] != -1:
        cllist[a] = (cllist[b] + c) % 2
    else:
        q.append([a, b, c])
for i in cllist:
    print(i)

Submission status: Time Limit Exceeded

Solution code:
import collections as c
n = int(input())
q = c.deque()

for i in range(n - 1):
    a, b, c = map(int, input().split())
    q.append([a-1, b-1, c])

cllist = [-1] * n
a, b, c = q.popleft()
cllist[a] = 0
cllist[b] = c % 2
s = {a, b}
while q:
    a, b, c = q.popleft()
    if a in s:
        cllist[b] = (cllist[a] + (c % 2)) % 2
        s.add(b)
    elif b in s:
        cllist[a] = (cllist[b] + (c % 2)) % 2
        s.add(a)
    else:
        q.append([a, b, c])
for i in cllist:
    print(i)

Submission status: Time Limit Exceeded

Solution code:
# /usr/bin/python
# -*- coding: utf-8 -*-
import sys
from collections import defaultdict


def solve():
  ## input
  N = int(input())
  route = defaultdict(set)
  costs = defaultdict(lambda:defaultdict(int))
  for _ in range(N-1):
    u,v,w = map(int, sys.stdin.readline().rstrip().split())
    route[u-1].add(v-1)
    route[v-1].add(u-1)
    costs[u-1][v-1] = w

  ## solve
  visited = set()
  p,q = [0,0]
  colors = [0]*N
  nxt = set([0])
  while len(visited)<N and len(nxt)>0:
    p = q
    q = nxt.pop()
    for r in route[q]:
      if p==r:
        continue
      else:
        colors[r] = (costs[q][r]+costs[r][q]+colors[q]) % 2
        nxt.add(r)
        visited.add(r)
  return colors


if __name__ == "__main__":
  ans = solve()
  for a in ans:
    print(a)

Submission status: Time Limit Exceeded

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

dist = [0]*N
st = deque()
push, pop = st.appendleft, st.pop
push(0)
while st:
    i = pop()
    for j in range(N):
        if a[i][j] > 0:
            dist[j] = dist[i] + a[i][j]
            a[i][j], a[j][i] = 0,0
            push(j)


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

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
N = int(input())
st = deque()
push, pop = st.appendleft, st.pop

for n in range(N-1):
    push([int(i) for i in input().split()])

dist = [0]*N
cnt = [0]*N

[u,v,w] = pop()
dist[v-1] = dist[u-1] + w 
cnt[u-1],cnt[v-1] = 1,1
while st:
    [u,v,w] = pop()
    if cnt[u-1] == 1:
        dist[v-1] = dist[u-1] + w 
        cnt[u-1],cnt[v-1] = 1,1
    elif cnt[v-1] == 1:
        dist[u-1] = dist[v-1] + w 
        cnt[u-1],cnt[v-1] = 1,1
    else:
        push([u,v,w])



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

Submission status: Time Limit Exceeded

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

d = [0]+[-1 for i in range(N-1)]
stack = []
stack.append(0)
while len(stack) != 0:
    s = stack.pop()
    if d[s] != -1:
        for x,w in connect_list[s]:
            d[x] = d[s] + w
            stack.append(x)

for i in range(N):
    print(i%2)

Submission status: Time Limit Exceeded

Solution code:
import sys
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def II(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def SI(): return input()
YN = lambda b: print('YES') if b else print('NO')
yn = lambda b: print('Yes') if b else print('No')

N = II()
u_li = []
v_li = []
w_li = []
for i in range(N-1):
    u, v, w = LI()
    u_li.append(u)
    v_li.append(v)
    w_li.append(w)

# 連結リストを作成。計算量削減のために、距離の情報も持つ。
max_node = max(max(u_li), max(v_li))
neighbor = [[] for i in range(max_node+1)]
for i in range(N-1):
    neighbor[u_li[i]].append((v_li[i], w_li[i]))
    neighbor[v_li[i]].append((u_li[i], w_li[i]))

# 深さ優先探索をしつつ色を塗っていく。
from collections import deque
def depth_first(neighbor, start):
    visited, stack = [], deque()
    stack.append(start)
    result = [None, 0] + [None]*(N-1)
    while len(stack) > 0:
        next_node = stack.pop()
        if next_node in visited: continue
        visited.append(next_node)
        for nei in neighbor[next_node]:
            if result[nei[0]] is not None: continue
            if nei[1]%2 == 0:
                result[nei[0]] = result[next_node]
            else:
                result[nei[0]] = (result[next_node]+1)%2
            stack.append(nei[0])
    return result

colors = depth_first(neighbor, 1)

for ans in colors[1:]:
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
n=int(input());e=[[]for _ in[0]*-~n];q=[(1,0)];f=[-1]*n;exec('v,w,c=map(int,input().split());e[v]+=(w,c),;e[w]+=(v,c),;'*~-n)
while q:
 v,c=q.pop();f[v-1]=c%2
 for w,d in e[v]:q+=[(w,c+d)]*(f[w-1]<0)
print(*f)

Submission status: Time Limit Exceeded

Solution code:
import sys
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def II(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def SI(): return input()
YN = lambda b: print('YES') if b else print('NO')
yn = lambda b: print('Yes') if b else print('No')

import numpy as np

N = II()
u_li = []
v_li = []
w_li = []
for i in range(N-1):
    u, v, w = LI()
    u_li.append(u)
    v_li.append(v)
    w_li.append(w)

# 連結リストを作成。計算量削減のために、距離の情報も持つ。
max_node = max(max(u_li), max(v_li))
neighbor = [[] for i in range(max_node+1)]
for i in range(N-1):
    neighbor[u_li[i]].append((v_li[i], w_li[i]))
    neighbor[v_li[i]].append((u_li[i], w_li[i]))

# 深さ優先探索をしつつ色を塗っていく。
from collections import deque
def depth_first(neighbor, start):
    visited, stack = [], deque()
    stack.append(start)
    result = [None, 0] + [None]*(N-1)
    while len(stack) > 0:
        next_node = stack.pop()
        if next_node in visited: continue
        visited.append(next_node)
        for nei in neighbor[next_node]:
            nei, w = nei[0], nei[1]
            if result[nei] is not None: continue
            if w%2 == 0:
                result[nei] = result[next_node]
            else:
                result[nei] = (result[next_node]+1)%2
            stack.append(nei)
    return result

colors = depth_first(neighbor, 1)

for ans in colors[1:]:
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def II(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def SI(): return input()
YN = lambda b: print('YES') if b else print('NO')
yn = lambda b: print('Yes') if b else print('No')

import numpy as np

N = II()
u_li = []
v_li = []
w_li = []
for i in range(N-1):
    u, v, w = LI()
    u_li.append(u)
    v_li.append(v)
    w_li.append(w)

# 辺のリストを作成。必ず（小, 大）となるようにする。
max_node = max(max(u_li), max(v_li))
from scipy.sparse import lil_matrix
edges = lil_matrix((max_node+1, max_node+1))
for i in range(N-1):
    u, v = (u_li[i], v_li[i]) if u_li[i] < v_li[i] else (v_li[i], u_li[i])
    edges[u,v] = w_li[i]

# 連結リストを作成
neighbor = [[] for i in range(max_node+1)]
for i in range(N-1):
    neighbor[u_li[i]].append(v_li[i])
    neighbor[v_li[i]].append(u_li[i])

# 深さ優先探索をしつつ色を塗っていく。
from collections import deque
def depth_first(neighbor, start):
    visited, stack = [], deque()
    stack.append(start)
    result = [None, 0] + [None]*(N-1)
    while len(stack) > 0:
        next_node = stack.pop()
        if next_node in visited: continue
        visited.append(next_node)
        for nei in neighbor[next_node]:
            if result[nei] is not None: continue
            u, v = (nei, next_node) if nei < next_node else (next_node, nei)
            if edges[u,v]%2 == 0:
                result[nei] = result[next_node]
            else:
                result[nei] = (result[next_node]+1)%2
            stack.append(nei)
    return result

colors = depth_first(neighbor, 1)

for ans in colors[1:]:
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def II(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def SI(): return input()
YN = lambda b: print('YES') if b else print('NO')
yn = lambda b: print('Yes') if b else print('No')

N = II()
u_li = []
v_li = []
w_li = []
for i in range(N-1):
    u, v, w = LI()
    u_li.append(u)
    v_li.append(v)
    w_li.append(w)

# 辺のリストを作成。必ず（小, 大）となるようにする。
max_node = max(max(u_li), max(v_li))
edges = {}
for i in range(N-1):
    u, v = (u_li[i], v_li[i]) if u_li[i] < v_li[i] else (v_li[i], u_li[i])
    edges.update({(u, v): w_li[i]})

# 連結リストを作成
neighbor = [[] for i in range(max_node+1)]
for i in range(N-1):
    neighbor[u_li[i]].append(v_li[i])
    neighbor[v_li[i]].append(u_li[i])

# 深さ優先探索をしつつ色を塗っていく。
from collections import deque
def depth_first(neighbor, start):
    visited, stack = [], deque()
    stack.append(start)
    result = [None, 0] + [None]*(N-1)
    while len(stack) > 0:
        next_node = stack.pop()
        if next_node in visited: continue
        visited.append(next_node)
        for nei in neighbor[next_node]:
            if result[nei] is not None: continue
            u, v = (nei, next_node) if nei < next_node else (next_node, nei)
            if edges[(u,v)]%2 == 0:
                result[nei] = result[next_node]
            else:
                result[nei] = (result[next_node]+1)%2
            stack.append(nei)
    return result

colors = depth_first(neighbor, 1)

for ans in colors[1:]:
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def II(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def SI(): return input()
YN = lambda b: print('YES') if b else print('NO')
yn = lambda b: print('Yes') if b else print('No')

import numpy as np

N = II()
u_li = []
v_li = []
w_li = []
for i in range(N-1):
    u, v, w = LI()
    u_li.append(u)
    v_li.append(v)
    w_li.append(w)


# 辺のリストを作成。必ず（小, 大）となるようにする。
edges = {}
for i in range(N-1):
    u, v = (u_li[i], v_li[i]) if u_li[i] < v_li[i] else (v_li[i], u_li[i])
    edges.update({(u, v): w_li[i]})

# 連結リストを作成
import itertools
neighbor = {}
for i, j in edges.keys():
    if i not in neighbor.keys():
        neighbor.update({i:[]})
    if j not in neighbor[i]:
        neighbor[i].append(j)
    if j not in neighbor.keys():
        neighbor.update({j:[]})
    if i not in neighbor[j]:
        neighbor[j].append(i)

# 深さ優先探索をしつつ色を塗っていく。
def depth_first(neighbor, start):
    visited, stack = [], []
    stack.append(start)
    result = [None, 0] + [None]*(N-1)
    while len(stack) > 0:
        next_node = stack.pop()
        if next_node in visited: continue
        ##
        visited.append(next_node)
        for nei in neighbor[next_node]:
            if result[nei] is not None: continue
            u, v = (nei, next_node) if nei < next_node else (next_node, nei)
            if edges[(u,v)]%2 == 0:
                result[nei] = result[next_node]
            else:
                result[nei] = (result[next_node]+1)%2
            stack.append(nei)
    return result

colors = depth_first(neighbor, 1)

for ans in colors[1:]:
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def II(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def SI(): return input()
YN = lambda b: print('YES') if b else print('NO')
yn = lambda b: print('Yes') if b else print('No')

import numpy as np

N = II()
u_li = []
v_li = []
w_li = []
for i in range(N-1):
    u, v, w = LI()
    u_li.append(u)
    v_li.append(v)
    w_li.append(w)


# 辺のリストを作成。必ず（小, 大）となるようにする。
edges = {}
for i in range(N-1):
    u, v = (u_li[i], v_li[i]) if u_li[i] < v_li[i] else (v_li[i], u_li[i])
    edges.update({(u, v): w_li[i]})

# 連結リストを作成
import itertools
neighbor = {}
for i, j in edges.keys():
    if i not in neighbor.keys():
        neighbor.update({i:[]})
    if j not in neighbor[i]:
        neighbor[i].append(j)
    if j not in neighbor.keys():
        neighbor.update({j:[]})
    if i not in neighbor[j]:
        neighbor[j].append(i)

# 深さ優先探索をしつつ色を塗っていく。
def depth_first(neighbor, start):
    visited, stack = [], []
    stack.append(start)
    result = [None, 0] + [None]*(N-1)
    while len(stack) > 0:
        next_node = stack.pop()
        if next_node in visited: continue
        visited.append(next_node)
        for nei in neighbor[next_node]:
            u, v = (nei, next_node) if nei < next_node else (next_node, nei)
            if edges[(u,v)]%2 == 0:
                result[nei] = result[next_node]
            else:
                result[nei] = (result[next_node]+1)%2
            stack.append(nei)
    return result

colors = depth_first(neighbor, 1)

for ans in colors[1:]:
    print(ans)