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:
from collections import deque
n = int(input())
tree = {}
bw = [-1] * n
for i in range(n-1):
    u, v, w = map(int, input().split())
    if u-1 not in tree:
        tree[u-1] = [(u-1, v-1, w)]
    else:
        tree[u-1].append((u-1, v-1, w))
    if v-1 not in tree:
        tree[v-1] = [(v-1, u-1, w)]
    else:
        tree[v-1].append((v-1, u-1, w))

q = deque()
for nei in tree[0]:
    q.append(nei)
bw[tree[0][0][0]] = 0

while q:
    node = q.popleft()
    if bw[node[1]] != -1:
        if node[2] % 2 == 0:
            bw[node[1]] = bw[node[0]]
    else:
        if node[2] % 2 == 1:
            bw[node[1]] = (bw[node[0]] + 1) % 2
        else:
            bw[node[1]] = bw[node[0]]

    if node[1] in tree:
        for nei in tree[node[1]]:
            if bw[nei[1]] != 0:
                q.append(nei)

for c in bw:
    print(c)

Submission status: Time Limit Exceeded

Solution code:
import collections

n=int(input())
ans=[0]*(n+1)
arr=[list(map(int,input().split())) for _ in range(n-1)]
arr=sorted(arr,key=lambda x:x[0])
s=set()
tmp=arr[0]
u,v,w=tmp[0],tmp[1],tmp[2]
s.add(u)
s.add(v)
if w%2==0:
  ans[u]=1
  ans[v]=1
elif w%2==1:
  ans[u]=1
  ans[v]=0
q=collections.deque()
cnt=1
cnt2=1
while 1:
  if cnt==n-1:
    break
  else:
    if cnt2<n-1:
      tmp=arr[cnt2]
      u,v,w=tmp[0],tmp[1],tmp[2]
    else:
      tmp=q.popleft()
      u,v,w=tmp[0],tmp[1],tmp[2]
    cnt2+=1
    if u in s:
      s.add(v)
      cnt+=1
      if w%2==0:
        ans[v]=ans[u]
      else:
        ans[v]=abs(ans[u]-1)
    elif v in s:
      s.add(u)
      cnt+=1
      if w%2==0:
        ans[u]=ans[v]
      else:
        ans[u]=abs(ans[v]-1)
    else:
      q.append([u,v,w])
for i in range(1,n+1):
  print(ans[i])

Submission status: Time Limit Exceeded

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

T = sorted(T, key = lambda x: (x[0],x[1]))

A = [-1 for k in range(N)]
A[0] = 0
for t in T:
    u = t[0]-1
    v = t[1]-1
    w = t[2]
    if w%2 == 0:
        if A[u] == 0 and A[v] == -1:
            A[v] = 0
        elif A[u] == 1 and A[v] == -1:
            A[v] = 1
        elif A[u] == -1 and A[v] == 0:
            A[u] = 0
        elif A[u] == -1 and A[v] == 1:
            A[u] = 1
        elif A[u] == -1 and A[v] == -1:
            T.append([u+1,v+1,w])
    else:
        if A[u] == 0 and A[v] == -1:
            A[v] = 1
        elif A[u] == 1 and A[v] == -1:
            A[v] = 0
        elif A[u] == -1 and A[v] == 0:
            A[u] = 1
        elif A[u] == -1 and A[v] == 1:
            A[u] = 0
        elif A[u] == -1 and A[v] == -1:
            T.append([u+1,v+1,w])

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

Submission status: Time Limit Exceeded

Solution code:


        
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:
n = int(input())

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


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


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

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

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

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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

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

Submission status: Time Limit Exceeded

Solution code:
"""
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:
from collections import deque
n=int(input())
color=[0]*n
cnt=[0]*n
edge=[ [] for _ in range(n)]

for i in range(n-1):
  ui, vi, wi = map(int, input().split())
  cnt[ui-1]+=1
  cnt[vi-1]+=1
  edge[ui-1].append([ui-1,[vi-1, wi]])
  edge[vi-1].append([vi-1,[ui-1, wi]])

queue=deque(edge[cnt.index(max(cnt))])
used=[0]*n
used[cnt.index(max(cnt))]=1
while queue:
  #print(queue)
  crt, ei = queue.popleft()
  if ei[1]%2==0: 
    color[ei[0]]=color[crt]
  else:
    color[ei[0]]=color[crt]^1
  for ej in edge[ei[0]]:
    if used[ej[0]]==0:
      queue.append(ej)
  used[ei[0]]=1

for c in color:
  print(c)
  

#print(color)
#print(edge)

Submission status: Time Limit Exceeded

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

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

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

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

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

Submission status: Time Limit Exceeded

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


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

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(60000000)
    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:
"""
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(60000000)
    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:
from collections import defaultdict
import sys
input = sys.stdin.readline
N = int(input())

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


