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:
#ABC126D-EvenRelation.py

import sys
import numpy as np

def main():
    #buffer = sys.stdin.buffer
    N = int(sys.stdin.readline())
    #UVW =  np.frombuffer(buffer.read((N-1)*4), dtype="b")
    #UVW = UVW.reshape((N-1,4))[:,:-1]
    UVW = [list(map(int, sys.stdin.readline().split())) for _ in range(N-1)]
    distanceList = [0]*N
    connectSet = {1}


    while True:
        s = len(UVW)
        if s == 0:
            break
        for i in range(s):
            u = UVW[i][0]
            v = UVW[i][1]
            w = UVW[i][2]
            if u in connectSet:
                if distanceList[v-1] == 0:
                    distanceList[v-1] = w + distanceList[u-1]
                    connectSet.add(v)
                UVW.pop(i)
                break
            elif v in connectSet:
                if distanceList[u-1] == 0:
                    distanceList[u-1] = w + distanceList[v-1]
                    connectSet.add(u)
                UVW.pop(i)
                break

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



if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
#5888164
N = int(input())
edge = [[] for _ in range(N)]
ans = [-1] * N
for i in range(N-1):
    u,v,w = map(int,input().split())
    u -= 1
    v -= 1
    w %= 2
    edge[u].append((v,w))
    edge[v].append((u,w))

stack = [(e,0) for e in edge[0]]
ans[0] = 0

while len(stack) > 0:
    e,c = stack.pop(0)
    n,w = e[0],e[1]
    if ans[n] >= 0:
        continue
    ans[n] = (c + w) % 2
    stack += [(e,ans[n]) for e in edge[n]]

for a in ans:
    print(a)

Submission status: Time Limit Exceeded

Solution code:
import copy

N = int(input())
lst = []
ctr_lst = []
ver_lst = []

class vertex:
	# idは頂点の番号
	# adj_idは隣り合う頂点の番号
	# adj_binは隣り合う頂点の偶奇
	# acmは累積距離
	# colorは色(初期は-1,0か1に塗り分け)
	def __init__(self, id):
		self.id = id
		self.adj_id = []
		self.adj_bin = []
		self.acm = 10000000000
		self.color = -1
		self.output = 0
	
# 頂点情報をリストに登録	
for i in range(N):
	ver_lst.append(vertex(i + 1))

# input
for n in range(N - 1):
	u, v, w = map(int, input().split())
	# wは偶数か奇数かの情報を持てばよい
	if w % 2 == 0:
		w = 0
	else:
		w = 1
	# ver_lstには頂点nの情報がn-1番目に格納されている
	ver_lst[u - 1].adj_id.append(v)
	ver_lst[u - 1].adj_bin.append(w)
	ver_lst[v - 1].adj_id.append(u)
	ver_lst[v - 1].adj_bin.append(w)
	
for i in range(len(ver_lst)):
	if len(ver_lst[i].adj_id) == 1:
		start_ver = i
		break
# print(ver_lst[i].id)
		
#幅優先探索で、累計距離を求める
Q = []
ver_lst[i].color = 0
ver_lst[i].acm = 0
Q.append(ver_lst[i])

while len(Q) != 0:
	u = Q.pop(0)
	# print(u.acm)
	for i in u.adj_id:
		if ver_lst[i - 1].color == -1:
			ver_lst[i - 1].color = 0
			# acmを求める処理
			for j in u.adj_id:
				# print("i, j = {}, {}".format(i, j))
				if j == ver_lst[i - 1].id:
					# print("u.acm + u.adj_bin[u.adj_id.index(j)] = {} + {}".format(u.acm, u.adj_bin[u.adj_id.index(j)]))
					ver_lst[i - 1].acm = (u.acm + u.adj_bin[u.adj_id.index(j)]) % 2 
					break
			Q.append(ver_lst[i - 1])
			# print(Q)
	u.color = 1

for i in range(N):
	print(ver_lst[i].acm)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque


