Problem:


Score : 400 points

Problem Statement

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

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

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

Constraints

All values in input are integers.

1 \leq N \leq 10^5

1 \leq u_i < v_i \leq N

1 \leq w_i \leq 10^9

Input

Input is given from Standard Input in the following format:

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

Output

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

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

Sample Input 1

3
1 2 2
2 3 1

Sample Output 1

0
0
1

Sample Input 2

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

Sample Output 2

1
0
1
0
1



Sample input:
3
1 2 2
2 3 1


Sample output:
0
0
1

Submission status: Time Limit Exceeded

Solution code:
n = int(input())

u = [0] * n
v = [0] * n
w = [0] * n

color = [-1] * n
dist = [-1] * n
adj_list = [[] for _ in range(n)]

for i in range(n - 1):
    u, v, w = map(int, input().split())
    u -= 1
    v -= 1

    adj_list[u].append([v, w])
    adj_list[v].append([u, w])

q = []
dist[0] = 0
color[0] = 0
q.append(0)

while len(q) > 0:
    node = q.pop(0)

    for next, d in adj_list[node]:
        if dist[next] > 0:
            continue

        if dist[next] == -1 or dist[next] > dist[node] + d:
            dist[next] = dist[node] + d

        q.append(next)

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

Submission status: Time Limit Exceeded

Solution code:
#!python3

def LI():
    return list(map(int, input().split()))

# input
N = int(input())
UVW = [LI() for _ in range(N - 1)]

# params
link = [[] for _ in range(N)]
w = [[None] * N for _ in range(N)]
for u, v, c in UVW:
    u -= 1
    v -= 1
    link[u].append(v)
    link[v].append(u)
    w[u][v] = w[v][u] = c


def dfs(ans, x):
    for y in link[x]:
        if ans[y] is None:
            if w[x][y] % 2 == 0:
                ans[y] = ans[x]
            else:
                ans[y] = 0 if ans[x] else 1
            dfs(ans, y)


def main():
    ans = [None] * N
    ans[0] = 0
    dfs(ans, 0)
    for a in ans:
        print(a)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
#!python3

def LI():
    return list(map(int, input().split()))

# input
N = int(input())
UVW = [LI() for _ in range(N - 1)]

# params
link = [[] for _ in range(N)]
w = [[None] * N for _ in range(N)]
for u, v, c in UVW:
    u -= 1
    v -= 1
    link[u].append(v)
    link[v].append(u)
    w[u][v] = w[v][u] = c


def main():
    ans = [None] * N
    ans[0] = 0
    l = [0]
    while l:
        next_l = []
        for i in l:
            for j in link[i]:
                if ans[j] is None:
                    ans[j] = (ans[i] + w[i][j] % 2) % 2
                    next_l.append(j)
        l = next_l

    for a in ans:
        print(a)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
#!python3

import sys
sys.setrecursionlimit(10 ** 6)


def LI():
    return list(map(int, input().split()))

# input
N = int(input())
UVW = [LI() for _ in range(N - 1)]

# params
link = [[] for _ in range(N)]
w = [[None] * N for _ in range(N)]
for u, v, c in UVW:
    u -= 1
    v -= 1
    link[u].append(v)
    link[v].append(u)
    w[u][v] = w[v][u] = c


def dfs(visit, ans, x):
    visit[x] = True
    for y in link[x]:
        if not visit[y]:
            if w[x][y] % 2 == 0:
                ans[y] = ans[x]
            else:
                ans[y] = 1 ^ ans[x]
            dfs(visit, ans, y)


def main():
    ans = [None] * N
    visit = [False] * N
    ans[0] = 0
    dfs(visit, ans, 0)
    for a in ans:
        print(a)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
#!python3

def LI():
    return list(map(int, input().split()))

# input
N = int(input())
UVW = [LI() for _ in range(N - 1)]

# params
link = [[] for _ in range(N)]
w = [[None] * N for _ in range(N)]
for u, v, c in UVW:
    u -= 1
    v -= 1
    link[u].append(v)
    link[v].append(u)
    w[u][v] = w[v][u] = c


def dfs(ans, x):
    for y in link[x]:
        if ans[y] is None:
            if w[x][y] % 2 == 0:
                ans[y] = ans[x]
            else:
                ans[y] = 1 ^ ans[x]
            dfs(ans, y)


