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().strip())
x = [[] for x in range(N)]
for i in range(N-1):
     u, v, w = list(map(int, input().split()))
     x[u-1].append([v-1, w])
     x[v-1].append([u-1,w])



ret = {}
done = []

queue = [0]

for i in range(N):
    curr = queue.pop()
    if curr == 0:
        ret[0] = 0

    for neigh in x[curr]:
        if neigh in done:
            continue
        if neigh[1] % 2 == 0:
            ret[neigh[0]] = ret[curr]
        else:
            ret[neigh[0]] = 0 if ret[curr] == 1 else 1

        if neigh[0] not in done:
            queue.append(neigh[0])
    done.append(curr)


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

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
arr = [None]*N
visited = [False]*N
UVW = []
for i in range(N-1):
    u, v, w = map(int, input().split())
    if i==0:
        arr[u-1] = 0
        visited[u-1] = True
    if visited[u-1]:
        arr[v-1] = arr[u-1] + w
        visited[v-1] = True
    elif visited[v-1]:
        arr[u-1] = arr[v-1] + w
        visited[u-1] = True
    else:
        UVW.append([u,v,w])

while len(UVW)>0:
    u,v,w = UVW.pop(0)
    if visited[u-1]:
        arr[v-1] = arr[u-1] + w
        visited[v-1] = True
    elif visited[v-1]:
        arr[u-1] = arr[v-1] + w
        visited[u-1] = True
    else:
        UVW.append([u,v,w])
    

for a in arr:
    if a%2==0:
        print(0)
    else:
        print(1)

Submission status: Time Limit Exceeded

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



ret = {}
done = []

queue = [0]

for i in range(N):
    curr = queue.pop()
    if curr == 0:
        ret[0] = 0

    for neigh in x[curr]:
        if neigh[1] % 2 == 0:
            ret[neigh[0]] = ret[curr]
        else:
            ret[neigh[0]] = 0 if ret[curr] == 1 else 1

        if neigh[0] not in done:
            queue.append(neigh[0])
    done.append(curr)


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

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)
while True:
    for inp in inputs:
        inp_st = inp.split()
        v1 = int(inp_st[0])
        v2 = int(inp_st[1])
        w = int(inp_st[2])
        w_even = True
        if w % 2 == 1:
            w_even = False
        # v1/v2がwhiteでwが偶数なら同じグループにv2/v1を追加する
        if v1 in white:
            if w_even:
                white.append(v2)
            else:
                black.append(v2)
        elif v1 in black:
            if w_even:
                black.append(v2)
            else:
                white.append(v2)
        elif v2 in black:
            if w_even:
                black.append(v1)
            else:
                white.append(v1)
        elif v2 in white:
            if w_even:
                white.append(v1)
            else:
                black.append(v1)
        else:
            # v1,v2が今まで出てきていなければremainに
            remain_inputs.append(inp)
    # print(remain_inputs)
    if not remain_inputs:
        break
    inputs = remain_inputs
    remain_inputs = []


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

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
sides=[list(map(int,input().split())) for _ in range(n-1)]
sides=[[side[0]-1,side[1]-1,side[2]%2]for side in sides]
# print(sides)
color=[-1 for _ in range(n)]
color[sides[0][0]]=0
while True:
    u,v,w=sides.pop(0)
    # print(u,v,w)
    if color[u]==-1 and color[v]==-1:
        sides.append([u,v,w])
    elif color[v]==-1:
        # print('u=',color[u],w)
        color[v]=(color[u]^w)
    elif color[u]==-1:
        # print('v=',color[v],w)
        color[u]=(color[v]^w)
    if len(sides)==0:
        break
# print(color)
for c in color:
    print(c)

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 = [[] for _ in range(N)]
for l in L:
    u, v, w = l
    W[u - 1][v - 1] = w
    P[u - 1].append(v - 1)
    P[v - 1].append(u - 1)

ans[0] = 0
F = [0]
it = 0
while len(F) > it:
    u = F[it]
    it += 1
    for v in P[u]:
        if ans[v] != -1:
            continue

        w = W[u][v] if u < v else W[v][u]
        ans[v] = ans[u] if w % 2 == 0 else 1 - ans[u]
        F.append(v)