def bfs(s):
    flag_list[s] = 1
    color_list[s] = 0
    q.append(s)
    while len(q)>0:
        u = q.popleft()
        for v, w in enumerate(m_list[u]):
            if w > 0 and flag_list[v] == 0:
                flag_list[v] = 1
                if w%2 == 0:
                    color_list[v] = color_list[u]
                else:
                    color_list[v] = (color_list[u]+1)%2
                q.append(v)
        flag_list[u] = 2


if __name__ == "__main__":
    input = sys.stdin.readline
    n = int(input())
    m_list = [[0]*n for _ in range(n)]
    color_list = [0]*n
    flag_list = [0]*n
    q = deque([])
    for _ in range(n-1):
        u, v, w = map(int, input().split())
        m_list[u-1][v-1] = w
        m_list[v-1][u-1] = w
    bfs(0)
    for color in color_list:
        print(color)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
tree = []
for i in range(0, N):
	tree.append([])
for i in range(0, N-1):
	u, v, w = map(int, input().split())
	tree[u-1].append([v-1, w])
	tree[v-1].append([u-1, w])
oddeven = []
for i in range(0, N):
	oddeven.append(-1)
queue = [[0, 0]]
while queue != []:
	now = queue.pop(0)
	oddeven[now[0]] = now[1]%2
	for i in range(0, len(tree[now[0]])):
		if oddeven[tree[now[0]][i][0]] == -1:
			queue.append([tree[now[0]][i][0], now[1]+tree[now[0]][i][1]])
