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
import Queue

n = int(raw_input())

graph = [[-1 for i in range(0, n)] for j in range(0, n)]
color = [-1 for i in range(0, n)]
for i in range(0, n - 1):
    u, v, w = map(int, raw_input().split(" "))
    # print("%d %d %d" % (u, v, w))
    graph[u-1][v-1] = w
    graph[v-1][u-1] = w

# for i in range(0, n):
#     for j in range(0, n):
#         sys.stdout.write(str(graph[j][i]) + "\t")
#
#     print("")

queue = Queue.Queue()
sum = 0
next_check = 0

while True:
    if sum >= n:
        break

    for i in range(next_check, n):
        if color[i] < 0:
            queue.put(i)
            color[i] = 0
            sum += 1
            next_check = i
            break

    while True:
        if queue.empty():
            break

        current_node = queue.get()
        for end in range(0, n):
            if graph[current_node][end] > 0 and color[end] < 0:
                color[end] = (color[current_node] + graph[current_node][end] % 2) % 2
                queue.put(end)
                sum += 1

for node in range(0, n):
    print(color[node])

Submission status: Time Limit Exceeded

Solution code:
import sys
import Queue

n = int(raw_input())

graph = [[-1 for i in range(0, n)] for j in range(0, n)]
color = [-1 for i in range(0, n)]
for i in range(0, n - 1):
    u, v, w = map(int, raw_input().split(" "))
    # print("%d %d %d" % (u, v, w))
    graph[u-1][v-1] = w
    graph[v-1][u-1] = w

# for i in range(0, n):
#     for j in range(0, n):
#         sys.stdout.write(str(graph[j][i]) + "\t")
#
#     print("")

queue = Queue.Queue()
sum = 0

while True:
    if sum >= n:
        break

    for i in range(0, n):
        if color[i] < 0:
            queue.put(i)
            color[i] = 0
            sum += 1
            break

    while True:
        if queue.empty():
            break

        current_node = queue.get()
        for end in range(0, n):
            if graph[current_node][end] > 0 and color[end] < 0:
                color[end] = (color[current_node] + graph[current_node][end] % 2) % 2
                queue.put(end)
                sum += 1

for node in range(0, n):
    print(color[node])

Submission status: Time Limit Exceeded

Solution code:
# 未完成
import numpy as np
N = int(input())  # 頂点数
vertexcolor = np.zeros(N)+(-1)  # その要素の頂点に色が塗られたか否か（塗られてなければ-1）

edge = np.zeros((N-1, 3))  # N以降の入力を保存，辺に関する情報を保存している
for i in range(N-1):
    edge[i] = np.array([int(i) for i in input().split()])

numofcoloredvertex = 2  # 色が塗られた頂点の数
# まずvertexcolor[edge[0][0] - 1]を白にする（黒でも問題はない）
vertexcolor[int(edge[0][0]) - 1] = 0

if edge[0][2] % 2 == 0:  # 頂点（edge[0][0] - 1）との距離が偶数ならvertexcolor[edge[0][1] - 1] も白，奇数なら黒
    vertexcolor[int(edge[0][1]) - 1] = 0

else:
    vertexcolor[int(edge[0][1]) - 1] = 1


while (numofcoloredvertex < N):  # 色が塗られた頂点の数がNになるまで続ける
    for j in range(1, N-1):
        # どちらかの頂点に色が塗られていれば，距離の偶奇でもう１つの頂点の色が決まる
        if vertexcolor[int(edge[j][0]) - 1] >= 0 and vertexcolor[int(edge[j][1]) - 1] == -1:
            numofcoloredvertex += 1
            if edge[j][2] % 2 == 0:

                vertexcolor[int(edge[j][1]) -
                            1] = vertexcolor[int(edge[j][0]) - 1]
            else:

                vertexcolor[int(edge[j][1]) - 1] = 1 - \
                    vertexcolor[int(edge[j][0]) - 1]

        elif vertexcolor[int(edge[j][1]) - 1] >= 0 and vertexcolor[int(edge[j][0]) - 1] == -1:
            numofcoloredvertex += 1
            if edge[j][2] % 2 == 0:

                vertexcolor[int(edge[j][0]) -
                            1] = vertexcolor[int(edge[j][1]) - 1]
            else:

                vertexcolor[int(edge[j][0]) - 1] = 1 - \
                    vertexcolor[int(edge[j][1]) - 1]