# 探索
for key, value in tree_dict.items():
    if len(value) == 1:
        break
# print(key)
paint_dict = dict()

q = [key]
paint_dict[key] = 0

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

Submission status: Time Limit Exceeded

Solution code:
from sys import exit

N = int(input())

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

for i in range(N - 1):
    _u, _v, _w = map(int, input().split())
    u.append(_u)
    v.append(_v)
    w.append(_w)

reached = []
distances = {}


def my_index(l, x, default=False):
    if x in l:
        return l.index(x)
    else:
        return default


def search(x, distance):
    if x in reached:
        # 既に達しているところだったら
        return

    # 達したことを記録
    reached.append(x)
    distances[x] = distance

    for i in range(N - 1):
        if x == u[i]:
            search(v[i], distance + w[i])
        if x == v[i]:
            search(u[i], distance + w[i])


search(1, 0)

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

Submission status: Time Limit Exceeded

Solution code:
N = int(input())

a = []
for i in range(N - 1):
    b = list(map(int, input().split(' ')))
    a.append(b)

cost = [[0 for i in range(N)] for j in range(N)]
for i in range(N - 1):
    cost[a[i][0] - 1][a[i][1] - 1] = a[i][2]
    cost[a[i][1] - 1][a[i][0] - 1] = a[i][2]

num = N * (N -1) / 2 - (N - 1)
while num > 0:
    for i in range(N - 1):
        for j in range(i+1, N):
            for k in range(N):
                if cost[i][j] == 0 and cost[i][k] > 0 and cost[k][j] > 0:
                    cost[i][j] = cost[i][k] + cost[k][j]
                    cost[j][i] = cost[i][j] 
                    num -= 1
    #print(cost)

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

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
n=int(input())
E=[]
for i in range(n-1):
  u,v,w=map(int,input().split())
  E.append([u,v,w])
def BFS(edges,N):
  roots=[[] for i in range(N)]
  for a,b,c in edges:
    roots[a-1]+=[(b-1,c)]
    roots[b-1]+=[(a-1,c)]
  dist=[-1]*N
  stack=[]
  stack.append(0)
  dist[0]=0
  while stack:
    label=stack.pop(-1)
    for i,c in roots[label]:
      if dist[i]==-1:
        dist[i]=dist[label]+c
        stack+=[i]
  return dist
for i in range(n):
  print(0 if BFS(E,n)[i]%2==0 else 1)

Submission status: Time Limit Exceeded

Solution code:
def sol(inp=input):
    n=int(inp())
    pots=[None for _ in range(n)]
    edges=[list(map(int,inp().split())) for _ in range(n-1)]
    adj=[{} for _ in range(n)]
    for e in edges:
        adj[e[0]-1][e[1]-1]=e[2]
        adj[e[1]-1][e[0]-1]=e[2]
    
    new_fixed={0}
    fixed=new_fixed.copy()
    pots[0]=0
    for _ in range(n):
        added=set()
        for u in new_fixed:
            for v in adj[u]:
                if v not in fixed:
                    pots[v]=pots[u]+adj[u][v]
                    added.add(v)
        fixed.union(added)
        new_fixed=added.copy()
        if len(fixed)==n:
            break
    return [str(p%2) for p in pots]
for c in sol():
  print(c)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
#print(N)

tree = []
for i in range(N - 1):
    tree.append(list(map(int, input().split(' '))))
#print(tree)

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

for point in tree:
    #print(point)
    if(color[point[0] - 1] == -1 and color[point[1] - 1] == -1):
        tree.append(point)

    elif(color[point[0] - 1] == 0):
        if(point[2] % 2 == 0):
            color[point[1] - 1] = 0
        else:
            color[point[1] - 1] = 1

    elif(color[point[1] - 1] == 0):
        if(point[2] % 2 == 0):
            color[point[0] - 1] = 0
        else:
            color[point[0] - 1] = 1

    elif(color[point[0] - 1] == 1):
        if(point[2] % 2 == 0):
            color[point[1] - 1] = 1
        else:
            color[point[1] - 1] = 0

    else:
        if(point[2] % 2 == 0):
            color[point[0] - 1] = 1
        else:
            color[point[0] - 1] = 0

for col in color:
    print(col)

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 u in edge[v]:
            edge[v].remove(u)
        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")

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

while True:
  flg = True
  for i in range(N):
    if s[i] == 2:
      s[i] = 0
      flg = False
      break
  if flg:
    break
      
  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())
# N, K = map(int, input().split())
L = [list(map(int, input().split())) for _ in range(N - 1)]

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

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

for a in ans:
    print(a)

Submission status: Time Limit Exceeded

Solution code:
import sys
import Queue

n = int(raw_input())

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

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

queue = Queue.Queue()
queue.put(0)
color[0] = 0
sum = 1

while True:
    if sum >= n:
        break

    while True:
        if queue.empty():
            break

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

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