for i in range(0, N):
	print(oddeven[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())

connect_list = [ [] for i in range(n) ]
distance_list = [ -1 for i in range(n) ]
color_list = [ "Gray" for i in range(n) ]
distance_list[0] = 0

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

search_list = [0]

while search_list != []:
	s = search_list[0]
	for i in connect_list[s]:
		if distance_list[i[0]] == -1:
			distance_list[i[0]] = (distance_list[s] + i[1]) % 2
			search_list.append(i[0])
	del search_list[0]

for i in distance_list:
	print(i)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
u = [-1] * n
u[0] = 0
a = []
for i in range(n-1):
    u1, u2, w = [int(j) for j in input().split()]
    u1, u2 = u1 - 1, u2 - 1
    a.append((u1, u2, w))
a.sort()
i=0
while a:
    j=a[i]
    if u[j[0]] != -1:
        u[j[1]] = (u[j[0]] + j[2]) % 2
        del a[i]
        i=0
    elif u[j[1]] != -1:
        u[j[0]] = (u[j[1]] + j[2]) % 2
        del a[i]
        i = 0
    else:
        i+=1

for i in u:
    print(i)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
u = [-1] * n
u[0] = 0
a = []
for i in range(n-1):
    u1, u2, w = [int(j) for j in input().split()]
    u1, u2 = u1 - 1, u2 - 1
    a.append((u1, u2, w))
i=0
while a:
    j=a[i]
    if u[j[0]] != -1:
        u[j[1]] = (u[j[0]] + j[2]) % 2
        del a[i]
        i=0
    elif u[j[1]] != -1:
        u[j[0]] = (u[j[1]] + j[2]) % 2
        del a[i]
        i = 0
    else:
        i+=1

for i in u:
    print(i)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
u = [-1] * n
u[0] = 0
a = []
for i in range(n-1):
    u1, u2, w = [int(j) for j in input().split()]
    u1, u2 = u1 - 1, u2 - 1
    a.append((u1, u2, w))
i=0
while a:
    j=a[i]
    if u[j[0]] != -1:
        u[j[1]] = (u[j[0]] + j[2]) % 2
        del a[i]
        i=-1
    elif u[j[1]] != -1:
        u[j[0]] = (u[j[1]] + j[2]) % 2
        del a[i]
        i = -1
    i+=1

for i in u:
    print(i)

Submission status: Time Limit Exceeded

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

n = int(input())
uvw = [[0] * 3 for i in range(n-1)]
for i in range(n-1):
    uvw[i][0],uvw[i][1],uvw[i][2] = map(int,input().split())
color = [-1] * (n+1)

uvw.sort()
color[1] = 0

loop = True
while loop:
    for i in range(n-1):
        if color[uvw[i][0]] == 0:
            if uvw[i][2] % 2 == 0:
                color[uvw[i][1]] = 0
            else:
                color[uvw[i][1]] = 1
        elif color[uvw[i][0]] == 1:
            if uvw[i][2] % 2 == 0:
                color[uvw[i][1]] = 1
            else:
                color[uvw[i][1]] = 0
        if color[uvw[i][1]] == 0:
            if uvw[i][2] % 2 == 0:
                color[uvw[i][0]] = 0
            else:
                color[uvw[i][0]] = 1
        elif color[uvw[i][1]] == 1:
            if uvw[i][2] % 2 == 0:
                color[uvw[i][0]] = 1
            else:
                color[uvw[i][0]] = 0
    loop = False
    for i in range(1,n):
        if color[i] == -1:
            loop = True
            break

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

Submission status: Time Limit Exceeded

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

graph=[[0]*N for _ in range(N)]
for u,v,w in uvw:
    graph[u - 1][v - 1] = w
    graph[v - 1][u - 1] = w

colors=[2]*N
nonvisited=[p for p in range(1,N)]
queue=deque([0])
colors[0]=0
while len(queue)>0:
    x=queue.popleft()
    if x!=0:
        nonvisited.pop(nonvisited.index(x))
    if len(nonvisited)==0:
        break
    for j in nonvisited:
        if graph[x][j]!=0:
            #nonvisited.pop(nonvisited.index(j))
            queue.append(j)
            colors[j]=(colors[x]+graph[x][j])%2
for p in colors:
    print(p)

Submission status: Time Limit Exceeded

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

graph=[[0]*N for _ in range(N)]
for u,v,w in uvw:
    graph[u - 1][v - 1] = w
    graph[v - 1][u - 1] = w
colors=[2]*N
queue=deque([0])
colors[0]=0
while len(queue)>0:
    x=queue.popleft()
    if all(colors[h]!=2 for h in range(N)):
        break
    for j in range(N):
        if colors[j]==2 and graph[x][j]!=0:
            queue.append(j)
            colors[j]=(colors[x]+graph[x][j])%2
for p in colors:
    print(p)

Submission status: Time Limit Exceeded

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

graph=[[0]*N for _ in range(N)]
for u,v,w in uvw:
    graph[u - 1][v - 1] = w
    graph[v - 1][u - 1] = w
colors=[2]*N
queue=deque([0])
colors[0]=0
while len(queue)>0:
    x=queue.popleft()
    for j in range(N):
        if colors[j]==2 and graph[x][j]!=0:
            queue.append(j)
            if graph[x][j]%2==0:
                colors[j]=colors[x]
            else:
                colors[j]=0 if colors[x]==1 else 1
for p in colors:
    print(p)

Submission status: Time Limit Exceeded

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

graph=[[0]*N for _ in range(N)]
for u,v,w in uvw:
    graph[u - 1][v - 1] = w
    graph[v - 1][u - 1] = w
colors=[2]*N
queue=[0]
colors[0]=0
while len(queue)>0:
    x=queue.pop(0)
    for j in range(N):
        if graph[x][j]!=0 and colors[j]==2:
            queue.append(j)
            if graph[x][j]%2==0:
                colors[j]=colors[x]
            else:
                colors[j]=0 if colors[x]==1 else 1
for p in colors:
    print(p)

Submission status: Time Limit Exceeded

Solution code:

from collections import deque

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

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


stack = deque()
stack.append(1)
#stack=[1]
visitted=[]
ans=[0]*n

while stack:
    cur = stack.pop()
    pre=ans[cur-1]
    visitted.append(cur)
    for v, w in tree[cur]:
        if v in visitted:
            continue
        #if v in stack:
        #    continue
        if w % 2 == 1:
            ans[v-1]=(pre+1)%2
        else:
            ans[v-1]=pre
        stack.append(v)

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

#for i in ans:
#    print(i)

Submission status: Time Limit Exceeded

Solution code:
"""
解説をもとに作成
"""


def solve():
    N = int(input())
    uvw = []
    result = [-1] * N
    for i in range(N - 1):
        lst = [int(i) for i in input().split()]
        uvw.append([lst[0],
                    lst[1],
                    lst[2]])
    # 木の頂点を求める
    # -> 任意の場所で良い. 1 とする.
    # 頂点から順に塗っていく
    result[0] = False
    result, uvw = paint(uvw, 1, result)
    for i in result:
        print(int(i))


def paint(uvw, num, result):
    import pprint
    target_uvw = []
    '''num につながる枝のデータを抽出'''
    # print('頂点 {} について探索'.format(num))
    for t in uvw:
        # print(t)
        if t[0] == num or t[1] == num:
            target_uvw.append(t)
    # print('探索対象 {} 件'.format(len(target_uvw)))
    # pprint.pprint(target_uvw)
    '''次につながる頂点をすべて検索して色塗り'''
    next_nums = []
    for t in target_uvw:
        uvw.remove(t)
        target = t[0] if t[0] != num else t[1]
        result[target - 1] = result[num - 1] if t[2] % 2 == 0 else not (
        result[num - 1])
        next_nums.append(target)
    '''次の頂点データについて検索を行う'''
    for nn in next_nums:
        result, uvw = paint(uvw, nn, result)
    return result, uvw


if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

dist = [0 for i in range(n)]
stack = deque([0])
used = [0]
while( len(stack) != 0 ):
    current = stack.popleft()
    current_dist = dist[current]

    for neibor_n, neibor_w in neibors[current]:
        if neibor_n not in used:
            used.append( neibor_n )
            stack.append( neibor_n )
            dist[neibor_n] = (neibor_w + current_dist) % 2  

for item in dist:
    print(item)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque


class dfs():
    
    def __init__(self, n, el):
        self.n = n
        self.el = el

        self.evenl = [0 for i in range(n)]
        #self.neibors = dict([(i,[]) for i in range(n)])
        self.neibors = [[] for i in range(n)]


    def calc(self, nf):
        used = []
        used.append( nf )
        stack = deque([ nf ])
        while( len(stack) != 0 ):
            current = stack.popleft()
            current_dist = self.evenl[current]

            for neibor in self.neibors[current]:
                neibor_n, neibor_w = neibor
                if neibor_n not in used:
                    used.append( neibor_n )
                    stack.append( neibor_n )
                    self.evenl[neibor_n] = self.xor( neibor_w, current_dist )                        

    def xor(self, x1,x2):
        return (x1 + x2) % 2

    def set_neibors(self):
        for e in self.el:
            u,v,w = e
            self.neibors[u-1].append( (v-1,w%2) )
            self.neibors[v-1].append( (u-1,w%2) )


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

m = dfs(n,el)
m.set_neibors()
m.calc(0)

for item in m.evenl:
    print(item)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque


class dfs():
    
    def __init__(self, n, el):
        self.n = n
        self.el = el

        self.evenl = [0 for i in range(n)]
        self.neibors = dict([(i,[]) for i in range(n)])


    def calc(self, nf):
        used = []
        used.append( nf )
        stack = deque([ nf ])
        while( len(stack) != 0 ):
            current = stack.popleft()
            current_dist = self.evenl[current]
            for neibor in self.neibors[current]:
                neibor_n, neibor_w = neibor
                if neibor_n not in used:
                    used.append( neibor_n )
                    stack.append( neibor_n )
                    self.evenl[neibor_n] = self.xor( neibor_w, current_dist )                        

    def xor(self, x1,x2):
        return (x1 + x2) % 2

    def set_neibors(self):
        for e in self.el:
            u,v,w = e
            self.neibors[u-1].append( (v-1,w%2) )
            self.neibors[v-1].append( (u-1,w%2) )


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

m = dfs(n,el)
m.set_neibors()
m.calc(0)

for item in m.evenl:
    print(item)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
L=[[] for i in range(n)]
for i in range(n-1):
    u,v,w=map(int, input().split())
    u-=1
    v-=1
    L[u].append([v,w])
    L[v].append([u,w])
ans=[-1]*n
ans[0]=0
stack=[0]
while stack:
    v=stack[0]
    stack=stack[1:]
    for u, w in L[v]:
        if ans[u]!=-1:
            continue
        ans[u]=(ans[v]+w)%2
        stack.insert(0,u)
for a in ans:
    print(a)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
tree = [[] for i in range(n+1)]

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

stack=[1]
visitted=[]
ans=[0]*n

while stack:
    cur = stack.pop()
    pre=ans[cur-1]
    visitted.append(cur)
    for v, w in tree[cur]:
        if v in visitted:
            continue
        #if v in stack:
        #    continue
        if w % 2 == 1:
            ans[v-1]=(pre+1)%2
        else:
            ans[v-1]=pre
        stack.append(v)

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

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
tree = [[] for i in range(n+1)]

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

stack=[1]
visitted=[]
ans=[0]*n

while stack:
    cur = stack.pop()
    visitted.append(cur)
    for v, w in tree[cur]:
        if v in visitted:
            continue
        #if v in stack:
        #    continue
        if w % 2 == 1:
            ans[v-1]=(ans[cur-1]+1)%2
        else:
            ans[v-1]=ans[cur-1]
        stack.append(v)

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

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
tree = [[] for i in range(n+1)]

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

stack=[1]
visitted=[]
ans=[0]*n

while stack:
    cur = stack.pop()
    visitted.append(cur)
    for v, w in tree[cur]:
        if v in visitted:
            continue
        #if v in stack:
        #    continue
        if w % 2 == 1:
            ans[v-1]=(ans[cur-1]+1)%2
        else:
            ans[v-1]=ans[cur-1]
        stack.append(v)

for i in ans:
    print(i)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
tree = [[] for i in range(n+1)]

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

stack=[1]
visitted=[]
ans=[0]*(n+1)

while stack:
    cur = stack.pop()
    visitted.append(cur)
    for v, w in tree[cur]:
        if v in visitted:
            continue
        if v in stack:
            continue
        if w % 2 == 1:
            ans[v]=(ans[cur]+1)%2
        else:
            ans[v]=ans[cur]
        stack.append(v)

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

Submission status: Time Limit Exceeded

Solution code:
n = int(input())

tree = [[] for i in range(n+1)]

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

stack=[1]
visitted=[]
ans=[0]*(n+1)

while stack:
    cur = stack.pop()
    visitted.append(cur)
    for v, w in tree[cur]:
        if v in visitted:
            continue
        if w % 2 == 1:
            ans[v]=(ans[cur]+1)%2
        else:
            ans[v]=ans[cur]
        stack.append(v)

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

Submission status: Time Limit Exceeded

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


def func(v, color):
    if visited[v] != 2:
        return
    visited[v] = color
    for next_v in range(n):
        if graph[v][next_v]:  # vとnext_vが繋がっている場合
            if graph[v][next_v] & 1:
                func(next_v, 1-color)
            else:
                func(next_v, color)


n = int(input())
side = [[int(x) for x in sys.stdin.readline().split()] for _ in range(n-1)]
graph = [[0] * n for _ in range(n)]
visited = [2] * n  # 2は未訪問 0は白 黒は1

for u, v, w in side:
    graph[u-1][v-1] = graph[v-1][u-1] = w

func(0, 0)

for i in visited:
    print(i)

Submission status: Time Limit Exceeded

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


def func(v, color):
    if visited[v] != 2:
        return
    visited[v] = color
    for next_v in range(n):
        if graph[v][next_v] != 0:  # vとnext_vが繋がっている場合
            if graph[v][next_v] % 2 == 0:
                func(next_v, color)
            else:
                func(next_v, color ^ 1)


n = int(input())
side = [[int(x) for x in sys.stdin.readline().split()] for _ in range(n-1)]
graph = [[0] * n for _ in range(n)]
visited = [2] * n  # 2は未訪問 0は白 黒は1

for u, v, w in side:
    graph[u-1][v-1] = graph[v-1][u-1] = w

func(0, 0)

for i in visited:
    print(i)

Submission status: Time Limit Exceeded

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


def func(v, color):
    if visited[v] != 2:
        return
    visited[v] = color
    for next_v in range(n):
        if graph[v][next_v] != 0:  # vとnext_vが繋がっている場合
            if graph[v][next_v] % 2 == 0:
                func(next_v, color)
            else:
                func(next_v, color ^ 1)


n = int(input())
side = [list(map(int, sys.stdin.readline().split())) for _ in range(n-1)]
graph = [[0] * n for _ in range(n)]
visited = [2] * n  # 2は未訪問 0は白 黒は1

for u, v, w in side:
    graph[u-1][v-1] = w
    graph[v-1][u-1] = w

func(0, 0)

for i in visited:
    print(i)

Submission status: Time Limit Exceeded

Solution code:

import copy

class dfs():
    
    def __init__(self, n, el):
        self.n = n
        self.el = el

        self.evenl = [1 for i in range(n)]
        self.g = [[0 for j in range(n)] for i in range(n)]
        self.pd = set([i for i in range(n)])

    def calc(self, nf, pd):
        pd.remove(nf)
        for i in pd:
            w = self.g[nf][i]
            if w > 0:
                if self.evenl[nf] == 1:
                    if w % 2 == 0:
                        self.evenl[i] = 1
                    else:
                        self.evenl[i] = 0
                else:
                    if w % 2 == 0:
                        self.evenl[i] = 0
                    else:
                        self.evenl[i] = 1

                self.g[nf][i] = 0
                self.g[i][nf] = 0

                self.calc(i, copy.deepcopy(pd) )

    def set_g(self):
        for e in self.el:
            u,v,w = e
            self.g[u-1][v-1] = w
            self.g[v-1][u-1] = w


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

m = dfs(n,el)
m.set_g()
m.calc( 0, set([i for i in range(n)]) )

for item in m.evenl:
    print(item)

Submission status: Time Limit Exceeded

Solution code:


class dfs():
    
    def __init__(self, n, el):
        self.n = n
        self.el = el

        self.evenl = [1 for i in range(n)]
        self.g = [[0 for j in range(n)] for i in range(n)]

    def calc(self, nf):
        for i in range( len(self.g) ):
            w = self.g[nf][i]
            if w > 0:
                if self.evenl[nf] == 1:
                    if w % 2 == 0:
                        self.evenl[i] = 1
                    else:
                        self.evenl[i] = 0
                else:
                    if w % 2 == 0:
                        self.evenl[i] = 0
                    else:
                        self.evenl[i] = 1

                self.g[nf][i] = 0
                self.g[i][nf] = 0

                self.calc(i)

    def set_g(self):
        for e in self.el:
            u,v,w = e
            self.g[u-1][v-1] = w
            self.g[v-1][u-1] = w


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

m = dfs(n,el)
m.set_g()
m.calc(0)

for item in m.evenl:
    print(item)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())

