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: Wrong Answer

Solution code:
n=int(input())
uvw=[list(map(int,input().split())) for _ in range(n-1)]
uvw=sorted(uvw,key=lambda x:x[0])

res=[-1 for _ in range(n)]
res[0]=0
for u,v,w in uvw:
    u-=1
    v-=1
    if w%2==0:
        if res[u]>=0:
            res[v]=res[u]
        elif res[v]>=0:
            res[u]=res[v]
    else:
        if res[u]==0:
            res[v]=1
        elif res[u]==1:
            res[v]=0
        elif res[v]==0:
            res[u]=1
        elif res[v]==1:
            res[u]=0
for u,v,w in uvw:
    u-=1
    v-=1
    if w%2==0:
        if res[u]>=0:
            res[v]=res[u]
        elif res[v]>=0:
            res[u]=res[v]
    else:
        if res[u]==0:
            res[v]=1
        elif res[u]==1:
            res[v]=0
        elif res[v]==0:
            res[u]=1
        elif res[v]==1:
            res[u]=0
for ans in res:
    print(ans)

Submission status: Wrong Answer

Solution code:
from sys import stdin, stdout, setrecursionlimit as lim

lim(100003)

n = input()
inp = stdin.readlines()

g = [[] for i in xrange(n + 1)]

for line in inp:
    u, v, w = map(int, line.strip().split())
    g[u].append([v, w])
    g[v].append([u, w])

out = ['0'] * (n + 1)
vis = [0] * (n + 1)
def dfs(u):
    global out
    
    out[u] = '1'
    vis[u] = 1
    for v, w in g[u]:
        if vis[v]: continue
        if w & 1: continue
        dfs(v)

root = 1
for u in xrange(1, n + 1):
    flag = 0
    for v, w in g[u]:
        if w % 2 == 0:
            flag = 1
            break
    if flag == 0: continue
    else:
        root = u
        break

dfs(root)

stdout.write("\n".join(out[1:]))

Submission status: Wrong Answer

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

def solve(N: int, u: "List[int]", v: "List[int]", w: "List[int]"):
    col = [-1 for _ in range(N+1)]

    G = [[] for _ in range(N+1)]
    for i in range(N-1):
        G[u[i]].append((v[i], w[i]))
        G[v[i]].append((u[i], w[i]))
    def dfs(p, c, cnt):
        if cnt == N:
            return
        for np, dis in G[p]:
            if col[np] == -1:
                cnt += 1
                if dis%2 == 0:
                    col[np] = c
                else:
                    c = 1 - c
                    col[np] = c
                dfs(np, c, cnt)

    dfs(1, 0, 0)
    for elem in col[1:]:
        print(elem)


    return


# Generated by 1.1.4 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: Wrong Answer

Solution code:
# Union-Find木
class UnionFind:
    # 経路圧縮・ランク
    # クエリO(α(N))
    # original source: http://at274.hatenablog.com/entry/2018/02/02/173000
    # date: 2018/06/27

    def __init__(self, n):
        self.par = [i for i in range(n+1)]
        self.rank = [0] * (n+1)

    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    def is_same(self, x, y):
        return self.find(x) == self.find(y)


n = int(input())
data = [list(map(int, input().split())) for _ in range(n-1)]
uf = UnionFind(n)
for u, v, w in data:
    if w % 2 == 0:
        uf.union(u, v)
for i in range(1, n+1):
    if uf.is_same(1, i):
        print(0)
    else:
        print(1)

Submission status: Time Limit Exceeded

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

N = int(input())


vlist = [[] for _ in range(N)]

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

ans = [-1] * N
q = queue.Queue()

ans[0] = 0
q.put(0)

while q:
    new = q.get()
    for node, weight in vlist[new]:
        if ans[node] != -1:
            continue
        ans[node] = (ans[new] + weight) % 2
        q.put(node)
    
for i in ans:
    print(i)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
set0=set([0])
set1 =set()
from collections import deque
ls = deque([])
for _ in range(n-1):
    u, v, w= map(int, input().split())
    ls.append((u-1, v-1, w%2))

