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:
# -*- 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)
	UF2 = 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)
		else:
			UF2.union(a, b)

	ans = []
	for i in range(N):
		if i == 0:
			ans.append(0)
			continue

		tmp = UF.find(i)
		flg = UF.is_same(0, tmp)

		if flg == True:
			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:
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]==8):
            ans[v[i]-1] = 9
        elif(ans[u[i]-1]==9):
            ans[v[i]-1] = 8
        elif(ans[v[i]-1]==8):
            ans[u[i]-1] = 9
        elif (ans[v[i]-1]==9):
            ans[u[i]-1] = 8
        else:
            ans[u[i]-1] = 8
            ans[v[i]-1] = 9
    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())
w=0
b=0
for i in range(N-1):
  u=list(map(int,input().split()))
  d = u[2] + w
  if d%2==0:
    print('0')
    w+=d
    b=0
  else:
    print('1')
    b+=d
    w=0
print('1')

Submission status: Wrong Answer

Solution code:
class Kumiwake(object):
    def __init__(self):
        self.A = []
        self.B = []
    def __call__(self, a, b):
        if a in self.A:
            if b in self.B:
                pass
            elif b in self.A:
                print('ERROR')
            else:
                self.B.append(b)
        elif a in self.B:
            if b in self.B:
                print('ERROR')
            elif b in self.A:
                pass
            else:
                self.A.append(b)
        else:
            if b in self.B:
                self.A.append(a)
            elif b in self.A:
                self.B.append(a)
            else:
                self.A.append(a)
                self.B.append(b)
        return

N = int(input())
kumi = Kumiwake()
for _ in range(N-1):
    u, v, w = list(map(int, input().split()))
    if w%2 == 1:
        kumi(u, w)

for n in range(1, N+1):
    if n in kumi.A:
        print(0)
    elif n in kumi.B:
        print(1)
    else:
        print(1)

Submission status: Wrong Answer

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

n = int(input())
uvw = []
e = {}
for i in range(n-1):
    x = input().split()
    uvw.append([int(x[0])-1, int(x[1])-1, int(x[2])%2])
    e[i] = []
e[n-1] = []

w_mat = [[0 for i in range(n)] for j in range(n)]
for u,v,w in uvw:
    e[u].append(v)
    e[v].append(u)
    w_mat[u][v] = w
    w_mat[v][u] = w

res = [0]*n
def f(idx, pre_idx):
    if w_mat[idx][pre_idx]:
        res[idx] = int(not res[pre_idx])
    for i in e[idx]:
        if i != pre_idx:
            f(i, idx)

f(0,0)

for x in res:
    print(x)

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())
k = WeightedUnionFind(n)
for i in range(n - 1):
    u, v, w = map(int, input().split())
    k.union(u, v, w)
for i in range(1, n+1):
    print(k.diff(1, i) % 2)

Submission status: Wrong Answer

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

for e in edge:
    print(e)

ans = [0]* N
for e in edge:
    u,v,w = e
    # 長さが奇数の場合、頂点の白黒を分ける
    if w %2 == 1:
        ans[v-1] = int(not ans[u-1])
    else:
        ans[v-1] = ans[u-1]
print(ans)

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 c % 2 == 0:
            ans[i] = ans[before]
        else:
            ans[i] = 1 - ans[before]
        if not went[i]:
            went[i] = True
            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())
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]]
print(ans[1:])
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())

colors = [False] * N

class Edge:

    def __init__(self,base,to,weight):
        self.base = base
        self.to = to
        self.weight = weight
        self.is_used = False


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

edges = sorted(edges,key=lambda e: (e.base,e.to))

for e in edges:
    if e.weight %2 != 0:
        colors[e.to - 1] = not colors[e.base - 1]

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

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:
		continue

	if colors[u-1]==-1 and colors[v-1]==-1:
		colors[u-1]=0
	elif colors[u-1]==-1 and 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:
class UnionFind():
    # 作りたい要素数nで初期化
    # 使用するインスタンス変数の初期化
    def __init__(self, n):
        self.n = n
        # root[x]<0ならそのノードが根かつその値が木の要素数
        # rootノードでその木の要素数を記録する
        self.root = [-1]*(n+1)
        # 木をくっつける時にアンバランスにならないように調整する
        self.rnk = [0]*(n+1)

    # ノードxのrootノードを見つける
    def Find_Root(self, x):
        if(self.root[x] < 0):
            return x
        else:
            # ここで代入しておくことで、後の繰り返しを避ける
            self.root[x] = self.Find_Root(self.root[x])
            return self.root[x]
    # 木の併合、入力は併合したい各ノード
    def Unite(self, x, y):
        # 入力ノードのrootノードを見つける
        x = self.Find_Root(x)
        y = self.Find_Root(y)
        # すでに同じ木に属していた場合
        if(x == y):
            return 
        # 違う木に属していた場合rnkを見てくっつける方を決める
        elif(self.rnk[x] > self.rnk[y]):
            self.root[x] += self.root[y]
            self.root[y] = x

        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            # rnkが同じ（深さに差がない場合）は1増やす
            if(self.rnk[x] == self.rnk[y]):
                self.rnk[y] += 1
    # xとyが同じグループに属するか判断
    def isSameGroup(self, x, y):
        return self.Find_Root(x) == self.Find_Root(y)

    # ノードxが属する木のサイズを返す
    def Count(self, x):
        return -self.root[self.Find_Root(x)]
n = int(input())
uf = UnionFind(n)
for i in range(n-1):
    u,v,w = map(int,input().split())
    if w%2==0:
        uf.Unite(u-1,v-1)

rl = []
for i in range(n):
    rl.append(uf.Find_Root(i))

# print(uf.root)

st = list(set(rl))
# print(rl)