def main():
    ans = [None] * N
    ans[0] = 0
    dfs(ans, 0)
    for a in ans:
        print(a)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from scipy.sparse.csgraph import dijkstra as shortest_path
n = int(input())
Sides = [[0 for i in range(n)] for j in range(n)]
for i in range(n-1):
    u, v, w = map(int, input().split())
    u -= 1
    v -= 1
    Sides[u][v] = w
    Sides[v][u] = w

Path_from_0 = shortest_path(np.array(Sides), indices=0)
for i in range(n):
    print(int(Path_from_0[i]) % 2)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from scipy.sparse.csgraph import shortest_path
n = int(input())
Sides = [[0 for i in range(n)] for j in range(n)]
for i in range(n-1):
    u, v, w = map(int, input().split())
    u -= 1
    v -= 1
    Sides[u][v] = w
    Sides[v][u] = w

Path_from_0 = shortest_path(np.array(Sides))
for i in range(n):
    print(int(Path_from_0[0][i]) % 2)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**7)

# 1 ✕ 1 (int)
N = int(input().rstrip())

# N ✕ M (2D array)
A = list(map(int, input().rstrip().split()) for _ in range(N - 1))

items = [[-1] * (N) for _ in range(N)]
colors = [-1 for _ in range(N)]

for i in range(N - 1):
    a, b, w = A[i]
    items[a - 1][b - 1] = w
    items[b - 1][a - 1] = w


def dfs(v, c):
    colors[v] = c
    for i in range(N):
        w = items[v][i]
        if w == -1:
            continue

        cc = colors[i]
        nc = c if w % 2 == 0 else not c
        if cc != -1 and colors[i] != nc:
            return False
        if cc == -1 and not dfs(i, nc):
            return False

    return True


dfs(0, True)
for c in colors:
    print(int(not c))

Submission status: Time Limit Exceeded

Solution code:
import sys
readline = sys.stdin.readline
from scipy.sparse.csgraph import dijkstra

def main():
    N = int(input())
    path = [[False] * N for _ in range(N)]
    for _ in range(N-1):
        u, v, w = map(int, readline().rstrip().split())
        path[u-1][v-1] = w
        path[v-1][u-1] = w
    
    G = dijkstra(path, indices=0)
    for i in range(N):
        if G[i] % 2 == 0:
            print(0)
        else:
            print(1)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

N = int(input())
# 色を収納するリストの定義
ans = [-1] * N
ans[0] = 1

u_v = []
W = []
for i in range(N-1):
    s = list(map(int, input().split()))
    u_v.append([s[0]-1, s[1]-1])
    W.append(s[2])

# 隣接する点がどこかを表すための多次元リストを作成する。各地点には距離をいれる
inf = float("INF")
Tree = [[inf] * N for _ in range(N)]
for i, (u, v) in enumerate(u_v):
    Tree[u][v] = W[i]
    Tree[v][u] = W[i]

# スタート点を決めた時のdfs
def dfs(Tree, s):
    for i, t in enumerate(Tree[s]):
        # 道が繋がっていて，まだきたことがなければ
        if t != inf and ans[i] == -1:
            ans[i] = ans[s] + t
            dfs(Tree, i)

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

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

N = int(input())
# 色を収納するリストの定義
ans = [-1] * N

u_v = []
W = []
for i in range(N-1):
    s = list(map(int, input().split()))
    u_v.append([s[0]-1, s[1]-1])
    W.append(s[2])

# 隣接する点がどこかを表すための多次元リストを作成する。各地点には距離をいれる
inf = float("INF")
Tree = [[inf] * N for _ in range(N)]
for i, (u, v) in enumerate(u_v):
    Tree[u][v] = W[i]
    Tree[v][u] = W[i]

for i in range(N):
    # まだ到達していない点からスタートするならok
    if ans[i] == -1:
        # queに入れる
        que = deque([])
        que.append(i)
        ans[i] = 1
        while len(que) > 0:
            # まずスタート点が取り出される
            item = que.popleft()
            # queで取り出された点が接続する点に対して処理(BFS)
            for j in range(len(Tree[item])):
                # 接続されていてかつまだきたことがないなら
                if Tree[item][j] != inf and ans[j] == -1:
                    # キューに追加する
                    que.append(j)
                    if Tree[item][j] % 2 == 0:
                        ans[j] = ans[item]
                    else:
                        ans[j] = abs(ans[item] - 1)

