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:
###
### atcorder test program
###

import sys
import math

### math class
# class math:
#     ### pi
#     pi = 3.14159265358979323846264338

#     ### GCD
#     def gcd(self, a, b):
#         if b == 0:
#             return a
#         return self.gcd(b, a%b)

#     ### LCM
#     def lcm(self, a, b):
#         return (a*b)//self.gcd(a,b)

# math = math()

### output class
class output:
    ### list
    def list(self, l):
        l = list(l)
        print(" ", end="")
        for i, num in enumerate(l):
            print(num, end="")
            if i != len(l)-1:
                print(" ", end="")
        print()

output = output()

### input sample
#i = input()
#A, B, C = [x for x in input().split()]
#N, K = [int(x) for x in input().split()]
#inlist = [int(w) for w in input().split()]
#R = float(input())
#A = [int(x) for x in input().split()]
#for line in sys.stdin.readlines():
#    x, y = [int(temp) for temp in line.split()]

### output sample
#print("{0} {1} {2:.5f}".format(A//B, A%B, A/B))
#print("{0:.6f} {1:.6f}".format(R*R*math.pi,R*2*math.pi))
#print(" {}".format(i), end="")

N = int(input())
data = []
ans = [0 for i in range(N)]

for i in range(N-1):
    data.append([int(x) for x in input().split()])

data.sort()

for link in data:
    if link[2]%2 == 1:
        ans[link[1]-1] = 1 if ans[link[0]-1] == 0 else 0

for link in data:
    if link[2]%2 == 1:
        ans[link[1]-1] = 1 if ans[link[0]-1] == 0 else 0

for link in data:
    if link[2]%2 == 1:
        ans[link[1]-1] = 1 if ans[link[0]-1] == 0 else 0


for i in ans:
    print(i)

Submission status: Wrong Answer

Solution code:
import numpy as np
N = int(input())

group = np.full(N, -1)

data_list = []
for idx in range(N-1):
    u, v, w = list(map(int, input().split()))
    
    data_list.append((u-1,v-1,w))
    
data_list = sorted(data_list, key=lambda x:x[1])
data_list = sorted(data_list, key=lambda x:x[0])
    
for idx, (u, v, w) in enumerate(data_list):
    if idx == 0:
        if w % 2 == 0:
            group[u] = 0
            group[v] = 0
        else:
            group[u] = 0
            group[v] = 1
    else:
        if group[u] > -1:
            if w % 2 == 0:
                group[v] = group[u]
            else:
                group[v] = 1 - group[u]
        elif group[v] > -1:
            if w % 2 == 0:
                group[u] = group[v]
            else:
                group[u] = 1 - group[v]
        else:
            print("unknown node exists", u, v)
            
        
for g in group:
    print(g)

Submission status: Wrong Answer

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

i  = lambda: int(input())
mi = lambda: map(int, input().split())

N = i()
ans = [0] * (N+1)

for _ in range(N-1):
  u, v, w = mi()
  if w % 2 == 0:
    if ans[u] != ans[v]:
      ans[u] = 1
      ans[v] = 1
  else:
    if ans[u] == ans[v]:
      ans[v] = 1
      
print('\n'.join(list(map(str, ans[1:]))))

Submission status: Wrong Answer

Solution code:
class UnionFind:

    def __init__(self, n):
        self.table = [-i - 1 for i in range(n + 1)]

    def merge(self, r1, r2):
        self.table[r1] = r2

    def find_root(self, k):
        path = []
        curr = k
        while self.table[curr] > 0:
            path.append(curr)
            curr = self.table[curr]
        for i in path:
            self.table[i] = curr
        return curr


def solve(string):
    n, *uvw = map(int, string.split())
    uvw = list(zip(uvw[::3], uvw[1::3], uvw[2::3]))
    uf = UnionFind(n)
    for _a, _b, w in uvw:
        ra = uf.find_root(_a)
        rb = uf.find_root(_b)
        if w % 2 == 0:
            uf.merge(ra, rb)
    r1 = uf.find_root(1)
    ans = ["0"] * n
    for i in range(n):
        if uf.find_root(i + 1) != r1:
            ans[i] = "1"
    return "\n".join(ans)


if __name__ == '__main__':
    n = int(input())
    print(solve('{}\n'.format(n) + '\n'.join([input() for _ in range(n - 1)])))