dist = [[float("inf") 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
    dist[b][a] = w
for i in range(1,n+1): dist[i][i]=0

for k in range(1,n+1):
    for i in range(1,n+1):
        for j in range(1,n+1):
            dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])


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

Submission status: Time Limit Exceeded

Solution code:

N = int(input())
uvw = []
colors = [-1,]

for i in range(N-1):
    kari = list(map(int,input().split()))
    uvw.append(kari)
    colors.append(-1)


now_color = 0

uvw.sort()

colors[0] = 0
nokori = N-1

#print (uvw)
#print (colors)

while nokori>0:

    for i in range(len(uvw)):

        if colors[uvw[i][0]-1] != -1 :
            if uvw[i][2] % 2 == 0:
                colors[uvw[i][1]-1] = colors[uvw[i][0]-1]
                

            elif colors[uvw[i][0]-1]==0:
                colors[uvw[i][1]-1] = 1
               
            else:
                colors[uvw[i][1]-1] = 0

            del uvw[i]
            nokori -= 1
            break

        if colors[uvw[i][1]-1] != -1 :
            if uvw[i][2] % 2 == 0:
                colors[uvw[i][0]-1] = colors[uvw[i][1]-1]

            elif colors[uvw[i][1]-1]==0:
                colors[uvw[i][0]-1] = 1

            else:
                colors[uvw[i][0]-1] = 0

            del uvw[i]
            nokori -= 1
            break