for i in ans:
    print(i)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
class UnionFind():
    def __init__(self,n):
        self.n=n
        self.parents = [i for i in range(n+1)]
        self.size = [1]*(n+1)
    def find(self,x):
        if self.parents[x]==x:
            return x
        else:
            self.parents[x]=self.find(self.parents[x])
            return self.parents[x]
    def unite(self,x,y):
        xRoot = self.find(x)
        yRoot = self.find(y)
        if xRoot == yRoot:
            return
        if self.size[xRoot]>self.size[yRoot]:
            self.parents[yRoot] = xRoot
        else:
            self.parents[xRoot] = yRoot
            if self.size[xRoot] == self.size[yRoot]:
                self.size[yRoot]+=1
tree = UnionFind(2*N)
for _ in range(N-1):
    u,v,w = map(int,input().split())
    if w%2==0:
        tree.unite(u,v)
        tree.unite(u+N,v+N)
    else:
        tree.unite(u,N+v)
        tree.unite(v,N+u)
print(0)
for i in range(2,N+1):
    if tree.find(1)==tree.find(i):
        print(0)
    else:
        print(1)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())

u_list = []
v_list = []
w_list = []

for _ in range(N-1):
  u, v, w = map(int, input().split())
  u_list.append(u-1)
  v_list.append(v-1)
  w_list.append(w)
  
color_dict = dict()
uvw_list = list(zip(u_list, v_list, w_list))
color_dict[0] = 1

def eval_single(u, v, w, color_dict):
  skip = True

  if u in color_dict:
    color_dict[v] = assign_color(color_dict[u], w)
    skip = False
    
  if v in color_dict:
    color_dict[u] = assign_color(color_dict[v], w)
    skip = False
    
  return skip, color_dict
  

def assign_color(color, w):
  if w%2==0:
    return color
  else:
    return color*(-1)
  
while True:
  ind_list = []
  for ind, (u, v, w) in enumerate(uvw_list):
    skip, color_dict = eval_single(u, v, w, color_dict)
    
    if skip:
      ind_list.append(ind)

  uvw_list = [uvw_list[ind] for ind in ind_list]
  
  #print(len(color_dict))
  if len(color_dict) == N:
    break

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

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
N=int(input())
road=[[]for i in range(N)]
dist=[[0]*N for i in range(N)]
for i in range(N-1):
  u1,v1,w1=map(int,input().split())
  road[u1-1].append(v1-1)
  road[v1-1].append(u1-1)
  dist[u1-1][v1-1]=w1
  dist[v1-1][u1-1]=w1
a=[0]*N
houmon=[0]*N
q=deque([])
q.append(0)
while(q):
  v=q.pop()
  houmon[v]=1
  for x in road[v]:
    if(houmon[x]==0):
      q.append(x)
      a[x]=a[v]+dist[v][x]
      houmon[x]=1
for i in range(N):
  if(a[i]%2==0):
    print(0)
  else:
    print(1)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(4100000)
input = sys.stdin.readline

def dijkstra(s,N,cost):
    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 or 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():
    N  = int(input())
    cost = [[float('inf')] * N for _ in range(N)]
    for _ in range(N-1):
        u, v, w = map(int, input().split())
        u -= 1
        v -= 1
        cost[u][v] = w
        cost[v][u] = w

    d = dijkstra(0,N,cost)

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


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
"""
二部グラフの問題。
同じ色に塗られた任意の2頂点について、その距離が偶数である。
-> this means that neighbor nodes' color must be another color.
"""
import sys
sys.setrecursionlimit(200000)
N = int(input())
edges = [{} for _ in range(N+1)]
for i in range(N-1):
    u,v,w = map(int,input().split())
    edges[u][v]=w%2
    edges[v][u]=w%2

color = [0 for _ in range(N+1)]
path = {}
def f(n,c):
    color[n]=c
    path[n]=""
    for v,d in edges[n].items():
        if v not in path:
            nextC = c
            if d == 1:
                nextC = (nextC+1)%2
            f(v,nextC)