Submission status: Wrong Answer

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

n = int(input())

a = [0 for i in range(n)]

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

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

Submission status: Wrong Answer

Solution code:
n=int(input())
ans=[0]*(n+1)
arr=[list(map(int,input().split())) for _ in range(n-1)]
arr=sorted(arr,key=lambda x:x[0])
s=set()
tmp=arr[0]
u,v,w=tmp[0],tmp[1],tmp[2]
s.add(u)
s.add(v)
if w%2==0:
  ans[u]=1
  ans[v]=1
elif w%2==1:
  ans[u]=1
  ans[v]=0
for i in range(1,n-1):
  tmp=arr[i]
  u,v,w=tmp[0],tmp[1],tmp[2]
  if u in s:
    s.add(v)
    if w%2==0:
      ans[v]=ans[u]
    else:
      ans[v]=abs(ans[u]-1)
  elif v in s:
    s.add(u)
    if w%2==0:
      ans[u]=ans[v]
    else:
      ans[u]=abs(ans[v]-1)
for i in range(1,n+1):
  print(ans[i])

Submission status: Wrong Answer

Solution code:
n = int(input())
e = [[int(i) for i in input().split()] for i in range(n-1)]
colors = {i:0 for i in range(1,n+1)}
for u,v,w in e:
    if w%2 == 1:
        colors[v] = 1
    if w%2 == 0 and colors[v] != colors[u]:
        colors[v] = colors[u]
for cont in colors.values():
    print(cont)

Submission status: Wrong Answer

Solution code:
from collections import deque
N = int(input())
t = []
ans = [True]*(N+1)
already = [False] * (N+1)

td = {i:[] for i in range(1,N+1)}
for i in range(N-1):
	ut,vt,wt = map(int,input().split(' '))
	td[ut].append((vt,wt%2))
	td[vt].append((ut,wt%2))

q = deque([1])
while(q):
	i = q.popleft()
	already[i] = True
	for v,w in td[i]:
		if not already[v]:
			q.append(v)
			#print(i,v,w)
			if w:
				ans[v] = not ans[i]

#print(td)

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

Submission status: Wrong Answer

Solution code:
N = int(input())

colors = [False] * N

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

for i in range(0,N):
    print(1 if colors[i] else 0)

Submission status: Wrong Answer

Solution code:
N = int(input())
T = []
for k in range(N-1):
    t = list(map(int,input().split()))
    T.append(t)

T = sorted(T, key = lambda x: (x[0],x[1]))
A = [-1 for k in range(N)]
A[0] = 0
for t in T:
    u = t[0]-1
    v = t[1]-1
    w = t[2]
    if w%2 == 0:
        if A[u] == 0 and A[v] == -1:
            A[v] = 0
        elif A[u] == 1 and A[v] == -1:
            A[v] = 1
        elif A[u] == -1 and A[v] == 0:
            A[u] = 0
        elif A[u] == -1 and A[v] == 1:
            A[u] = 1
    else:
        if A[u] == 0 and A[v] == -1:
            A[v] = 1
        elif A[u] == 1 and A[v] == -1:
            A[v] = 0
        elif A[u] == -1 and A[v] == 0:
            A[u] = 1
        elif A[u] == -1 and A[v] == 1:
            A[u] = 0

print(*A, sep="\n")

Submission status: Wrong Answer

Solution code:
N = int(input())
l = list("k"*(N+1))
for  i in range(N-1):
        a,b,c=map(int, input().split())
        if c%2==1:
                l[a-1]="s"
                l[b-1]="s"
m = 0
for i in range(N):
        if i == "s":
                l[i]=m%2
                if l[i+1]=="a":
                        m+=1
                        

for i in range(N):
        if l[i]=="k":
                print(0)
        else:
                print(1)

Submission status: Wrong Answer

Solution code:
n = int(input())
e = [[int(i) for i in input().split()] for i in range(n-1)]
colors = {i:0 for i in range(1,n+1)}
for u,v,w in e:
    if w%2 == 1:
        colors[v] = 1
    if w%2 == 0 and u != v:
        colors[v] = colors[u]
for cont in colors.values():
    print(cont)

Submission status: Wrong Answer