for i in range(n):
    if rl[i] == st[0]:
        print(0)
    else:
        print(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:
            continue
        color[p] = color[pos] ^ 1
        stack.append(p)

for c in color:
    print(c)

Submission status: Wrong Answer

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

for i in res:
    print(i)

Submission status: Wrong Answer

Solution code:
N=int(input())
a = [0]*N
b = [0]*N
u1,v1,w1 = [int(j) for j in input().split()]
b[u1-1] = 1
b[v1-1] = 1
if w1%2 == 0:
    a[u1-1] = 1
    a[v1-1] = 1
else:
    a[u1-1] = 1

for i in range(N-2):
    u,v,w = [int(j) for j in input().split()]
    if w % 2 == 0:
        if max(a[u-1],a[v-1]) ==1:
            a[u-1] = 1
            a[v-1] = 1
    else:
        if b[u-1] == 1:
            a[v-1] = 1-a[u-1]
        elif b[v-1] == 1:
            a[u-1] = 1 - a[v-1]
        else:
            a[u-1] = 1
    b[u-1] = 1
    b[v-1] = 1

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

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

Submission status: Wrong Answer

Solution code:
class UnionFind(object):
    def __init__(self, n=1):
        self.par = [i for i in range(n)]
        self.rank = [0 for _ in range(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]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x != y:
            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

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

def solve():
  n = int(input())
  
  uf = UnionFind(n)
  ans = [0]*n
  tmp = []
  for i in range(n-1):
    x,y,z = (int(i) for i in input().split())
    if z%2 == 1:
      tmp.append((x,y,z))
    else:
     uf.union(x-1,y-1)
     ans[x-1] = 1
     ans[y-1] = 1
  while tmp:
    x,y,z = tmp.pop(0)
    
  
  for i in ans:
    print(i)
     
     
  
solve()

Submission status: Wrong Answer

Solution code:
N = int(input())
color_list = [-1] * N

def color_det(u, v, flag_same):
    if u == -1:
        if flag_same == True:
            u = v
        else:
            u = 1 - v
    else:
        if flag_same == True:
            v = u
        else:
            v = 1 - u
    
    return u, v

for n in range(N - 1):
    u, v, w = map(int, input().split())
    u -= 1
    v -= 1
    w %= 2
    
    if n == 0:
        if w == 0:
            color_list[u] = 0
            color_list[v] = 0
        else:
            color_list[u] = 0
            color_list[v] = 1
    else:
        if w == 0:
            color_list[u], color_list[v] = color_det(color_list[u], color_list[v], True)
        else:
            color_list[u], color_list[v] = color_det(color_list[u], color_list[v], False)

for c in color_list:
    print(c)

Submission status: Wrong Answer

Solution code:
N = int(input())
uvw = [tuple(input().split()) for i in range(N-1)]
ans = []
for i in range(N):
  ans.append('0')
cnt = 0
for u, v, w in uvw:
  if(cnt == 0):
    cnt = 1
    ans[int(u)-1] = '1'
    if(int(w) % 2 == 0):
      ans[int(v)-1] = '1'
  else:
    if(ans[int(u)-1] == '1' or ans[int(v)-1] == '1'):
      if(int(w) % 2 == 0):
        ans[int(u)-1] = '1'
        ans[int(v)-1] = '1'
for i in range(N):
  print(ans[i])

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:
        if a[u-1] == 0:
            a[v-1] = 1
        elif a[u-1] == 1:
            a[v-1] = 0

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

Submission status: Wrong Answer

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

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

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

for i in range(len(S)):
    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:
#!python3
import sys

def main():
    n = int(input())
    es = [list(map(int, input().split())) for i in range(n-1)]

    sd = dict()
    dd = dict()

    noe = 0
    for e in es:
        e0, e1 = e[0] - 1, e[1] - 1

        if e0 < e1:
            if e[2] % 2 == 0:
                if sd.get(e0) is None:
                    sd[e0] = [e1]
                else:
                    sd[e0].append(e1)
            else:
                if dd.get(e0) is None:
                    dd[e0] = [e1]
                else:
                    dd[e0].append(e1)
            if e1 > noe:
                noe = e1

        else:
            if e[2] % 2 == 0:
                if sd.get(e1) is None:
                    sd[e1] = [e0]
                else:
                    sd[e1].append(e0)
            else:
                if dd.get(e1) is None:
                    dd[e1] = [e0]
                else:
                    dd[e1].append(e0)
            if e0 > noe:
                noe = e0

    rs = [None] * (noe + 1)
    rs[0] = 0

    def rec(tc, i):
        if sd.get(i):
            for j in sd[i]:
                rs[j] = tc
                rec(tc, j)

        if dd.get(i):
            if tc == 0:
                nc = 1
            else:
                nc = 0
            for j in dd[i]:
                rs[j] = nc
                rec(nc, j)

    for i in range(noe):
        rec(rs[i], i)

        if not None in rs:
            break
    
    for cl in rs:
        if cl:
            print(0)
        else:
            print(1)

if __name__ == '__main__':
    main()

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(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())
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 l[i] == "s":
                l[i]=m%2
                if l[i+1]=="s":
                        m+=1
                        

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

Submission status: Wrong Answer

Solution code:
N = int(input())-1
vw = [list(map(int, input().split())) for _ in range(N)]
vw.sort(key=lambda x:x[0])
ret = [0] * (N+1)
ret[0] = 1
for i in range(N):
    if vw[i][2] % 2 == 0:
        ret[vw[i][1]-1] = ret[vw[i][0]-1]
    else:
        ret[vw[i][1]-1] = ret[vw[i][0]-1] ^ 1

for i in ret:
    print(i)

Submission status: Wrong Answer

Solution code:
from collections import deque

N = int(input())

leave = deque()
for _ in range(N-1):
    u, v, w = map(int, input().split())
    if divmod(w, 2)[1] == 0:
        continue
    leave.append((u, v, w))

white = []
black = []

length = len(leave)
flag = False
while length > 0:
    tmp = deque()
    while leave:
        u, v, w = leave.popleft()
        if u in white:
            black.append(v)
            continue
        if u in black:
            white.append(v)
            continue
        if v in white:
            black.append(u)
            continue
        if v in black:
            white.append(u)
            continue
        if flag:
            flag = False
            white.append(u)
            black.append(v)
            continue
        tmp.append((u, v, w))
    leave = tmp
    if length == len(leave):
        flag = True
    length = len(leave)

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

Submission status: Wrong Answer

Solution code:

def main():
	n = int(input())
	mem = [[]]*n
	ans = [0]*n
	ans[0] = 1
	for _ in range(n-1):
		u, v, w = map(int, input().split())
		u -= 1
		v -= 1
		if w % 2 == 0:
			mem = mem[:u] + [mem[u]+[[v, True]]] + mem[u+1:]
		else:
			mem = mem[:u] + [mem[u]+[[v, False]]] + mem[u+1:]
	for i in range(n):
		for j in mem[i]:
			if ans[j[0]] == 0:
				if j[1]:
					ans[j[0]] = ans[i]
				else:
					ans[j[0]] = ans[i]*(-1)
	for i in range(n):
		print(0 if ans[i] == -1 else 1)
main()

Submission status: Wrong Answer

Solution code:
n = int(input())
tree = [None]*n
for i in range(n-1):
     a = list(map(int,input().split()))
     if a[2]%2 == 1:
          if tree[a[0]-1] == None:
               tree[a[0]-1] = [a[1]-1]
          else:
               tree[a[0]-1].append(a[1]-1)
          if tree[a[1]-1] == None:
               tree[a[1]-1] = [a[0]-1]
          else:
               tree[a[1]-1].append(a[0]-1)

ans = ["#"]*n

for i in range(n):
     if tree[i] != None:
          if ans[i]=="#":
               ans[i] = 0
          for j in tree[i]:
               if ans[j] == "#":
                    ans[j] = (ans[i]+1)%2

for i in range(n):
     if ans[i] == "#":
          print(0)
     else:
          print(ans[i])

Submission status: Wrong Answer

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

class UnionFind:
    def __init__(self, nn):
        self.par = [i for i in range(nn+1)]
        self.rank = [0] * (nn+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)

tree = UnionFind(n)
for i in range(n-1):
    u = a[i][0]
    v = a[i][1]
    w = a[i][2]
    if w % 2 == 0:
        tree.union(u, v)

counter = []
for i in range(1, n+1):
    counter.append(tree.find(i))

counter1 = list(set(counter))
for i in range(n):
    if counter[i] == counter1[0]:
        print('0')
    else:
        print('1')

Submission status: Wrong Answer

Solution code:
n = int(input())

u = [0] * (n-1)
v = [0] * (n-1)
w = [0] * (n-1)

node = [i for i in range(n)]

group1 = []
group2 = []

for i in range(n-1):
    u[i], v[i], w[i] = map(int, input().split())
    u[i] -= 1
    v[i] -= 1
    w[i] = w[i] % 2
    # 同じなら0、違ったら1
    if w[i] == 0:
        if node[u[i]] == u[i]:
            node[u[i]] = node[v[i]]
        elif node[u[i]] != u[i]:
            node[v[i]] = node[u[i]]

for i in range(n-1):
    if w[i] == 1:
        if u[i] in group1:
            group2.append(node[v[i]])
        elif u[i] in group2:
            group1.append(node[v[i]])
        elif v[i] in group1:
            group2.append(node[u[i]])
        elif v[i] in group2:
            group1.append(node[u[i]])
        else:
            group1.append(node[v[i]])
            group2.append(node[u[i]])

for i in range(n):
    if node[i] in group1:
        node[i] = 0
    else:
        node[i] = 1

for color in node:
    print(color)

Submission status: Wrong Answer

Solution code:
N = int(input())

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

for e in edge:
    if e[2]%2 == 1 and node[e[0]-1] == node[e[1]-1]:
        node[e[1]-1] = 1

print("\n".join(map(str, node)))

Submission status: Wrong Answer

Solution code:
def d_even_relation(N, Nodes):
    from collections import deque
    graph = [{} for _ in range(N)]
    for u, v, w in Nodes:
        graph[u - 1][v - 1] = w

    ans = [0] * N
    queue = deque([(-1, 0)])
    previous = -1
    while queue:
        parent, child = queue.pop()
        if parent == -1:
            ans[child] = 0
        else:
            length = graph[parent][child]
            if length % 2 == 0:
                ans[child] = ans[parent]
            else:
                ans[child] = 1 if ans[parent] == 0 else 0
        for k in graph[child].keys():
            if not previous == k:
                queue.appendleft((child, k))
        previous = parent
    return '\n'.join(map(str, ans))

N = int(input())
Nodes = [[int(i) for i in input().split()] for j in range(N - 1)]
print(d_even_relation(N, Nodes))

Submission status: Wrong Answer

Solution code:
import numpy as np


def read():
    N = int(input().strip())
    u = np.empty((N-1, ), dtype=np.int32)
    v = np.empty((N-1, ), dtype=np.int32)
    w = np.empty((N-1, ), dtype=np.int32)
    for i in range(N-1):
        # u[i] < v[i] は保証されている
        u[i], v[i], w[i] = list(map(int, input().strip().split()))
        # 添字を0スタートにする
        u[i] -= 1
        v[i] -= 1
    return N, u, v, w


def solve(N, u, v, w):
    c = np.zeros((N, ), dtype=np.uint8)  # 0: white, 1: black
    c[0] = 0
    for i in np.argsort(u):  # fill in ascending order
        if w[i] % 2 == 0:
            c[v[i]] = c[u[i]]
        else:
            c[v[i]] = 1 - c[u[i]]
    return c


if __name__ == '__main__':
    inputs = read()
    colors = solve(*inputs)
    for col in colors:
        print("%d" % col)

Submission status: Wrong Answer

Solution code:
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 is_same(self, x, y):
        return self.find(x) == self.find(y)

    def unite(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 main():

    N = int(input())
    tmp = []
    for i in range(N-1):
        tmp.append([int(a) for a in input().split()])

    tree = UnionFind(N)
    for u, v, w in tmp:
        if w % 2 == 0 and not tree.is_same(u, v):
            tree.unite(u, v)
    
    for i in tree.par[1:]:
        if i == tree.par[1]:
            print(0)
        else:
            print(1)


main()

Submission status: Wrong Answer

Solution code:
n = int(input())
result = [-1 for _ in range(n)]
for _ in range(n-1):
  u, v, w = map(int, input().split())
  if w % 2 == 0:
    if result[u-1] == 0 or result[v-1] == 0:
      result[v-1] = 0
      result[u-1] = 0
    elif result[u-1] == 1 or result[v-1] == 1:
      result[v-1] = 1
      result[u-1] = 1
    else:
      result[v-1] = 0
      result[u-1] = 0
  else:
    if result[u-1] == 0: 
      result[v-1] = 1
    elif result[v-1] == 0:
      result[u-1] = 1
    elif result[u-1] == 1:
      result[v-1] = 0
    elif result[v-1] == 1:
      result[u-1] = 0
    else:
      result[v-1] = 1
      result[u-1] = 0

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

Submission status: Wrong Answer

Solution code:


def main():
    N = int(input())
    a = [0 for _ in range(N+1)]
    for i in range(N-1):
        u, v, w = list(map(int, input().split()))
        if w % 2 == 0:
            if a[u] == 0:
                if a[v] == 0:
                    a[u] = 1
                    a[v] = 1
                else:
                    a[u] = a[v]
            else:
                a[v] = a[u]
        else:
            if a[u] == 0:
                if a[v] == 0:
                    a[u] = 1
                    a[v] = -1
                else:
                    a[u] = -a[v]
            else:
                a[v] = -a[u]
    for A in a[1:]:
        if A < 0:
            print(0)
        else:
            print(1)

if __name__ == "__main__":
    main()

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] == 0 and ans[a-1] == ans[b-1]:
            ans[b-1] = 1

for i in ans:
    print(i)

Submission status: Wrong Answer

Solution code:
n=int(input())
a=[]
for i in range(n-1):
  a.append(list(map(int,input().split())))
a.sort()
ans=[0]+[-i-1 for i in range(n-1)]
for l in a:
  if l[2]&1 == 0:
    ans[l[1]-1]=ans[l[0]-1]
  else:
    ans[l[1]-1]=(ans[l[0]-1]+1)&1
for i in ans:
    print(i)

Submission status: Wrong Answer

Solution code:
from operator import itemgetter


def main():
    N = int(input())
    color = [-1] * N
    comb = [[]] * N
    for _ in range(N-1):
        u, v, w = map(int, input().split())
        if w % 2 != 0:
            comb[u-1].append(v-1)
            comb[v-1].append(u-1)
    for n in range(N):
        node = comb[n]
        if color[n] == -1:
            color[n] = 0
        if len(node) > 0:
            for m in node:
                color[m] = 1 - color[n]
    for c in color:
        print(c)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import numpy as np

N = int(input())
matrix = []
for _ in range(N-1):
    u, v, w = list(map(int, input().split(' ')))
    matrix.append([u, v, w])

matrix = np.array(matrix)

distance = []
for i in range(1, N+1):
    edges = matrix[matrix[:, 0] == i]
    d = []
    for e in edges:
        d.append([e[1], e[2]])
    distance.append([i, d])

color = ['0'] + ['1'] * (N - 1)

for dist in distance:
    if color[dist[0] - 1] == '0':
        for d in dist[1]:
            if d[1] % 2 == 0:
                color[d[0] - 1] = '0'

for c in color:
    print(c)