for k in range(N):
    print("{}".format(int(vertexcolor[k])))

Submission status: Time Limit Exceeded

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

n = int(input())
edges = [list(map(int, input().split())) for _ in range(n - 1)]
bw = [-1 for i in range(n + 1)]
bw[1] = 0

def dfs(frm):
	tmp = []
	for e in edges[:]:
		if e[0] == frm:
			tmp.append([e[1], e[2]])
			edges.remove(e)
		elif e[1] == frm:
			tmp.append([e[0], e[2]])
			edges.remove(e)

	for t in tmp:
		if bw[t[0]] == -1:
			if t[1] % 2 == 0:
				bw[t[0]] = bw[frm]
			else:
				bw[t[0]] = abs(bw[frm] - 1)
			dfs(t[0])

dfs(1)

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

Submission status: Time Limit Exceeded

Solution code:
n = int(input())

d = [[float("inf") for i in range(n)] for i in range(n)] 

for i in range(n-1):
    u,v,w = map(int,input().split())
    d[u-1][v-1] = w
    d[v-1][u-1] = w
for i in range(n):
    d[i][i] = 0 #自身のところに行くコストは０

def warshall_floyd(d):
    #d[i][j]: iからjへの最短距離
    for k in range(n):
        for i in range(n):
            for j in range(n):
                d[i][j] = min(d[i][j],d[i][k] + d[k][j])
    return d

d = warshall_floyd(d)

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

Submission status: Time Limit Exceeded

Solution code:
import bisect
import numpy as np

def search(l, val):
    a = bisect.bisect_left(l, val)
    b = bisect.bisect_right(l, val)
    return list(range(a, b))

def resolve():
    N = int(input())
    X = [list(map(int,input().split())) for _ in range(N-1)]
    # u番目の頂点, v番目の頂点, 距離w
    
    X0 = sorted(X, key=lambda x: x[1])
    X1 = sorted(X)
    X0np = np.array(X0)
    X1np = np.array(X1)

    # 未彩色は-1
    color = [-1] * N
    color[0] = 0

    q = [(1, color[0])]
    while len(q) > 0:
        q0 = q[0]
        q = q[1:]

        r0 = search(X0np[:, 1], q0[0])
        for r in r0:
            val = X0[r][0]
            if color[val-1] == -1:
                c = (q0[1] + X0[r][2]) % 2
                color[val-1] = c
                q.append((val, c))
        r1 = search(X1np[:, 0], q0[0])
        for r in r1:
            val = X1[r][1]
            if color[val-1] == -1:
                c = (q0[1] + X1[r][2]) % 2
                color[val-1] = c
                q.append((val, c))
    
    for c in color:
        print(c)
        
resolve()

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:
            if 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:
            if 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:
# -*- coding: utf-8 -*-
import numpy as np
n = int(input())
u=[]
v=[]
w=[]
for i in range(n-1):
  a, b, c = map(int, input().split())
  u.append(a)
  v.append(b)
  w.append(c)
tree=np.ones(n)*(-1)
points=[1]
tree[0] = 0
flag=True
while flag:
  for i in range(n-1):
    if u[i] == points[0]:
      if w[i]%2 == 0:
        if tree[v[i]-1]==-1:
          points.append(v[i])
          tree[v[i]-1]=tree[u[i]-1]
      else:
        if tree[v[i]-1]==-1:
          points.append(v[i])
          if tree[u[i]-1] ==0:
            tree[v[i]-1]=1
          else:
            tree[v[i]-1]=0
    elif v[i] == points[0]:
      if w[i]%2 == 0:
        if tree[u[i]-1]==-1:
          points.append(u[i])
          tree[u[i]-1]=tree[v[i]-1]
      else:
        if tree[u[i]-1]==-1:
          points.append(u[i])
          if tree[v[i]-1] ==0:
            tree[u[i]-1]=1
          else:
            tree[u[i]-1]=0
  del points[0]
  if len(points)==0:
    flag = False
  if (len(tree[tree==-1])==0):
    flag = False