Solution code:
import collections
n = int(input())
d = [[int(u) for u in input().split(" ")] for row in range(n-1)]
c = collections.Counter([u[0] for u in d] + [u[1] for u in d])
r = [u[0] for u in sorted(c.items(), key=lambda x:-x[1])]
d = sorted(d, key=lambda x: min(r.index(x[0]), r.index(x[1])))
s = [None for u in range(n)]
for u, v, w in d:
    print(u, v, w, s)
    if w % 2 == 0:
        if s[u-1] == None and s[v-1] == None:
            s[u-1] = True
            s[v-1] = True
        elif s[u-1] != None:
            s[v-1] = s[u-1]
        elif s[v-1] != None:
            s[u-1] = s[v-1]
    else:
        if s[u-1] == None and s[v-1] == None:
            s[u-1] = True
            s[v-1] = False
        elif s[u-1] != None:
            s[v-1] = not s[u-1]
        elif s[v-1] != None:
            s[u-1] = not s[v-1]
print("\n".join(["1" if u else "0" for u in s]))

Submission status: Wrong Answer

Solution code:
n = int(input())
graph = [{} for _ in range(n-1)]

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

zero = set()
one = set()

for i in range(n-1):
    cond = True
    if i+1 in one:
        cond = False
    for j in graph[i]:
        if graph[i][j]%2 == 0:
            if cond:
                zero.add(i+1)
                zero.add(j)
            else:
                zero.add(j)
        else:
            if cond:
                one.add(j)
            else:
                zero.add(j)

for i in range(1, n+1):
    if i in zero:
        print(0)
    else:
        print(1)

Submission status: Wrong Answer

Solution code:
class UnionFind:
    def __init__(self, n):
        self.nodes = [-1 for i in range(n)]

    def root(self, i):
        if self.nodes[i] < 0:
            return i
        else:
            self.nodes[i] = self.root(self.nodes[i])
            return self.nodes[i]

    def size(self, t):
        rt = self.root(t)
        return - self.nodes[rt]

    def unite(self, x, y):
        rx = self.root(x)
        ry = self.root(y)
        if rx == ry:
            return
        else:
            if self.size(rx) > self.size(ry):
                self.nodes[ry] = rx
                self.nodes[rx] -= self.size(ry)
            else:
                self.nodes[rx] = ry
                self.nodes[ry] -= self.size(rx)

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

def main():
    n = int(input())
    uf = UnionFind(n)
    for i_line in range(n - 1):
        u_1, v_1, w = [int(x) for x in input().split()]
        u = u_1 - 1
        v = v_1 - 1
        if w % 2 == 0:
            uf.unite(u, v)

    for i in range(n):
        if i == 0:
            print(0)
        else:
            if uf.same(0, i):
                print(0)
            else:
                print(1)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
N = int(input())

colors = [0] * (N+1)
vertices = defaultdict(bool)
edges = defaultdict(dict)
for i in range(1, N):
    u, v, w = map(int, input().split())
    edges[u][v] = w % 2 == 0
    edges[v][u] = w % 2 == 0
    vertices[u] = False
    vertices[v] = False

queue = [(u, v)]
while len(queue) > 0:
    u, v = queue.pop(0)
    vertices[u] = True
    if vertices[v]:
        continue
    vertices[v] = True
    if colors[u] == colors[v]:
        if not edges[u][v]:
            colors[v] = 1 - colors[u]
    else:
        if edges[u][v]:
            colors[v] = colors[u]

    for nv in edges[v].keys():
        if not vertices[nv]:
            queue.append((v, nv))

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

Submission status: Wrong Answer

Solution code:
N = int(input())
u = [0]*(N-1)
v = [0]*(N-1)
w = [0]*(N-1)

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

ans = [-1]*N
score = 0
for i in range(N-1):
    if ans[u[i]-1] == -1 and ans[v[i]-1] == -1:
        ans[u[i]-1] = 0
        ans[v[i]-1] = score + w[i]%2
        score += 2
    elif ans[u[i]-1] == -1 and ans[v[i]-1] > -1:
        if v[i] % 2 == 0:
            ans[u[i]-1] = v[i] + w[i]%2
        else:
            ans[u[i]-1] = v[i] - w[i]%2
    elif ans[v[i]-1] == -1 and ans[u[i]-1] > -1:
        if u[i] % 2 == 0:
            ans[v[i]-1] = u[i] + w[i]%2
        else:
            ans[v[i]-1] = u[i] - w[i]%2
    elif ans[u[i]-1] % 2 != ans[v[i]-1] % 2:
        for j in range(N-1):
            if int(ans[j]/2) == int(ans[v[i]-1]/2):
                if ans[j] % 2 == 0:
                    ans[j] += 1
                else:
                    ans[j] -= 1
                

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