for a in ans:
    print(a)

Submission status: Time Limit Exceeded

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

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

N = INT()
uvw = [LIST() for _ in range(N-1)]
uvw.sort(key=lambda x:(x[0], x[1]))
color = [0]*N  # -1で白 1で黒を表す
searched = [0]*N  # 探索した場所に1をいれる
color[0] = -1  # 0番目のノードを白で初期化
searched[0] = 1  # 0 番目のノードは探索済み
for u, v, w in uvw:
	if searched[u-1] == 0 and searched[v-1] == 0:
		uvw.append([u, v, w])
		continue
	if searched[v-1] == 1:
		u, v = v, u
	if w % 2 == 0:
		color[v-1] = color[u-1]
		searched[v-1] = 1
	else:
		color[v-1] = color[u-1] * (-1)
		searched[v-1] = 1
	# print(searched)
# print(color)
for i in color:
	if i == -1:
		print('0')
	else:
		print('1')

Submission status: Time Limit Exceeded

Solution code:
N = int(input())

u = []
v = []
w = []

while True:
  try:
  	tmp = input()
  except EOFError as e:
    break
  if tmp==None or tmp=='':
    break
  u_,v_,w_ = map(int,tmp.split())
  u = u+[u_-1]
  v = v+[v_-1]
  w = w+[w_%2]

M = len(u)

s = [2]*N

for i in range(N):
  if s[i] == 2:
    s[i] = 0
  flg = True
  while flg:
    flg = False
    for j in range(M):
      if s[u[j]]==2 and s[v[j]]!=2:
        if w[j] == 0:
        	s[u[j]] = s[v[j]]
        else:
        	s[u[j]] = 1 - s[v[j]]
        flg = True
      elif s[v[j]]==2 and s[u[j]]!=2:
        if w[j] == 0:
        	s[v[j]] = s[u[j]]
        else:
        	s[v[j]] = 1 - s[u[j]]
        flg = True
for j in range(N):
  print(s[j])

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
r = [None]*N
s = 0

same = []
other = []

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

    if w%2==0:
        if   r[u] != None and r[v] == None:
            r[v] = r[u]
        elif r[u] == None and r[v] != None:
            r[u] = r[v]
        elif r[u] == None and r[v] == None:
            r[u] = r[v] = s
            s+=1
        else:
            same.append((r[u],r[v]))
            
    if w%2==1:
        if r[u] == None:
            r[u] = s
            s+=1
        if r[v] == None:
            r[v] = s
            s+=1
        other.append((r[u],r[v]))
        
color = [{r[0]},set()]

while len(color[0])+len(color[1]) < s:
    for k1, k2 in same:
        for cl in color:
            if k1 in cl: cl.add(k2)
            if k2 in cl: cl.add(k1)

    for k1, k2 in other:
        for cl1, cl2 in ((color[0],color[1]), (color[1],color[0])):
            if k1 in cl1: cl2.add(k2)
            if k2 in cl1: cl2.add(k1)

cmap = [0]*s
for cc in color[1]:
    cmap[cc]=1

for rr in r:
    print(cmap[rr])

Submission status: Time Limit Exceeded

Solution code:
import sys