for i in range(n):
  print(int(tree[i]))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
T = []
for k in range(N-1):
    t = list(map(int,input().split()))
    T.append(t)

T = sorted(T, key = lambda x: x[0])
A = [-1 for k in range(N)]
A[0] = 0

while len(T) > 0:
    c = 0
    while A[T[c][0]-1] == A[T[c][1]-1] == -1:
        c += 1
    u = T[c][0]-1
    v = T[c][1]-1
    w = T[c][2] 
    T.pop(c)
    if w%2 == 0:
        if A[u] == 0 and A[v] == -1:
            A[v] = 0
        elif A[u] == 1 and A[v] == -1:
            A[v] = 1
        elif A[u] == -1 and A[v] == 0:
            A[u] = 0
        elif A[u] == -1 and A[v] == 1:
            A[u] = 1
    else:
        if A[u] == 0 and A[v] == -1:
            A[v] = 1
        elif A[u] == 1 and A[v] == -1:
            A[v] = 0
        elif A[u] == -1 and A[v] == 0:
            A[u] = 1
        elif A[u] == -1 and A[v] == 1:
            A[u] = 0

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

Submission status: Time Limit Exceeded

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


A = [-1 for k in range(N)]
A[0] = 0

while len(T) > 0:
    c = 0
    while A[T[c][0]-1] == A[T[c][1]-1] == -1:
        c += 1
    u = T[c][0]-1
    v = T[c][1]-1
    w = T[c][2] 
    T.pop(c)
    if w%2 == 0:
        if A[u] == 0 and A[v] == -1:
            A[v] = 0
        elif A[u] == 1 and A[v] == -1:
            A[v] = 1
        elif A[u] == -1 and A[v] == 0:
            A[u] = 0
        elif A[u] == -1 and A[v] == 1:
            A[u] = 1
    else:
        if A[u] == 0 and A[v] == -1:
            A[v] = 1
        elif A[u] == 1 and A[v] == -1:
            A[v] = 0
        elif A[u] == -1 and A[v] == 0:
            A[u] = 1
        elif A[u] == -1 and A[v] == 1:
            A[u] = 0

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

Submission status: Time Limit Exceeded

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

ans = [-1] * N
W = [[0 for __ in range(N)] for _ in range(N)]
P = [set() for _ in range(N)]
for l in L:
    u, v, w = l
    W[u - 1][v - 1] = w
    P[u - 1].add(v - 1)
    P[v - 1].add(u - 1)

ans[0] = 0
F = [0] * (N + 1)
it = 0
po = 1
already = {0}
for _ in range(N + 1):
    if it > po:
        break
    u = F[it]
    it += 1
    for v in (P[u] - already):
        w = W[u][v] if u < v else W[v][u]
        ans[v] = ans[u] if w % 2 == 0 else 1 - ans[u]
        F[po] = v
        already.add(v)
        po += 1

res = ""
for a in ans:
    res += "{}\n".format(a)
print(res)

Submission status: Time Limit Exceeded

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

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

a = [0,0]+[-1]*(n-1)

while True:
    f = False
    for i in range(n-1):
        b = True
        if g[i][2]%2 == 0:
            b = False
        if a[g[i][0]] == -1 or a[g[i][1]] == -1:
            f = True
        if a[g[i][0]] == 0:
            if b:
                a[g[i][1]] = 1
            else:
                a[g[i][1]] = 0
        elif a[g[i][0]] == 1:
            if b:
                a[g[i][1]] = 0
            else:
                a[g[i][1]] = 1
        if a[g[i][1]] == 0:
            if b:
                a[g[i][0]] = 1
            else:
                a[g[i][0]] = 0
        elif a[g[i][1]] == 1:
            if b:
                a[g[i][0]] = 0
            else:
                a[g[i][0]] = 1
    if not f:
        break

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