ans = [-1] * n
ans[0] = 0
while ls:
    u, v, w = ls.popleft()
    if w == 0: # same
        if u in set0 or v in set0:
            #set0 |= set([u, v])
            set0.add(u)
            set0.add(v)
            ans[u]=0
            ans[v]=0
        elif u in set1 or v in set1:
            #set1 |= set([u, v])
            set1.add(u)
            set1.add(v)
            ans[u] = 1
            ans[v] = 1
        else:
            ls.append((u, v, w))
    else:#different
        if u in set0:
            set1.add(v)
            ans[v] =1
        elif v in set0:
            set1.add(u)
            ans[u] =1
        elif v in set1:
            set0.add(u)
            ans[u] =0
        elif u in set1:
            set0.add(v)
            ans[v] =0
        else:
            ls.append((u, v, w))

for i in ans:
    print(i)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
set0=set([0])
set1 =set()
from collections import deque
ls = deque([])
for _ in range(n-1):
    u, v, w= map(int, input().split())
    ls.append((u-1, v-1, w%2))

ans = [-1] * n
ans[0] = 0
while ls:
    u, v, w = ls.popleft()
    if w == 0: # same
        if u in set0 or v in set0:
            set0 |= set([u, v])
            ans[u]=0
            ans[v]=0
        elif u in set1 or v in set1:
            set1 |= set([u, v])
            ans[u] = 1
            ans[v] = 1
        else:
            ls.append((u, v, w))
    else:#different
        if u in set0:
            set1.add(v)
            ans[v] =1
        elif v in set0:
            set1.add(u)
            ans[u] =1
        elif v in set1:
            set0.add(u)
            ans[u] =0
        elif u in set1:
            set0.add(v)
            ans[v] =0
        else:
            ls.append((u, v, w))

for i in ans:
    print(i)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque
input=sys.stdin.readline
N=int(input())
tree=[[] for _ in range(N)]
for _ 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))
ans=[-1]*N
ans[0]=0
d=deque([0])
done=[0]
while d:
  p=deque.popleft(d)
  color=ans[p]
  for v,w in tree[p]:
    if not v in done:
      deque.append(d,v)
      done.append(v)
      ans[v]=color^(w%2)
print(*ans,sep='\n')

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

N=int(input())
tree=[[] for _ in range(N)]
for _ 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))
ans=[-1]*N
ans[0]=0
d=deque([0])
done=[0]
while d:
  p=deque.popleft(d)
  color=ans[p]
  for v,w in tree[p]:
    if not v in done:
      deque.append(d,v)
      done.append(v)
      ans[v]=color^(w%2)
print(*ans,sep='\n')

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
# 問題：https://atcoder.jp/contests/abc126/tasks/abc126_d


class Graph():

    def __init__(self):
        self.adjacency_dict = {}
    
    def add_vertex(self, v):
        self.adjacency_dict[v] = []

    def add_edge(self, v1, v2):
        self.adjacency_dict[v1].append(v2)
        self.adjacency_dict[v2].append(v1)

    def get_vertexes(self):
        return self.adjacency_dict.keys()

    def get_edges(self, v):
        return self.adjacency_dict[v]

    def print_graph(self):
        print(self.adjacency_dict)

n = int(input())
p = [[] for _ in range(n)]
for i in range(n):
    for _ in range(n):
        p[i].append(0)

res = []
g = Graph()
for i in range(n):
    res.append(-1)
    g.add_vertex(i)

for i in range(n-1):
    u, v, w = map(int, input().strip().split())
    g.add_edge(u-1, v-1)
    p[u-1][v-1] = w % 2
    p[v-1][u-1] = w % 2

q = []
res[0] = 0
q.append(0)
while(len(q) > 0):
    v = q.pop()
    for u in g.get_edges(v):
        if res[u] != -1:
            continue
        w = p[u][v]
        res[u] = (res[v] + w) % 2
        q.append(u)

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

Submission status: Time Limit Exceeded

Solution code:
import sys
def input(): return sys.stdin.readline().rstrip()
def ii(): return int(input())
def mi(): return map(int, input().split())
def li(): return list(mi())

