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:

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

def dfs(a,b):
    if G[a][b]!=-1:
        return G[a][b]
    seen[a]=1
    #distance of a to b
    for g,d in enumerate(G[a]):
        if d==-1:continue
        if seen[g]==1:continue
        if g==b:
            return d
        seen[g]=1
        dis=dfs(g,b)
        if dis !=0:
            G[g][b]=d+dis
            return d+dis
        seen[g]=0
    return 0

di[0]=0
for i in range(N):
    if di[i]!=-1:continue
    seen=[0]*N
    di[i]=dfs(0,i)

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

Submission status: Wrong Answer

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):
    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]:
                di[z]=dis+d
                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: Wrong Answer

Solution code:
n = int(input())
edge = []
for _ in range(n-1):
    u, v, w = map(int, input().split())
    edge.append((u-1, v-1, w))

edge.sort()
color = [-1] * n
for u, v, w in edge:
    if color[u] == color[v] == -1:
        color[u] = 0
        color[v] = 0 if w % 2 == 0 else 1
    elif color[u] == -1:
        color[u] = color[v] if w % 2 == 0 else color[v] ^ 1
    else:
        color[v] = color[u] if w % 2 == 0 else color[u] ^ 1
print('\n'.join(map(str, color)))

Submission status: Wrong Answer

Solution code:
n = int(input())
col = [0]*n
for i in range(n-1):
    u , v , w = map(int, input().split())
    if w%2==0:
        col[v-1]=col[u-1]
    else:
        col[v-1]=(col[u-1]+1)%2
for i in col:
    print(i)

Submission status: Wrong Answer

Solution code:
N = int(input())
edge = [[] for _ in range(N)]

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

ans = [0] * N


def dfs(v, pv):
    childs = filter(lambda cv: cv[0] != pv, edge[v])
    for cv, cw in childs:
        if cw == 1:
            ans[cv] = 1
        else:
            dfs(cv, v)


dfs(0, -1)
print(*ans)

Submission status: Wrong Answer

Solution code:
#import sys
MOD = 10 ** 9 + 7
INFI = 10**10
#input = sys.stdin.readline
import math
from collections import deque
import itertools
import heapq
#import bisect
from fractions import Fraction
import copy
from functools import lru_cache
from collections import defaultdict
import pprint

#oo=list("ABCDEFGHIJKLMNOPQRSTUVWXYZ")
# ko=list("abcdefghijklmnopqrstuvwxyz")

def sosuhante(n):
    for k in range(2, int(math.sqrt(n))+1):
        if n% k ==0:
            return False
    return True
def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result

def kingaku(a,b,n):
    keta=len(str(n))
    return a*n+b*keta

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

#    h,w,a,b = map(int, input().split())
#    c = [[0 for j in range(n)] for i in range(n)]

def ret(a):
    c=[None]*(len(a)-1)
    if len(a)==1:
        return a[0]
    elif len(a)==0:
        return 0
    for i in range(1,len(a)):
        c[i-1]=abs(a[i]-a[i-1])
    return ret(c)

def soinsubunkai(n):
    a = []
    i = 1
    while i*i <= n:
        if n % i == 0 and i!=1:
            a.append(i)
            n=n//i

        if n% i !=0 or i==1:
            i += 1
    nokori=[n]
    return a + nokori