Submission status: Wrong Answer

Solution code:
import sys

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces

def another (n):
    if n== 0:
        return 1
    else:
        return 0
n = ni()
pli = [0] * n
for i in range(n-1):
    u, v, w = na()
    if w % 2 == 1:
        if pli[u-1] ^ pli[v-1] == 0:
            pli[v - 1] =  another(pli[v - 1])

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

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
import math
from bisect import bisect_left
from bisect import bisect_right
import collections
import copy
input = sys.stdin.readline
 
# bisect_left(lists, 3)
# bisect_right(lists, 3)
 
def main():
	#N, K = map(int, input().split(" "))
	N = int(input())
	#S = input()
	#S = S[:-1]
	#S = list(S)

	U = []
	for _ in range(N-1):
		a, b, c = map(int, input().split(" "))
		U.append((a, b, c))

	UF = UnionFind(N)
	for i, val in enumerate(U):
		a, b, c = val
		a -= 1
		b -= 1
		if c % 2 == 0:
			#print("+{} {}".format(a, b))
			UF.union(a, b)

	ans = []
	for i in range(N):
		tmp = UF.find(i)
		tmp2 = UF.getSize(i)

		#print("--{} {} {}".format(i, tmp, tmp2))

		if tmp != i or tmp2 > 1:
			ans.append(0)
		else:
			ans.append(1)
	
	for i in ans:
		print(i)

class UnionFind(object):
	def __init__(self, n=1):
		self.par = [i for i in range(n)]
		self.rank = [0 for _ in range(n)]
		self.size = [1 for _ in range(n)]
		
	# x が属するグループを探索
	def find(self, x):
		if self.par[x] == x:
			return x
		else:
			self.par[x] = self.find(self.par[x])
			return self.par[x]
		
	# x と y のグループを結合
	def union(self, x, y):
		x = self.find(x)
		y = self.find(y)
		if x != y:
			# メンバ数の更新
			sum = self.size[x] + self.size[y]
			self.size[x] = sum
			self.size[y] = sum
			# 短いリストを長いリストのルートに繋ぎ直す
			if self.rank[x] < self.rank[y]:
				x, y = y, x
			if self.rank[x] == self.rank[y]:
				self.rank[x] += 1
			self.par[y] = x
	
	# x と y が同じグループがどうか
	def is_same(self, x, y):
		return self.find(x) == self.find(y)
		
	# x が属するグループのメンバ数を返却
	def getSize(self, x):
		par_x = self.find(x)
		return self.size[par_x]

if __name__ == "__main__":
	main()

Submission status: Wrong Answer

Solution code:
n = int(input())

edges = []
for i in range(n-1):
	edges.append(list(map(int, input().split())))
edges = sorted(edges, key=lambda x: x[0])

colors = [-1]*n
for edge in edges:
	u, v, w = edge
	if colors[u-1]==-1 and colors[v-1]==-1:
		colors[u-1]=0
	elif colors[v-1]!=-1:
		u,v = v,u

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

for i in colors:
	if i==-1:
		print(0)
	else:
		print(i)

Submission status: Wrong Answer

Solution code:
# coding: utf-8
# Your code here!

N = int(input())

edges = [0] * N
for i in range(N-1):
    u, v, w = map(int, input().rstrip().split(' '))
    
    if w % 2 == 0:
        edges[u-1] = 1
        edges[v-1] = 1
    
for edge in edges:
    print(edge)

Submission status: Wrong Answer

Solution code:
import numpy as np
n = int(input())

u,v,w = [],[],[]
for k in range(n-1):
    uu, vv, ww =  list(map(int, input().split()))
    uuu = min([uu, vv])
    vvv = max([uu, vv])
    u.append(uu)
    v.append(vv)
    w.append(ww)

u = np.array(u) - 1
v = np.array(v) - 1
w = np.array(w)

same_ind = w%2 == 0
color = np.int32(np.zeros(n)) - 1