from collections import deque
def main():
    n = ii()
    edge = [[] for _ in range(n)]
    for i in range(n-1):
        u, v, w = mi()
        u -= 1
        v -= 1
        edge[u].append((v, w))
        edge[v].append((u, w))
    dist = [0]*n
    parent = [-1]*n
    que = deque([0])
    while que:
        v = que.pop()
        for nv, nx in edge[v]:
            if parent[nv] == v:
                continue
            parent[nv] = v
            dist[nv] = dist[v]+nx%2
            dist[nv]%= 2
            que.append(nv)
    print(*dist, sep='\n')
    


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
def input(): return sys.stdin.readline().rstrip()
def ii(): return int(input())
def mi(): return map(int, input().split())
def li(): return list(mi())

from collections import deque
def main():
    n = ii()
    edge = [[] for _ in range(n)]
    for i in range(n-1):
        u, v, w = mi()
        u -= 1
        v -= 1
        edge[u].append((v, w))
        edge[v].append((u, w))
    dist = [0]*n
    parent = [-1]*n
    que = deque([(0, 0)])
    while que:
        v, x = que.pop()
        for nv, nx in edge[v]:
            if parent[nv] == v:
                continue
            parent[nv] = v
            dist[nv] = dist[v]+nx%2
            dist[nv]%= 2
            que.append((nv, dist[nv]))
    print(*dist, sep='\n')
    


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#coding: utf-8

N = int(input())

G = []
for i in range(N+1):
    G.append([-1]*(N+1))

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

ret = [-1] * (N+1)

def dfs(node, d):
    if ret[node] != -1:
        return

    if d % 2 == 0:
        ret[node] = 0
    else:
        ret[node] = 1 

    for i in range(N+1):
        if G[node][i] == -1:
            continue
        dfs(i, d + G[node][i])

dfs(1, 0)
for i in range(N):
    print(ret[i+1])

Submission status: Time Limit Exceeded

Solution code:
g = {}
a = int(input())
vertices = [i for i in range(1, a + 1)]
for i in range(a - 1):
    c = [int(s) for s in input().split()]
    if c[0] not in g: g[c[0]] = [(c[1], c[2])]
    else: g[c[0]].append((c[1], c[2]))

    if c[1] not in g: g[c[1]] = [(c[0], c[2])]
    else: g[c[1]].append((c[0], c[2]))

Q = [vertices[0]]
d = {i: False for i in vertices}
d[vertices[0]] = True
c = {}
c[vertices[0]] = 0
delta = [vertices[0]] 
while(True):
    for i in g[Q[0]]:
        if d[i[0]] == False:
            delta.append(i[0]) 
            d[i[0]] = True
            if i[1] % 2 == 0: c[i[0]] = c[Q[0]]
            else: c[i[0]] = (c[Q[0]] + 1) % 2
            Q.append(i[0])
    Q = Q[1:]
    if Q == []:
        if set(delta) == set(vertices): break
        else: Q.append(list(set(delta).intersection(set(vertices)))[0])

for i in vertices: print(c[i])

Submission status: Time Limit Exceeded

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

di[0]=0

for i in range(N):
    if di[i]!=-1:continue
    seen=[0]*N
    stack=[[i,0]]
    while stack:
        x,d=stack.pop()
        for g,dis in G[x]:
            if di[g]!=-1:
                di[i]=(di[g]+d+dis)%2
                break
            if seen[g]==0:
                stack.append([g,d+dis])
                seen[g]=1

for i in range(N):
    print(di[i]%2)

Submission status: Time Limit Exceeded

Solution code:

from copy import copy
N=int(input())
G=[[] for _ in range(N)]
di=[-1]*N
for i in range(N-1):
    u,v,w=map(int,input().split())
    G[u-1].append([v-1,w])
    G[v-1].append([u-1,w])

di[0]=0
for g,w in G[0]:
    di[g]=w

