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:
class Edge:
    def __init__(self, v1, v2, weight):
        self.v1 = min(v1, v2)
        self.v2 = max(v1, v2)
        self.weight = weight
        self.isOdd = weight % 2 > 0
        self.isEven = not self.isOdd

    def __lt__(self, other):
        return (self.v1, self.v2) < (other.v1, other.v2)

White = True
Black = False

N = int(input())
edges = {}
colored_v = {}
uncolored_v = [x for x in range(1, N+1)]

for i in range(1, N):
    v1, v2, w = list(map(int, input().split()))
    edges[i] = Edge(v1, v2, w)


for _ in range(40):
    if len(uncolored_v) == 0:
        break
    colored_v[uncolored_v[0]] = White
    uncolored_v.remove(uncolored_v[0])
    for ek,ev in sorted(edges.items()):
        if ev.v1 not in colored_v and ev.v2 not in colored_v:
            continue
        if ev.v1 in colored_v and ev.v2 in colored_v:
            continue
        if ev.v1 in colored_v:
            s, e = ev.v1, ev.v2
        else:
            s, e = ev.v2, ev.v1
        if ev.isEven:
            colored_v[e] = colored_v[s]
            uncolored_v.remove(e)
        if ev.isOdd:
            colored_v[e] = not colored_v[s]
            uncolored_v.remove(e)




for v in sorted(colored_v.items()):
    print(0 if v[1] else 1)

Submission status: Wrong Answer

Solution code:
N = int(input())

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

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

for i in range(1 ,len(odd)):
    color[odd[i][0]] = 0
    color[odd[i][1]] = 0

flag = 1
while flag:
    for i in range(1, len(even)):
        tmp = even[i]
        if color[tmp[0]] == 0:
            color[tmp[1]] = 1
        elif color[tmp[0]] == 1:
            color[tmp[1]] = 0
        elif color[tmp[1]] == 0:
            color[tmp[0]] = 1
        elif color[tmp[1]] == 1:
            color[tmp[0]] = 0
    flag = 0
    for i in range(1, N+1):
        if(color[i]==-1):
            flag = 1
            break 

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

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**6)
n = int(input())
edge = [[] for i in range(n)]
colors = [0] * n
for i in range(n-1):
    u, v, w = [int(item) for item in input().split()] 
    u -= 1
    v -= 1
    edge[u].append([v, w%2])
    edge[v].append([u, w%2])

def dfs(frm, n):
    for tv, tw in edge[n]:
        if tv == frm:
            continue
        else:
            if tw == 1:
                colors[tv] = (colors[frm] + 1) % 2
            else:
                colors[tv] = colors[frm]
            dfs(n, tv)

colors[0] = 0
dfs(0, 0)
for item in colors:
    print(item)

Submission status: Wrong Answer

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N = INT()
uvw = [LIST() for _ in range(N-1)]
uvw.sort(key=lambda x:(x[0], x[1]))
# print(uvw)
uvw_ = [0]*(N-1)
index = 0
looked = [0]*N
looked[0] = 1
for u, v, w in uvw:
	if looked[u-1] == 0 and looked[v-1] == 0:
		uvw_[-1] = [u, v, w]
	else:
		uvw_[index] = [u, v, w]
		looked[u-1] = 1
		looked[v-1] = 1 
		index += 1
# print(uvw_)
color = [0]*N  # -1で白 1で黒を表す
searched = [0]*N  # 探索した場所に1をいれる
color[0] = -1  # 0番目のノードを白で初期化
searched[0] = 1  # 0 番目のノードは探索済み
for u, v, w in uvw:
	if searched[v-1] == 1:
		u, v = v, u
	if w % 2 == 0:
		color[v-1] = color[u-1]
		searched[v-1] = 1
	else:
		color[v-1] = color[u-1] * (-1)
		searched[v-1] = 1
	# print(searched)
# print(color)
for i in color:
	if i == -1:
		print('0')
	else:
		print('1')

Submission status: Wrong Answer

Solution code:
N=int(input())
a=[]
dic_num={}
dic_dis = [[0 for i in range(N)] for j in range(N)]
for i in range(N-1):
    u,v,w=map(int,input().split())
    dic_num.setdefault(u,[]).append(v)
    dic_num.setdefault(v,[]).append(u)
    dic_dis[u-1][v-1]=w
    dic_dis[v-1][u-1]=w
    a.append([u,v,w])