Submission status: Time Limit Exceeded

Solution code:

def main():
	n = int(input())
	mem = [[]]*n
	ans = [0]*n
	ans[0] = 1
	inp = []
	for _ in range(n-1):
		u, v, w = map(int, input().split())
		u -= 1
		v -= 1
		inp += [[u,v,1 if w % 2==0 else -1]]
	inp.sort(key=lambda x:x[0])
	while inp:
		temp = inp[0]
		if ans[temp[0]] == 0:
			if ans[temp[1]] == 0:
				inp += [temp]
			else:
				ans[temp[0]] = temp[2] * ans[temp[1]]
		else:
			ans[temp[1]] = ans[temp[0]] * temp[2]
		inp.pop(0)
	for i in range(n):
		print(0 if ans[i] == -1 else 1)
main()

Submission status: Time Limit Exceeded

Solution code:
n = int(input())

dist = [[0 for i in range(n+1)] for i in range(n+1)]
for i in range(n-1):
    a,b,w = map(int,input().split())
    dist[a][b] = w

come = [[0 for i in range(n+1)] for i in range(n+1)]
color = [-1 for i in range(n+1)]
color[0],color[1]=0,0
renew = 0
while -1 in color:
    if renew ==0: tmp = 1
    renew = 0
    for i in range(tmp+1,n+1):
        if dist[tmp][i]==0: continue
        if dist[tmp][i]%2==0: color[i]=color[tmp]
        else: color[i]=(color[tmp]+1)%2
        if come[tmp][i]==0: tmp = i; come[tmp][i]==1; renew = 1; break


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

Submission status: Time Limit Exceeded

Solution code:
def main():
    N = int(input())
    edges = [[-1]*N for n in range(N)]
    colors = [-1]*N
    for i in range(N-1):
        u, v, w = [int(n) for n in input().split()]
        edges[u-1][v-1] = w
        edges[v-1][u-1] = w
    colors[0] = 0
    bfs(edges, 0, colors)
    for i in colors:
        print(i)
            
def bfs(edges, current, colors):
    ed = edges[current]
    for i in range(len(ed)):
        if ed[i] == -1:
            continue
        if colors[i] != -1:
            continue
        
        if ed[i] % 2 == 0:
            colors[i] = colors[current]
        else:
            colors[i] = colors[current] ^ 1
        bfs(edges, i, colors)
    # for i in colors:
    #     print(i, end=" ")
    # print()

        

        
main()

Submission status: Time Limit Exceeded

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

T = deque(T)
A = [-1 for k in range(N)]
A[0] = 0

while len(T) > 0:
    t = T.popleft()
    u = t[0]-1
    v = t[1]-1
    w = t[2]
    if w%2 == 0:
        if A[u] == 0 and A[v] == -1:
            A[v] = 0
        elif A[u] == 1 and A[v] == -1:
            A[v] = 1
        elif A[u] == -1 and A[v] == 0:
            A[u] = 0
        elif A[u] == -1 and A[v] == 1:
            A[u] = 1
        elif A[u] == -1 and A[v] == -1:
            T.append([u+1,v+1,w])
    else:
        if A[u] == 0 and A[v] == -1:
            A[v] = 1
        elif A[u] == 1 and A[v] == -1:
            A[v] = 0
        elif A[u] == -1 and A[v] == 0:
            A[u] = 1
        elif A[u] == -1 and A[v] == 1:
            A[u] = 0
        elif A[u] == -1 and A[v] == -1:
            T.append([u+1,v+1,w])

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

Submission status: Time Limit Exceeded

Solution code:
import sys

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