def make_divisors(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[::-1]

def main():
    n=int(input())
    dis=[INFI for _ in range(n+1)]
    graph=[[] for _ in range(n+1)]
    for i in range(n-1):
        a,b,c=map(int,input().split())
        graph[a].append([b,c])
        graph[b].append([a,c])
    stack=[]
    visited=[0 for _ in range(n+1)]
    dis[0]=0
    dis[1]=0
    for i in graph[1]:
        stack.append(i[0])
        dis[i[0]]=i[1]
    while True:
        s=stack.pop()
        for i in graph[s]:
            if visited[i[0]]==0:
                stack.append(i[0])
                dis[i[0]]=dis[s]+i[1]
                visited[i[0]]=1
        if len(stack)==0:
            break
    print(dis)
    for i in range(1,n+1):
        if dis[i]%2==0:
            print(0)
        else:
            print(1)




if __name__ == "__main__":

    main()

Submission status: Wrong Answer

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

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

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

def route(last, now, dist):
    print('check', last, now, dist)
    for next_node, next_distance in zip(paths[now].keys(), paths[now].values()):
        node_colors[next_node] = (dist + next_distance) % 2
        if next_node != last:
            route(now, next_node, dist + next_distance)

node_colors[1] = 0

route(0, 1, 0)

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

Submission status: Wrong Answer

Solution code:
"""bfs"""

import sys
sys.setrecursionlimit(10**6)

n = int(input())

to = [[] for _ in range(n)]
cost = [[] for _ in range(n)]

for i in range(n-1):
    a,b,w = map(int, input().split())
    a -= 1; b -= 1
    to[a].append(b); cost[a].append(w)
    to[b].append(a); cost[b].append(w)

ans = [-1]*n # 頂点を探索済みかどうか判定するために初期値を-1に
ans[0] = 0

import queue

q = queue.Queue()
q.put(0)

while not q.empty():
    v = q.get()
    for i in range(len(to[v])):
        u = to[v][i]
        w = cost[v][i]
        if ans[u] != -1: continue
        ans[u] = ans[v]+w%2
        q.put(u)
        
print(*ans)

Submission status: Wrong Answer

Solution code:
"""bfs"""

import sys
sys.setrecursionlimit(10**6)

n = int(input())

to = [[] for _ in range(n)]
cost = [[] for _ in range(n)]

for i in range(n-1):
    a,b,w = map(int, input().split())
    a -= 1; b -= 1
    to[a].append(b); cost[a].append(w)
    to[b].append(a); cost[b].append(w)

ans = [-1]*n # 頂点を探索済みかどうか判定するために初期値を-1に

import queue

q = queue.Queue()
q.put(0)

while not q.empty():
    v = q.get()
    for i in range(len(to[v])):
        u = to[v][i]
        w = cost[v][i]
        if ans[u] != -1: continue
        ans[u] = ans[v]+w%2
        q.put(u)
        
print(*ans)

Submission status: Wrong Answer

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]
print(1)
while stack:
  now=stack.pop(-1)
  #now_d=t0.index(tree[now][p])
  
  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]]
     #print(a[ii][2]+tree[now][d])
      if (a[ii][2]+tree[now][d]) % 2==0:
        print(1)
      else:
        print(0)
  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(a[ii][2]+tree[now][d])
      if (a[ii][2]+tree[now][d]) % 2==0:
        print(1)
      else:
        print(0)
#print(tree)

Submission status: Wrong Answer

Solution code:
from collections import deque

n = int(input())
dp = [[] for _ in range(2*n+1)]
co = [-1 for _ in range(2*n+1)]

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

    if(w % 2 == 1):
        dp[u].append(v)
        dp[v].append(u)
    else:
        dp[u].append(u+n)
        dp[u+n].append(v)
        dp[v].append(v+n)
        dp[v+n].append(u)

q = deque()

q.append(1)
co[1] = 0

while(len(q)):
    temp = q.popleft()
    for i in dp[temp]:
        if(co[i] == -1):
            co[i] = (co[temp] + 1) % 2
            q.append(i)

print(dp)
print(co)
for i in range(1,n+1):
    print(co[i])

Submission status: Wrong Answer

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

#木の根
root=1
next=root
#
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):
  for ii in range(i+1, n+1):
    #iとiiの最小共通祖先を探す
    if i==root:
      w=i
    else:
      #print(i,ii,tree[i],tree[ii])
      gap=abs(tree[i][dep]-tree[ii][dep])
      if tree[i][dep] >= tree[ii][dep]:
        deeper=i
        shallow=ii
      else:
        deeper=ii
        shallow=i
      for _ in range(gap):
        deeper=tree[deeper][p]

      dis=tree[deeper][dep]
      for _ in range(dis):
        p1=tree[deeper][p]
        p2=tree[shallow][p]
        #print("p1p2",p1,p2)
        #最小共通祖先決定
        if p1==p2:
          w=p1
          break
    
    #2頂点間の距離
    distance=tree[i][d]+tree[ii][d]-2*tree[w][d]
    #print("distance",distance,i,ii)
    if distance % 2 == 0:
      ans[i-1],ans[ii-1]=1, 1