check=[0]*N
stack=[1]
ans=[0]*N
while len(stack)!=0:
    point=stack.pop(0)
    if  point==1:
        ans[0]=1
    else:
        if dic_dis[point-1][before_point-1]%2==0:
            ans[point-1]=1
    before_point=point
    check[point-1]=1
    next_points=[]
    for next_p in dic_num[point]:
        if check[next_p-1]==0:
            next_points.append(next_p)
    stack.extend(next_points)
for i in range(N):
    print(ans[i])

Submission status: Wrong Answer

Solution code:
N = int(input())

A = [2 for i in range(N)]
L = []
for i in range(N-1) :
    u,v,w = map(int,input().split())
    u -= 1
    v -= 1
    if u < v :
        u,v = v,u
    L.append([u,v,w])
L = sorted(L,key=lambda x :x[0])

for i in range(len(L)) :
    u,v,w = L[i]
    if A[u] == A[v] == 2 :
        if w % 2 == 0 :
            A[u] = A[v] = 0
        else :
            A[u] = 0
            A[v] = 1
    elif A[u] != 2 :
        if w % 2 == 0 :
            A[v] = A[u]
        else :
            A[v] = (A[u] + 1) % 2
    elif A[v] != 2 :
        if w % 2 == 0 :
            A[u] = A[v]
        else :
            A[u] = (A[v] + 1) % 2
print(*A,sep="\n")

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
class WeightedUnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n+1)]
        self.rank = [0] * (n+1)
        # 根への距離を管理
        self.weight = [0] * (n+1)

    # 検索
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            y = self.find(self.par[x])
            # 親への重みを追加しながら根まで走査
            self.weight[x] += self.weight[self.par[x]]
            self.par[x] = y
            return y

    # 併合
    def union(self, x, y, w):
        rx = self.find(x)
        ry = self.find(y)
        # xの木の高さ < yの木の高さ
        if self.rank[rx] < self.rank[ry]:
            self.par[rx] = ry
            self.weight[rx] = w - self.weight[x] + self.weight[y]
        # xの木の高さ ≧ yの木の高さ
        else:
            self.par[ry] = rx
            self.weight[ry] = -w - self.weight[y] + self.weight[x]
            # 木の高さが同じだった場合の処理
            if self.rank[rx] == self.rank[ry]:
                self.rank[rx] += 1

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

    # xからyへのコスト
    def diff(self, x, y):
        return self.weight[x] - self.weight[y]

n=int(input())
u=WeightedUnionFind(n)
for i in range(n-1):
    x,y,z=map(int,input().split())
    u.union(x,y,z)

ans=[0]
for i in range(2,n+1):
    
    if u.diff(u.find(1),i)%2==0:
        ans.append(0)
    else:
        ans.append(1)
for x in ans:
    print(x)

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

# tree = {2: [{'to': 5, 'w': 3}, {'to': 3, 'w': 10}], 5: [{'to': 2, 'w': 3}, {'to': 6, 'w': 2}], 6: [{'to': 5, 'w': 2}], 3: [{'to': 2, 'w': 10}, {'to': 1, 'w': 3}, {'to': 4, 'w': 3}], 1: [{'to': 3, 'w': 3}], 4: [{'to': 3, 'w': 3}]}
result = [-1] * N

def reverse(i):
	if i == 0:
		return 1
	if i == 1:
		return 0

for n in range(1, N + 1):
	for leaf in tree[n]:
		if leaf['w'] % 2 != 0:
			if result[n - 1] == -1:
				result[n - 1] = 0

			result[leaf['to'] - 1] = reverse(result[n - 1])

		if leaf['w'] % 2 == 0:
			result[leaf['to'] - 1] = result[n - 1]

for r in result:
	print(r)

Submission status: Wrong Answer

Solution code:
N = int(input())
u = [[] for _ in range(N-1)]
v = [[] for _ in range(N-1)]
w = [[] for _ in range(N-1)]
s = [[] for _ in range(N)]

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

frag = True
while frag is True:
    s_tmp = s
    for i in range(N-1):
        if w[i]%2 == 0:
            s[u[i]-1] = 0
            s[v[i]-1] = 0
        else:
            s[u[i]-1] = 0
            s[v[i]-1] = 1
    if s == s_tmp:
        frag = False
        
for i in range(len(s)):
    print(s[i])

Submission status: Wrong Answer

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

edge.sort(key=lambda x: x[1])
edge.sort(key=lambda x: x[0])
l[edge[0][0] - 1] = 0

