Problem:


Score : 400 points

Problem Statement

We have a tree with N vertices numbered 1 to N.
The i-th edge in the tree connects Vertex u_i and Vertex v_i, and its length is w_i.
Your objective is to paint each vertex in the tree white or black (it is fine to paint all vertices the same color) so that the following condition is satisfied:

For any two vertices painted in the same color, the distance between them is an even number.

Find a coloring of the vertices that satisfies the condition and print it. It can be proved that at least one such coloring exists under the constraints of this problem.

Constraints

All values in input are integers.

1 \leq N \leq 10^5

1 \leq u_i < v_i \leq N

1 \leq w_i \leq 10^9

Input

Input is given from Standard Input in the following format:

N
u_1 v_1 w_1
u_2 v_2 w_2
.
.
.
u_{N - 1} v_{N - 1} w_{N - 1}

Output

Print a coloring of the vertices that satisfies the condition, in N lines.
The i-th line should contain 0 if Vertex i is painted white and 1 if it is painted black.

If there are multiple colorings that satisfy the condition, any of them will be accepted.

Sample Input 1

3
1 2 2
2 3 1

Sample Output 1

0
0
1

Sample Input 2

5
2 5 2
2 3 10
1 3 8
3 4 2

Sample Output 2

1
0
1
0
1



Sample input:
3
1 2 2
2 3 1


Sample output:
0
0
1

Submission status: Time Limit Exceeded

Solution code:
import sys
import re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
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()
U = []
V = []
W = []
for i in range(N-1):
    u, v, w = MAP()
    U.append(u-1)
    V.append(v-1)
    W.append(w)


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


d = [[float("inf")] * N for i in range(N)]
# d[u][v] : 辺uvのコスト(存在しないときはinf)
for u, v, w in zip(U, V, W):
    d[u][v] = w
    d[v][u] = w
for i in range(N):
    d[i][i] = 0 #自身のところに行くコストは０

d = warshall_floyd(d)

c = [0] * N

for i in range(len(d)):
    for j in range(i, len(d[i])):
        if (c[i] + c[j]) % 2 == 0 and d[i][j] % 2 != 0:
            if c[j] == 0:
                c[j] = 1
            else:
                c[j] = 0

for i in range(len(c)):
    print(c[i])

Submission status: Time Limit Exceeded

Solution code:
import sys
import re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
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()
U = []
V = []
W = []
for i in range(N-1):
    u, v, w = MAP()
    U.append(u-1)
    V.append(v-1)
    W.append(w)


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


d = [[float("inf")] * N for i in range(N)]
# d[u][v] : 辺uvのコスト(存在しないときはinf)
for u, v, w in zip(U, V, W):
    d[u][v] = w
    d[v][u] = w
for i in range(N):
    d[i][i] = 0 #自身のところに行くコストは０

d = warshall_floyd(d)

c = [0] * N

for i in range(len(d)):
    for j in range(len(d[i])):
        if (c[i] + c[j]) % 2 == 0 and d[i][j] % 2 != 0:
            if c[j] == 0:
                c[j] = 1
            else:
                c[j] = 0

for i in range(len(c)):
    print(c[i])

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque
input = sys.stdin.readline

def main():
    n=int(input())
    l=[[] for _ in range(n+1)]
    for _ in range(n-1):
        u,v,w=map(int,input().split())
        l[u].append([v,w])
        l[v].append([u,w])
    ans=[0]*(n+1)
    chk=[(1,0)]
    while chk:
        x,d=chk.pop()
        for v,w in l[x]:
            chk.append((v,d+w))
            if (d+w)%2==0:
                ans[v]=0
            else:
                ans[v]=1
    [print(i) for i in ans[1:]]

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

n = int(input())
visit = [-1 for _ in range(n+1)]
tree = [[-1 for _ in range(n+1)] for __ in range(n+1)]
friends = [[] for _ in range(n+1)]
for i in range(n-1):
    u, v, w = map(int, input().split())
    tree[u][v] = w
    tree[v][u] = w
    friends[u].append(v)
    friends[v].append(u)