for i in ans:
  print(i)

Submission status: Wrong Answer

Solution code:
N = int(input())

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

    if w % 2 == 0:
        if colors[u] == -1 and colors[v] == -1:
            colors[u] = 0
            colors[v] = 0

        elif colors[u] == -1 and colors[v] != -1:
            colors[u] = colors[v]

        elif colors[u] != -1 and colors[v] == -1:
            colors[v] = colors[u]

        else:
            continue

    else:
        if colors[u] == -1 and colors[v] == -1:
            colors[u] = 0
            colors[v] = 1

        elif colors[u] == -1 and colors[v] != -1:
            if colors[v] == 1:
                colors[u] = 0
            else:
                colors[u] = 1

        elif colors[u] != -1 and colors[v] == -1:
            if colors[u] == 1:
                colors[v] = 0
            else:
                colors[v] = 1
        
        else:
            continue

for i in colors:
    print(i)

Submission status: Wrong Answer

Solution code:
n = int(input())

ikeru = [[] for _ in range(n)]
for i in range(n-1):
	a, b, c = map(int, input().split())
	ikeru[a-1].append((b-1, c))

#fukasa = [0 for _ in range(n)]
#fukasamoto = [0 for _ in range(n)]
kaisuu = 0
settansaku = set([])
setmada = {0}
kouho = 1
guuki = [0 for _ in range(n)]

while kouho != 0:
	kaisuu += 1
	for i in list(setmada):
		settansaku.add(i)
		setmada.remove(i)
		kouho -= 1
		for k, leng in ikeru[i]:
			if not k in setmada:
				if not k in settansaku:
					setmada.add(k)
					guuki[k] = (guuki[i] + leng) % 2
					kouho += 1
					#fukasa[k] = kaisuu
					#fukasamoto[k] = i+1

print("\n".join([str(guuki[i]) for i in range(n)]))

Submission status: Wrong Answer

Solution code:
from heapq import heappop, heappush

n = int(input())
a = [[] for _ in range(n)]
for _ in range(n - 1):
    u, v, w = map(int, input().split())
    a[u - 1].append((v - 1, w))
    a[v - 1].append((u - 1, w))
d = [-1] * n
todo = [(0, 0)]
seen = set()
while todo:
    e, p = heappop(todo)
    if p in seen:
        continue
    seen.add(p)
    d[p] = e
    for pi, ei in a[p]:
        heappush(todo, (e + ei, pi))
print(d)
for di in d:
    print(di % 2)

Submission status: Wrong Answer

Solution code:
from heapq import heappop, heappush

n = int(input())
a = [[] for _ in range(n)]
for _ in range(n - 1):
    u, v, w = map(int, input().split())
    a[u - 1].append((v - 1, w))
    a[v - 1].append((u - 1, w))
d = [10**9] * n
todo = [(0, 0)]
seen = set()
while todo:
    e, p = heappop(todo)
    if p in seen:
        continue
    seen.add(p)
    d[p] = min(e, d[p])
    for pi, ei in a[p]:
        heappush(todo, (e + ei, pi))
for di in d:
    print(di % 2)

Submission status: Wrong Answer

Solution code:
from collections import deque

n = int(input())
a = [[] for _ in range(n)]
for _ in range(n - 1):
    u, v, w = map(int, input().split())
    a[u - 1].append((v - 1, w))
    a[v - 1].append((u - 1, w))
d = [10**9] * n
todo = deque([(0, 0)])
seen = set()
while todo:
    p, e = todo.popleft()
    if p in seen:
        continue
    seen.add(p)
    d[p] = min(e, d[p])
    for pi, ei in a[p]:
        todo.append((pi, e + ei))
for di in d:
    print(di % 2)

Submission status: Wrong Answer