for i in range(1,N):
    if di[i]!=-1:continue
    seen=[0]*N
    stack=copy(G[0])
    seen[0]=1
    dis=0
    while stack:
        y,d=stack.pop()
        if seen[y]==1:continue
        seen[y]=1
        if y==i:
            di[i]=dis+d
            break
        else:
            for z,dist in G[y]:
                if seen[z]==0:
                    di[z]=dis+d+dist
                    stack.append([z,dis+d+dist])

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

Submission status: Time Limit Exceeded

Solution code:

from copy import copy
N=int(input())
G=[[] for _ in range(N)]
di=[-1]*N
for i in range(N-1):
    u,v,w=map(int,input().split())
    d=w%2
    G[u-1].append([v-1,d])
    G[v-1].append([u-1,d])

di[0]=0
for i in range(1,N):
    seen=[0]*N
    stack=copy(G[0])
    seen[0]=1
    dis=0
    while stack:
        y,d=stack.pop()
        if seen[y]==1:continue
        seen[y]=1
        if y==i:
            di[i]=dis+d
            break
        else:
            for z,dist in G[y]:
                if seen[z]==0:
                    stack.append([z,dis+d+dist])

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

Submission status: Time Limit Exceeded

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


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

  color = [-1]*(N+1)
  color[1] = 0
  S = [1]
  S_append = S.append
  S_pop = S.pop
  while len(S):
    now = S[-1]
    for next_, w in G[now]:
      if color[next_] != -1:
        continue
      S_append(next_)
      color[next_] = (w % 2) ^ color[now]
      break
    else:
      S_pop()

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


if(__name__ == '__main__'):
  main()

Submission status: Time Limit Exceeded

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


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

  color = [-1 for _ in range(N+1)]
  color[1] = 0
  S = [1]
  S_append = S.append
  S_pop = S.pop
  while len(S):
    now = S[-1]
    for next_, w in G[now]:
      if color[next_] != -1:
        continue
      S_append(next_)
      color[next_] = (w % 2) ^ color[now]
      break
    else:
      S_pop()

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


if(__name__ == '__main__'):
  main()

Submission status: Time Limit Exceeded

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


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

  color = [-1 for _ in range(N+1)]
  color[1] = 0
  S = [1]
  while len(S):
    now = S[-1]
    for next_, w in G[now]:
      if not color[next_] == -1:
        continue
      S.append(next_)
      color[next_] = (w % 2) ^ color[now]
      # if w % 2:
      #   color[next_] = 1 ^ color[now]
      # else:
      #   color[next_] = 0 ^ color[now]
      # # white, odd
      # if color[now]:
      #   color[next_] = 0 if w % 2 else 1
      # # black, even
      # else:
      #   color[next_] = 1 if w % 2 else 0
      break
    else:
      S.pop()

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


if(__name__ == '__main__'):
  main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
#
# Created: Jul, 12, 2020 08:04:43 by Nobody
# $Author$
# $Date$
# $URL$
__giturl__ = "$URL$"


from sys import stdin
input = stdin.readline


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

  color = [-1 for _ in range(N+1)]
  color[1] = 0
  S = [1]
  while len(S):
    now = S[-1]
    for next_, w in G[now]:
      if not color[next_] == -1:
        continue
      S.append(next_)
      color[next_] = (w % 2) ^ color[now]
      # if w % 2:
      #   color[next_] = 1 ^ color[now]
      # else:
      #   color[next_] = 0 ^ color[now]
      # # white, odd
      # if color[now]:
      #   color[next_] = 0 if w % 2 else 1
      # # black, even
      # else:
      #   color[next_] = 1 if w % 2 else 0
      break
    else:
      S.pop()

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


if(__name__ == '__main__'):
  main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
#
# Created: Jul, 12, 2020 08:04:43 by Nobody
# $Author$
# $Date$
# $URL$
__giturl__ = "$URL$"


from sys import stdin
input = stdin.readline


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

  color = [-1 for _ in range(N+1)]
  color[1] = 0
  S = [1]
  while len(S):
    now = S[-1]
    for next_, w in G[now]:
      if not color[next_] == -1:
        continue
      S.append(next_)
      # white, odd
      if color[now]:
        color[next_] = 0 if w % 2 else 1
      # black, even
      else:
        color[next_] = 1 if w % 2 else 0
      break
    else:
      S.pop()

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