q = deque([1])
visit[1] = 0
while q:
    position = q.popleft()
    for i in friends[position]:
        if visit[i] < 0:
            visit[i] = visit[position] + tree[position][i]
            q.append(i)

for i in visit[1:]:
    print(i%2)

Submission status: Time Limit Exceeded

Solution code:
import sys
def input(): return sys.stdin.readline().rstrip()

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

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

    depth = [-1] * (N)
    depth[0] = 0
    def dfs(x):
        for i, g in enumerate(graph[x]):
            if depth[i] > -1 or g == -1:
                continue
            depth[i] = depth[x] + g
            dfs(i)
    dfs(0)
    print("\n".join(['1' if d % 2 == 0 else '0' for d in depth]))

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
visited = [False] * N
colors = [-1] * N
dist = [float('inf')] * N

def dfs(u):
    if visited[u]:
        return

    visited[u] = True
    for i, v in enumerate(edges[u]):
        if v == -1:
            continue
        if visited[i]:
            continue
        if colors[i] != -1:
            continue

        dist[i] = dist[u] + v
        if dist[i] % 2 == 0:
            colors[i] = 0
        else:
            colors[i] = 1
        dfs(i)


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


colors[0] = 0
dist[0] = 0
dfs(0)
for c in colors:
    print(c)

Submission status: Time Limit Exceeded

Solution code:
import queue

n=int(input())
color=[-1]*n

u0,v0,w0=map(int,input().split())
u0-=1
v0-=1
if w0%2==0:
    color[u0]=0
    color[v0]=0
else:
    color[u0]=0
    color[v0]=1

q=queue.Queue()
for i in range(n-2):
    q.put(tuple(map(int,input().split())))

while not q.empty():
    u,v,w=q.get()
    u-=1
    v-=1
    if color[u]==-1 and color[v]==-1:
        q.put((u+1,v+1,w))
    else:
        if w%2==0:
            if color[u]!=-1 and color[v]==-1:
                color[v]=color[u]
            elif color[u]==-1 and color[v]!=-1:
                color[u]=color[v]
        else:
            if color[u]!=-1 and color[v]==-1:
                if color[u]==0:
                    color[v]=1
                else:
                    color[v]=0
            elif color[u]==-1 and color[v]!=-1:
                if color[v]==0:
                    color[u]=1
                else:
                    color[u]=0
for i in range(n):
    print(color[i])

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
# Your code here!
def dfs(num,hiyo):
    ans[num]=hiyo
    for item in way[num]:
        if ans[item]==-1:
            dfs(item,hiyo+cost[num][item])
    
    return 

N=int(input())

way=[[] for i in range(N)]
cost=[[0]*N for i in range(N)]
ans=[-1]*N

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

dfs(0,0)

for item in ans:
    print(item%2)

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
# Your code here!
def dfs(num,hiyo):
    ans[num]=hiyo
    for item in way[num]:
        if ans[item]==-1:
            dfs(item,hiyo+cost[num][item])
    
    return 

N=int(input())

way=[[] for i in range(N)]
cost=[[0]*N for i in range(N)]
ans=[-1]*N

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

#lis.sort(key=lambda x:(x[0],x[1]))

dfs(0,0)

for item in ans:
    print(item%2)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
u=[0 for i in range(0,N-1)]
v=[0 for i in range(0,N-1)]
w=[0 for i in range(0,N-1)]
for i in range(0,N-1):
    u[i],v[i],w[i]=map(int,input().split())
w=[w[i]%2 for i in range(0,N-1)]
hen=[[] for i in range(0,N+1)]
for i in range(0,N-1):
    hen[u[i]].append([v[i],w[i]])
    hen[v[i]].append([u[i],w[i]])
ans=[[0,0] for i in range(0,N+1)]
ans[1]=[0,1]
q=[]
q.append(1)
sub=[]
while q!=[]:
    while q!=[]:
        x=q[0]
        q.remove(x)
        if ans[x][0]==0:
            for p in hen[x]:
                s=p[0]
                t=p[1]
                if ans[s][1]==0:
                    if p[1]==0:
                        ans[s][0]=0
                    else:
                        ans[s][0]=1
                    sub.append(s)
                    ans[s][1]=1
        else:
            for p in  hen[x]:
                s=p[0]
                t=p[1]
                if ans[s][1]==0:
                    if p[1]==0:
                        ans[s][0]=1
                    else:
                        ans[s][0]=0
                    sub.append(s)
                    ans[s][1]=1
        if q==[]:
            q=sub
            sub=[]
            break