Solution code:
import sys
N = int(input())
G = [{} for _ in range(N)]
for _ in range(N - 1):
    u, v, w = map(int, sys.stdin.readline().split())
    u -= 1
    v -= 1
    G[u][v] = w
    G[v][u] = w

ans = [0] * N
todo = [(0, 0)]
done = set()
while todo:
    p, d = todo.pop()
    for np, dd in G[p].items():
        if not np in done:
            nd = d + dd
            ans[np] = ans[p] ^ (nd % 2)
            todo.append((np, nd))
    done.add(p)

for x in ans:
    print(x)

Submission status: Wrong Answer

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

def root(par, a):
    a_ = a
    while par[a] != a:
        a = par[a]
    par[a_] = a
    return a

def unite(par, a, b):
    pass

par = [i for i in range(N + 1)]
for _ in range(N - 1):
    u, v, w = map(int, sys.stdin.readline().split())
    u -= 1
    v -= 1
    if w % 2 == 0:
        par[u] = N
        par[v] = N

for i in range(N):
    if root(par, i) == N:
        print("0")
    else:
        print("1")

Submission status: Wrong Answer

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

def root(par, a):
    a_ = a
    while par[a] != a:
        a = par[a]
    par[a_] = a
    return a

white = 0
par = [i for i in range(N)]
for _ in range(N - 1):
    u, v, w = map(int, sys.stdin.readline().split())
    u -= 1
    v -= 1
    if w % 2 == 0:
        ru = root(par, u)
        rv = root(par, v)
        if ru != rv:
            par[rv] = ru
        white = u

whiteroot = root(par, white)
for i in range(N):
    if root(par, i) == whiteroot:
        print("0")
    else:
        print("1")

Submission status: Wrong Answer

Solution code:
N = int(input())
graph = [[] for  _ in range(N)]
now = 0
for _ in range(N-1):
    x,y,w = map(int,input().split())
    x -= 1
    y -= 1
    graph[x].append((y,w))
    graph[y].append((x,w))
    now = x
    
vis = [0 for _ in range(N)]

even = set()
odd = set()
import sys
sys.setrecursionlimit(100000000)


def dfs(now):
    print(now)
    for nv in graph[now]:
        if vis[nv[0]]: continue
        if nv[1] % 2 == 0:
            if now in even:
                even.add(nv[0])
            else:
                odd.add(nv[0])
        else:
            if now in even:
                odd.add(nv[0])
            else:
                even.add(nv[0])
        vis[nv[0]] = 1
        dfs(nv[0])
vis[x] = 1
even.add(x)
dfs(x)

for i in range(N):
    if i in even:
        print(1)
    else:
        print(0)

Submission status: Wrong Answer

Solution code:
N = int(input())
graph = [[] for  _ in range(N)]
now = 0
for _ in range(N-1):
    x,y,w = map(int,input().split())
    x -= 1
    y -= 1
    graph[x].append((y,w))
    graph[y].append((x,w))
    now = x
    
vis = [0 for _ in range(N)]

even = set()
odd = set()
import sys
sys.setrecursionlimit(1000000)


def dfs(now):
    print(now)
    for nv in graph[now]:
        if vis[nv[0]]: continue
        if nv[1] % 2 == 0:
            if now in even:
                even.add(nv[0])
            else:
                odd.add(nv[0])
        else:
            if now in even:
                odd.add(nv[0])
            else:
                even.add(nv[0])
        vis[nv[0]] = 1
        dfs(nv[0])
vis[x] = 1
even.add(x)
dfs(x)

for i in range(N):
    if i in even:
        print(1)
    else:
        print(0)

Submission status: Wrong Answer

Solution code:
N = int(input())
graph = [[] for  _ in range(N)]
for _ in range(N-1):
    x,y,w = map(int,input().split())
    x -= 1
    y -= 1
    graph[x].append((y,w))
    graph[y].append((x,w))
    
vis = [0 for _ in range(N)]

even = set()
odd = set()

