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 queue
import sys
sys.setrecursionlimit(10**6)

N = int(input())
uvw = []
for _ in range(N-1):
    uvw.append(tuple(map(int, input().split())))

G=[[0]*(N+1) for _ in range(N+1)]
for el in uvw:
    G[el[0]][el[1]]=el[2]
    G[el[1]][el[0]] = el[2]
#print(G)

H=[[] for _ in range(N+1)]
for el in uvw:
    H[el[0]].append(el[1])
    H[el[1]].append(el[0])
#print(H)

seen=[False]*(N+1)
distance=[0]*(N+1)
todo=queue.Queue()
def dfs(n):
    seen[n]=True
    for nxt in H[n]:
        if seen[nxt] == False:
            distance[nxt] = distance[n] + G[n][nxt]
            todo.put(nxt)
    if todo.empty():
        return None
    else:
        dfs(todo.get())

dfs(1)
#print(distance)
#print(seen)

for val in distance[1:]:
    if val % 2 == 0:
        print(0)
    else:
        print(1)

Submission status: Time Limit Exceeded

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

N = int(input())
uvw = []
for _ in range(N-1):
    uvw.append(tuple(map(int, input().split())))

G=[[0]*(N+1) for _ in range(N+1)]
for el in uvw:
    G[el[0]][el[1]]=el[2]
    G[el[1]][el[0]] = el[2]
#print(G)

H=[[] for _ in range(N+1)]
for el in uvw:
    H[el[0]].append(el[1])
    H[el[1]].append(el[0])
#print(H)

seen=[False]*(N+1)
distance=[0]*(N+1)
def dfs(n):
    seen[n]=True
    for nxt in H[n]:
        if seen[nxt] == False:
            distance[nxt] = distance[n] + G[n][nxt]
            dfs(nxt)

dfs(1)
#print(distance)
#print(seen)

for val in distance[1:]:
    if val % 2 == 0:
        print(0)
    else:
        print(1)

Submission status: Time Limit Exceeded

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

G=[[0]*(N+1) for _ in range(N+1)]
for el in uvw:
    G[el[0]][el[1]]=el[2]
    G[el[1]][el[0]] = el[2]
#print(G)

H=[[] for _ in range(N+1)]
for el in uvw:
    H[el[0]].append(el[1])
    H[el[1]].append(el[0])
#print(H)

seen=[False]*(N+1)
distance=[0]*(N+1)
def dfs(n):
    seen[n]=True
    for nxt in H[n]:
        if seen[nxt] == False:
            distance[nxt] = distance[n] + G[n][nxt]
            dfs(nxt)

dfs(1)
#print(distance)
#print(seen)

for val in distance[1:]:
    if val % 2 == 0:
        print(0)
    else:
        print(1)

Submission status: Time Limit Exceeded

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

g1 = [[0]*n for _ in range(n)]
for i,j,k in ns:
    g1[i - 1][j - 1] = k
    g1[j - 1][i - 1] = k

from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import floyd_warshall
graph = csr_matrix(g1)

dist_matrix = floyd_warshall(csgraph=graph, directed=False)

ans = [0]*n
for i,j in enumerate(dist_matrix[0]):
    if j % 2 == 1:
        ans[i] = 1

for i in ans:
    print(i)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
G = [[-1 for _ in range(N)] for _ in range(N)]
for _ in range(N - 1):
    u, v, w = map(int, input().split())
    G[u - 1][v - 1] = G[v - 1][u - 1] = w % 2

C = [-1 for _ in range(N)]


def dfs(pos, color):
    for i in range(N):
        if C[i] != -1:
            continue
        # even
        if G[pos][i] == 0:
            c = color
            C[i] = c
            dfs(i, c)
        # odd
        elif G[pos][i] == 1:
            c = 1 - color
            C[i] = c
            dfs(i, c)


C[0] = 0
dfs(0, 0)
for i in range(N):
    print(C[i])

Submission status: Time Limit Exceeded