ans[0]=100
ans.remove(100)
for i in range(0,N):
    print(ans[i][0])

Submission status: Time Limit Exceeded

Solution code:
def dijkstra(s,n,w,cost):
    #始点sから各頂点への最短距離
    #n:頂点数,　w:辺の数, cost[u][v] : 辺uvのコスト(存在しないときはinf)
    d = [float("inf")] * n
    used = [False] * n
    d[s] = 0
    
    while True:
        v = -1
        #まだ使われてない頂点の中から最小の距離のものを探す
        for i in range(n):
            if (not used[i]) and (v == -1):
               v = i
            elif (not used[i]) and d[i] < d[v]:
                v = i
        if v == -1:
               break
        used[v] = True
               
        for j in range(n):
               d[j] = min(d[j],d[v]+cost[v][j])
    return d

################################
n = int(input()) #n:頂点数　w:辺の数
w=n-1
cost = [[float("inf") for i in range(n)] for i in range(n)] 
#cost[u][v] : 辺uvのコスト(存在しないときはinf この場合は10**10)
for i in range(w):
    x,y,z = map(int,input().split())
    x=x-1
    y=y-1
    cost[x][y] = z
    cost[y][x] = z
A=dijkstra(0,n,w,cost)
for i in range(n):
  print(A[i]%2)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
dic = [[-1]*(N+1) for _ in range(N+1)]
M = [[] for _ in range(N+1)]
used = [-1]*(N+1) 
for i in range(N-1):
    u,v,w = map(int,input().split())
    M[u-1].append([v-1,w])
    M[v-1].append([u-1,w])


# from collections import deque 
q = []
q.append([0,0])
used[0] = 0
# print(M)
while q:
    # print(q)
    e,c = q.pop()
    for i,d in M[e]:
        if used[i]==-1:
            C = (c+d)%2
            used[i] = C
            q.append([i,C])  
for i in used[:-1]:
    print(i)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
dic = [[-1]*(N+1) for _ in range(N+1)]
M = [[] for _ in range(N+1)]
used = [-1]*(N+1) 
for i in range(N-1):
    u,v,w = map(int,input().split())
    M[u-1].append([v-1,w])
    M[v-1].append([u-1,w])


from collections import deque 
q = deque()
q.append([0,0])
used[0] = 0
# print(M)
while q:
    # print(q)
    e,c = q.pop()
    for i,d in M[e]:
        if used[i]==-1:
            C = (c+d)%2
            used[i] = C
            q.append([i,C])  
for i in used[:-1]:
    print(i)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
dic = [[-1]*(N+1) for _ in range(N+1)]
M = [[] for _ in range(N+1)]
used = [-1]*(N+1) 
for i in range(N-1):
    u,v,w = map(int,input().split())
    dic[u-1][v-1]=w
    dic[v-1][u-1]=w
    M[u-1].append(v-1)
    M[v-1].append(u-1)


from collections import deque 
q = deque()
q.append([0,0])
used[0] = 0
# print(M)
while q:
    # print(q)
    e,c = q.pop()
    for i in M[e]:
        if used[i]==-1:
            C = (c+dic[i][e])%2
            used[i] = C
            q.append([i,C])  
for i in used[:-1]:
    print(i)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

N = int(input())
color = [0]*(N+1)
q = deque()

u, v, w = map(int, input().split())
finded = set([u, v])
color[v] = (color[u] + (w % 2)) % 2

for _ in range(N-2):
    u, v, w = map(int, input().split())
    if u in finded:
        finded.add(v)
        color[v] = (color[u] + (w % 2)) % 2
    elif v in finded:
        finded.add(u)
        color[u] = (color[v] + (w % 2)) % 2
    else:
        q.append([u, v, w])