def dfs(now):
    for nv in graph[now]:
        if vis[nv[0]]: continue
        if nv[1] % 2 == 0:
            if nv in even:
                even.add(nv[1])
            else:
                odd.add(nv[1])
        else:
            if nv in even:
                odd.add(nv[1])
            else:
                even.add(nv[1])
        vis[nv[0]] = 1
        dfs(nv[0])
vis[0] = 1
even.add(0)
#dfs(0)
for i in range(N):
    if i in even:
        print(1)
    else:
        print(0)

Submission status: Wrong Answer

Solution code:
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

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

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())






N = int(input())
uf = UnionFind(N)
for _ in range(N-1):
    x,y,w = map(int,input().split())
    x -= 1
    y -= 1
    if w % 2 == 0:
        uf.union(x,y)
for i in range(N):
    if uf.size(i) == 1:
        print(1)
    else:
        print(0)

Submission status: Wrong Answer

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

def root(par, a):
    a_ = a
    while par[a] != a:
        a = par[a]
    par[a_] = a
    return a

r = 0
par = [i for i in range(N)]
for _ in range(N - 1):
    u, v, w = map(int, sys.stdin.readline().split())
    u -= 1
    v -= 1
    if w % 2 == 0:
        ru = root(par, u)
        rv = root(par, v)
        if ru != rv:
            par[rv] = ru
        r = ru

for i in range(N):
    if root(par, i) == r:
        print("0")
    else:
        print("1")

Submission status: Wrong Answer

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

def root(par, a):
    a_ = a
    while par[a] != a:
        a = par[a]
    par[a_] = a
    return a

def union(par, a, b):
    ra = root(par, a)
    rb = root(par, b)
    if ra != rb:
        par[rb] = ra

par = [i for i in range(N)]
for _ in range(N - 1):
    u, v, w = map(int, sys.stdin.readline().split())
    u -= 1
    v -= 1
    if w % 2 == 0:
        union(par, u, v)

r0 = root(par, 0)
print("0")
for i in range(1, N):
    if root(par, i) == r0:
        print("0")
    else:
        print("1")

Submission status: Wrong Answer

Solution code:
import queue
n = int(input())
ans = [2]*n
ans[0] = 0
c = [list(map(int, input().split())) for i in range(n-1)]
root  = [[0]*n for i in range(n)]
q = queue.Queue()
for i in  range(n-1):
  root[c[i][0]-1][c[i][1]-1]=c[i][2]
  root[c[i][1]-1][c[i][0]-1]=c[i][2]
  
for i in range(n):
  if root[0][i] != 0:
    if root[0][i] % 2== 0:
      ans[i]= 0
    else: 
      ans[i]= 1
    q.put(i)

if n >= 2:
  flg = True
else: 
  flg = False
while flg:
  flg = False
  temp = q.get()
  for i in range(n):
    if root[temp][i] != 0 and ans[i]== 2:
      flg = True
      if root[temp][i] % 2==0:
        ans[i]=ans[temp]
      else:
        if ans[temp]==0:
          ans[i]=1
        else:
          ans[i]=0
      q.put(i)
for i in range(n):
  print(ans[i])

Submission status: Wrong Answer

Solution code:
from collections import deque
from collections import defaultdict

n = int(input())

graph = defaultdict(dict)
visited = [1] + [0] * n
ans = [0] * (n + 1)

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

q = deque([1])

while q:
    curr = q.popleft()
    for v, w in graph[curr].items():
        if not visited[v]:
            ans[v] = (ans[curr] + w) % 2
            visited[v] = 1
            q.append(v)
        else:
            continue

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

Submission status: Wrong Answer

Solution code:
import sys

def dfs(s):
    color = [0]*n
    visited = [False]*n
    visited[s] = True
    q = [s]
    while q:
        p = q.pop()
        visited[p] = True
        for d,v in edge[p]:
            if visited[v]:
                continue
            if d%2 != 0:
                color[v] = 1
            q.append(v)
    return color

if __name__ == "__main__":
    n = int(input())
    edge = [[] for i in range(n)]
    for i in range(n-1):
        u,v,w = map(int,input().split())
        u-=1
        v-=1
        edge[u].append([w,v])
        edge[v].append([w,u])
    ans = dfs(0)
    print(*ans)