f(1,0)

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

Submission status: Time Limit Exceeded

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

from collections import deque 
def main():
    N = int(readline())
    to = [[] for _ in range(N)]
    wight = [[-1 for _ in range(N)] for _ in range(N)]
    for _ in range(N-1):
        u, v, w = map(int, readline().split())
        u-=1
        v-=1
        to[u].append(v)
        to[v].append(u)
        wight[u][v] = w
        wight[v][u] = w

    dq = deque()
    dq.append(0)
    dist = [-1 for _ in range(N)]
    dist[0] = 0
    while len(dq)>0:
        v = dq.popleft()
        for nx in to[v]:
            if dist[nx] != -1:
                continue
            dist[nx] = (dist[v]+wight[v][nx])%2
            dq.append(nx)

    for i in dist:
        print(i)
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

from collections import deque 
def main():
    N = int(readline())
    to = [[] for _ in range(N)]
    wight = [[-1 for _ in range(N)] for _ in range(N)]
    for _ in range(N-1):
        u, v, w = map(int, readline().split())
        u-=1
        v-=1
        to[u].append(v)
        to[v].append(u)
        wight[u][v] = w%2
        wight[v][u] = w%2

    dq = deque()
    dq.append(0)
    dist = [-1 for _ in range(N)]
    dist[0] = 0
    while len(dq)>0:
        v = dq.popleft()
        for nx in to[v]:
            if dist[nx] != -1:
                continue
            dist[nx] = dist[v]^wight[v][nx]
            dq.append(nx)

    for i in dist:
        print(i)
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(500*500)

N = int(input())
edges = [list(map(int, input().split())) for _ in range(N-1)]

print(edges)
# Aというリストに対応する辺とその距離を収納する。
A = [[] for _ in range(N+1)]
for edge in edges:
    A[edge[0]].append([edge[1], edge[2]])
    A[edge[1]].append([edge[0], edge[2]])

# 頂点1からの距離を記録するリスト
depth = [-1] * (N+1)
depth[1] = 0

# sという点から他の点への距離を出す再帰関数
def dfs(A, s):
    for v in A[s]:
        if depth[v[0]] == -1:
            depth[v[0]] == depth[s] + v[1]
            dfs(A, v[0])

# 1からの距離
dfs(A, 1)
for d in depth[1:]:
    if d % 2 == 0:
        print(0)
    else:
        print(1)

Submission status: Time Limit Exceeded

Solution code:
import sys


def input():
    return sys.stdin.readline().strip()


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():
    N = int(input())
    cost = [[float("inf") for i in range(N)] for i in range(N)]

    for i in range(N - 1):
        u, v, w = map(int, input().split())
        cost[u - 1][v - 1] = w
        cost[v - 1][u - 1] = w
    D = dijkstra(0, N, N - 1, cost)
    for d in D:
        if d % 2 == 0:
            print(0)
        else:
            print(1)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

tree = [[None]*N for _ in range(N)]
ans = [None]*N


for i in range(N-1):
    s = ifm[i]
    tree[s[0]-1][s[1]-1] = s[2]%2
    tree[s[1]-1][s[0]-1] = s[2]%2

    
def dfs(i, n):
    if ans[i] != None:
        return
    ans[i] = n
    cnt = 0
    for j in range(N):
        if ans[j] == None:
            break
        cnt += 1
    if cnt == N:
        for i in range(N):
            print(ans[i])
    for j in range(N):
        if tree[i][j] != None:
            dfs(j, (n+tree[i][j])%2)
            
dfs(0, 0)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
ifm = list(list(map(int, input().split())) for i in range(N-1))

tree = [[None]*N for _ in range(N)]
ans = [None]*N


for i in range(N-1):
    s = ifm[i]
    tree[s[0]-1][s[1]-1] = s[2]%2
    tree[s[1]-1][s[0]-1] = s[2]%2

    
def dfs(i, n):
    if ans[i] != None:
        return
    ans[i] = n
    for j in range(N):
        if tree[i][j] != None:
            dfs(j, (n+tree[i][j])%2)
            