class Graph():

    def __init__(self, vertices):
        self.V = vertices
        self.graph = [[0 for column in range(vertices)]
                      for row in range(vertices)]

    def printSolution(self, dist):
        print
        "Vertex tDistance from Source"
        for node in range(self.V):
            print
            node, "t", dist[node]

    # A utility function to find the vertex with
    # minimum distance value, from the set of vertices
    # not yet included in shortest path tree
    def minDistance(self, dist, sptSet):

        # Initilaize minimum distance for next node
        # min = sys.maxint
        min = float("inf")

        # Search not nearest vertex not in the
        # shortest path tree
        for v in range(self.V):
            if dist[v] < min and sptSet[v] == False:
                min = dist[v]
                min_index = v

        return min_index

    # Funtion that implements Dijkstra's single source
    # shortest path algorithm for a graph represented
    # using adjacency matrix representation
    def dijkstra(self, src):

        dist = [float("inf")] * self.V
        dist[src] = 0
        sptSet = [False] * self.V

        for cout in range(self.V):

            # Pick the minimum distance vertex from
            # the set of vertices not yet processed.
            # u is always equal to src in first iteration
            u = self.minDistance(dist, sptSet)

            # Put the minimum distance vertex in the
            # shotest path tree
            sptSet[u] = True

            # Update dist value of the adjacent vertices
            # of the picked vertex only if the current
            # distance is greater than new distance and
            # the vertex in not in the shotest path tree
            for v in range(self.V):
                if self.graph[u][v] > 0 and sptSet[v] == False and \
                        dist[v] > dist[u] + self.graph[u][v]:
                    dist[v] = dist[u] + self.graph[u][v]

        # self.printSolution(dist)
        return dist


# Driver program

N = int(input())
g = Graph(N)

graph = [[0] * N for _ in range(N)]

# g.graph = [[0, 4, 0, 0, 0, 0, 0, 8, 0],
#            [4, 0, 8, 0, 0, 0, 0, 11, 0],
#            [0, 8, 0, 7, 0, 4, 0, 0, 2],
#            [0, 0, 7, 0, 9, 14, 0, 0, 0],
#            [0, 0, 0, 9, 0, 10, 0, 0, 0],
#            [0, 0, 4, 14, 10, 0, 2, 0, 0],
#            [0, 0, 0, 0, 0, 2, 0, 1, 6],
#            [8, 11, 0, 0, 0, 0, 1, 0, 7],
#            [0, 0, 2, 0, 0, 0, 6, 7, 0]
#            ];


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

g.graph = graph

dist = g.dijkstra(0);
# d = G.dijkstra(1, 2)

# print(dist)

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

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
    W[v - 1][u - 1] = w
    P[u - 1].add(v - 1)
    P[v - 1].add(u - 1)

ans[0] = 0
F = [0]
while len(F) != 0:
    u = F.pop()
    for v in list(P[u]):
        if ans[v] != -1:
            continue

        w = W[u][v]
        ans[v] = ans[u] if w % 2 == 0 else 1 - ans[u]
        F.append(v)

for a in ans:
    print(a)

Submission status: Time Limit Exceeded

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


ret = {}
done = []

queue = [0]

for i in range(N):
    curr = queue.pop()
    if curr == 0:
        ret[0] = 0

    for j in range(N):
        if x[curr][j] > 0:
            if x[curr][j] %2 == 0:
                ret[j] = ret[curr]
            else:
                ret[j] = 0 if ret[curr] == 1 else 1
            if j not in done:
                queue.append(j)
    done.append(curr)


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

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

while True:
    for i in range(n - 1):
        u, v, w = uvw[i]
        u -= 1
        v -= 1
        if wb[u] == -1 and wb[v] == -1:
            # 両方未確定なので何も出来ない
            continue
        if wb[u] != -1 and wb[v] != -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]
        progress -= 1
        if progress == 0:
            # 完了
            print(*wb, sep='\n')
            sys.exit(0)

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()

import collections


class BellmanFord():
    def __init__(self):
        self.edges = []

    def add(self, u, v, d, directed=False):
        """
        u = from, v = to, d = cost
        directed = Trueのとき、有向グラフである。
        """
        if directed is False:
            self.edges.append([u, v, d])
            self.edges.append([v, u, d])
        else:
            self.edges.append([u, v, d])

    def BellmanFord_search(self, s):
        """
        次のBellmanFord_negative_boolまで考慮した時には、0-indexedであることに注意
        s =  始点
        return: d[i] 始点sから各点iまでの最短経路
        """
        d = collections.defaultdict(lambda: float('inf'))
        d[s] = 0
        numEdges = len(self.edges)
        while True:
            update = False
            for i in range(numEdges):
                e = self.edges[i]
                # e: 辺iについて [from,to,cost]
                if d[e[0]] != float("inf") and d[e[1]] > d[e[0]] + e[2]:
                    d[e[1]] = d[e[0]] + e[2]
                    update = True
            if not update:
                break
        return d

    def BellmanFord_negative_bool(self, numNodes, zero_indexed=False):
        # 負の閉路の検出, Trueなら負の閉路が存在する
        d = collections.defaultdict(lambda: float('inf'))
        d[0] = 0
        numEdges = len(self.edges)
        for i in range(numNodes):
            for j in range(numEdges):
                e = self.edges[j]
                if d[e[1]] > d[e[0]] + e[2]:
                    d[e[1]] = d[e[0]] + e[2]
                    if i == numNodes-1:
                        return True
        return False