for i in range(n - 1):
    if l[edge[i][0] - 1] == -1:
        if l[edge[i][1] - 1] == -1:
            l[edge[i][0] - 1] = 0
            if edge[i][2] % 2 == 1:
                l[edge[i][1] - 1] = 1 - l[edge[i][0] - 1]
        else:
            if edge[i][2] % 2 == 1:
                l[edge[i][0] - 1] = 1 - l[edge[i][1] - 1]
    else:
        if l[edge[i][1] - 1] == -1:
            if edge[i][2] % 2 == 1:
                l[edge[i][1] - 1] = 1 - l[edge[i][0] - 1]

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

import operator

N = int(input())
uvw = []
for i in range(N - 1):
    (u, v, w) = tuple(map(int, input().split(' ')))
    if u < v:
        uvw.append((u, v, w))
    else:
        uvw.append((v, u, w))

a = [-1] * N
for (u, v, w) in sorted(uvw, key=operator.itemgetter(0)):
    print('{} {} {}'.format(u, v, w))
    if w % 2 == 1:
        if a[u - 1] == -1 and a[v - 1] == -1:
            a[u - 1] = 0
            a[v - 1] = 1
        elif a[u - 1] == -1:
            a[u - 1] = 1 - a[v - 1]
        elif a[v - 1] == -1:
            a[v - 1] = 1 - a[u - 1]

for i in a:
    if i < 0:
        print(0)
    else:
        print(i)

Submission status: Wrong Answer

Solution code:
N = int(input(""))

vertex = [list() for i in range(N)]

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

colors = [-1]*N
for idx, v in enumerate(vertex):
    v.sort()

    # already has color
    if colors[idx] != -1:
        for u in v:
            colors[u] = 0 if colors[idx] == 1 else 1
    # if no color
    else:
        if len(v) == 0:
            colors[idx] = 0
        else:
            flag = 0
            for u in v:
                if colors[u] != -1:
                    colors[idx] = 0 if colors[u] == 1 else 0
                    flag = 1
                    break
            if flag == 0:
                colors[idx] = 0
            for u in v:
                colors[u] = 0 if colors[idx] == 1 else 1

for c in colors:
    print(c)

Submission status: Wrong Answer

Solution code:
N = int(input())
u = [0]*N
v = [0]*N
w = [0]*N
for n in range(N-1):
    u[n], v[n], w[n] = map(int, input().split())
color = [0]*N
color[0] = 1
x = 0
next_x =[]
position = [0]*N
while position == [1]*N:
    for n in range(N):
        if u[n] == x and position[n] == 0:
            if w[n]//2 == 0:
                color[v[n]] = color[x]
            next_x.append(v[n])
        if v[n] == x and position[n] == 0:
            if w[n]//2 == 0:
                color[u[n]] = color[x]
            next_x.append(u[n])
    x = next_x.pop(-1)
    continue

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

Submission status: Wrong Answer

Solution code:
n=int(input())
l=[list(map(int,input().split())) for i in range(n-1)]
ans=[-1]*(n+1)
for i in range(n-1):
    if l[i][2]%2==0:
        ans[l[i][1]]=ans[l[i][0]]
    else:
        ans[l[i][1]]=(-1)*ans[l[i][0]]
for k in range(1,n+1):
    if ans[k]==-1:
        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)]
for i in range(N - 1):
    UVW[i].append(i)

UVW.sort(key=lambda x: x[0])

ans = [0] * (N + 1)
for uvw in UVW:
    u, v, w, z = uvw
    if w % 2 == 1:
        if ans[u] == ans[v]:
            if ans[v] == 1:
                ans[v] = 0
            else:
                ans[v] = 1
UVW.sort(key=lambda x: x[3])

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

Submission status: Wrong Answer

Solution code:
from collections import deque

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

adj = [[] for _ in range(N+1)]
for b in branch:
  adj[b[0]].append([b[1],b[2]])
  adj[b[1]].append([b[0],b[2]])

ans = [-1] * (N+1)
deq = deque()
deq.appendleft(1)
while len(deq) > 0:
  v = deq.pop()
  for u, w in adj[v]:
    if ans[u] == -1:
      deq.appendleft(u)
    if ans[v] == -1 and ans[u] == -1:
      if w % 2 == 0:
        ans[v] = 0
        ans[u] = 0
      else:
        ans[v] = 0
        ans[u] = 1
    elif ans[v] == 0:
      if w % 2 == 0:
        ans[u] = 0
      else:
        ans[u] = 1
    else:
      if w % 2 == 0:
        ans[u] = 1
      else:
        ans[u] = 0