dfs(0, 0)

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

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
G=[]
for i in range(N-1):
    u,v,w=map(int,input().split())
    u-=1;v-=1
    G.append([u,v,w])
G.sort()
col=[-1 for i in range(N)]
col[0]=0

from collections import deque
G=deque(G)

while len(G)>0:
    e=G.popleft()
    if col[e[0]]!=-1:
        col[e[1]]=(e[2]+col[e[0]])%2
    elif col[e[1]]!=-1:
        col[e[0]]=(e[2]+col[e[1]])%2
    else:
        G.append(e)

for i in col:
    print(i)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

n=int(input())
d=[[-1 for j in range(n)] for i in range(n)]
g=[[] for i in range(n)]
color=[-1 for i in range(n)]
color[0]=0
for i in range(n):
  d[i][i]=0

for i in range(n-1):
  u,v,w=map(int,input().split())
  u-=1
  v-=1
  d[u][v]=w
  d[v][u]=w
  g[u].append(v)
  g[v].append(u)

que=deque([0])

while que:
  #print("que",que)
  now=que.popleft()
  for i in g[now]:
    if color[i]!=-1:
      continue
    if d[now][i]%2==0:
      if color[now]==0:
        color[i]=0
      else:
        color[i]=1
    else:
      if color[now]==0:
        color[i]=1
      else:
        color[i]=0
    que.append(i)

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

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**6)
n=int(input())
a = [[0]*n for _ in range(n)]
visited = [0] * n
dist = [0]*n
col = [1]*n

def dfs(i:"int",c:"int"):
    for j in range(n):
        if a[i][j] and not visited[j]>0:
            visited[j]=1
            if a[i][j]%2==0:
                col[j]=c
            else:
                col[j]=c*-1
            dfs(j, col[j])



if __name__ == '__main__':
    for i in range(n-1):
        u,v,d = map(int, input().split())
        a[u-1][v-1]=a[v-1][u-1]=d
    visited[0]=1
    dfs(0, 1)
    for i in range(n):
        print(col[i] if col[i]>0 else 0)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
n=int(input())
a = [[0]*n for _ in range(n)]
visited = [0] * n
col = [1]*n
que = deque()

for i in range(n-1):
    u,v,d = map(int, input().split())
    a[u-1][v-1]=a[v-1][u-1]=d

#方針：貪欲に
for i in range(n):
    if a[0][i]!=0:
        que.append([i, 0])
        visited[i]=1
while que:
    x = que.pop()
    for i in range(n):
        if a[x[0]][i]!=0 and not visited[i]:
            que.append([i, x[0]])
            visited[i]=1
    if a[x[0]][x[1]]%2 == 0:
        col[x[0]]=col[x[1]]
    else:
        col[x[0]]=(col[x[1]])*-1

for i in range(n):
    print(max(col[i], 0))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
n=int(input())
a = [[0]*n for _ in range(n)]
visited = [0] * n
col = [1]*n
que = deque()

for i in range(n-1):
    u,v,d = map(int, input().split())
    a[u-1][v-1]=a[v-1][u-1]=d

#方針：貪欲に
for i in range(n):
    if a[0][i]!=0:
        que.append([i, a[0][i], 0])
        visited[i]=1

while que:
    x = que.pop()
    for i in range(n):
        if a[x[0]][i]!=0 and not visited[i]:
            que.append([i, a[x[0]][i], x[0]])
            visited[i]=1
    if x[1]%2 == 0:
        col[x[0]]=col[x[2]]
    else:
        col[x[0]]=(col[x[2]])*-1

for i in range(n):
    print(max(col[i], 0))

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(10 ** 9)
input = sys.stdin.readline

N = int(input())
en = [[] for _ in range(N)]
on = [[] for _ in range(N)]
for i in range(N - 1):
    u, v, w = map(int, input().split())
    if w % 2:
        on[u - 1].append(v - 1)
        on[v - 1].append(u - 1)
    else:
        en[u - 1].append(v - 1)
        en[v - 1].append(u - 1)

color = [None] * N


def dfs(node, parent, col):
    if color[node] is not None:
        return
    color[node] = col
    for k in en[node]:
        if k != parent:
            dfs(k, node, col)
    for k in on[node]:
        if k != parent:
            dfs(k, node, (col + 1) % 2)