uvw = [(u, v, w) if u < v else (v, u, w) for u, v, w in uvw]
uvw = sorted(uvw, key=lambda x: x[0])

#  0: 白
#  1: 黒
# -1: 未確定
wb = [-1] * n

# とりあえず一箇所を白に固定する
wb[0] = 0

# 残りの未確定頂点数
progress = n - 1

i = 0
while uvw:
    if len(uvw) <= i:
        i = 0
    u, v, w = uvw[i]
    u -= 1
    v -= 1
    if wb[u] == -1 and wb[v] == -1:
        # 両方未確定なので何も出来ない
        i = i + 1
        continue
    if wb[u] in (0, 1):
        u, v = v, u
    if w % 2 == 0:
        wb[u] = wb[v]
    else:
        wb[u] = 1 - wb[v]

    uvw.pop(i)
    progress -= 1
    if progress == 0:
        # 完了
        print(*wb, sep='\n')
        sys.exit(0)

Submission status: Time Limit Exceeded

Solution code:
import sys


def input():
    return sys.stdin.readline()[:-1]


N = int(input())
A = [list(map(int, input().split())) for i in range(N-1)]
A = [(e[0] - 1, e[1] - 1, e[2]) if e[0] <= e[1] else (e[1] - 1, e[0] - 1, e[2]) for e in A]

B = {i: [] for i in range(N)}  # かく頂点がどの頂点と繋がっているか
C = {(e[0], e[1]): e[2] for e in A}  # へんのながさ
# print(C)
for e in A:
    B[e[0]].append(e[1])
    B[e[1]].append(e[0])
# print(B)
not_visited = [1 for i in range(N)]
not_visited[0] = 0
color = [-1 for i in range(N)]
color[0] = 0  # node 0は0色
beam = [0]
while True:
    now = beam[-1]
    for b in B[now]:
        if not_visited[b]:
            edge = (now, b) if now <= b else (b, now)
            # print(edge)
            if C[edge] %2 ==0:
                color[b] = color[now]
            else:
                color[b] = 1 - color[now]
            if not_visited[b]:
                beam.insert(0, b)
            not_visited[b] = 0
    beam.pop()
    if sum(not_visited) == 0:
        break

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

Submission status: Time Limit Exceeded

Solution code:
n_s = input()
n = int(n_s)
inputs = []
for i in range(n-1):
    inp = input()
    inputs.append(inp)
white = []
black = []
# remain_inputs = []
# 一番最初のノードは白に入れる
g_inp_st = inputs[0].split()
g_v = int(g_inp_st[0])
white.append(g_v)
add_node = []
added_node = []
added_node.append(g_v)
add_node.append(g_v)
while len(added_node) < n:
    # すべてのノードがどちらかに入っていないとき
    search_node = add_node.pop()
    remove_ids = []
    for i, inp in enumerate(inputs):
        inp_st = inp.split()
        v1 = int(inp_st[0])
        v2 = int(inp_st[1])
        w = int(inp_st[2])
        cont = False
        if v1 == search_node and not v2 in added_node:
            new_node = v2
            cont = True
        if v2 == search_node and not v1 in added_node:
            new_node = v1
            cont = True
        if cont:
            w_even = True
            if w % 2 == 1:
                w_even = False
            # v1/v2がwhiteでwが偶数なら同じグループにv2/v1を追加する
            if search_node in white:
                if w_even:
                    white.append(new_node)
                    added_node.append(new_node)
                    add_node.append(new_node)
                    remove_ids.append(inp)
                else:
                    black.append(new_node)
                    added_node.append(new_node)
                    add_node.append(new_node)
                    remove_ids.append(inp)
            elif search_node in black:
                if w_even:
                    black.append(new_node)
                    added_node.append(new_node)
                    add_node.append(new_node)
                    remove_ids.append(inp)
                else:
                    white.append(new_node)
                    added_node.append(new_node)
                    add_node.append(new_node)
                    remove_ids.append(inp)
    for rm in remove_ids:
        inputs.remove(rm)


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

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