print(ans[1:])

Submission status: Wrong Answer

Solution code:
import random
n = int(input())
listA = []
listB = []
listN=[]
stockL=[]
index=0
while index < n-1:
    u, v, w = map(int, input().split())
    if w == 1:
        listA.append(u)
        listB.append(v)
        listN.append(u)
        listN.append(v)
    else:
        stockL.append([u, v])
    index+=1

flag=1
while flag:
    flag=0
    index=0
    while index < len(stockL):
        u = stockL[index][0]
        v = stockL[index][1]
        if u in listA:
            if v in listA:
                flag=1
                vI = listA.index(v)
                uI = listA.index(u)
                if random.random() > 0.5:
                    listA[vI], listB[vI] = listB[vI], listA[vI]
                else:
                    listA[uI], listB[uI] = listB[uI], listA[uI]
            else:
                if v in listB:
                    pass
                else:
                    listA.append(u)
                    listB.append(v)
        elif u in listB:
            if v in listB:
                flag=1
                vI = listB.index(v)
                uI = listB.index(u)
                if random.random() > 0.5:
                    listA[vI], listB[vI] = listB[vI], listA[vI]
                else:
                    listA[uI], listB[uI] = listB[uI], listA[uI]
            else:
                if v in listA:
                    pass
                else:
                    listB.append(v)
                    listB.append(u)
        else:
            if v in listB:
                listB.append(u)
                listB.append(v)
            elif v in listA:
                listA.append(v)
                listA.append(u)
            else:
                pass
        index+=1
index2=1
while index2 < n+1:
    if index2 in listA:
        print(0)
    elif index2 in listB:
        print(1)
    else:
        print(0)
    index2+=1

Submission status: Wrong Answer

Solution code:
n = int(input())

color = [0] * (n+1)

for i in range(n-1):
  u, v, w = map(int,input().split())
  if w % 2 == 0 and color[u] != color[v]:
    color[v] = color[u]
  elif w % 2 == 1 and color[u] == color[v]:
    color[v] = (color[u] + 1) % 2

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

Submission status: Wrong Answer

Solution code:
N = int(input())

tree = [list() for _ in range(N)]
color = [-1 for _ in range(N)]
color[0] = 0

for _ in range(N-1):
    u, v, w = map(int, input().strip().split(' '))
    tree[u-1] += [v-1]
    tree[v-1] += [u-1]


stack = [0]
while len(stack) > 0:
    pos = stack.pop()
    for p in tree[pos]:
        if color[p] == -1:
            color[p] = color[pos] ^ 1
            stack.append(p)

for c in color:
    print(c)

Submission status: Wrong Answer

Solution code:
import numpy as np
N = int(input())
datalist = []
for i in range(N-1):
    data = tuple(map(int,input().split()))
    datalist.append(data)
print(datalist)
colorlist = np.array([True for _ in range(N+1)])

for data in datalist:
    if data[2]%2 != 0:
        colorlist[data[1]] = not colorlist[data[0]]

for a in colorlist.astype(np.int)[1:]:
    print(a)

Submission status: Wrong Answer

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

for i in ans:
    print(i)

Submission status: Wrong Answer

Solution code:
n = int(input().strip())

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

for i in range(n-1):
	u, v, w = map(int, input().strip().split())
	if w % 2:
		# if odd, different color is mandatory
		if color[u] == -1 and color[v] == -1:
			color[u] = 0
			color[v] = 1
		elif color[u] == -1:
			color[u] = 1-color[v]
		elif color[v] == -1:
			color[v] = 1-color[u]
		else:
			if color[u] == color[v]:
				color[u] = 1-color[v]		

print('\n'.join(['0' if i == -1 else str(i) for i in color[1:]]))

Submission status: Wrong Answer

Solution code:
import sys
from operator import itemgetter

stdin = sys.stdin

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

n = ni()
uvw = list()

ans = ["0"] * n
for i in range(n-1):
    u_i, v_i, w_i = na()

    uvw.append([u_i, v_i, w_i])
    
uvw.sort(key=itemgetter(0))

for i in range(n-1):
    if int(uvw[i][2]) % 2 != 0:
        if ans[int(uvw[i][0])-1] == "0":
            ans[int(uvw[i][1])-1] = "1"
        else:
            ans[int(uvw[i][1])-1] = "0"
for i in ans:
    print(i)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

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

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