dfs(0, -1, 0)
print(*color, sep="\n")

Submission status: Time Limit Exceeded

Solution code:
N = int(input())

Dist = [[0 for i in range(N)] for j in range(N)]
Seen = [-1] * N

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

que = [0]
Seen[0] = 0
flag = True
while -1 in Seen:
    now = que.pop()
    for next in range(N):
        if Dist[now][next] == 0:
            continue
        elif Seen[next] == -1:
            que.insert(0, next)
            if Dist[now][next] % 2 == 0:
                Seen[next] = Seen[now]
            else:
                Seen[next] = 1 - Seen[now]
for i in range(N):
    print(Seen[i])

Submission status: Time Limit Exceeded

Solution code:
N = int(input())

Dist = [[0 for i in range(N)] for j in range(N)]
Seen = [-1] * N

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

que = [0]
Seen[0] = 0
flag = True
while -1 in Seen:
    now = que.pop()
    for next in range(N):
        if Dist[now][next] == 0:
            continue
        elif Seen[next] == -1:
            que.insert(0, next)
            if Dist[now][next] % 2 == 0:
                Seen[next] = Seen[now]
            else:
                Seen[next] = 1 - Seen[now]
for i in range(N):
    print(Seen[i])

Submission status: Time Limit Exceeded

Solution code:
N = int(input())

Dist = [[0 for i in range(N)] for j in range(N)]
Seen = [-1] * N

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

que = [0]
Seen[0] = 0
flag = True
while len(que) != 0:
    if not flag:
        break
    now = que.pop()
    for next in range(N):
        if Dist[now][next] == 0:
            continue
        elif Seen[next] == -1:
            que.insert(0, next)
            if Dist[now][next] % 2 == 0:
                Seen[next] = Seen[now]
            else:
                Seen[next] = 1 - Seen[now]
        elif Seen[next] != -1:
            if Dist[now][next] % 2 == (Seen[now] + Seen[next]) % 2:
                continue
            else:
                flag = False
                break

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

Submission status: Time Limit Exceeded

Solution code:
import queue
n = int(input())
uvw = [list(map(int, input().split())) for i in range(n-1)]
color = [0]*n
visited = [0]*n
visited[0] = 1
q = queue.Queue()
q.put(1)
while not q.empty():
  p = q.get()
  for j in uvw:
    if j[0] == p and visited[j[1]-1] == 0:
      q.put(j[1])
      visited[j[1]-1] = 1
      if j[2] % 2 == 0:
        color[j[1]-1] = color[j[0]-1]
      else:
        color[j[1]-1] = 1 - color[j[0]-1]
    if j[1] == p and visited[j[0]-1] == 0:
      q.put(j[0])
      visited[j[0]-1] = 1
      if j[2] % 2 == 0:
        color[j[0]-1] = color[j[1]-1]
      else:
        color[j[0]-1] = 1 - color[j[1]-1]
for i in color:
  print(i)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

N = int(input())
tree =   [[] for _ in range(N)]
parent = [-1] * N
color = [-1] * N
color[0] = 0
for n in range(N-1):
  u, v, w = map(int,input().split())
  tree[u-1].append([v-1,w])
  tree[v-1].append([u-1,w])

q = deque()
q.append(0)

while q:
  index = q.pop()
  for i in range(len(tree[index])):
    target = tree[index][i][0]
    if parent[target] == index: continue
    parent[target] = index
    if tree[index][i][1]%2 == 0:
      color[target] = color[index]
    else:
      color[target] = (color[index] + 1)%2
    q.append(target)
print(*color, sep="\n")

Submission status: Time Limit Exceeded

Solution code:
def dfs(v, g, color, paint=0):
	color[v] = paint
	for i in range(len(g)):
		if i == v or g[v][i] == -1:
			continue
		if g[v][i]:
			np = paint if g[v][i] % 2 == 0 else 1 - paint
			g[v][i] = -1
			g[i][v] = -1
			dfs(i, g, color, np)

def resolve():
	n = int(input())
	color = [-1]*n
	g = [[-1]*n for _ in range(n)]
	for _ in range(n-1):
		u, v, w = map(int, input().split())
		g[u-1][v-1] = w
		g[v-1][u-1] = w
	for v in range(n):
		if color[v] > -1:
			continue
		dfs(v, g, color)

	for i in color:
		print(i)