n=int(input())
E=[]
W=[]
node_l=np.zeros(n)
node_l[0]=1
for i in range(n-1):
    u,v,w=map(int,input().split())
    #print(u,v,w)
    E.append([u,v])
    W.append(w)
#print(E,W)

def bfs(node,node_l,l,w_l):
    i=0
    A=[]
    L=[]
    for edge in l:
        if edge[0]==node and node_l[edge[1]-1]==0:
            L.append(edge[1])
            A.append(i)
        elif edge[1]==node and node_l[edge[0]-1]==0:
            L.append(edge[0])
            A.append(i)
        i+=1
    if L==[]:
        return
    for j in range(len(L)):
        if W[A[j]]%2==0:
            node_l[L[j]-1]=node_l[node-1]
            bfs(L[j],node_l,l,w_l)
        else:
            node_l[L[j]-1]=node_l[node-1]*-1
            bfs(L[j],node_l,l,w_l)
    return
bfs(1,node_l,E,W)
for i in range(n):
    if node_l[i]==1:
        print('1',end='\n')
    else:
        print('0',end='\n')

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
import sys
input = sys.stdin.readline
N = int(input())

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

key = 1
# print(key)
paint_dict = dict()

q = [key]
paint_dict[key] = 0

idx = 0
while idx < N:
    k = q[idx]
    #print("k", k, paint_dict[k])
    for to, w in tree_dict[k]:
        if to not in q[:idx]:
            if (w + paint_dict[k]) % 2 == 0:
                paint_dict[to] = 0
            else:
                paint_dict[to] = 1
            #print(paint_dict[to], to, w)
            q.append(to)
    idx += 1
for i in range(N):
    print(paint_dict[i+1])

Submission status: Time Limit Exceeded

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

import queue
ans=[-1 for i in range(n)]
ans[0]=0

fin=[]
q=queue.Queue()
q.put(1)

while  (set(fin)!=set(range(1,n+1))):
    p=q.get()
    fin.append(p)
    t=[i for i, x in enumerate(u) if x == p ]
    
    for i in t:

        if v[i] not in fin:
            q.put(v[i])
        if w[i]==0:
            ans[v[i]-1]=ans[p-1]
        else:
            if ans[p-1]==0:
                ans[v[i]-1]=1
            else:
                ans[v[i]-1]=0
        
    t=[i for i, x in enumerate(v) if x == p]

    for i in t:
        if u[i] not in fin:
            q.put(u[i])        
        if w[i]==0:
            ans[u[i]-1]=ans[p-1]
        else:
            if ans[p-1]==0:
                ans[u[i]-1]=1
            else:
                ans[u[i]-1]=0
    
    
for i in ans:
    print(i)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque

input = sys.stdin.readline

N = int(input())
nodes = deque()
for i in range(N - 1):
    nodes.append(list(map(int, input().split())))

B, W = set(), set()
u, v, w = nodes.popleft()
if w % 2 == 0:
    B.add(u)
    B.add(v)
else:
    B.add(u)
    W.add(v)

while len(nodes) != 0:
    u, v, w = nodes.popleft()
    if w % 2 == 0:
        if u in B or v in B:
            B.add(u)
            B.add(v)
        elif u in W or v in W:
            W.add(u)
            W.add(v)
        else:
            nodes.append([u, v, w])
    else:
        if u in B or v in W:
            B.add(u)
            W.add(v)
        elif u in W or v in B:
            W.add(u)
            B.add(v)
        else:
            nodes.append([u, v, w])

ans = [0] * N
for x in W:
    ans[x - 1] = 1
for x in ans:
    print(x)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())

edges = []
for i in range(n-1):
	edges.append(list(map(int, input().split())))
edges = sorted(edges, key=lambda x: x[0])


colors = [-1]*n
first = edges.pop(0)
u,v,w = first
colors[u-1] = 0
if w%2==0:
	colors[v-1] = 0
else:
	colors[v-1] = 1