for u, v, w in edge:
    u -= 1; v -= 1
    ad[u].append((v,w))
    ad[v].append((u,w))

ans = [0]*N

def dfs(v=0,pre=-1):
    for nv,w in ad[v]:
        if nv != pre:
            if w % 2 == 1:
                ans[nv] = 1
            dfs(nv,v)

dfs()

for a in ans:
    print(a)

Submission status: Wrong Answer

Solution code:
n=int(input())
vertex=[i for i in range(n)]
uvw=[]
u,v,w=0,1,2
for i in range(n-1):
    ui,vi,wi=[int(x) for x in input().split()]
    uvw.append((ui-1,vi-1,wi))
uvw=sorted(uvw,key=lambda x :x[0])
# print(uvw)
for i in range(n-1):
    if uvw[i][w]%2==0:
        minNum=min(vertex[uvw[i][u]],vertex[uvw[i][v]])
        (vertex[uvw[i][u]],vertex[uvw[i][v]])=(minNum,minNum)
def find_root(k):
    if k==vertex[k]:
        return k
    else:
        return find_root(vertex[k])
for i in range(n):
    vertex[i]=find_root(i)
# print(vertex)
ans=[0]*n
for i in range(n-1):
    if uvw[i][w]%2==1:
        ans[max(vertex[uvw[i][u]],vertex[uvw[i][v]])]=ans[min(vertex[uvw[i][u]],vertex[uvw[i][v]])]^1
for i in range(n):
    print(ans[vertex[i]])

Submission status: Wrong Answer

Solution code:
N = int(input())
u = []
v = []
w = []

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

s = '\n'.join(l)
print(s)

Submission status: Wrong Answer

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

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

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

Submission status: Wrong Answer

Solution code:
N=int(input())

diff_dic = {}
for i in range(N-1):
  ui,vi,wi=map(int,input().split())
  if wi%2 == 1:
    if ui not in diff_dic:
      diff_dic[ui] = [vi]
    else:
      diff_dic[ui].append(vi)

paint_list = [0]*N
for ui,vlist in sorted(diff_dic.items()):
  for vi in vlist:
    paint_list[vi-1] = (paint_list[ui-1]+1)%2
    
for i in paint_list:
  print(i)

Submission status: Wrong Answer

Solution code:
#D問題
N=int(input())
UVW=[]
B=[]
W=[]
for i in range(N-1):
    u,v,w = map(int,input().split())
    UVW.append([u,v,w])
    
UVW.sort()
for i in range(N-1):
    u=UVW[i][0]
    v=UVW[i][1]
    w=UVW[i][2]
    if w%2 == 0:
        if u in B:
            B.append(v)
        elif u in W:
            W.append(v)
        elif v in B:
            B.append(u)
        elif v in W:
            W.append(u)
        else:
            B.append(u)
            B.append(v)
    else:
        if u in B:
            W.append(v)
        elif u in W:
            B.append(v)
        elif v in B:
            W.append(u)
        elif v in W:
            B.append(u)
        else:
            B.append(u)
            W.append(v)

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

Submission status: Wrong Answer

Solution code:
n = int(input())
edges = [list(map(int, input().split())) for _ in range(n - 1)]
even_edges = [e for e in edges if e[2] % 2 == 0]
odd_edges = [e for e in edges if e[2] % 2 == 1]

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

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

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

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

	def diff(self, x, y):
		return self.weight[x] - self.weight[y]

uf = WeightedUnionFind(n)

for e in even_edges:
	uf.union(e[0], e[1], 0)

for e in odd_edges:
	uf.union(e[0], e[1], 1)

print(0)
for i in range(2, n + 1):
	if uf.diff(1, i) % 2 == 0:
		print(0)
	else:
		print(1)

Submission status: Wrong Answer

Solution code:
n = int(input())
s = []
t = []
for _ in range(n-1):
    u, v, w = map(int, input().split(' '))
    r1 = (u in s) and (not u in t)
    r2 = (not u in s) and (u in t)
    r3 = (not u in s) and (not u in t)
    r4 = (v in s) and (not v in t)
    r5 = (not v in s) and (v in t)
    r6 = (not v in s) and (not v in t)
    r7 = w % 2 == 0
    if r7:
        if r3 and r6:
            s += [u, v]
        elif r3 and r4:
            s += [u]
        elif r3 and r5:
            t += [u]
        elif r6 and r1:
            s += [v]
        elif r6 and r2:
            t += [v]
    else:
        if r3 and r6:
            s += [u]
            t += [v]
        elif r3 and r4:
            t += [u]
        elif r3 and r5:
            s += [u]
        elif r6 and r1:
            t += [v]
        elif r6 and r2:
            s += [v]

