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:
N = int(input())
a = set([1])
b = set([])
l = []
for i in range(N - 1):
	l.append(list(map(int, input().split())))	
l = sorted(l)
i = 0
while i < len(l):
	u, v, w = l[i][0], l[i][1], l[i][2]
	if u not in a and u not in b and v not in a and v not in b:
		l.append(l[i])
	elif u not in a and u not in b:
		u, v = v, u
	if u in a and w % 2 == 0:
		a.add(v)
	elif u in a:
		b.add(v)
	elif u in b and w % 2 == 0:
		b.add(v)
	elif u in b:
		a.add(v)
	i += 1
for i in range(1, N + 1):
	if i in a:
		print('0')
	else:
		print('1')

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
uvwList = []
Dict = {}

for x in range(N-1):
    u, v, w = input().split()
    uvwList.append([str(u), str(v), int(w)])

Dict['1'] = 0

def f(Out, Dict, List):
    if List == []:
        return
    color = Dict[Out]
    for x in List:
        if Out not in x:
            continue
        else:
            if x[0] == Out:
                if x[1] in Dict:
                    continue
                if x[2] % 2 == 1:
                    Dict[x[1]] = 1-color
                else:
                    Dict[x[1]] = color
                f(x[1], Dict, List)
            else:
                if x[0] in Dict:
                    continue
                if x[2] % 2 == 1:
                    Dict[x[0]] = 1-color
                else:
                    Dict[x[0]] = color
                f(x[0], Dict, List)
    return

f('1', Dict, uvwList)

for x in range(1, N+1):
    print(Dict[str(x)])

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
v = [list(map(int,input().split())) for _ in range(n-1)]
g = {}
for a,b,w in v:
    if a not in g:
        g[a] = []
    if b not in g:
        g[b] = []
    g[a].append([b,w])
    g[b].append([a,w])
from collections import deque
queue = deque([[1,0]])
b = deque()
done = set([])
while queue:
    q,d = queue.popleft()
    if d%2==1:
        b.appendleft(q)
    d %= 2
    done |= set([q])
    for new_q in g[q]:
        v_,d_ = new_q
        if v_ not in done:
            queue.appendleft([v_,d+d_])
for i in range(1,n+1):
    if i in b:
        print(1)
    else:
        print(0)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
v = [list(map(int,input().split())) for _ in range(n-1)]
g = {}
for a,b,w in v:
    if a not in g:
        g[a] = []
    if b not in g:
        g[b] = []
    g[a].append([b,w])
    g[b].append([a,w])
from collections import deque
queue = deque([[1,0]])
b = deque()
done = set([])
while queue:
    q,d = queue.popleft()
    if d%2==1:
        b.appendleft(q)
    done |= set([q])
    for new_q in g[q]:
        v_,d_ = new_q
        if v_ not in done:
            queue.appendleft([v_,d+d_])
for i in range(1,n+1):
    if i in b:
        print(1)
    else:
        print(0)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
v = [list(map(int,input().split())) for _ in range(n-1)]
g = {}
for a,b,w in v:
    if a not in g:
        g[a] = []
    if b not in g:
        g[b] = []
    g[a].append([b,w])
    g[b].append([a,w])
from collections import deque
queue = deque([[1,0]])
b = deque()
done = []
while queue:
    q,d = queue.popleft()
    if d%2==1:
        b.appendleft(q)
    done.append(q)
    for new_q in g[q]:
        v_,d_ = new_q
        if v_ not in done:
            queue.appendleft([v_,d+d_])
for i in range(1,n+1):
    if i in b:
        print(1)
    else:
        print(0)

Submission status: Time Limit Exceeded

Solution code:
from queue import Queue

N = int(input())
d = {}
for i in range(N-1):
    u, v, w = map(int, input().split())
    if u in d:
        d[u].append([v, w])
    else:
        d[u] = [[v, w]]
    if v in d:
        d[v].append([u, w])
    else:
        d[v] = [[u, w]]