Submission status: Wrong Answer

Solution code:

N = int(input())

top = [0] * (N+1)
tree = [[] for _ in range(N+1)]

UVW = []
for i in range(N-1):
    u, v, w = map(int, input().split())
    if w % 2 != 0:
        UVW.append([u, v, w])
    tree[u].append(v)
    tree[v].append(u)
    
#print(tree)
    
for u, v, w in UVW:
    s = 1-top[u]
    for i in tree[v]:
        top[i] = s
    top[v] = s
    top[u] = 1-s
    
top = top[1:]
for i in top:
    print(i)

Submission status: Wrong Answer

Solution code:
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60


def main():
    N = int(readline())
    G = [[] for _ in range(N)]
    for _ in range(N - 1):
        u, v, w = map(int, readline().split())
        if w % 2:
            G[u - 1].append(v - 1)
            G[v - 1].append(u - 1)

    color = [-1] * N

    def dfs(G, v, c):
        color[v] = c
        for nv in G[v]:
            if color[nv] == -1:
                dfs(G, nv, 1 - c)

    for v in range(N):
        if color[v] != -1:
            continue
        dfs(G, v, 0)

    print(*color, sep='\n')
    return


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60


def main():
    N = int(readline())
    G = [[] for _ in range(N)]
    for _ in range(N - 1):
        u, v, w = map(int, readline().split())
        if w % 2:
            G[u - 1].append(v - 1)
            G[v - 1].append(u - 1)

    color = [-1] * N

    def dfs(G, v, c):
        color[v] = c
        for nv in G[v]:
            if color[nv] != -1:
                if color[nv] == c:
                    return False
                continue
            if not dfs(G, nv, 1 - c):
                return False

        return True

    for v in range(N):
        if color[v] != -1:
            continue
        dfs(G, v, 0)

    print(*color, sep='\n')
    return


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from copy import deepcopy
from collections import deque
def main():
    def find(x):
        if par[x] < 0:
            return x
        else:
            par[x] = find(par[x])
            return par[x]
    def unite(x, y):
        x = find(x)
        y = find(y)
        if x == y:
            return False
        else:
            if par[x] > par[y]:
                x, y = y, x
            par[x] += par[y]
            par[y] = x
            return True
    def roots():
        return [i for i, x in enumerate(par) if x < 0]

    n = int(input())
    par = [-1] * n
    uvw = {e:[] for e in range(n)}

    for _ in range(n - 1):
        u, v, w = map(int, input().split())
        u -= 1
        v -= 1
        uvw[u].append((u, v, w))
        uvw[v].append((v, u, w))
        unite(u, v)
    root_node = roots()[0]
    color = [-1] * n
    color[root_node] = 0
    print(uvw)
    node_next = deque()
    node_next.append(root_node)
    node_next_next = deque()
    node_seen = set()

    while len(node_seen) < n:
        while node_next:
            node_togo = node_next.popleft()
            if node_togo in node_seen:
                continue
            else:
                node_seen.add(node_togo)
            # 次の層のノード群情報を取得し、「次にみるノードlist」にいれる。
            node_adj = uvw[node_togo]
            node_next_next += [i[1] for i in node_adj]
            # 次の層を処理＝色塗りする
            for adj in node_adj:
                if adj[1] in node_seen or color[adj[1]] != -1:
                    continue
                if adj[2] % 2 == 0:
                    color[adj[1]] = color[node_togo]
                else:
                    color[adj[1]] = color[node_togo] ^ 1
        node_next = deepcopy(node_next_next)
        node_next_next = deque()
    print(*color, sep='\n')


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**6)
N = int(input())
adj = [ [] for _ in range(N) ]
for _ in range(N-1):
  u,v,w = map(int,input().split())
  u -= 1
  v -= 1
  adj[u].append((v,w))
  adj[v].append((u,w))

def dfs(node, w, color):
  colors[node] = color

  for nei,nw in adj[node]:
    if colors[nei] != -1: continue
    nc = 1 if (w+nw)%2==0 else 0
    dfs(nei, nw, nc)

  return True