Solution code:
def main():
    import collections
    import sys
    input = sys.stdin.readline
    N = int(input())
    uvw = [map(int, input().split()) for i in range(N-1)]

    G = [[-1]*N for i in range(N)]
    for u, v, w in uvw:
        u -= 1
        v -= 1
        G[u][v] = w
        G[v][u] = w
    q = collections.deque()
    q.append((0, 0))
    s = set(range(1, N))
    ans = [0]*N
    while(q):
        x, a = q.popleft()
        tmp = set()
        for y in s:
            if G[x][y] > 0:
                q.append((y, a+G[x][y]))
                ans[y] = (a+G[x][y]) % 2
                tmp.add(y)
        s -= tmp
    print(*ans, sep="\n")


main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    import collections
    import sys
    input = sys.stdin.readline
    N = int(input())
    uvw = [map(int, input().split()) for i in range(N-1)]

    G = [[-1]*N for i in range(N)]
    for u, v, w in uvw:
        u -= 1
        v -= 1
        G[u][v] = w
        G[v][u] = w
    q = collections.deque()
    q.append((0, 0))
    s = set(range(1, N))
    ans = [0]*N
    while(q):
        x, a = q.popleft()
        tmp = set()
        for y in s:
            if G[x][y] > 0:
                q.append((y, a+G[x][y]))
                ans[y] = (a+G[x][y]) % 2
                tmp.add(y)
        s -= tmp
    print(*ans, sep="\n")
main()

Submission status: Time Limit Exceeded

Solution code:
import sys 
sys.setrecursionlimit(100000000)
n = int(input())
graph = [[] for _ in range(n)]
color = [-1]*n
dist = [-1]*n
dist[0] = 0
visited = [0]*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]]
  
def dfs(u, d):
  visited[u] = 1
  if sum(visited) == n:
    return 
  for v, w in graph[u]:
    if dist[v] == -1:
      dist[v] = (w + d) % 2
      dfs(v, d+w)
      
dfs(0, 0)
for i in dist:
  print(i)

Submission status: Time Limit Exceeded

Solution code:
import sys 
sys.setrecursionlimit(100000000)
n = int(input())
graph = [[] for _ in range(n)]
color = [-1]*n
dist = [-1]*n
dist[0] = 0
visited = [0]*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]]
 
def dfs(u):
  visited[u] = 1
  if sum(visited) == n:
    return 
  for v, w in graph[u]:
    if dist[v] == -1:
      dist[v] = (dist[u] + w) % 2
      dfs(v)

dfs(0)
for i in dist:
  print(i)

Submission status: Time Limit Exceeded

Solution code:
import sys 
sys.setrecursionlimit(100000000)
n = int(input())
graph = [[] for _ in range(n)]
col = [-1]*n
dist = [float('inf')]*n
dist[0] = 0
visited = [0]*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]]

def dfs(u):
  if sum(visited) == n:
    return 
  for v, w in graph[u]:
    if dist[v] == float('inf'):
      dist[v] = dist[u] + w 
      dfs(v)

  return 

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

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**9)                    #再帰の深さブースト

n = int(input())
edge = {}
ans = [0 for i in range(n)]
for i in range(n):
    edge[i] = {}
for i in range(n-1):
    u,v,w = map(int, input().split())
    edge[u-1][v-1] = w
    edge[v-1][u-1] = w

def bfsC(pre, now, nowc):
    for node, weight in edge[now].items():
        if node != pre:
            if weight%2 == 0:
                ans[node] = nowc
            else:
                ans[node] = 1 - nowc
            bfsC(now, node, ans[node])
bfsC(-1, 0, 0)
for i in range(n):
    print(ans[i])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import sys
N=int(input())
numbers=[]
for _ in range(N-1):
    u,v,w=map(int,input().split())
    numbers.append([u-1,v-1,w])
inf=pow(10,9)
route=[[inf for _ in range(N)] for _ in range(N)]
for a in numbers:
    route[a[0]][a[1]]=a[2]
    route[a[1]][a[0]]=a[2]
visited_point=[inf for _ in range(N)]
visited_point[0]=0
stack=deque([0])
while len(stack)>0:
    n=stack.popleft()
    number=0
    for z in route[n]:
        if z==inf:
            number+=1
            continue
        if visited_point[number]==inf:
            visited_point[number]=visited_point[n]+z
            stack.append(number)
        number+=1