for i in colors:
    print (i)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
l=[[] for _ in range(n)]
cost=[[] for _ in range(n)]
ans=[-1 for _ in range(n)]
ans[0]=0
q=[]
q.append(0)
for iii in range(n-1):
  a,b,w=[int(_) for _ in input().split()]
  a-=1
  b-=1
  l[a].append(b)
  cost[a].append(w)
  l[b].append(a)
  cost[b].append(w)
while not q==[]:
  v=q[0]
  q=q[1:]
  for jjj in range(len(l[v])):
    u = l[v][jjj]
    w = cost[v][jjj]
    if not ans[u]==-1:
      continue
    ans[u]=(ans[v]+w)%2
    q.append(u)
for a in ans:
  print(a)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
node_array = [list(map(int, input().split())) for i in range(N - 1)]
# print(node_array)
tree_num_array = [-1] * N
# print(tree_num_array)

tree_num_max = -1
tree = {}
last_tree_num = -1
for node in node_array:
    # print(tree)
    i, j, w = node
    i = i - 1
    j = j - 1
    if tree_num_array[i] == -1 and tree_num_array[j] == -1:
        # print(i, j, "added")
        tree_num_max += 1
        tree[tree_num_max] = {i: 0, j: w}
        tree_num_array[i] = tree_num_max
        tree_num_array[j] = tree_num_max
        last_tree_num = tree_num_max
        continue
    elif tree_num_array[i] == -1:
        # print(i, "added")
        tree_num_added = tree_num_array[j]
        tree[tree_num_added][i] = tree[tree_num_added][j] + w
        tree_num_array[i] = tree_num_added
        last_tree_num = tree_num_added
    elif tree_num_array[j] == -1:
        # print(j, "added")
        tree_num_added = tree_num_array[i]
        tree[tree_num_added][j] = tree[tree_num_added][i] + w
        tree_num_array[j] = tree_num_added
        last_tree_num = tree_num_added
    else:
        tree_num_added = tree_num_array[i]
        tree_num_united = tree_num_array[j]
        # print(tree_num_added, tree_num_united, "united")
        tree_value_i = tree[tree_num_added][i]
        tree_value_j = tree[tree_num_united][j]
        for key, value in tree[tree_num_united].items():
            tree[tree_num_added][
                key] = tree_value_i + w + abs(value - tree_value_j)
            tree_num_array[int(key)] = tree_num_added
        last_tree_num = tree_num_added