found = True
while edges:
	for i in range(len(edges)):
		u,v,w = edges[i]
		if colors[u-1]==-1 and colors[v-1]==-1 and found:
			if i==len(edges)-1:
				found = False
			continue
		else:
			if found == False:
				colors[u-1] = 0
				if w%2==0:
					colors[v-1] = 0
				else:
					colors[v-1] = 1
					
			if colors[u-1]==-1 and colors[v-1]!=-1:
				u,v = v,u

			if w%2==0:
				colors[v-1] = colors[u-1]
			else:
				if colors[u-1] == 1:
					colors[v-1] = 0
				else:
					colors[v-1] = 1
			edges.pop(i)
			found = True
			break

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

Submission status: Time Limit Exceeded

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

T = sorted(T, key = lambda x: (x[0],x[1]))
T = deque(T)
A = [-1 for k in range(N)]
A[0] = 0

while len(T) > 0:
    t = T.popleft()
    u = t[0]-1
    v = t[1]-1
    w = t[2]
    if w%2 == 0:
        if A[u] == 0 and A[v] == -1:
            A[v] = 0
        elif A[u] == 1 and A[v] == -1:
            A[v] = 1
        elif A[u] == -1 and A[v] == 0:
            A[u] = 0
        elif A[u] == -1 and A[v] == 1:
            A[u] = 1
        elif A[u] == -1 and A[v] == -1:
            T.append([u+1,v+1,w])
    else:
        if A[u] == 0 and A[v] == -1:
            A[v] = 1
        elif A[u] == 1 and A[v] == -1:
            A[v] = 0
        elif A[u] == -1 and A[v] == 0:
            A[u] = 1
        elif A[u] == -1 and A[v] == 1:
            A[u] = 0
        elif A[u] == -1 and A[v] == -1:
            T.append([u+1,v+1,w])

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

Submission status: Time Limit Exceeded

Solution code:
import sys


def input():
    return sys.stdin.readline()[:-1]


N = int(input())
A = [list(map(int, input().split())) for i in range(N-1)]
A = [(e[0] - 1, e[1] - 1, e[2]) if e[0] <= e[1] else (e[1] - 1, e[0] - 1, e[2]) for e in A]

B = {i: [] for i in range(N)}  # かく頂点がどの頂点と繋がっているか
C = {(e[0], e[1]): e[2] for e in A}  # へんのながさ
# print(C)
for e in A:
    B[e[0]].append(e[1])
    B[e[1]].append(e[0])
# print(B)
not_visited = [1 for i in range(N)]
not_visited[0] = 0
color = [-1 for i in range(N)]
color[0] = 0  # node 0は0色
beam = [0]
while True:
    now = beam[-1]
    for b in B[now]:
        if not_visited[b]:
            edge = (now, b) if now <= b else (b, now)
            # print(edge)
            if C[edge] %2 ==0:
                color[b] = color[now]
            else:
                color[b] = 1 - color[now]
            not_visited[b] = 0
            beam.insert(0, b)
    beam.pop()
    if sum(not_visited) == 0:
        break

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

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import numpy as np
n = int(input())
u=[]
v=[]
w=[]
for i in range(n-1):
  a, b, c = map(int, input().split())
  u.append(a)
  v.append(b)
  w.append(c)
tree=np.ones(n)*(-1)
points=[1]
tree[0] = 0
flag=True
while flag:
  for i in range(n-1):
    if u[i] == points[0]:
      points.append(v[i])
      if w[i]%2 == 0:
        if tree[v[i]-1]==-1:
          tree[v[i]-1]=tree[u[i]-1]
      else:
        if tree[v[i]-1]==-1:
          if tree[u[i]-1] ==0:
            tree[v[i]-1]=1
          else:
            tree[v[i]-1]=0
    elif v[i] == points[0]:
      points.append(u[i])
      if w[i]%2 == 0:
        if tree[u[i]-1]==-1:
          tree[u[i]-1]=tree[v[i]-1]
      else:
        if tree[u[i]-1]==-1:
          if tree[v[i]-1] ==0:
            tree[u[i]-1]=1
          else:
            tree[u[i]-1]=0
  del points[0]
  if len(points)==0:
    flag = False
  if (len(tree[tree==-1])==0):
    flag = False