for a in visited_point:
    if a%2==0:
        print(0)
    else:
        print(1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import sys
N=int(input())
numbers=[]
for _ in range(N-1):
    if __name__ == '__main__':
        u,v,w=sys.stdin.readline().split()
    numbers.append([int(u)-1,int(v)-1,int(w)])
inf=pow(10,9)
route=[[inf for _ in range(N)] for _ in range(N)]
for a in numbers:
    route[a[0]][a[1]]=a[2]
    route[a[1]][a[0]]=a[2]
visited_point=[inf for _ in range(N)]
visited_point[0]=0
stack=deque([0])
while len(stack)>0:
    n=stack.popleft()
    number=0
    for z in route[n]:
        if z==inf:
            number+=1
            continue
        if visited_point[number]==inf:
            visited_point[number]=visited_point[n]+z
            stack.append(number)
        number+=1
for a in visited_point:
    if a%2==0:
        print(0)
    else:
        print(1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
N=int(input())
numbers=[]
for _ in range(N-1):
    u,v,w=input().split()
    numbers.append([int(u)-1,int(v)-1,int(w)])
inf=pow(10,9)
route=[[inf for _ in range(N)] for _ in range(N)]
for a in numbers:
    route[a[0]][a[1]]=a[2]
    route[a[1]][a[0]]=a[2]
visited_point=[inf for _ in range(N)]
visited_point[0]=0
stack=deque([0])
while len(stack)>0:
    n=stack.popleft()
    number=0
    for z in route[n]:
        if z==inf:
            number+=1
            continue
        if visited_point[number]==inf:
            visited_point[number]=visited_point[n]+z
            stack.append(number)
        number+=1
for a in visited_point:
    if a%2==0:
        print(0)
    else:
        print(1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
N=int(input())
numbers=[]
for _ in range(N-1):
    u,v,w=input().split()
    numbers.append([int(u)-1,int(v)-1,int(w)])
inf=pow(10,9)
route=[[inf for _ in range(N)] for _ in range(N)]
for a in numbers:
    route[a[0]][a[1]]=a[2]
    route[a[1]][a[0]]=a[2]
visited_point=[inf for _ in range(N)]
visited_point[0]=0
stack=deque([0])
while len(stack)>0:
    n=stack.pop()
    number=0
    for z in route[n]:
        if z==inf:
            number+=1
            continue
        if visited_point[number]==inf:
            visited_point[number]=visited_point[n]+z
            stack.appendleft(number)
        number+=1
for a in visited_point:
    if a%2==0:
        print(0)
    else:
        print(1)

Submission status: Time Limit Exceeded

Solution code:
from _collections import deque
N=int(input())
numbers=[]
for _ in range(N-1):
    u,v,w=input().split()
    numbers.append([int(u)-1,int(v)-1,int(w)])
inf=pow(10,9)
route=[[inf for _ in range(N)] for _ in range(N)]
for a in numbers:
    route[a[0]][a[1]]=a[2]
    route[a[1]][a[0]]=a[2]
visited_point=[inf for _ in range(N)]
visited_point[0]=0
stack=deque([0])
while len(stack)>0:
    n=stack.pop()
    number=0
    for z in route[n]:
        if z==inf:
            number+=1
            continue
        if visited_point[number]==inf:
            visited_point[number]=visited_point[n]+z
            stack.appendleft(number)
        number+=1
for a in visited_point:
    if a%2==0:
        print(0)
    else:
        print(1)

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(10**5 + 1)

n = int(input())
go = [[]for _ in range(n)]
ge = [[]for _ in range(n)]

for _ in range(n-1):
    x,y,z = map(int, input().split())
    if z % 2 == 0:
        ge[x-1].append(y-1)
        ge[y-1].append(x-1)
    else:
        go[x-1].append(y-1)
        go[y-1].append(x-1)

color = [0] * n

def dfs(v, c):
    color[v] = c
    for i in range(len(go[v])):
        if color[go[v][i]] == 0:
            dfs(go[v][i], -c)
    for i in range(len(ge[v])):
        if color[ge[v][i]] == 0:
            dfs(ge[v][i], c)

dfs(0, 1)

for i in range(n):
    if color[i] == -1:
        print(0)
    else:
        print(1)

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

################################
def main():
    import sys 
    input=sys.stdin.readline
    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())
        cost[x-1][y-1]=z
        cost[y-1][x-1]=z
    length=(dijkstra(0,n,w,cost))
    
    for i in length:
        if i%2==0:
            print(0)
        else:
            print(1)
if __name__=="__main__":
    main()

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())
    cost[x-1][y-1]=z
    cost[y-1][x-1]=z
length=(dijkstra(0,n,w,cost))

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

Submission status: Time Limit Exceeded

Solution code:
import sys
input=sys.stdin.readline
n=int(input())

#グラフの連結成分を調べる
def Graph():
    G=[[] for i in range(n)]
    #up_G=[0]*n#up_G[i]=頂点iの親
    for i in range(n-1):
        a,b,c=map(int,input().split())
        c=0 if c%2==0 else 1
        G[a-1].append((b,c))
        G[b-1].append((a,c))
    return G

#木上のDFSテンプレ
from collections import deque
def dfs(G,v,p):
    q=deque()
    q.append((v,p))
    dis=0
    dis_l=[-1]*n
    dis_l[0]=0
    while q:
        V,P=q[-1]
        for new_v in G[V-1]:
            v0,v1=new_v
            #new_vが頂点の時はアウト
            if v0==P:continue
            if dis_l[v0-1]>=0:continue
            dis=(dis_l[V-1]+v1)%2
            dis_l[v0-1]=dis
            q.append((v0,V))
            break
        else:
            q.pop()
    return dis_l


log=Graph()
ans=dfs(log,1,-1)
print(*ans,sep='\n')

Submission status: Time Limit Exceeded

Solution code:
def main():
    from collections import deque
    import sys
    input = sys.stdin.buffer.readline
    N = int(input())
    edge = [[] for _ in range(N)]
    for i in range(N-1):
        a, b, c = (int(i) for i in input().split())
        edge[a-1].append((c % 2, b-1))
        edge[b-1].append((c % 2, a-1))

    dist = [-1]*N
    color = [-1]*N

    def dfs(v, G):
        todo = deque([])
        dist[v] = 0
        color[v] = 0
        todo.append(v)
        while todo:
            u = todo[-1]
            for c, next_v in G[u]:
                if dist[next_v] != -1:
                    continue
                dist[next_v] = dist[u] + c
                if dist[next_v] % 2 == 1:
                    color[next_v] = 1
                else:
                    color[next_v] = 0
                todo.append(next_v)
                break
            else:
                todo.pop()

    dfs(0, edge)
    print(*color, sep="\n")
    # print("\n", *dist, sep="\n")


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    input = sys.stdin.buffer.readline
    sys.setrecursionlimit(1000000)
    N = int(input())
    edge = [[] for _ in range(N)]
    for i in range(N-1):
        a, b, c = (int(i) for i in input().split())
        edge[a-1].append((c, b-1))
        edge[b-1].append((c, a-1))

    dist = [-1]*N
    color = [-1]*N

    def dfs(v, G):
        todo = []
        dist[v] = 0
        color[v] = 0
        todo.append(v)
        while todo:
            u = todo[-1]
            for c, next_v in G[u]:
                if dist[next_v] != -1:
                    continue
                dist[next_v] = dist[u] + c
                if dist[next_v] % 2 == 1:
                    color[next_v] = 1
                else:
                    color[next_v] = 0
                todo.append(next_v)
                break
            else:
                todo.pop()

    dfs(0, edge)
    print(*color, sep="\n")
    # print("\n", *dist, sep="\n")


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
input=sys.stdin.readline
n=int(input())

#グラフの連結成分を調べる
def Graph():
    G=[[] for i in range(n)]
    #up_G=[0]*n#up_G[i]=頂点iの親
    for i in range(n-1):
        a,b,c=map(int,input().split())
        c=0 if c%2==0 else 1
        G[a-1].append((b,c))
        G[b-1].append((a,c))
    return G

#木上のDFSテンプレ
from collections import deque
def dfs(G,v,p):
    q=deque()
    q.append((v,p))
    dis=0
    dis_l=[-1]*n
    dis_l[0]=0
    while q:
        V,P=q[-1]
        for new_v in G[V-1]:
            v0,v1=new_v
            #new_vが頂点の時はアウト
            if v0==P:continue
            if dis_l[v0-1]>=0:continue
            dis=dis_l[V-1]+v1
            dis_l[v0-1]=dis
            q.append((v0,V))
            break
        else:
            q.pop()
    return dis_l


log=Graph()
ans=dfs(log,1,-1)

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

Submission status: Time Limit Exceeded

Solution code:
import sys
input=sys.stdin.readline
def main():
    n=int(input())

    #グラフの連結成分を調べる
    def Graph():
        G=[[] for i in range(n)]
        #up_G=[0]*n#up_G[i]=頂点iの親
        for i in range(n-1):
            a,b,c=map(int,input().split())
            G[a-1].append((b,c))
            G[b-1].append((a,c))
        return G

    #木上のDFSテンプレ
    from collections import deque
    def dfs(G,v,p):
        q=deque([])
        q.append([v,p])
        dis=0
        dis_l=[-1]*n
        dis_l[0]=0
        while q:
            V,P=q[-1]
            for new_v in G[V-1]:
                v0,v1=new_v
                #new_vが頂点の時はアウト
                if v0==P:continue
                if dis_l[v0-1]>=0:continue
                dis=dis_l[V-1]+v1
                dis_l[v0-1]=dis
                q.append([v0,V])
                break
            else:
                q.pop()
        return dis_l


    log=Graph()
    ans=dfs(log,1,-1)

    for i in ans:
        if i%2==0:
            print(0)
        else:
            print(1)
            
if __name__=='__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
input=sys.stdin.readline
n=int(input())
uvw=[list(map(int,input().split())) for i in range(n-1)]

#グラフの連結成分を調べる
def Graph(ab):
    G=[[] for i in range(n)]
    #up_G=[0]*n#up_G[i]=頂点iの親
    for a,b,c in ab:
        G[a-1].append((b,c))
        G[b-1].append((a,c))
    return G

#木上のDFSテンプレ
from collections import deque
def dfs(G,v,p):
    q=deque([])
    q.append([v,p])
    dis=0
    dis_l=[-1]*n
    dis_l[0]=0
    while q:
        V,P=q[-1]
        for new_v in G[V-1]:
            v0,v1=new_v
            #new_vが頂点の時はアウト
            if v0==P:continue
            if dis_l[v0-1]>=0:continue
            dis=dis_l[V-1]+v1
            dis_l[v0-1]=dis
            q.append([v0,V])
            break
        else:
            q.pop()
    return dis_l


log=Graph(uvw)
ans=dfs(log,1,-1)

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

Submission status: Time Limit Exceeded

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

#グラフの連結成分を調べる
def Graph(ab):
    G=[[] for i in range(n)]
    #up_G=[0]*n#up_G[i]=頂点iの親
    for a,b,c in ab:
        G[a-1].append((b,c))
        G[b-1].append((a,c))
    return G

#木上のDFSテンプレ
from collections import deque
def dfs(G,v,p):
    q=deque([])
    q.append([v,p])
    dis=0
    dis_l=[-1]*n
    dis_l[0]=0
    while q:
        V,P=q[-1]
        for new_v in G[V-1]:
            v0,v1=new_v
            #new_vが頂点の時はアウト
            if v0==P:continue
            if dis_l[v0-1]>=0:continue
            dis=dis_l[V-1]+v1
            dis_l[v0-1]=dis
            q.append([v0,V])
            break
        else:
            q.pop()
    return dis_l


log=Graph(uvw)
ans=dfs(log,1,-1)

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

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    input = sys.stdin.buffer.readline
    N = int(input())
    edge = [[] for _ in range(N)]
    for i in range(N-1):
        a, b, c = (int(i) for i in input().split())
        edge[a-1].append((c % 2, b-1))
        edge[b-1].append((c % 2, a-1))

    dist = [-1]*N
    color = [-1]*N

    def dfs(v, G):
        todo = []
        dist[v] = 0
        color[v] = 0
        todo.append(v)
        while todo:
            u = todo[-1]
            for c, next_v in G[u]:
                if dist[next_v] != -1:
                    continue
                dist[next_v] = dist[u] + c
                if dist[next_v] % 2 == 1:
                    color[next_v] = 1
                else:
                    color[next_v] = 0
                todo.append(next_v)
                break
            else:
                todo.pop()

    dfs(0, edge)
    print(*color, sep="\n")
    # print("\n", *dist, sep="\n")


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    input = sys.stdin.buffer.readline
    N = int(input())
    edge = [[] for _ in range(N)]
    for i in range(N-1):
        a, b, c = (int(i) for i in input().split())
        edge[a-1].append((c, b-1))
        edge[b-1].append((c, a-1))

    dist = [-1]*N
    color = [-1]*N

    def dfs(v, G):
        todo = []
        dist[v] = 0
        color[v] = 0
        todo.append(v)
        while todo:
            u = todo[-1]
            for c, next_v in G[u]:
                if dist[next_v] != -1:
                    continue
                dist[next_v] = dist[u] + c
                if dist[next_v] % 2 == 1:
                    color[next_v] = 1
                else:
                    color[next_v] = 0
                todo.append(next_v)
                break
            else:
                todo.pop()

    dfs(0, edge)
    print(*color, sep="\n")
    # print("\n", *dist, sep="\n")


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
n = int(input())
graph = [[float('inf') for _ in range(n)] for _ in range(n)]
graph1 = {i:[] for i in range(n)}
for _ in range(n-1):
  u,v,w = map(int,input().split())
  graph[u-1][v-1] = w
  graph[v-1][u-1] = w
  graph1[u-1].append(v-1)
  graph1[v-1].append(u-1)
  
  
color = [-1 for i in range(n)] 
color[0] = 0
def dfs(i,j):#(child, parent)
  for k in graph1[i]:
    if k ==j:
      continue
    if color[k] != -1:
      continue
    if graph[k][i] %2:
      color[k] = 1 -color[i]
    else:
      color[k] = color[i]
    dfs(k,i)
dfs(0,-1)

for i in range(n):
  print(color[i])

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
graph = [[float('inf') for _ in range(n)] for _ in range(n)]
graph1 = {i:[] for i in range(n)}
for _ in range(n-1):
  u,v,w = map(int,input().split())
  graph[u-1][v-1] = w
  graph[v-1][u-1] = w
  graph1[u-1].append(v-1)
  graph1[v-1].append(u-1)
  
  
color = [-1 for i in range(n)] 
color[0] = 0
def dfs(i,j):#(child, parent)
  for k in graph1[i]:
    if k ==j:
      continue
    if color[k] != -1:
      continue
    if graph[k][i] %2:
      color[k] = 1 -color[i]
    else:
      color[k] = color[i]
    dfs(k,i)
dfs(0,-1)

for i in range(n):
  print(color[i])

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy
from collections import deque
sys.setrecursionlimit(10**5)

def input():
    return sys.stdin.readline().rstrip('\n')

N = int(input())

childsof = {i:deque([]) for i in range(N+1)}

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

distances = numpy.full(N+1, -1, dtype=numpy.int32)
distances[1] = 0

def dfs(i):
    childs = childsof[i]

    for c in childs:
        j = c[0]
        if distances[j] == -1:
            distances[j] = distances[i] + c[1]
            dfs(j)

dfs(1)

for d in distances[1:]:
    if d % 2 == 0: #even
        print(0)
    else:
        print(1)

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import dijkstra

def input():
    return sys.stdin.readline().rstrip('\n')

N = int(input())

# めちゃくちゃ遅くて TLE
#V = [[0]*N for _ in range(N)]
#
#for i in range(N-1):
#    u,v,w = list(map(int, input().split()))
#    V[u-1][v-1] = w

U = numpy.zeros(N, dtype=numpy.int32)
V = numpy.zeros(N, dtype=numpy.int32)
W = numpy.zeros(N, dtype=numpy.int32)

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

D = dijkstra(csr_matrix((W,(U,V)), shape=(N,N)), directed=False, indices=0)

for d in D:
    if d % 2 == 0: #even
        print(0)
    else:
        print(1)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/python3
# -*- coding: utf-8 -*-

import sys
import numpy
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import dijkstra

def input():
    return sys.stdin.readline().rstrip('\n')

N = int(input())

# めちゃくちゃ遅くて TLE
#V = [[0]*N for _ in range(N)]
#
#for i in range(N-1):
#    u,v,w = list(map(int, input().split()))
#    V[u-1][v-1] = w

U = numpy.array([0]*N, dtype=numpy.int32)
V = numpy.array([0]*N, dtype=numpy.int32)
W = numpy.array([0]*N, dtype=numpy.int32)

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

D = dijkstra(csr_matrix((W,(U,V)), shape=(N,N)), directed=False, indices=0)

for d in D:
    if d % 2 == 0: #even
        print(0)
    else:
        print(1)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/python3

import sys
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import dijkstra

def input():
    return sys.stdin.readline().rstrip('\n')

N = int(input())

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

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

D = dijkstra(csr_matrix(V), directed=False, indices=0)
#print(D)

for d in D:
    if d % 2 == 0: #even
        print(0)
    else:
        print(1)

Submission status: Time Limit Exceeded

Solution code:
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import dijkstra

N = int(input())

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

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

D = dijkstra(csr_matrix(V), directed=False, indices=0)
#print(D)

for d in D:
    if d % 2 == 0: #even
        print(0)
    else:
        print(1)

Submission status: Time Limit Exceeded

Solution code:
from scipy.sparse.csgraph import dijkstra

N = int(input())

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

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

D = dijkstra(V, directed=False, indices=0)
#print(D)

for d in D:
    if d % 2 == 0: #even
        print(0)
    else:
        print(1)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/python3

import sys
#from collections import deque
#from copy import copy
#from bisect import bisect_right, bisect_left
#import array
from scipy.sparse.csgraph import dijkstra

N = int(input())

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

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

D = dijkstra(V, directed=False, indices=0)
#print(D)

for i in range(0,N):
    if D[i] % 2 == 0: #even
        print(0)
    else:
        print(1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
n = int(input())
lst = [[set(),set()] for i in range(n)]
a = set([1])
b = set()
for i in range(n-1):
    u,v,w = map(int,input().split())
    if w % 2 == 0:
        lst[u-1][0].add(v)
        lst[v-1][0].add(u)
    else:
        lst[u-1][1].add(v)
        lst[v-1][1].add(u)
q = deque([1])
while q:
    i = q.popleft()
    if i in a:
        for j in lst[i-1][0]:
            lst[j-1][0].discard(i)
            q.append(j)
            a.add(j)
        for j in lst[i-1][1]:
            lst[j-1][1].discard(i)
            q.append(j)
            b.add(j)
    if i in b:
        for j in lst[i-1][0]:
            lst[j-1][1].discard(i)
            q.append(j)
            b.add(j)
        for j in lst[i-1][1]:
            lst[j-1][0].discard(i)
            q.append(j)
            a.add(j)
for i in range(1,n+1):
    if i in a:
        print(0)
    else:
        print(1)

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 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()
e = [[] for _ in range(N)]

for _ in range(N-1):
    t = LIST()
    e[t[0]-1].append([t[1]-1, t[2]%2])
    e[t[1]-1].append([t[0]-1, t[2]%2])

a = [0] * N
f = []

"""
for edge in G:
    if edge[2]%2 == 1:
        a[edge[1]-1] = 1 - a[edge[0]-1]
    else:
        a[edge[1]-1] = a[edge[0]-1]
"""
def r(n):
    f.append(n)
    for nn in e[n]:
        if nn[0] not in f:
            if nn[1] == 0:
                a[nn[0]] = a[n]
                r(nn[0])
            else:
                a[nn[0]] = 1 - a[n]
                r(nn[0])

r(0)
for item in a:
    print(item)