if(__name__ == '__main__'):
  main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
#
# Created: Jul, 12, 2020 08:04:43 by Nobody
# $Author$
# $Date$
# $URL$
__giturl__ = "$URL$"


from collections import defaultdict
from collections import deque
from collections import OrderedDict
import itertools
from sys import stdin
input = stdin.readline


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

  color = [-1 for _ in range(N+1)]
  color[1] = 0
  S = [1]
  while len(S):
    now = S[-1]
    for next_, w in G[now]:
      if not color[next_] == -1:
        continue
      S.append(next_)
      # white, odd
      if color[now]:
        color[next_] = 0 if w % 2 else 1
      # black, even
      else:
        color[next_] = 1 if w % 2 else 0
      break
    else:
      S.pop()

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


if(__name__ == '__main__'):
  main()

Submission status: Time Limit Exceeded

Solution code:
class Point:
    def __init__(self):
        self.color = None
        self.paths = {}
    def nextp(self):
        return list(self.paths.keys())
    def d_to_p(self, p):
        return self.paths[p]

n = int(input())
pts = [Point() for i in range(n)]

while True:
    try:
        u, v, w = map(int, input().split())
        pts[u-1].paths[v-1] = w
        pts[v-1].paths[u-1] = w
    except:
        break

pts[0].color = 0
done = 1
candy = [0]

while done != n:
    t_c = []
    for now in candy:
        tmpl = pts[now].nextp()
        for p in tmpl:
            if pts[p].color == None:
                if pts[now].color == 0:
                    if pts[now].d_to_p(p) % 2 == 0:
                        pts[p].color = 0
                    else:
                        pts[p].color = 1
                else:
                    if pts[now].d_to_p(p) % 2 == 0:
                        pts[p].color = 1
                    else:
                        pts[p].color = 0
                done += 1
            if p not in t_c:
                t_c.append(p)
    candy = t_c

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

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
n=int(input())
a=[list(map(int,input().split())) for i in range(n-1)]

t=np.array(a).T
#木の根
root=1
tree={1:[1,0]}
#p:親,d:距離
p=0
d=1

t0=t[0].tolist()
stack=[root]
while stack:
  now=stack.pop(-1)
  #now_d=t0.index(tree[now][p])
  
  #right=list(zip(*np.where(t[1]==now)))
  r=[i for i in zip(*np.where(t[1]==now)) if a[i[0]][0]!=tree[now][p]]
  l=[i for i in zip(*np.where(t[0]==now)) if a[i[0]][1]!=tree[now][p]]
  #print(r,tree[now][p])
  #print(right)
  #left=list(zip(*np.where(t[0]==now)))
  #print(r,l)
  for i in r:
    ii=i[0]
    stack.append(a[ii][0])
    tree[a[ii][0]]=[now, a[ii][2]+tree[now][d]]
     #print(a[ii][2]+tree[now][d])
      
  for i in l:
    ii=i[0]
    stack.append(a[ii][1])
    tree[a[ii][1]]=[now, a[ii][2]+tree[now][d]]
    #print(a[ii][2]+tree[now][d])
    
#print(tree)
for i in range(1,n+1):
  if tree[i][d]%2==0:
    print(1)
  else:
    print(0)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
n=int(input())
a=[list(map(int,input().split())) for i in range(n-1)]

t=np.array(a).T
#木の根
root=1
tree={1:[-1,0]}
#p:親,d:距離
p=0
d=1

stack=[root]
while stack:
  now=stack.pop(-1)
  right=list(zip(*np.where(t[1]==now)))
  left=list(zip(*np.where(t[0]==now)))
  #print(right,left)
  for i in right:
    ii=i[0]
    if a[ii][0] != tree[now][p]:
      stack.append(a[ii][0])
      tree[a[ii][0]]=[now, a[ii][2]+tree[now][d]]
  for i in left:
    ii=i[0]
    if a[ii][1] != tree[now][p]:
      stack.append(a[ii][1])
      tree[a[ii][1]]=[now, a[ii][2]+tree[now][d]]