isChecked = [False for i in range(N)]
ans = [0 for i in range(N)]
q = Queue()
# [current v, sum length]
q.put([1, 0])
while not q.empty():
    v, l = q.get()
    if isChecked[v-1]:
        continue
    ans[v-1] = 0 if l%2 == 0 else 1
    isChecked[v-1] = True
    for u, w in d[v]:
        q.put([u, l+w])

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

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 = min(u_li[i], v_li[i])
    v = max(u_li[i], v_li[i])
    edges.update({(u, v): w_li[i]})

# 連結リストを作成
import itertools
neighbor = {}
node_count = max(max(u_li), max(v_li))
for i, j in itertools.combinations(range(1,node_count+1),2):  # 辺のリストが（小, 大）となっているのが前提。
    if (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 = min(nei, next_node)
            v = max(nei, next_node)
            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:
# coding: utf-8
# Your code here!
n = int(input())

tree= [[] for i in range(n+1)]
cost=[[0 for i in range(n+1)]for j in range(n+1)]
color=[-1 for i in range(n+1)]
que=[]
for i in range(n-1):
    u,v,w=map(int,input().split(' '))
    tree[u].append(v)
    tree[v].append(u)
    cost[u][v]=w
    cost[v][u]=w

que.append(1)
color[1]=0


while(len(que)!=0): 
    node = que.pop()
    for next_node in tree[node]:
        if color[next_node]==-1:
            # print((color[node]+cost[node][next_node])%2)
            color[next_node]=(color[node]+cost[node][next_node])%2
            que.append(next_node)
            # print(color)
for i in range(1,len(color)):
    print(color[i])

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
# Your code here!
n = int(input())

tree= [[] for i in range(n+1)]
cost=[[0 for i in range(n+1)]for j in range(n+1)]
color=[0 for i in range(n+1)]
already=[False for i in range(n+1)]
que=[]
for i in range(n-1):
    u,v,w=map(int,input().split(' '))
    tree[u].append(v)
    tree[v].append(u)
    cost[u][v]=w
    cost[v][u]=w
    if(i==n-2):
        que.append(u)
        color[u]=0
        already[u]=True


while(len(que)!=0): 
    node = que.pop()
    for next_node in tree[node]:
        if already[next_node]==False:
            already[next_node]=True
            # print((color[node]+cost[node][next_node])%2)
            color[next_node]=(color[node]+cost[node][next_node])%2
            que.append(next_node)
            
for i in range(1,len(color)):
    print(color[i])

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
l=[]
for i in range (n-1):
    l.append(list(map(int,input().split())))
ans=[-1 for _ in range (n)]
ans[0]=0
j=2
while j<=n:
    for k in range (n-1):
        if ans[l[k][0]-1]!=-1 and ans[l[k][1]-1]==-1:
            ans[l[k][1]-1]=(ans[l[k][0]-1]+l[k][2])%2
            j+=1
            continue
        if ans[l[k][1]-1]!=-1 and ans[l[k][0]-1]==-1:
            ans[l[k][0]-1]=(ans[l[k][1]-1]+l[k][2])%2
            j+=1
for m in range (n):
    print(ans[m])

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict


def get_data(data_dic, num, check_data):
    for i in range(len(data_dic))[::-1]:
        if data_dic[i][0] == num:
            check_data.add(data_dic[i])
            data_dic.pop(i)
        elif data_dic[i][1] == num:
            data_add = (data_dic[i][1], data_dic[i][0], data_dic[i][2])
            check_data.add(data_add)
            data_dic.pop(i)
    return check_data, data_dic


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


    data_dic = [tuple(map(int, input().split())) for i in range(num - 1)]
    parent_data = [-1 for i in range(num + 1)]
    dist_data = [0 for i in range(num + 1)]

    check_data_now, data_dic = get_data(data_dic, 1, set())
    check_data_next = set()

    while len(check_data_now) > 0:
        parent_list = set()
        for u, v, w in check_data_now:
            parent_data[v] = u
            dist_data[v] = w % 2
            parent_list.add(v)


        for ele in parent_list:
            check_data_next, data_dic = get_data(data_dic, ele, check_data_next)
        check_data_now = check_data_next
        check_data_next = set()

    dist_ori_data = [-1 for i in range(num + 1)]
    dist_ori_data[1] = 0

    for i in range(1, num + 1):
        if dist_ori_data[i] != -1:
            continue
        dist = 0
        now_data = i
        while parent_data[now_data] != -1:
            if dist_ori_data[now_data] != -1:
                dist += dist_ori_data[now_data]
                break
            else:
                dist += dist_data[now_data]
                now_data = parent_data[now_data]
        dist_ori_data[i] = dist % 2

    for i in range(1, num + 1):
        dist = dist_ori_data[i]
        if dist % 2 == 0:
            print(0)
        else:
            print(1)








if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict


def get_data(data_dic, num, check_data):
    for i in range(len(data_dic))[::-1]:
        if data_dic[i][0] == num:
            check_data.add(data_dic[i])
            data_dic.pop(i)
        elif data_dic[i][1] == num:
            data_add = (data_dic[i][1], data_dic[i][0], data_dic[i][2])
            check_data.add(data_add)
            data_dic.pop(i)
    return check_data, data_dic


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


    data_dic = [tuple(map(int, input().split())) for i in range(num - 1)]
    parent_data = [-1 for i in range(num + 1)]
    dist_data = [0 for i in range(num + 1)]

    check_data_now, data_dic = get_data(data_dic, 1, set())
    check_data_next = set()

    while len(check_data_now) > 0:
        parent_list = set()
        for u, v, w in check_data_now:
            parent_data[v] = u
            dist_data[v] = w % 2
            parent_list.add(v)


        for ele in parent_list:
            check_data_next, data_dic = get_data(data_dic, ele, check_data_next)
        check_data_now = check_data_next
        check_data_next = set()


    for i in range(1, num + 1):
        now_data = i
        dist = 0

        while parent_data[now_data] != -1:
            dist += dist_data[now_data]
            now_data = parent_data[now_data]
        if dist % 2 == 0:
            print(0)
        else:
            print(1)








if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
graph = {}
root = -1
for n in range(N-1):
    u, v, w = map(int, input().split())
    u -= 1
    v -= 1

    if root == -1:
        root = u
    if u not in graph:
        graph[u] = {}
    if v not in graph:
        graph[v] = {}
    graph[u][v] = w
    graph[v][u] = w    

answer = [-1] * N
queue = [[root, 0]]
counter = -1
while -1 in answer:
    counter += 1
    node = queue[counter][0]
    depth = queue[counter][1]
    answer[node] = depth
    for n in graph[node]:
        if answer[n] == -1:
            queue.append([n, depth + graph[node][n]])

for a in answer:
   print('0' if a % 2 else '1')

Submission status: Time Limit Exceeded

Solution code:
def solve(string):
    n, *uvw = map(int, string.split())
    uvw = list(zip(uvw[::3], uvw[1::3], uvw[2::3]))
    whites = set([1])
    blacks = set([])
    while len(uvw) > 0:
        tmp = []
        for i in range(len(uvw)):
            t = uvw.pop()
            if t[0] in whites:
                if t[2] % 2 == 0:
                    whites.add(t[1])
                else:
                    blacks.add(t[1])
            elif t[1] in whites:
                if t[2] % 2 == 0:
                    whites.add(t[0])
                else:
                    blacks.add(t[0])
            elif t[0] in blacks:
                if t[2] % 2 == 0:
                    blacks.add(t[1])
                else:
                    whites.add(t[1])
            elif t[1] in blacks:
                if t[2] % 2 == 0:
                    blacks.add(t[0])
                else:
                    whites.add(t[0])
            else:
                tmp.append(t)
        uvw = tmp
    ans = ["0"] * n
    for i in range(n):
        if i + 1 in blacks:
            ans[i] = "1"

    return "\n".join(ans)


if __name__ == '__main__':
    n = int(input())
    print(solve('{}\n'.format(n) + '\n'.join([input() for _ in range(n - 1)])))

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
uu=[]
vv=[]
ww=[]
br=[]
wr=[]
n=int(n)


i=1
while i!=n:
    i=i+1
    u,v,w=input().split(" ")

    u=int(u)
    v=int(v)
    w=int(w)
    uu.append(u)
    uu.append(v)
    vv.append(v)
    vv.append(u)
    ww.append(w)
    ww.append(w)

br.append(uu[0])

if ww[0]%2==0:
    br.append(vv[0])
else:
    wr.append(vv[0])
del uu[0]
del vv[0]
del ww[0]
x=br[0]
i=0

while uu!=[]:
    try:
        while True:
            y=uu.index(x)
            if ww[y]%2==0:
                br.append(vv[y])
            else:
                wr.append(vv[y])
            x=vv[y]
            del uu[y]
            del vv[y]
            del ww[y]
            i=0
    except:
        pass
    try:
        x=br[i]
    except:
        pass
    i=i+1
i=0

while n!=i:
    i=i+1
    try:
        br.index(i)
        print(1)
    except:
        print(0)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
uu=[]
vv=[]
ww=[]
br=[]
wr=[]
n=int(n)


i=1
while i!=n:
    i=i+1
    u,v,w=input().split(" ")

    u=int(u)
    v=int(v)
    w=int(w)
    uu.append(u)
    uu.append(v)
    vv.append(v)
    vv.append(u)
    ww.append(w)
    ww.append(w)

br.append(uu[0])

if ww[0]%2==0:
    br.append(vv[0])
else:
    wr.append(vv[0])
del uu[0]
del vv[0]
del ww[0]
x=br[0]
i=0

while uu!=[]:
    try:
        while True:
            y=uu.index(x)
            if ww[y]%2==0:
                br.append(vv[y])
            else:
                wr.append(vv[y])
            x=vv[y]
            del uu[y]
            del vv[y]
            del ww[y]
            i=0
    except:
        pass
    try:
        x=br[i]
    except:
        i=0
    i=i+1
i=0

while n!=i:
    i=i+1
    try:
        br.index(i)
        print(1)
    except:
        print(0)

Submission status: Time Limit Exceeded

Solution code:
import collections
class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.dist = [0] * n
 
    def root(self, i, d):
        if self.parent[i] == i:
            return i, d
        else:
            self.parent[i], d2 = self.root(self.parent[i], d + self.dist[i])
            return self.parent[i], d2
    
    def find(self, x, y):
        return self.root(x) == self.root(y)
 
    def union(self, i, j, d):
        i2, d1 = self.root(i, 0)
        j2, d2 = self.root(j, 0)
        if i2 < j2 :
            self.parent[j2] = i2
            self.dist[j] = d1 + d
        else:
            self.parent[i2] = j2
            self.dist[i] = d2 + d
            
N = int(input())
ps = [list(map(int, input().split())) for _ in range(N-1)]
ps = collections.deque(ps)
tree = UnionFind(N)
prv = set([1])
while ps:
    i, j, d = ps.popleft()
    if i in prv or j in prv:
        tree.union(i-1, j-1, d)
        prv.add(i)
        prv.add(j)
    else:
        ps.append([i, j, d])

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

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
# IMPORT ###############################################################################################################
import sys                                                      # システム
sys.setrecursionlimit(10**6)                                    # 再帰処理の上限変更
from collections import deque, Counter                          # キュー・個数カウント
from itertools   import accumulate, permutations, combinations  # 累積和・順列・組み合わせ
from operator    import itemgetter                              # ソート補助
from bisect      import bisect_left, bisect_right, bisect       # 二分探索
from heapq       import heappop, heappush                       # プライオリティキュー
from fractions   import gcd                                     # 最大公約数
from math        import ceil, floor, sqrt, cos, sin, tan, pi    # 数学処理
from copy        import deepcopy                                # オブジェクトコピー
import numpy         as np                                      # 数値計算

# MAIN #################################################################################################################
def main():
    # Init #############################################################################################################
    im = InputManager()
    # Input ############################################################################################################
    n = im.inputSingle()
    nodes = [Node(i+1) for i in range(n)]
    for i in range(n-1):
        u, v, w = im.inputMultiple()
        nodes[u-1].addConnection(nodes[v-1], w)
        nodes[v-1].addConnection(nodes[u-1], w)
    # Logic ############################################################################################################
    weights = [-1 for i in range(n)]
    for i in range(n):
        weights[i] = Node.rootFind(nodes[0], nodes[i], [nodes[i]], 0)
    # Output ###########################################################################################################
    # print(weights)
    for weight in weights:
        if weight % 2 == 0:
            print(0)
        else:
            print(1)
    # Return ###########################################################################################################
    return

class Node(object):
    def __init__(self, index):
        self._index = index
        self._connections = []
    
    @property
    def connections(self):
        return self._connections
    
    def addConnection(self, node, weight):
        self._connections.append({"node": node, "weight": weight})
    
    def __eq__(self, other):
        return self._index == other._index
    
    @staticmethod
    def rootFind(targetNode, baseNode, excludeNodes, weight):
        if baseNode == targetNode:
            # print("Founded: " + str(weight))
            return weight
        for connection in baseNode.connections:
            if connection["node"] in excludeNodes:
                continue
            else:
                # print(str(baseNode._index) + " -> " + str(connection["node"]._index) + " : " + str([exclude._index for exclude in excludeNodes]))
                tmpExcludeNodes = deepcopy(excludeNodes)
                tmpExcludeNodes.append(connection["node"])
                calculatedWeight = Node.rootFind(targetNode, connection["node"], tmpExcludeNodes, weight + connection["weight"])
                if calculatedWeight > 0:
                    return calculatedWeight
        # print("Not Founded")
        return -1

# INPUT MANAGER ########################################################################################################
class InputManager(object):
    def __init__(self):
        pass

    @staticmethod
    def inputSingle(dtype=int):
        return dtype(input())
    
    @staticmethod
    def inputMultiple(dtype=int, aslist=False):
        if aslist:
            return list(map(dtype, input().split()))
        else:
            return map(dtype, input().split())

    @staticmethod
    def input2D(h, dtype=int):
        return [list(map(dtype, input().split())) for i in range(h)]

# CALL MAIN ############################################################################################################
main()

Submission status: Time Limit Exceeded

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

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

ans = [-1]*N
ans[0] = 0

for u,v,w in uvw:
    path[u-1].append([v-1,w%2])
    path[v-1].append([u-1,w%2])
    
Q = [0]     
while Q:
    v = Q.pop(0)
    for p,d in path[v]:
        if ans[p] == -1:
            ans[p] = (ans[v]+d)%2
            Q.append(p)
            
for a in ans:
    print(a)

Submission status: Time Limit Exceeded

Solution code:
import collections
class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.dist = [0] * n
 
    def root(self, i, d):
        if self.parent[i] == i:
            return i, d
        else:
            self.parent[i], d2 = self.root(self.parent[i], d + self.dist[i])
            return self.parent[i], d2
    
    def find(self, x, y):
        return self.root(x) == self.root(y)
 
    def union(self, i, j, d):
        i2, d1 = self.root(i, 0)
        j2, d2 = self.root(j, 0)
        if i2 < j2 :
            self.parent[j2] = i2
            self.dist[j] = d1 + d
        else:
            self.parent[i2] = j2
            self.dist[i] = d2 + d
            
N = int(input())
ps = [list(map(int, input().split())) for _ in range(N-1)]
ps.sort()
ps = collections.deque(ps)
tree = UnionFind(N)
prv = set([1])
while ps:
    i, j, d = ps.popleft()
    if i in prv or j in prv:
        tree.union(i-1, j-1, d)
        prv.add(i)
        prv.add(j)
    else:
        ps.append([i, j, d])

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

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.ones((N, ), dtype=np.int32) * -1  # -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:
def flip_color(color):
    return "1" if color == "0" else "0"

def struct_tree(tree):
    new_tree = [[] for i in range(N+1)]
    for edge in tree:
        new_tree[edge[0]].append((edge[1],edge[2]))
        new_tree[edge[1]].append((edge[0],edge[2]))
    return new_tree        

    
def tree_walk(start,tree,N):
    tree = struct_tree(tree)
    visited_flag = [False for i in range(N+1)]
    visited_flag[0] = None # hack
    visited_flag[1] = "0"
    queue = [1]
    while(len(queue)>0):
        v = queue[0]
        queue = queue[1:]
        edges = tree[v]
        for edge in edges:
            v_process = edge[0]
            if not visited_flag[v_process]:
                if edge[1] %2 == 1:
                    visited_flag[v_process] = flip_color(visited_flag[v])
                else:
                    visited_flag[v_process] = visited_flag[v]
                queue.append(v_process)
    for color in visited_flag[1:]:
        print(color)

N = int(input())
tree = [list(map(int,input().split()))for i in range(N-1)]
tree_walk(1,tree,N)

Submission status: Time Limit Exceeded

Solution code:

def flip_color(color):
    return "1" if color == "0" else "0"

def struct_tree(tree):
    new_tree = [[] for i in range(N+1)]
    for edge in tree:
        new_tree[edge[0]].append((edge[1],edge[2]))
        new_tree[edge[1]].append((edge[0],edge[2]))
    return new_tree        

    
def tree_walk(start,tree,N):
    tree = struct_tree(tree)
    visited_flag = [False for i in range(N+1)]
    visited_flag[0] = None # hack
    visited_flag[1] = "0"
    queue = [1]
    while(len(queue)>0):
        v = queue[0]
        queue = queue[1:]
        edges = tree[v]
        for edge in edges:
            v_process = edge[0]
            if not visited_flag[v_process]:
                if edge[1] %2 == 1:
                    visited_flag[v_process] = flip_color(visited_flag[v])
                else:
                    visited_flag[v_process] = visited_flag[v]
                queue.append(v_process)
    for color in visited_flag[1:]:
        print(color)

N = int(input())
tree = [list(map(int,input().split()))for i in range(N-1)]
tree_walk(1,tree,N)

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.ones((N, ), dtype=np.uint8) * -1  # -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:
import numpy as np


def read():
    N = int(input().strip())  # N <= 10**5
    to = [[] for _ in range(N)]
    cost = [[] for _ in range(N)]
    for i in range(N-1):
        # u[i] < v[i] は保証されている
        u, v, w = list(map(int, input().strip().split()))
        to[u-1].append(v-1)
        to[v-1].append(u-1)
        cost[u-1].append(w % 2)
        cost[v-1].append(w % 2)
    return N, to, cost


def solve(N, to, cost):
    c = np.ones((N, ), dtype=np.uint8) * -1  # -1: unvisited, 0: white, 1: black
    q = list()
    c[0] = 0
    q.append(0)
    while len(q) > 0:
        s = q.pop()
        for t, co in zip(to[s], cost[s]):
            if c[t] == -1:
                if co:
                    c[t] = 1 - c[s]
                else:
                    c[t] = c[s]
                q.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:
# from collections import defaultdict
# dd = defaultdict(lambda: 0)

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

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

opened = {0}
g0 = {0}
used = {0}

while len(opened) != 0:
    n = opened.pop()
    for n2 in T[n]:
        if n2 in g0:
            continue
        if n in g0:
            if T[n][n2] % 2 == 0:
                g0.add(n2)
        else:
            if T[n][n2] % 2 == 1:
                g0.add(n2)
        opened.add(n2)
        used.add(n2)

for i in range(N):
    print(0 if i in g0 else 1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
n=int(input())
d=[-1]*n
l=deque([])
for i in range(n-1):
    u,v,w=map(int,input().split())
    u,v=min(u,v),max(u,v)
    l.append((u-1,v-1,w))
f=0
while len(l):
    x=l.popleft()
    if f:
        if x[2]%2 and d[x[0]]==0:
            d[x[1]]=1
        elif x[2]%2 and d[x[0]]==1:
            d[x[1]]=0
        elif x[2]%2==0 and d[x[0]]==1:
            d[x[1]]=1
        elif x[2]%2==0 and d[x[0]]==0:
            d[x[1]]=0
        elif x[2]%2 and d[x[1]]==0:
            d[x[0]]=1
        elif x[2]%2 and d[x[1]]==1:
            d[x[0]]=0
        elif x[2]%2==0 and d[x[1]]==1:
            d[x[0]]=1
        elif x[2]%2==0 and d[x[1]]==0:
            d[x[0]]=0
        else:
            l.append(x)
    else:
        f=1
        if x[2]%2:
            d[x[0]]=0
            d[x[1]]=1
        else:
            d[x[0]]=0
            d[x[1]]=0
for i in d:
    print(i)

Submission status: Time Limit Exceeded

Solution code:
import sys
import Queue

n = int(raw_input())

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

# for k, v in graph.items():
#     print("%s -> %d" % (str(k), v))

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 (current_node, end) in graph 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])