g = BellmanFord()
n = ni()

for i in range(n-1):
    u,v,w = na()
    g.add(u,v,w)

d = g.BellmanFord_search(1)

for i in range(1,n+1):
    if d[i] % 2 ==0:
        print(0)
    else:
        print(1)

Submission status: Time Limit Exceeded

Solution code:
from scipy.sparse.csgraph import floyd_warshall
n=int(input())
T=[[0]*n for i in range(n)]
for i in range(n-1):
  u,v,w=map(int,input().split())
  T[u-1][v-1]=w
  T[v-1][u-1]=w
d=floyd_warshall(csgraph=T, directed=False, return_predecessors=False)
for i in range(n):
  print(0 if d[0][i]%2==0 else 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,count):
    i=0
    for edge in l:
        if edge[0]==node:
            if node_l[edge[1]-1]==0:
                if W[i]%2==0:
                    node_l[edge[1]-1]=node_l[node-1]
                    count+=1
                    if count>=n:
                        return
                    bfs(edge[1],node_l,l,w_l,count)
                else:
                    node_l[edge[1]-1]=node_l[node-1]*-1
                    count+=1
                    if count>=n:
                        return
                    bfs(edge[1],node_l,l,w_l,count)
        elif edge[1]==node:
            if node_l[edge[0]-1]==0:
                if W[i]%2==0:
                    node_l[edge[0]-1]=node_l[node-1]
                    count+=1
                    if count>=n:
                        return
                    bfs(edge[0],node_l,l,w_l,count)
                else:
                    node_l[edge[0]-1]=node_l[node-1]*-1
                    count+=1
                    if count>=n:
                        return
                    bfs(edge[0],node_l,l,w_l,count)
        i+=1
    return

count=1
bfs(1,node_l,E,W,count)
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:
N = int(input())
V = []
for _ in range(N-1):
    u, v, w = map(int, input().split())
    V.append((u,v,w))

edges = V[:]

def warshall_floyd(d, n):
    # d: グラフ二次元リスト
    # n: 頂点数 (0始まり)
    #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

graph = [[float("inf") for i in range(N)] for i in range(N)] 
for x,y,z in edges:
    graph[x-1][y-1] = z
    graph[y-1][x-1] = z
for i in range(N):
    graph[i][i] = 0 #自身のところに行くコストは０
shortest = warshall_floyd(graph, N)

color = [1] * N
color[0] = 0

for i, sub in enumerate(shortest):
    for j, l in enumerate(sub):
        if l % 2 == 0:
            color[j] = color[i]
for c in color:
    print(c)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
l = []
maps = [-1 for i in range(n)]
maps[0] = 0
for i in range(n-1):
    a, b, c = map(int, input().split())
    l.append([a-1, b-1, c])

while l != []:
    x = l.pop(0)
    if(maps[x[0]] != -1):
        maps[x[1]] = (maps[x[0]]+x[2])%2
    elif(maps[x[1]] != -1):
        maps[x[0]] = (maps[x[1]]+x[2])%2
    else: l.append(x)
    #print(maps)
for i in maps:
    print(i)

Submission status: Time Limit Exceeded

Solution code:
"""
Author    : raj1307 - Raj Singh
Institute : Jalpaiguri Government Engineering College
Date      : 19.05.19
"""
from __future__ import division, print_function
import itertools,os,sys

from io import BytesIO, IOBase