#print(tree)
tree[1]=[1,0,0]
ans=[0]*n

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

Submission status: Time Limit Exceeded

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

#木の根
root=1
tree={1:[-1,0,0]}
#p:親,d:距離,dep:深さ
p=0
d=1
dep=2
stack=[root]
while stack:
  now=stack.pop(-1)
  for i in range(len(a)):
    if a[i][1] == now and a[i][0] != tree[now][p]:
      stack.append(a[i][0])
      tree[a[i][0]]=[now, a[i][2]+tree[now][d],tree[now][dep]+1]
      
    if a[i][0] == now and a[i][1] != tree[now][p]:
      stack.append(a[i][1])
      tree[a[i][1]]=[now, a[i][2] + tree[now][d],tree[now][dep]+1]
      
#print(tree)

tree[1]=[1,0,0]
ans=[0]*n

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

Submission status: Time Limit Exceeded

Solution code:
import networkx as nx

N = int(input())

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

G = nx.Graph()

color = [0 for _ in range(N)]  # 0: tbd，1: white, 2: black

for u, v, w in UVW:
    G.add_edge(u - 1, v - 1, weight=w)

color[0] = -1

for i in range(N - 1):
    if color[i] == 0 or i == 0:
        for j in range(i + 1, N):
            if color[j] == 0:
                d = nx.shortest_path_length(G, source=i, target=j, weight="weight")
                if int(d + 0.5) % 2 == 0:
                    color[j] = color[i]
                else:
                    color[j] = color[i] * -1

ans = [1 if i == -1 else 0 for i in color]
print(*ans)

Submission status: Time Limit Exceeded

Solution code:
import networkx as nx

N = int(input())

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

G = nx.Graph()

color = [0 for _ in range(N)]  # 0: tbd，1: white, 2: black

for u, v, w in UVW:
    G.add_edge(u - 1, v - 1, weight=w)

color[0] = -1

for i in range(N - 1):
    for j in range(i + 1, N):
        if color[j] == 0:
            d = nx.shortest_path_length(G, source=i, target=j, weight="weight")
            if int(d + 0.5) % 2 == 0:
                color[j] = color[i]
            else:
                color[j] = color[i] * -1