# print(tree)
ans_dict = sorted(tree[last_tree_num].items(), key=lambda x: int(x[0]))
# print(ans_dict)
for distance in ans_dict:
    print(distance[1] % 2)

Submission status: Time Limit Exceeded

Solution code:
def t(d, a, r, i, c):
  if r[i]!=-1:
    return
  r[i]=c
  for aj in a[i]:
    t(d, a, r, aj, (c+d[i][aj])%2)

N, = list(map(int, input().split()))
d = []
for i in range(N):
  d.append([-1 for j in range(N)])
a = [[] for i in range(N)]
for i in range(N-1):
  u, v, w = list(map(int, input().split()))
  u -= 1
  v -= 1
  d[u][v] = w%2
  d[v][u] = w%2
  a[u].append(v)
  a[v].append(u)
r = [-1 for i in range(N)]
t(d, a, r, 0, 0)
for i in range(N):
  print(r[i])

Submission status: Time Limit Exceeded

Solution code:
import sys
import queue

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

q = queue.Queue()
q.put(0)
paint_list[0] = 0

while not q.empty():
    node = q.get()
    for target in range(N):
        dist = edges[node][target]
        if dist != -1 and paint_list[target] == -1:
            paint_list[target] = paint_list[node] ^ dist
            q.put(target)
print("\n".join(map(str, paint_list)))

Submission status: Time Limit Exceeded

Solution code:
import sys
import queue

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

q = queue.Queue()
q.put(0)
paint_list[0] = 0
is_visited = [0]

while not q.empty():
    node = q.get()
    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)
            q.put(target)
print("\n".join(map(str, paint_list)))