if sys.version_info[0] < 3:
    from __builtin__ import xrange as range
    from future_builtins import ascii, filter, hex, map, oct, zip
else:
    from builtins import str as __str__
    str = lambda x=b'': x if type(x) is bytes else __str__(x).encode()

BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._buffer = BytesIO()
        self._fd = file.fileno()
        self._writable = 'x' in file.mode or 'r' not in file.mode
        self.write = self._buffer.write if self._writable else None

    def read(self):
        return self._buffer.read() if self._buffer.tell() else os.read(self._fd, os.fstat(self._fd).st_size)

    def readline(self):
        while self.newlines == 0:
            b, ptr = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE)), self._buffer.tell()
            self._buffer.seek(0, 2), self._buffer.write(b), self._buffer.seek(ptr)
            self.newlines += b.count(b'\n') + (not b)
        self.newlines -= 1
        return self._buffer.readline()

    def flush(self):
        if self._writable:
            os.write(self._fd, self._buffer.getvalue())
            self._buffer.truncate(0), self._buffer.seek(0)


sys.stdin, sys.stdout = FastIO(sys.stdin), FastIO(sys.stdout)
input = lambda: sys.stdin.readline().rstrip(b'\r\n')


def print(*args, **kwargs):
    sep, file = kwargs.pop('sep', b' '), kwargs.pop('file', sys.stdout)
    at_start = True
    for x in args:
        if not at_start:
            file.write(sep)
        file.write(str(x))
        at_start = False
    file.write(kwargs.pop('end', b'\n'))
    if kwargs.pop('flush', False):
        file.flush()



def ii(): return int(input())
def si(): return str(input())
def mi(): return map(int,input().strip().split(" "))
def li(): return list(mi())

from collections import deque, Counter, OrderedDict,defaultdict
#from heapq import nsmallest, nlargest, heapify, #heappop ,heappush, heapreplace
#from math import ceil,floor,log,sqrt,factorial,pow,pi
#from bisect import bisect_left,bisect_right
#from decimal import *,
import threading

def dmain():
    sys.setrecursionlimit(100000000)
    threading.stack_size(40960000)
    thread = threading.Thread(target=main)
    thread.start()

abc='abcdefghijklmnopqrstuvwxyz'
abd={'a': 0, 'b': 1, 'c': 2, 'd': 3, 'e': 4, 'f': 5, 'g': 6, 'h': 7, 'i': 8, 'j': 9, 'k': 10, 'l': 11, 'm': 12, 'n': 13, 'o': 14, 'p': 15, 'q': 16, 'r': 17, 's': 18, 't': 19, 'u': 20, 'v': 21, 'w': 22, 'x': 23, 'y': 24, 'z': 25}
mod=1000000007
dx,dy=[-1,1,0,0],[0,0,1,-1]
def getKey(item): return item[0] 
def sort2(l):return sorted(l, key=getKey)
def d2(n,m,num):return [[num for x in range(m)] for y in range(n)]
def isPowerOfTwo (x): return (x and (not(x & (x - 1))) )
def decimalToBinary(n): return bin(n).replace("0b","")
def ntl(n):return [int(i) for i in str(n)]
def powerMod(x,y,p):
    res = 1
    x %= p
    while y > 0:
        if y&1:
            res = (res*x)%p
        y = y>>1
        x = (x*x)%p1
    return res
def gcd(x, y):
    while y:
        x, y = y, x % y
    return x

def isPrime(n) : # Check Prime Number or not 
    if (n <= 1) : 
        return False
    if (n <= 3) : 
        return True
    if (n % 2 == 0 or n % 3 == 0) : 
        return False
    i = 5
    while(i * i <= n) : 
        if (n % i == 0 or n % (i + 2) == 0) : 
            return False
        i = i + 6
    return True


# For getting input from input.txt file 
#sys.stdin = open('input.txt', 'r')  
  
# Printing the Output to output.txt file 
#sys.stdout = open('output.txt', 'w') 

graph=defaultdict(list)
visited=[False]*1000000


def dfs(v,d): 
    
    
    visited[v]= True
    
    if d%2==0:
        col[v]=1
    for i in graph[v]:
        if visited[i] == False: 
                dfs(i,d+a[i][v]) 