ans = [1 if i == -1 else 0 for i in color]
print(*ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
n=int(input())
brdictlist = [{} for _ in range(n+1)]
for i in range(n-1):
    u,v,w= map(int,input().split())
    if w%2==0:
        brdictlist[u][0] = brdictlist[u].get(0,[]) + [v]
        brdictlist[v][0] = brdictlist[v].get(0,[]) + [u]
    else:
        brdictlist[u][1] = brdictlist[u].get(1,[]) + [v]
        brdictlist[v][1] = brdictlist[v].get(1,[]) + [u]
relcol = [-1]*(n+1)
incol = set()
searchedbranch = set()
q=deque()
q.append(1)
relcol[1]=1
incol.add(1)
coltable = [[0,1],[1,0]]
while True:
    tempques = deque()
    while len(q)!=0:
        tempq=q.pop()
        searchedbranch.add(tempq)
        for key in brdictlist[tempq].keys():
            tempcol=coltable[key][relcol[tempq]]
            for node in brdictlist[tempq][key]:
                if not node in incol:
                    relcol[node]=tempcol
                    if not node in searchedbranch:
                        tempques.append(node)
    q=tempques
    if len(searchedbranch)==n:break
for c in relcol[1:]:print(c)

Submission status: Time Limit Exceeded

Solution code:
N, *m=map(int, open(0).read().split())

im = iter(m)
UVW = list(zip(im, im, im))

# set default color to -1

colors = {i:-1 for i in range(1,N+1)}
u,v,w = UVW[0]
colors[u] = 0

def opposite(u, v):
    if v == -1:
        return u
    if v == 0:
        return 1
    if v == 1:
        return 0

def same(u, v):
    if v == -1:
        return u
    else:
        return v

while -1 in colors.values():
    next_UVW = []
    for u, v, w in UVW:
        if colors[u] == -1 and colors[v] == -1:
            next_UVW.append((u, v, w))
            continue

        if w % 2 == 0:
            colors[u] = same(colors[u], colors[v])
            colors[v] = same(colors[v], colors[u])

        if w % 2 == 1:
            colors[u] = opposite(colors[u], colors[v])
            colors[v] = opposite(colors[v], colors[u])

        if colors[u] == -1 or colors[v] == -1:
            next_UVW.append((u,v,w))

    UVW = next_UVW



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

Submission status: Time Limit Exceeded

Solution code:
N, *m=map(int, open(0).read().split())

im = iter(m)
UVW = list(zip(im, im, im))

# set default color to -1

colors = {i:-1 for i in range(1,N+1)}
u,v,w = UVW[0]
colors[u] = 0

def opposite(u, v):
    if v == -1:
        return u
    if v == 0:
        return 1
    if v == 1:
        return 0

def same(u, v):
    if v == -1:
        return u
    else:
        return v

while -1 in colors.values():
    next_UVW = []
    for u, v, w in UVW:
        if colors[u] == -1 and colors[v] == -1:
            continue

        if w % 2 == 0:
            colors[u] = same(colors[u], colors[v])
            colors[v] = same(colors[v], colors[u])

        if w % 2 == 1:
            colors[u] = opposite(colors[u], colors[v])
            colors[v] = opposite(colors[v], colors[u])

        if colors[u] == -1 or colors[v] == -1:
            next_UVW.append((u,v,w))

    UVW = next_UVW



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

Submission status: Time Limit Exceeded

Solution code:
N, *m=map(int, open(0).read().split())

im = iter(m)
UVW = list(zip(im, im, im))

# set default color to -1

colors = {i:-1 for i in range(1,N+1)}
u,v,w = UVW[0]
colors[u] = 0

def opposite(u, v):
    if v == -1:
        return u
    if v == 0:
        return 1
    if v == 1:
        return 0

def same(u, v):
    if v == -1:
        return u
    else:
        return v

while -1 in colors.values():
    next_UVW = []
    for u, v, w in UVW:
        if w % 2 == 0:
            colors[u] = same(colors[u], colors[v])
            colors[v] = same(colors[v], colors[u])

        if w % 2 == 1:
            colors[u] = opposite(colors[u], colors[v])
            colors[v] = opposite(colors[v], colors[u])

        if colors[u] == -1 or colors[v] == -1:
            next_UVW.append((u,v,w))

    UVW = next_UVW



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

Submission status: Time Limit Exceeded

Solution code:
N, *m=map(int, open(0).read().split())

im = iter(m)
UVW = list(zip(im, im, im))

# set default color to -1

colors = {i:-1 for i in range(1,N+1)}
u,v,w = UVW[0]
colors[u] = 0

def opposite(u, v):
    if v == -1:
        return u
    if v == 0:
        return 1
    if v == 1:
        return 0

def same(u, v):
    if v == -1:
        return u
    else:
        return v

while -1 in colors.values():
    for u, v, w in UVW:
        if w % 2 == 0:
            colors[u] = same(colors[u], colors[v])
            colors[v] = same(colors[v], colors[u])

        if w % 2 == 1:
            colors[u] = opposite(colors[u], colors[v])
            colors[v] = opposite(colors[v], colors[u])



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

Submission status: Time Limit Exceeded

Solution code:
N, *m=map(int, open(0).read().split())

im = iter(m)
UVW = list(zip(im, im, im))

# set default color to -1

colors = {i:-1 for i in range(1,N+1)}
colors[1] = 0

def opposite(u, v):
    if v == -1:
        return u
    if v == 0:
        return 1
    if v == 1:
        return 0

def same(u, v):
    if v == -1:
        return u
    else:
        return v

while -1 in colors.values():
    for u, v, w in UVW:
        if w % 2 == 0:
            colors[u] = same(colors[u], colors[v])
            colors[v] = same(colors[v], colors[u])

        if w % 2 == 1:
            colors[u] = opposite(colors[u], colors[v])
            colors[v] = opposite(colors[v], colors[u])



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

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