while len(q) != 0:
    u, v, w = q.popleft()
    if u in finded:
        finded.add(v)
        color[v] = (color[u] + (w % 2)) % 2
    elif v in finded:
        finded.add(u)
        color[u] = (color[v] + (w % 2)) % 2
    else:
        q.append([u, v, w])

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

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

N = int(input())
finded = set([1])
color = [0]*(N+1)
q = deque()

for _ in range(N-1):
    u, v, w = map(int, input().split())
    if u in finded:
        finded.add(v)
        color[v] = (color[u] + (w % 2)) % 2
    elif v in finded:
        finded.add(u)
        color[u] = (color[v] + (w % 2)) % 2
    else:
        q.append([u, v, w])

while len(q) != 0:
    u, v, w = q.popleft()
    if u in finded:
        finded.add(v)
        color[v] = (color[u] + (w % 2)) % 2
    elif v in finded:
        finded.add(u)
        color[u] = (color[v] + (w % 2)) % 2
    else:
        q.append([u, v, w])

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

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**9)
 
N = int(input())
uvw = [[int(x) for x in input().split()] for _ in range(N-1)]
 
 
def bfs(uvw, status, check, now_p):
    for i in range(N-1):
        if check[i] == 1:
            continue

        if uvw[i][0] == now_p:
            check[i] = 1
            status[uvw[i][1] - 1] = status[now_p - 1] + uvw[i][2]
            bfs(uvw, status, check, uvw[i][1])
            continue
 
        if uvw[i][1] == now_p:
            check[i] = 1
            status[uvw[i][0] - 1] = status[now_p - 1] + uvw[i][2]
            bfs(uvw, status, check, uvw[i][0])
            continue

    return status
 
 
#from 1
status = [0] * N
check =  [0] * (N-1)
 
status = bfs(uvw, status, check, 1)
for arrr in status:
    print(arrr%2)

Submission status: Time Limit Exceeded

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

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


def bfs(uvw, status, check, now_p):
    for i in range(N-1):
        if uvw[i][0] == now_p and check[i] == 0:
            check[i] = 1
            status[uvw[i][1] - 1] = status[now_p - 1] + uvw[i][2]
            bfs(uvw, status, check, uvw[i][1])

        if uvw[i][1] == now_p and check[i] == 0:
            check[i] = 1
            status[uvw[i][0] - 1] = status[now_p - 1] + uvw[i][2]
            bfs(uvw, status, check, uvw[i][0])

    return status


#from 1
status = [0] * N
check =  [0] * (N-1)

status = bfs(uvw, status, check, 1)
for arrr in status:
    print(arrr%2)

Submission status: Time Limit Exceeded

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


def bfs(uvw, status, check, now_p):
    for i in range(N-1):
        if uvw[i][0] == now_p and check[i] == 0:
            check[i] = 1
            status[uvw[i][1] - 1] = status[now_p - 1] + uvw[i][2]
            bfs(uvw, status, check, uvw[i][1])

        if uvw[i][1] == now_p and check[i] == 0:
            check[i] = 1
            status[uvw[i][0] - 1] = status[now_p - 1] + uvw[i][2]
            bfs(uvw, status, check, uvw[i][0])

    return status


#from 1
status = [0] * N
check =  [0] * (N-1)


status = bfs(uvw, status, check, 1)
for arrr in status:
    if arrr % 2 == 0:
        print('0')
    else:
        print('1')

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

n = int(input())
c = np.array([[0] * n] * n, dtype=np.uint8)
for i in range(n - 1):
    s = list(map(int, input().split()))
    c[s[0] - 1, s[1] - 1] = s[2]
    c[s[1] - 1, s[0] - 1] = s[2]


def calDistance_dfs(c, d, start=0):
    d[start] = 0
    stack = []
    stack.append(start)
    while len(stack) != 0:
        current = stack.pop()
        for idx, val in enumerate(c[current, :]):
            if val != 0 and d[idx] == -1:
                stack.append(idx)
                d[idx] = d[current] + val



d = np.array([-1] * n)
calDistance_dfs(c, d, 0)

for i in d:
    print(i % 2)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

n = int(input())
searching = deque()
searched = deque()