n=ii()
col=[0]*(n+1)
a=d2(n+1,n+1,0)
def main():

    for i in range(n-1):
        x,y,w=mi()
        graph[x].append(y)
        graph[y].append(x)
        a[x][y]=w
        a[y][x]=w
    
    
    for i in range(1,n+1):
        if visited[i]==False:
            dfs(i,0)
            
            
    for i in range(1,n+1):
        print(col[i])
   

if __name__ == "__main__":
    #main()
    dmain()

Submission status: Time Limit Exceeded

Solution code:
import sys
import collections
from collections import Counter
from collections import deque
from collections import defaultdict
import itertools
from itertools import accumulate
from itertools import permutations
from itertools import combinations
from itertools import takewhile
from itertools import compress
import functools
from functools import reduce
import math
####from math import gcd
####from math import inf
from math import ceil
from math import floor
##from math import log10
##from math import log2
##from math import log
from math import factorial
import re
from functools import lru_cache

# @lru_cache(maxsize=1000)

# MOD = 10 ** 9 + 7

# N = int(input())
# A = [int(x) for x in input().split()]
# V = [[0] * 100 for _ in range(100)]

from collections import deque, namedtuple

# we'll use infinity as a default distance to nodes.
inf = float('inf')
Edge = namedtuple('Edge', 'start, end, cost')


def make_edge(start, end, cost=1):
    return Edge(start, end, cost)



class Graph:
    def __init__(self, edges):
        # let's check that the data is right
        wrong_edges = [i for i in edges if len(i) not in [2, 3]]
        if wrong_edges:
            raise ValueError('Wrong edges data: {}'.format(wrong_edges))

        self.edges = [make_edge(*edge) for edge in edges]

    @property
    def vertices(self):
        return set(
            sum(
                ([edge.start, edge.end] for edge in self.edges), []
            )
        )

    def get_node_pairs(self, n1, n2, both_ends=True):
        if both_ends:
            node_pairs = [[n1, n2], [n2, n1]]
        else:
            node_pairs = [[n1, n2]]
        return node_pairs

    def remove_edge(self, n1, n2, both_ends=True):
        node_pairs = self.get_node_pairs(n1, n2, both_ends)
        edges = self.edges[:]
        for edge in edges:
            if [edge.start, edge.end] in node_pairs:
                self.edges.remove(edge)

    def add_edge(self, n1, n2, cost=1, both_ends=True):
        node_pairs = self.get_node_pairs(n1, n2, both_ends)
        for edge in self.edges:
            if [edge.start, edge.end] in node_pairs:
                return ValueError('Edge {} {} already exists'.format(n1, n2))

        self.edges.append(Edge(start=n1, end=n2, cost=cost))
        if both_ends:
            self.edges.append(Edge(start=n2, end=n1, cost=cost))

    @property
    def neighbours(self):
        neighbours = {vertex: set() for vertex in self.vertices}
        for edge in self.edges:
            neighbours[edge.start].add((edge.end, edge.cost))

        return neighbours



    def dijkstra(self, source, dest):
        assert source in self.vertices, 'Such source node doesn\'t exist'

        distances = {vertex: inf for vertex in self.vertices}
        previous_vertices = {
            vertex: None for vertex in self.vertices
        }
        distances[source] = 0
        vertices = self.vertices.copy()

        while vertices:
            current_vertex = min(
                vertices, key=lambda vertex: distances[vertex])
            vertices.remove(current_vertex)
            if distances[current_vertex] == inf:
                break
            for neighbour, cost in self.neighbours[current_vertex]:
                alternative_route = distances[current_vertex] + cost
                if alternative_route < distances[neighbour]:
                    distances[neighbour] = alternative_route
                    previous_vertices[neighbour] = current_vertex

        path, current_vertex = deque(), dest
        while previous_vertices[current_vertex] is not None:
            path.appendleft(current_vertex)
            current_vertex = previous_vertices[current_vertex]
        if path:
            path.appendleft(current_vertex)

        return distances
        # return path