colors = [-1] * N
for i in range(N):
  if colors[i] == -1:
    dfs(i, 0, 1)

for c in colors: print(c)

Submission status: Wrong Answer

Solution code:
N=int(input())
links=[set() for _ in [0]*N]
print(links)
for i in range(1,N):
  u,v,w=map(int,input().split())
  u-=1
  v-=1
  links[u].add((v,w))
  links[v].add((u,w))
ans=[-1]*N
q=[(0,0,-1)]
while q:
  v,d,p=q.pop()
  if d%2==0:
    ans[v]=0
  else:
    ans[v]=1
  for u,w in links[v]:
    if u==p:
      continue
    q.append((u,w+d,v))
print('\n'.join(map(str,ans)))

Submission status: Wrong Answer

Solution code:
n = int(input())
edge = [[int(i) for i in input().split()] for j in range(n-1)]

color = [-1] * (n+1)

color[edge[0][0]] = 0
for i in range(n-1):
    u, v, w = edge[i][0], edge[i][1], edge[i][2]
    if w % 2 == 0:
        color[v] = color[u]
    else:
        color[v] = (color[u] + 1) % 2
print('\n'.join([str(n) for n in color[1:]]))

Submission status: Wrong Answer

Solution code:
from collections import deque 
#スタック
q = deque([])#append pop

N = int(input())
#木
tree = [[]for i in range(0,N+1,1)]
for i in range(1,N,1):
    u,v,w = map(int,input().split())
    tree[u].append([v,w])
    tree[v].append([u,w])
ans = [0]*(N+1)

q.append([1,0,0])#今回のノード、距離、前回のノード

while len(q)>0:
    now,dist,pre = q.pop()
    ans[now] = (ans[pre] + dist%2)%2
    for i in tree[now]:
        if i[0]!=pre:
            q.append([i[0],i[1],now])

print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())

uvw = []
for i in range(N-1):
    u, v, w = map(int, input().split())
    if w % 2 != 0:
        uvw.append([u, v, w])
        
uvw.sort()

mark = [0] * (N+1)
for i in range(len(uvw)):
    u, v, w = uvw[i]
    if mark[u] != 1:
        mark[v] = 1
        
for i in range(1, N+1):
    print(mark[i])

Submission status: Wrong Answer

Solution code:
from collections import deque
N = int(input())
G = [[] for _ in range(N)]
for _ 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])

Q = deque()
Q.append(0)
c = [-1] * N
c[0] = 0
while len(Q) > 0:
    q = Q.popleft()
    pc = c[q]
    for g, w in G[q]:
        if c[g] != -1:
            continue
        if w % 2 == 0:
            c[g] = pc
        else:
            c[g] = 1 - pc
        Q.append(g)

print(c)

Submission status: Wrong Answer

Solution code:
N = int(input())
uvw = []
mark = [-1] * (N+1)
for i in range(N-1):
    u, v, w = map(int, input().split())
    if w % 2 == 0:
        mark[u] = 0
        mark[v] = 0
    elif (w % 2 == 1) and (mark[u] == 0):
        mark[v] = 1
    elif (w % 2 == 1) and (mark[v] == 0):
        mark[u] = 1
    elif (w % 2 == 1) and (mark[u] == 1):
        mark[v] = 0
    elif (w % 2 == 1) and (mark[v] == 1):
        mark[u] = 0
    else:
        uvw.append([u, v, w])
        
for i in range(len(uvw)):
    u, v, w = uvw[i]
    if w % 2 == 0:
        mark[u] = 0
        mark[v] = 0
    elif (w % 2 == 1) and (mark[u] == 0):
        mark[v] = 1
    elif (w % 2 == 1) and (mark[v] == 0):
        mark[u] = 1
    elif (w % 2 == 1) and (mark[u] == 1):
        mark[v] = 0
    elif (w % 2 == 1) and (mark[v] == 1):
        mark[u] = 0
        
#print(uvw)
#print(mark)

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