for k in range(n-1):
    if same_ind[k]:
        if color[v[k]] == -1:
            color[v[k]] = u[k]
        else:
            color[u[k]] = v[k]
#     print(color)


def find(color, ind):
    if color[ind] != -1:
        return find(color, color[ind])
    else:
        return ind

groups = []
for k in range(n):
    if k == 0:
        a = find(color, k)
        print(0)
    else:
        b = find(color, k)
        if a == b:
            print(0)
        else:
            print(1)

Submission status: Wrong Answer

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

UVW.sort(key = lambda x: (x[0], x[1]))
color = [2 for _ in range(N)]
color[0] = 0

for i in range(N - 1):
  uvw = UVW[i]
  if uvw[2] % 2 == 0:
    if color[uvw[0] - 1] != 2:
      color[uvw[1] - 1] = color[uvw[0] - 1]
    elif color[uvw[1] - 1] != 2:
      color[uvw[0] - 1] = color[uvw[1] - 1]
  else:
    if color[uvw[0] - 1] != 2:
      color[uvw[1] - 1] = color[uvw[0] - 1] ^ 1
    elif color[uvw[1] - 1] != 2:
      color[uvw[0] - 1] = color[uvw[1] - 1] ^ 1

for c in color:
  print(c)

Submission status: Wrong Answer

Solution code:
import numpy as np
n = int(input())
us = []
vs = []
ws = []
for i in range(n-1):
    u, v, w = list(map(int, input().split()))
    us.append(u)
    vs.append(v)
    ws.append(w)
chotens = np.zeros(n)
for i, w in enumerate(ws):
    if w % 2 ==0:
        chotens[vs[i]-1] =0
    else:
        chotens[vs[i]-1] =1
for choten in chotens:
    print(int(choten))

Submission status: Wrong Answer

Solution code:
# coding: UTF-8
import sys
#sys.setrecursionlimit(n)
import heapq
import re
import bisect
import random
import math
import itertools
from collections import defaultdict, deque
from copy import deepcopy
from decimal import *

readl= lambda: list(map(int, sys.stdin.readline().split()))
readt= lambda: tuple(map(int, sys.stdin.readline().split()))
read = lambda: sys.stdin.readline().rstrip()
readi = lambda: int(read())
readmi = lambda: map(int, sys.stdin.readline().split())
readms = lambda: map(str, sys.stdin.readline().split())

n = readi()
tree = defaultdict(lambda: defaultdict(int))
for i in range(n - 1):
    a, b, c= readmi()
    tree[a][b] = c
    tree[b][a] = c
ans = [0] * (n + 1)
used = [0] * (n + 1)
for dic, v in sorted(tree.items(), key=lambda x:x[0]):
    for i in v:
        if used[i] != 1:
            used[i] = 1
            if tree[dic][i] % 2 == 0:
                if ans[i - 1] == 0:
                    ans[i] = 0
                else:
                    ans[i] = 1
            else:
                if ans[i - 1] == 0:
                    ans[i] = 1
                else:
                    ans[i] = 0
for i in range(1, n + 1):
    print(ans[i])

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**6)
N = int(input())

data = [[] for _ in range(N+1)]

for i in range(N-1):
    a, b, c = map(int, input().split())

    data[a].append((b,c))
    data[b].append((a,c))


ans = [0] * (N+1)
went = [False] * (N+1)

went[0] = True
went[1] = True
before = 1

def f(before):
    for i, c in data[before]:
        if not went[i]:
            went[i] = True
            if c % 2 == 0:
                ans[i] = ans[before]
            else:
                ans[i] = 1 - ans[before]
            return f(i)
    return

f(1)

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

Submission status: Wrong Answer

Solution code:
N = int(input())

color = [False] * N

for _ in range(N - 1):
    u, v, w = map(int, input().split())
    if w % 2 == 0:
        color[u - 1] = True
        color[v - 1] = True

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

Submission status: Wrong Answer

Solution code:
from sys import stdin
input = stdin.readline
n=int(input())
even=tuple()
for i in range(n-1):
    u,v,w=map(int,input().split())
    if w%2==0:
        even+=(u,v)
for i in range(1,n+1):
    if i in even:
        print(0)
    else:
        print(1)

Submission status: Wrong Answer