def flatten(data):
    for item in data:
        if hasattr(item, '__iter__'):
            for element in flatten(item):
                yield element
        else:
            yield item


distance_matrix = [[-1 for _ in range(n)] for _ in range(n)]
for i in range(n):
    distance_matrix[i][i] = 0
distance_from_one = [0 for _ in range(n)]
tree = [[] for _ in range(n)]

for i in range(n-1):
    array = list(map(int, input().split()))
    x = array[0]
    y = array[1]
    z = array[2]
    distance_matrix[x-1][y-1] = z
    distance_matrix[y-1][x-1] = z
    tree[x-1].append(y-1)
    tree[y-1].append(x-1)
for i in tree[0]:
    searching.append(i)
    distance_from_one[i] = distance_matrix[0][i]
searched.append(0)


while len(searching) != 0:
    node = searching.popleft()
    if node not in searched:
        searched.append(node)
        for node_2 in tree[node]:
            if node_2 not in searching and node_2 not in searched:
                distance_from_one[node_2] = distance_from_one[node] + distance_matrix[node][node_2]
                searching.append(node_2)

for i in distance_from_one:
    if i%2 == 0:
        print(1)
    else:
        print(0)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
ki = [[]for i in range(n)]
dist = [[0]*n for i in range(n)]
d = [0]*n
for i in range(n-1):
    u,v,w = map(int,input().split())
    u -= 1
    v -= 1
    ki[u].append(v)
    ki[v].append(u)
    dist[u][v] = w
    dist[v][u] = w
def dfs(now,last = -1):
    for next in ki[now]:
        if next == last:continue
        d[next] = d[now] + dist[now][next]
        dfs(next,now)
dfs(0)

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

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
UVW = []
for n in range(N - 1):
    uvw = [int(s) for s in input().split(' ')]
    UVW.append(uvw)
c = [-1] * (N + 1)
u1, _, _ = UVW[0]
c[u1] = 0

while UVW:
    skip_UVW = []
    for u, v, w in UVW:
        if c[u] == -1 and c[v] == -1:
            skip_UVW.append((u, v, w))
            continue
        if w % 2 == 0:
            if c[u] != -1:
                c[v] = c[u]
            else:
                c[u] = c[v]
        else:
            if c[u] == 0:
                c[v] = 1
            elif c[u] == 1:
                c[v] = 0
            elif c[v] == 0:
                c[u] = 1
            elif c[v] == 1:
                c[u] = 0
    UVW = skip_UVW

for ret in c[1:]:
    print(ret)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
UVW = []
for n in range(N - 1):
    uvw = [int(s) for s in input().split(' ')]
    UVW.append(uvw)
UVW.sort()
c = [-1] * (N + 1)
u1, _, _ = UVW[0]
c[u1] = 0

while UVW:
    skip_UVW = []
    for u, v, w in UVW:
        if c[u] == -1 and c[v] == -1:
            skip_UVW.append((u, v, w))
            continue
        if w % 2 == 0:
            if c[u] != -1:
                c[v] = c[u]
            else:
                c[u] = c[v]
        else:
            if c[u] == 0:
                c[v] = 1
            elif c[u] == 1:
                c[v] = 0
            elif c[v] == 0:
                c[u] = 1
            elif c[v] == 1:
                c[u] = 0
    UVW = skip_UVW

for ret in c[1:]:
    print(ret)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
N = int(input())
uvw = [[]for i in range(N)]
for i in range(N-1):
    u,v,w = list(map(int,input().split()))
    uvw[u-1].append([v-1,w%2])
    uvw[v-1].append([u-1,w%2])    
color = [0 for i in range(N)]
que = deque()
que.append(0)
alr = [0]
while que:
    q = que.popleft()
    colorq = color[q]
    for i in uvw[q]:
        if i[0] not in alr:
            que.append(i[0])
            alr.append(i[0])
            if i[1] == 0:
                color[i[0]] = colorq
            else:
                color[i[0]] = abs(colorq-1)
for i in color:
    print(i)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
L = [-1 for i in range(N)]
flg = [0 for i in range(N)]
D = {}
S = []
A = []
u, v, w = map(int, input().split())
if w % 2 == 0:
  D[u], D[v] = 0, 0