# graph = Graph([
#     ("a", "b", 7),  ("a", "c", 9),  ("a", "f", 14), ("b", "c", 10),
#     ("b", "d", 15), ("c", "d", 11), ("c", "f", 2),  ("d", "e", 6),
#     ("e", "f", 9)])
#
# print(graph.dijkstra("a", "e"))


N = int(input())

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



d = G.dijkstra(1,2)

for i in range(1,N+1):
    print(0 if d[i]%2==0 else 1)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
ans = [2] * n
u, v, w = map(int, input().split())
ans[u-1] = 0
if w % 2:  
  ans[v-1] = 1
else:
  ans[v-1] = 0
tmp = []
for i in range(1, n - 1):
  u, v, w = map(int, input().split())
  if ans[u-1] != 2:
    if w % 2:
      ans[v-1] = (ans[u-1] + 1) % 2
    else:
      ans[v-1] = ans[u-1] % 2
  elif ans[v-1] != 2:
    if w % 2:
      ans[u-1] = (ans[v-1] + 1) % 2
    else:
      ans[u-1] = ans[v-1] % 2
  else:
    tmp.append([u, v, w])
while len(tmp) > 0:
  u, v, w = tmp[0][0], tmp[0][1], tmp[0][2]
  tmp = tmp[1:]
  if ans[u-1] != 2:
    if w % 2:
      ans[v-1] = (ans[u-1] + 1) % 2
    else:
      ans[v-1] = ans[u-1] % 2
  elif ans[v-1] != 2:
    if w % 2:
      ans[u-1] = (ans[v-1] + 1) % 2
    else:
      ans[u-1] = ans[v-1] % 2
  else:
    tmp.append([u, v, w])
for i in range(n):
  print(ans[i])

Submission status: Time Limit Exceeded

Solution code:
import sys

input = sys.stdin.readline

def f(n):
    uvw = [list(map(int, input().split())) for _ in range(n - 1)]
    ans = [-1] * (n + 1)
    ans[uvw[0][0]] = True
    while uvw:
        nuvw = []
        for u, v, w in uvw:
            if ans[u] != -1:
                if w % 2:
                    ans[v] = not ans[u]
                else:
                    ans[v] = ans[u]
            elif ans[v] != -1:
                if w % 2:
                    ans[u] = not ans[v]
                else:
                    ans[u] = ans[v]
            else:
                nuvw.append([u, v, w])
        uvw = nuvw
    for x in ans[1:]:
        print(x * 1)

n = int(input())
f(n)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
sides=[list(map(int,input().split())) for _ in range(n-1)]
sides=[[side[0]-1,side[1]-1,side[2]%2]for side in sides]
# print(sides)
color=[-1 for _ in range(n)]
color[0]=0
while True:
    u,v,w=sides.pop(0)
    # print(u,v,w)
    if color[u]==-1 and color[v]==-1:
        sides.append([u,v,w])
    elif color[v]==-1:
        # print('u=',color[u],w)
        color[v]=(color[u]^w)
    elif color[u]==-1:
        # print('v=',color[v],w)
        color[u]=(color[v]^w)
    if len(sides)==0:
        break
# print(color)
for c in color:
    print(c)

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:0}

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

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

dfs(1, 0)

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

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
N = int(input())
edge = [[] for _ in range(N)]
W = [[3 for i in range(N)] for i in range(N)]
Color = [1 for i in range(N)]

for _ in range(N - 1):
    a, b, w = map(int, input().split())
    w = w % 2
    edge[a - 1].append(b - 1)
    edge[b - 1].append(a - 1)
    W[a-1][b-1] = w % 2
    W[b-1][a-1] = w % 2


d = [[-1] * N]

d[0][0] = 0
q = deque([0])
while len(q) > 0:
    u = q.popleft()
    for v in edge[u]:
        if d[0][v] > -1:
            continue
        d[0][v] = 1
        if W[u][v] == 0:
            Color[v] = Color[u]
        if W[u][v] == 1:
            Color[v] = (Color[u] + 1) % 2
        q.append(v)

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