Solution code:
N = int(input())

inputs = []
for n in range(0, N - 1):
	inputs.append(list(map(int,input().split())))


tree = {}
for i in inputs:
	if i[0] in tree:
		tree[i[0]].append({'to': i[1], 'w': i[2]})
	else:
		tree[i[0]] = [{'to': i[1], 'w': i[2]}]

	if i[1] in tree:
		tree[i[1]].append({'to': i[0], 'w': i[2]})
	else:
		tree[i[1]] = [{'to': i[0], 'w': i[2]}]


result = [-1] * N

first = True
for k in tree.keys():
	if first:
		result[k - 1] = 1
		first = False

	for leaf in tree[k]:
		if result[leaf['to'] - 1] != -1:
			continue
		if leaf['w'] % 2 == 0:
			result[leaf['to'] - 1] = 1
		else:
			result[leaf['to'] - 1] = 0

for r in result:
	print(r)

Submission status: Wrong Answer

Solution code:
from sys import stdin

class UnionFind:
    def __init__(self, n):
        # 親
        self.par = [i for i in range(n)]
        # 木の深さ
        self.rank = [1] * (n)
        # size[i]: iを根とするグループのサイズ
        self.size = [1] * (n)

    # 木の根を求める
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            # 検索していく過程で親を書き換える（経路圧縮による効率化）
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    # xとyの属する集合の併合
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        # 木の高さの低い方を高い方に繋げる（ランクによる効率化）
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
            self.size[y] += self.size[x] # サイズの更新
        else:
            self.par[y] = x
            self.size[x] += self.size[y] # サイズの更新
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    # 同じ集合に属するか判定
    def is_same(self, x, y):
        return self.find(x) == self.find(y)

    # 木のサイズを求める
    def get_size(self, x):
        return self.size[x]

N = int(stdin.readline().rstrip())
data = [list(map(int, stdin.readline().rstrip().split())) for _ in range(N-1)]

# Union-Find木の定義
unionfind = UnionFind(N+1)

for u, v, w in data:
    if w % 2 == 0:
        unionfind.union(u, v)

for i in range(1, N+1):
    if unionfind.is_same(1, i):
        print(0)
    else:
        print(1)

Submission status: Wrong Answer

Solution code:
def printAns(ans):
    for i in range(len(ans)):
        print(ans[i])

n = int(input())
ans = [0 for k in range(n)]
u = []
v = []
uu = []
vv = []
for i in range(n-1):
    tmpU, tmpV, tmpW = map(int, input().split())
    if(tmpW%2!=0):
        u.append(tmpU)
        v.append(tmpV)
    else:
        uu.append(tmpU)
        vv.append(tmpV)

if(len(u)==0):
    printAns(ans)
else:
    for i in range(len(u)):
        if(ans[u[i]-1]==0):
            ans[u[i]-1] = 8
            ans[v[i]-1] = 9
        elif(ans[u[i]-1]==8):
            ans[v[i]-1] = 9
        else:
            ans[v[i]-1] = 8
    for i in range(len(uu)):
        if(ans[uu[i]-1]==8 or ans[uu[i]-1]==9):
            ans[vv[i]-1] = ans[uu[i]-1]
        elif(ans[vv[i]-1]==8 or ans[vv[i]-1]==9):
            ans[uu[i]-1] = ans[vv[i]-1]
    for i in range(n):
        if(ans[i]==9):
            ans[i] = 1
        else:
            ans[i] = 0
    printAns(ans)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
N = int(input())
uvw = [list(map(int,input().split())) for i in range(N-1)]
u = []
v = []
length = []
for i in range(N-1):
    u.append(uvw[i][0])
    v.append(uvw[i][1])
    length.append(uvw[i][2])

netmatrix = [[0]*(N) for i in range(N)]


for i in range(N-1):
    netmatrix[u[i]-1][v[i]-1] = 1
    netmatrix[v[i]-1][u[i]-1] = 1



coloring = [1]*N
memo = "white"
for i in range(N-1):
    if length[i] % 2 == 0:
        if memo == "white":
            coloring[u[i]-1] = 0
            coloring[v[i]-1] = 0

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

Submission status: Wrong Answer

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

class UnionFind:
    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 same_check(self, x, y):
        return self.find(x) == self.find(y)