else:
  D[u], D[v] = 0, 1
for i in range(N - 2):
  u, v, w = map(int, input().split())
  if u in D:
    D[v] = (D[u] + w) % 2
  elif v in D:
    D[u] = (D[v] + w) % 2
  else:
    if w % 2 == 0:
      S.append([u, v])
    else:
      A.append([u, v])
while len(D) != N:
  for i in range(len(S)):
    if S[i][0] in D:
      D[S[i][1]] = D[S[i][0]]
    elif S[i][1] in D:
      D[S[i][0]] = D[S[i][1]]
  for i in range(len(A)):
    if A[i][0] in D:
      D[A[i][1]] = (D[A[i][0]] + 1) % 2
    elif A[i][1] in D:
      D[A[i][0]] = (D[A[i][1]] + 1) % 2
for i in range(1, N+1):
  print(D[i])

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
li=[list(map(int,input().split())) for i in range(n-1)]

#色の情報を記録する配列を作る。0が白で、1が黒
col=[-1]*(n+1) #最初は全ての頂点が情報なし。
col[1]=0 #頂点1の色は白。

#2点間の距離の情報を記録する配列を作る
#ついでにグラフも作る
kyori=[[0]*(n+1) for i in range(n+1)]
graph = [[] for _ in range(n+1)]

for x,y,z in li:
  kyori[x][y]=kyori[y][x]=z
  graph[x].append(y)
  graph[y].append(x)

def dfs(v):
    dist = [-1] * (n+1)
    stack = [v]
    dist[v] = 0
    while stack:
        v = stack.pop()
        dw = dist[v] + 1
        for w in graph[v]: #頂点vに接続してる点についての調査
            if dist[w] >= 0: #0以上であれば既に調査済み
                continue
            dist[w] = dw #調査済みでない場合は、distに現在の深さを記録。
            if kyori[v][w]%2:
              col[w]=col[v]^1
            else:
              col[w]=col[v]
            stack.append(w)
    return col
print(*dfs(1)[1:], sep="\n")

Submission status: Time Limit Exceeded

Solution code:
import sys

input = sys.stdin.readline

n = int(input())
graph = [[] for i in range(n + 1)]
cost = [[None] * (n + 1) for j in range(n + 1)]
for i in range(n - 1):
    u, v, w = map(int, input().split())
    graph[u].append(v)
    graph[v].append(u)
    cost[u][v] = w
    cost[v][u] = w
ans = [] * (n + 1)


def dfs(a):
    dist = [-1] * (n + 1)
    stack = [a]
    dist[a] = 0
    while stack:
        v = stack.pop()
        for w in graph[v]:
            if dist[w] == -1:
                dist[w] = dist[v] + cost[w][v]
                dist[w] %= 2
                stack.append(w)
            else:
                continue
    return dist


dist = dfs(1)
print(*dist[1:], sep="\n")

Submission status: Time Limit Exceeded

Solution code:
import sys

input = sys.stdin.readline

n = int(input())
graph = [[] for i in range(n + 1)]
cost = [[[] for i in range(n + 1)] for j in range(n + 1)]
for i in range(n - 1):
    u, v, w = map(int, input().split())
    graph[u].append(v)
    graph[v].append(u)
    cost[u][v] = w
    cost[v][u] = w
ans = [] * (n + 1)


def dfs(a):
    dist = [-1] * (n + 1)
    stack = [a]
    dist[a] = 0
    while stack:
        v = stack.pop()
        for w in graph[v]:
            if dist[w] == -1:
                dist[w] = (dist[v] + cost[w][v])%2
                stack.append(w)
            else:
                continue
    return dist


dist = dfs(1)
print(*dist[1:], sep="\n")

Submission status: Time Limit Exceeded

Solution code:
import sys

input = sys.stdin.readline

n = int(input())
graph = [[] for i in range(n + 1)]
cost = [[[] for i in range(n + 1)] for j in range(n + 1)]
for i in range(n - 1):
    u, v, w = map(int, input().split())
    graph[u].append(v)
    graph[v].append(u)
    cost[u][v] = w
    cost[v][u] = w