resolve()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

q = deque([1])
while q:
  x = q.popleft()
  for y, w in graph[x]:
    if(parent[y] == x):
      continue
    else:
      parent[y] = x
      ans[y] = ans[x]^(w&1)
      q.append(y)
      
for i in range(1, n+1):
  print(ans[i])

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys

class Node:
    def __init__(self, n, N):
        self.id = n
        self.edges = []
        self.weights = [-1]*N
        self.color = 1
        self.s = 0
    def set_edge(self, e, w):
        self.edges.append(e)
        self.weights[e]=w
    def set_color(self, c_):
        self.color = c_
        self.s = 1

def solve(N: int, u: "List[int]", v: "List[int]", w: "List[int]"):

    # init nodes
    nodes = [Node(i,N) for i in range(N)]
    # set edges
    for ui, vi, wi in zip(u, v, w):
        nodes[ui-1].set_edge(vi-1,wi)
        nodes[vi-1].set_edge(ui-1,wi)

    def cal(node):
        c_ = node.color
        for n in node.edges:
            if nodes[n].s == 0:
                if node.weights[n]%2==1:
                    nodes[n].set_color(c_*-1)
                else:
                    nodes[n].set_color(c_)                
                cal(nodes[n])
    
    cal(nodes[0])

    for n in nodes:
        print((n.color==1)*1)

    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    u = [int()] * (N - 1)  # type: "List[int]"
    v = [int()] * (N - 1)  # type: "List[int]"
    w = [int()] * (N - 1)  # type: "List[int]"
    for i in range(N - 1):
        u[i] = int(next(tokens))
        v[i] = int(next(tokens))
        w[i] = int(next(tokens))
    solve(N, u, v, w)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys

class Node:
    def __init__(self, n, N):
        self.id = n
        self.edges = []
        self.weights = [-1]*N
        self.color = 1
        self.s = 0
    def set_edge(self, e, w):
        self.edges.append(e)
        self.weights[e]=w
    def set_color(self, c_):
        self.color = c_
        self.s = 1

def solve(N: int, u: "List[int]", v: "List[int]", w: "List[int]"):

    # init nodes
    nodes = [Node(i,N) for i in range(N)]
    # set edges
    for ui, vi, wi in zip(u, v, w):
        nodes[ui-1].set_edge(vi-1,wi)
        nodes[vi-1].set_edge(ui-1,wi)

    def cal(node):
        c_ = node.color
        for n in node.edges:
            if nodes[n].s == 0:
                if node.weights[n]%2==1:
                    nodes[n].set_color(c_*-1)
                else:
                    nodes[n].set_color(c_)                
                cal(nodes[n])
    cal(nodes[0])

    for n in nodes:
        print((n.color==1)*1)

    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    u = [int()] * (N - 1)  # type: "List[int]"
    v = [int()] * (N - 1)  # type: "List[int]"
    w = [int()] * (N - 1)  # type: "List[int]"
    for i in range(N - 1):
        u[i] = int(next(tokens))
        v[i] = int(next(tokens))
        w[i] = int(next(tokens))
    solve(N, u, v, w)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
N=int(input())
tree=[[] for _ in range(N)]
for i in range(N-1):
    u,v,w=map(int,input().split())
    tree[u-1].append([v-1,w])
    tree[v - 1].append([u - 1, w])
#print(tree)
col=[-1]*N
dist=[-1]*N
v=0
d=deque()
d.append(v)
color=0
col[0]=0
dist[0]=0
while min(dist)==-1:
    v=d.popleft()
    for i in tree[v]:
        if dist[i[0]]==-1:
            #print(dist[i[0]],dist[v],i[1])
            dist[i[0]]=dist[v]+i[1]
            d.append(i[0])
    #print(dist,d)
    #input()
for i in range(N):
    print(dist[i]%2)

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)
color=[0]*(N+1)
def dfs(n):
    seen[n]=True
    for nxt in H[n]:
        if seen[nxt] == False:
            if G[n][nxt] % 2 == 0:
                color[nxt]=color[n]
            else:
                color[nxt]=color[n] ^ 1
            dfs(nxt)

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

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