def solve(N: int, U: "List[int]", V: "List[int]", W: "List[int]"):

    uni = UnionFind(N)
    for u,v,w in zip(U,V,W):
        if w % 2 == 0:
            uni.union(u-1,v-1)

    for i in range(N):
        if uni.same_check(0,i):
            print("0")
        else:
            print("1")

    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:

from collections import defaultdict


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


    data_dic = defaultdict(set)

    for i in range(num - 1):
        u, v, w = map(int, input().split())
        if w % 2 == 1:
            max_data, min_data = max(u, v), min(u, v)
            data_dic[min_data].add(max_data)


    color_dic = [-1 for i in range(num + 1)]
    fin_flg = [0 for i in range(num + 1)]

    for i in range(1, num + 1):
        if fin_flg[i]:
            continue

        fin_flg[i] = 1
        if i in data_dic:

            set_a = set()
            set_a.add(i)
            set_b = data_dic[i]

            next_set = set()
            now_set = set_b

            count = 0
            while len(now_set) > 0:
                for aaa in now_set:
                    if fin_flg[aaa]:
                        continue
                    fin_flg[aaa] = 1
                    next_set |= data_dic[aaa]

                if count == 1:
                    count = 0
                    set_b |= next_set
                else:
                    count = 1
                    set_a |= next_set
                now_set = next_set
                next_set = set()

            for ele in set_a:
                color_dic[ele] = 0
            for ele in set_b:
                color_dic[ele] = 1

        else:
            if color_dic[i] == -1:
                color_dic[i] = 0

    # print(color_dic)

    for i in range(num):
        print(color_dic[i + 1])






if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
N = int(input())

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

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
n = int(input())
e = [[int(i) for i in input().split()] for i in range(n-1)]
colors = {i:0 for i in range(1,n+1)}
for u,v,w in e:
    if w%2 == 1:
        colors[v] = 1
for cont in colors.values():
    print(cont)

Submission status: Wrong Answer

Solution code:
class UnionFindNode(object):
    """
    Union-Find構造
    ノードのグループ併合や、所属グループ判定を高速に処理する
    """

    def __init__(self, group_id, parent=None, value=None):
        self.group_id_ = group_id
        self.parent_ = parent
        self.value = value
        self.size_ = 1

    def __str__(self):
        template = "UnionFindNode(group_id: {}, \n\tparent: {}, value: {}, size: {})"
        return template.format(self.group_id_, self.parent_, self.value, self.size_)

    def is_root(self):
        return not self.parent_

    def root(self):
        parent = self
        while not parent.is_root():
            parent = parent.parent_
            self.parent_ = parent
        return parent

    def find(self):
        parent = self.root()
        return parent.group_id_

    def size(self):
        parent = self.root()
        return parent.size_

    def unite(self, unite_node):
        parent = self.root()
        unite_parent = unite_node.root()

        if parent.group_id_ != unite_parent.group_id_:
            if parent.size() > unite_parent.size():
                unite_parent.parent_ = parent
                parent.size_ = parent.size_ + unite_parent.size_
            else:
                parent.parent_ = unite_parent
                unite_parent.size_ = parent.size_ + unite_parent.size_
    def is_group(self,other):#selfとotherが同じグループに属するか
        return self.root()==other.root()
N=int(input())
U=[UnionFindNode(i) for i in range(N)]
for i in range(N-1):
    u,v,w=map(int,input().split())
    if w%2==0:
        U[u-1].unite(U[v-1])
for i in range(N):
    if i==0:
        print(0)
        continue
    if U[0].is_group(U[i]):
        print(0)
    else:
        print(1)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

N = int(input())

colors = [0] * (N+1)
vertices = defaultdict(bool)
edges = defaultdict(dict)
for i in range(1, N):
    u, v, w = map(int, input().split())
    edges[u][v] = w % 2 == 0
    edges[v][u] = w % 2 == 0
    vertices[u] = False
    vertices[v] = False

queue = [(u, v)]
while len(queue) > 0:
    u, v = queue.pop(0)
    vertices[u] = True
    if vertices[v]:
        continue
    vertices[v] = True
    if colors[u] == colors[v] and not edges[u][v]:
        colors[v] = 1 - colors[u]

    for nv in edges[v].keys():
        if not vertices[nv]:
            queue.append((v, nv))

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