ans = [] * (n + 1)


def dfs(a):
    dist = [-1] * (n + 1)
    stack = [a]
    dist[a] = 0
    while stack:
        v = stack.pop()
        for w in graph[v]:
            if dist[w] == -1:
                dist[w] = dist[v] + cost[w][v]
                dist[w] %= 2
                stack.append(w)
            else:
                continue
    return dist


dist = dfs(1)
print(*dist[1:], sep="\n")

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
graph = [[] for i in range(n + 1)]
cost = [[[] for i in range(n + 1)] for j in range(n + 1)]
for i in range(n - 1):
    u, v, w = map(int, input().split())
    graph[u].append(v)
    graph[v].append(u)
    cost[u][v] = w
    cost[v][u] = w
ans = [] * (n + 1)


def dfs(a):
    dist = [-1] * (n + 1)
    stack = [a]
    dist[a] = 0
    while stack:
        v = stack.pop()
        for w in graph[v]:
            if dist[w] == -1:
                dist[w] = dist[v] + cost[w][v]
                dist[w] %= 2
                stack.append(w)
            else:
                continue
    return dist


dist = dfs(1)
print(*dist[1:], sep="\n")

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(500*500);

def dfs(G,v,bef_v):
	if v == bef_v :
		seen[v] = 0;
	else :
		#print(bef_v,v,G[v],weight[bef_v][v],seen[bef_v])
		ind = 0;
		for i in range(len(G[bef_v][0])) :
			if G[bef_v][0][i] == v :
				ind = i;
		if G[bef_v][1][ind] % 2 :
			seen[v] = int(not seen[bef_v]);
		else :
			seen[v] = seen[bef_v];
	
	for next_v in G[v][0] :
		if seen[next_v]==-1 :
			dfs(G,next_v,v);


n = int(input());
G = [[0]*2 for i in range(n) ];
for i in range(n) :
	G[i][0] = [];
	G[i][1] = [];
for i in range(n-1) :
	s = input().split(' ');
	u = int(s[0])-1;
	v = int(s[1])-1;
	w = int(s[2]);
	G[u][0].append(v);
	G[v][0].append(u);
	G[u][1].append(w);
	G[v][1].append(w);


seen = [-1]*n;
dfs(G,0,0);

for i in range(n):
	print(seen[i]);

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(500*500);

def dfs(G,v,bef_v):
	#print(bef_v,v,G[v],weight[bef_v][v],seen[bef_v])
	if weight[bef_v][v] % 2 :
		seen[v] = int(not seen[bef_v]);
	else :
		seen[v] = seen[bef_v];
	
	for next_v in G[v] :
		if seen[next_v]==-1 :
			dfs(G,next_v,v);


n = int(input());
weight = [[0]*n for i in range(n) ];
G = [0]*n;
for i in range(n) :
	G[i] = [];
for i in range(n-1) :
	s = input().split(' ');
	u = int(s[0])-1;
	v = int(s[1])-1;
	w = int(s[2]);
	G[u].append(v);
	G[v].append(u);
	weight[u][v] = w;
	weight[v][u] = w;


seen = [-1]*n;
seen[0] = 0;
dfs(G,0,0);

for i in range(n):
	print(seen[i]);

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
uvw=[list(map(int, input().split())) for i in range(N-1)]
mat=[[0]*(N+1) for i in range(N+1)]
nodelink=[[] for i in range(N+1)]
for i in range(N-1):
  mat[uvw[i][0]][uvw[i][1]]=uvw[i][2]
  mat[uvw[i][1]][uvw[i][0]]=uvw[i][2]
  nodelink[uvw[i][0]].append(uvw[i][1])
  nodelink[uvw[i][1]].append(uvw[i][0])
  
color=[-1]*(N+1)

def f(nuru, iro):
  color[nuru]=iro
  tonari=nodelink[nuru]
  for nuruyo in tonari:
    if color[nuruyo]<0:
      if (mat[nuru][nuruyo]%2)==0:
        f(nuruyo, iro)
      else:
        f(nuruyo, 1-iro)
      