for i in range(n):
  print(int(tree[i]))

Submission status: Time Limit Exceeded

Solution code:
import collections
N = int(input())

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

d = {}
uvw = collections.deque()
for x in sorted(uvw1):
    uvw.append(x)

u, v, w = uvw[0]
d[u] = 0

while len(uvw):
    u, v, w = uvw.popleft()
    if d.get(u, -1) >= 0:
        d[v] = d[u] ^ w
        continue
    elif d.get(v, -1) >= 0:
        d[u] = d[v] ^ w
        continue
    uvw.append((u, v, w))

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

Submission status: Time Limit Exceeded

Solution code:
class Apex:
    edges = ...  # type: List[Edge]

    def __init__(self, color):
        self.edges = []
        self.color = color


class Edge:

    def __init__(self, b, length):
        self.b = b
        self.length = length


class Node:

    def __init__(self, a, b, length):
        self.a = a
        self.b = b
        self.length = length


N = int(input())
nodes = [None] * (N - 1)  # type: List[Node]
for i in range(N - 1):
    u, v, w = list(map(int, input().split()))
    nodes[i] = Node(u, v, w)

apexes = [None] * N  # type: List[Apex]
for i in range(N):
    apexes[i] = Apex(-1)

for i in range(N - 1):
    node = nodes[i]
    a = apexes[node.a - 1]
    b = apexes[node.b - 1]
    a.edges.append(Edge(b, node.length))
    b.edges.append(Edge(a, node.length))

apexes[0].color = 0

count = 1
while True:
    count = 0
    for i in range(N):
        apex = apexes[i]
        if apex.color != -1:
            for edge in apex.edges:
                if edge.b.color == -1:
                    if edge.length % 2 == 0:
                        edge.b.color = apex.color
                    else:
                        if apex.color == 0:
                            edge.b.color = 1
                        else:
                            edge.b.color = 0
        else:
            count += 1
    if count == 0:
        break
for i in range(N):
    print(apexes[i].color)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())

Li = [0] * 2 + [2] * (n -1)

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

while 2 in Li:
    for u, v, w in uvws:
        if w % 2:
            if Li[u] != 2 and Li[v] == 2:
                Li[v] = 1 - Li[u]
            elif Li[u] == 2 and Li[v] != 2:
                Li[u] = 1 - Li[v]
        else:
            if Li[u] != 2 and Li[v] == 2:
                Li[v] = Li[u]
            elif Li[u] == 2 and Li[v] != 2:
                Li[u] = Li[v]

for item in Li[1:]:
    print(item)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
ans = [2] * N
memo = []
Mu = []
Mv = []
Mw = []
for i in range(N-1):
    u, v, w = map(int, input().split())
    Mu.append(u)
    Mv.append(v)
    Mw.append(w)
ans[0] = 1
memo.append(1)
for a in range(N-1):
    for b in memo:
        for c in range(N-1):
            if Mu[c] == b:
                memo.append(Mv[c])
                if Mw[c] % 2 == 0:
                    if ans[b-1] == 1:
                        ans[Mv[c]-1] = 1
                    else:
                        ans[Mv[c]-1] = 0
                else:
                    if ans[b-1] == 1:
                        ans[Mv[c]-1] = 0
                    else:
                        ans[Mv[c]-1] = 1
            elif Mv[c] == b:
                memo.append(Mu[c])
                if Mw[c] % 2 == 0:
                    if ans[b-1] == 1:
                        ans[Mu[c]-1] = 1
                    else:
                        ans[Mu[c]-1] = 0
                else:
                    if ans[b-1] == 1:
                        ans[Mu[c]-1] = 0
                    else:
                        ans[Mu[c]-1] = 1
for e in ans:
    print(e)