result = [0] * n

for i in t:
    result[i-1] = 1        
for j in result:
    print(j)

Submission status: Wrong Answer

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

N = int(input())
S = [input().split() for _ in range(N-1)]

color = [0 for _ in range(N)]

for n in range(1,N):
    for i in range(len(S)):
        if int(S[i][0]) == n:
            if int(S[i][2]) % 2 == 1:
                if color[int(S[i][0])-1] == 1:
                    color[int(S[i][1])-1] = 0
                else:
                    color[int(S[i][1])-1] = 1
            else:
                if color[int(S[i][0])-1] == 1:
                    color[int(S[i][1])-1] = 1
                else:
                    color[int(S[i][1])-1] = 0

for i in color:
    print(i)

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()
white = []
black = []

for _ in range(N-1):
  u, v, w = mi()
  if w % 2 == 0:
    if u in white:
        if v not in white:
            white.append(v)
    elif u in black:
        if v not in black:
            black.append(v)
    else:
        if v in white:
            white.append(u)
        elif v in black:
            black.append(u)
        else:
            white += [u,v]
  else:
        if u in white:
            if v not in black:
                black.append(v)
        elif u in black:
            if v not in white:
                white.append(v)
        else:
            if v in white:
                black.append(u)
            elif v in black:
                white.append(u)
            else:
                white.append(u)
                black.append(v)

for i in range(1, N+1):
    if i in black:
        print(1)
    else:
        print(0)

Submission status: Wrong Answer

Solution code:
N = int(raw_input().strip())

ans = [0 for x in range(N)]
arr = []
for i in range(N-1):
    d = map(int, raw_input().strip().split())
    arr.append(d)

for item in arr:
    a, b, c = item
    if c % 2 == 1:
        if ans[a-1] == ans[b-1]:
            ans[b-1] = 1

for item in arr:
    a, b, c = item
    if c % 2 == 0:
        if ans[a-1] != ans[b-1]:
            ans[a-1] = ans[b-1] = 1

for i in ans:
    print(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
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

for i in range(1, N+1):
    if not went[i]:
        went[i] = True
        f(i)

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

Submission status: Wrong Answer

Solution code:
# def gcd(a_gcd, b_gcd):
#     while b_gcd != 0:
#         a_gcd, b_gcd = b_gcd, a_gcd % b_gcd
#     return a_gcd
#
#
# def lcm(a_lcm, b_lcm):
#     return a_lcm * b // gcd(a_lcm, b_lcm)
#
#
# def max_sum(N_max_sum, a_max_sum):
#     dp = [0] * (N_max_sum + 1)
#     for i in range(N_max_sum):
#         dp[i + 1] = max(dp[i], dp[i] + a_max_sum[i])
#     return dp[N]
#
#
# def knapsack(N_knapsack, W, weight, value):
#     inf = float("inf")
#     dp = [[-inf for _ in range(W+1)] for j in range(N_knapsack + 1)]
#     for i in range(W+1):
#         dp[0][i] = 0
#
#     for i in range(N_knapsack):
#         for w in range(W+1):
#             if weight[i] <= w:
#                 dp[i+1][w] = max(dp[i][w-weight[i]]+value[i], dp[i][w])
#             else:
#                 dp[i+1][w] = dp[i][w]
#     return dp[N_knapsack][W]


# import math
#
# # n = int(input())
# N, K = map(int, input().split())
#
# sum = [0 for _ in range(math.ceil(math.log(K, 2)) + 1)]
#
#
# for i in range(N, 0, -1):
#     for j in range(len(sum)):
#         if K <= i * pow(2, j):
#             sum[j] += 1
#             break
#
# ans = 0
#
# for i in range(len(sum)):
#     # print(pow(2, i))
#     # print(sum[i])
#     ans += sum[i] / (pow(2, i) * N)
#
# print(ans)


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)


N = int(input())
U = []
V = []
W = []

for _ in range(N-1):
    u, v, w = map(int, input().split())
    U.append(u)
    V.append(v)
    W.append(w)


node_list = UnionFind(N)

for i in range(N - 1):
    if (W[i] % 2) == 0:
        node_list.union(U[i], V[i])

zero = node_list.find(0)

for i in range(N):
    if zero == node_list.find(i):
        print(0)
    else:
        print(1)