f(1, 0)

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

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
uvw=[list(map(int, input().split())) for i in range(N-1)]
mat=[[0]*(N+1) for i in range(N+1)]
nodelink=[[] for i in range(N+1)]
for i in range(N-1):
  mat[uvw[i][0]][uvw[i][1]]=uvw[i][2]
  mat[uvw[i][1]][uvw[i][0]]=uvw[i][2]
  nodelink[uvw[i][0]].append(uvw[i][1])
  nodelink[uvw[i][1]].append(uvw[i][0])
  
color=[-1]*(N+1)

def f(nuru, iro):
  color[nuru]=iro
  tonari=g(nuru)
  for nuruyo in tonari:
    if color[nuruyo]<0:
      if h(nuru, nuruyo)==0:
        f(nuruyo, iro)
      else:
        f(nuruyo, 1-iro)
      
def g(x):
  return nodelink[x]

def h(a, b):
  return mat[a][b]%2

f(1, 0)

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

Submission status: Time Limit Exceeded

Solution code:
N, = map(int, input().split())
import sys
sys.setrecursionlimit(10**6)
d = [set() for _ in range(N+1)]
Cs = [0 for _ in range(N+1)]
for _ in range(N-1):
    u, v, p = map(int, input().split())
    d[u].add((v, p))
    d[v].add((u, p))

def it(v, p):
    for u, c in d[v]:
        if u == p:
            continue
        Cs[u] = int(not Cs[v]) if c%2 else Cs[v]
        it(u, v)
it(1, None)
for i in range(1, N+1):
    print(Cs[i])

Submission status: Time Limit Exceeded

Solution code:
#coding: utf-8
import math
import heapq
import bisect
import numpy as np
#from scipy.misc import comb

N = int(input())

G = [[-1]*(N+1) for _ in range(N+1)]

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

dist = [-1]*(N+1)
dist[1] = 0

def dfs(u):
    for v in range(1,N+1):
        if G[u][v] != -1:
            if dist[v] == -1:
                dist[v] = (dist[u]+G[u][v])%2
                dfs(v)

dfs(1)

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

Submission status: Time Limit Exceeded

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

N=int(input())
L=[0]*(N-1) 
MAP=[-1]*(N+1)
MAP[1]=0
for i in range(N-1):
    L[i]=list(map(int,input().split()))
    t=[L[i][1],L[i][0],L[i][2]]
    L.append(t)

L1=sorted(L,key=lambda x: (x[0],x[1]))
LIST=[[]for i in range(N+1)]

for i in range(len(L)):
    LIST[L1[i][0]].append([L1[i][1],L1[i][2]])

def calc(k):
    global MAP
    for i in range(len(LIST[k])):
        #print(LIST[k],len(LIST[k]))
        if(MAP[LIST[k][i][0]]==-1):
            MAP[LIST[k][i][0]]=(MAP[k]+LIST[k][i][1])%2
            #print(LIST[k][i][0],MAP[LIST[k][i][0]])
            calc(LIST[k][i][0])

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

Submission status: Time Limit Exceeded

Solution code:
import bisect

N=int(input())
L=[0]*(N-1) 
MAP=[0]*(N+1)
for i in range(N-1):
    L[i]=list(map(int,input().split()))
L1=sorted(L,key=lambda x: (x[0],x[1]))
L2=sorted(L,key=lambda x: (x[1],x[0]))
LIST=[1]


f=0
c=0
k=0
t=LIST[k]
while(len(LIST)<N):
    while(N-1>c):
        if(L1[c][0]==t):
            f=1
            if(LIST.count(L1[c][1])==0):
                LIST.append(L1[c][1])
                MAP[L1[c][1]]=(MAP[L1[c][0]]+L1[c][2])%2
        elif(f==1):
            break
        c+=1
    f=0
    c=0

    while(N-1>c):
        if(L2[c][1]==t):
            f=1
            if(LIST.count(L2[c][0])==0):
                LIST.append(L2[c][0])
                MAP[L2[c][0]]=(MAP[L2[c][1]]+L2[c][2])%2
        elif(f==1):
            break
        c+=1
    f=0
    c=0

    k+=1
    t=LIST[k]




      

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