Problem:


Score : 400 points

Problem Statement

We have a tree with N vertices numbered 1 to N.
The i-th edge in the tree connects Vertex u_i and Vertex v_i, and its length is w_i.
Your objective is to paint each vertex in the tree white or black (it is fine to paint all vertices the same color) so that the following condition is satisfied:

For any two vertices painted in the same color, the distance between them is an even number.

Find a coloring of the vertices that satisfies the condition and print it. It can be proved that at least one such coloring exists under the constraints of this problem.

Constraints

All values in input are integers.

1 \leq N \leq 10^5

1 \leq u_i < v_i \leq N

1 \leq w_i \leq 10^9

Input

Input is given from Standard Input in the following format:

N
u_1 v_1 w_1
u_2 v_2 w_2
.
.
.
u_{N - 1} v_{N - 1} w_{N - 1}

Output

Print a coloring of the vertices that satisfies the condition, in N lines.
The i-th line should contain 0 if Vertex i is painted white and 1 if it is painted black.

If there are multiple colorings that satisfy the condition, any of them will be accepted.

Sample Input 1

3
1 2 2
2 3 1

Sample Output 1

0
0
1

Sample Input 2

5
2 5 2
2 3 10
1 3 8
3 4 2

Sample Output 2

1
0
1
0
1



Sample input:
3
1 2 2
2 3 1


Sample output:
0
0
1

Submission status: Wrong Answer

Solution code:
N = int(input())

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]

print(tree)

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:

# union-find木
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())

uf = UnionFind(N);

tree1 = -1;
tree2 = -1;
undone = [[0,0,0]]

for i in range(1, N):
    u, v, w = map(int, input().split())
    w = w%2
    if(w == 0):
        uf.union(u, v)
    else:
        if(tree1 == -1):
            tree1 = uf.find(u)
            tree2 = uf.find(v)
        else:
            if(uf.find(u) == tree1 or uf.find(v) == tree2):
                uf.union(tree1, u)
                uf.union(tree2, v)
            elif(uf.find(u) == tree2 or uf.find(v) == tree1):
                uf.union(tree1, v)
                uf.union(tree2, u)
            else:
                undone.append([u, v, w])

    if(undone[0][0] == u or undone[0][0] == v):
        if(uf.find(u) == tree1 or uf.find(v) == tree2):
            uf.union(tree1, u)
            uf.union(tree2, v)
        elif(uf.find(u) == tree2 or uf.find(v) == tree1):
            uf.union(tree1, v)
            uf.union(tree2, u)
        else:
            undone.append([u, v, w])

answer = []

for i in range(1, N+1):
    if(tree1 == uf.find(i)):
        print(0)
    else:
        print(1)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
# スペース区切りの整数の入力
N = int(raw_input())
l = []
for i in range(N-1):
    l.append(raw_input().split())

print l
ans = [0]*N
for i in range(N-1):
    u = int(l[i][0])
    v = int(l[i][1])
    w = int(l[i][2])

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


print ans

Submission status: Wrong Answer

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

a = int(input())

list = [2] * a

for i in range(a):
    if i+1 == a:
        break
    b,c,d = map(int,input().split())
    b = b -1
    c = c-1
    if i == 0:
        list[b] = 0
        list[c] = 0
    else:
        if d % 2 == 0:
            if  list[b] != 2:
                list[c] = list[b]
            elif list[c] != 2:
                list[b] = list[c]
        elif d % 2 != 0:
            if  list[b] == 0:
                list[c] = 1
            elif  list[b] == 1:
                list[c] = 0
            elif list[c] == 0:
                list[b] = 1
            elif list[c] == 1:
                list[b] = 0
print(list)

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=[0]*n
ans[0]=0
for i in range(n-1):
  if w[i]%2==0:
    ans[v[i]-1]=ans[u[i]-1]
  else:
    ans[v[i]-1]=(ans[u[i]-1]+1)%2
for ii in range(n):
  print(ans[ii])

Submission status: Wrong Answer

Solution code:
N = int(input())

NG_pair_li = []
NG_set_li = []
NG_set = ()

A = []
B = []

for i in range(N-1):
    u, v, w =  list(map(int, input().split(" ")))
    if w%2 != 0:
        if u in NG_set and v in NG_set:
            if u not in A and v not in B:
                A.append(u)
                B.append(v)
            else:
                A.append(v)
                B.append(u)
            
            NG_set_li.extend([u, v])
            NG_set = set(NG_set_li)
        else:
            NG_pair_li.append([u, v])
            NG_set_li.extend([u, v])
            NG_set = set(NG_set_li)
            
for u, v in NG_pair_li:
    if u not in A and v not in B:
        A.append(u)
        B.append(v)
    else:
        A.append(v)
        B.append(u)

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

Submission status: Wrong Answer

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

for i in range(n-1):
    U,V,W = (int(x) for x in input().split())
    u.append(U)
    v.append(V)
    w.append(W)

color = [-1]*n
temp = [1]
color[0] = 0

x = 1
while(temp):
    #print(temp)
    #print(color)
    #print()
    next_temp = [] 
    for i in temp:
        for j, namej in enumerate(u):
            #print(j, namej)
            if namej == i and color[v[j]-1] == -1:
                color[v[j]-1] = x
                next_temp.append(v[j])
        for j, namej in enumerate(v):
            if namej == i and color[u[j]-1] == -1:
                color[u[j]-1] = x
                next_temp.append(u[j])
    
    x = -x+1
    temp = next_temp
    

for i in color:
    print(i)

Submission status: Wrong Answer

Solution code:
class UNION_FIND(object):
    def __init__(self,n):
        #親の番号を格納する。親だった場合は-(その集合のサイズ)
        #作るときはParentの値を全て-1にする
        #こうすると全てバラバラになる
        self.parent=[-1 for i in range(n)]
        
    def root(self,x):
        #Aがどのグループに属しているか調べる
        if self.parent[x]<0:
            return x
        else:
            self.parent[x]=self.root(self.parent[x])  #親を再帰で探知 再帰は最後に上のifにひっかかる
            return self.parent[x]
 
    def size(self,x):
        #自分のいるグループの頂点数を調べる
        return -self.parent[self.root(x)]   #親をとってきたい
        
    def union(self,x,y):
        #AとBをくっ付ける
        #AとBを直接つなぐのではなく、root(A)にroot(B)をくっつける
        #print(self.parent)
        x=self.root(x)
        y=self.root(y)
        #print(x,y)
        if x==y:   #すでにくっついてるからくっ付けない
            return False
            
        #大きい方(A)に小さいほう(B)をくっ付けたい
        #大小が逆だったらひっくり返しちゃう。
        if self.size(x)<self.size(y):
            x,y=y,x
        self.parent[x]+=self.parent[y]  #Aのサイズを更新する
        self.parent[y]=x   #Bの親をAに変更する
        return True
        
n=int(input())        
u=UNION_FIND(2*n)
for i in range(n-1):
    a,b,c=map(int,input().split())
    if c%2==0:
        u.union(2*(a-1),2*(b-1))
        u.union(2*(a-1)+1,2*(b-1)+1)
    else:
        u.union(2*(a-1),2*(b-1)+1)
        u.union(2*(a-1)+1,2*(b-1))
for i in range(n):
    print(int(u.root(i)==u.root(2*i)))

Submission status: Wrong Answer

Solution code:
n = int(input())
unit = set()
for _ in range(n-1):
    u, v, w = map(int, input().split())
    if w % 2 == 0:
        unit.add(u)
        unit.add(v)
for i in range(1, n + 1):
    if i in unit:
        print(0)
    else:
        print(1)

Submission status: Wrong Answer

Solution code:
N = int(input())

# 初期の木の根とランクを設定（初めはみんな根なのでpar[i]=i）
par = [0 for i in range(N)]
rank = [0 for i in range(N)]
for n in range(N):
    par[n] = n

# 木の根を探索する関数
# 根が自身でない場合は再帰的にたどる
# x,yが同じ集合に属するかの判定はroot(par[x])==root(par[y])か否か
def root(x):
    if par[x] == x:
        return x
    else:
        par[x] = root(par[x])
        return par[x]

# 繋げる操作を指定された時に動かす関数
def unite(x,y):
    x = par[x]
    y = par[y]
    # rankが低い方に高い方を繋げる
    if rank[x] < rank[y]:
        par[x] = y
    else:
        par[y] = x
        # 同じだった場合xのランクが一つ増える扱いになる
        if rank[x] == rank[y]:
            rank[x] += 1

# 実際にクエリを受け取って動かす
for i in range(N-1):
    u,v,w = map(int,input().split())
    u = u-1
    v = v-1
    if w % 2 == 0:
        unite(u,v)

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

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[v] = 1-color[u]			

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

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:
    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())

ls = []
B = []
W = []

for n in range(N-1):
	l = list(map(int, input().split()))
	ls.append(l)

for l in ls:
	if l[2] % 2 != 0:
		if l[0] not in B and l[1] not in W:
			B.append(l[0])
			W.append(l[1])
		elif l[0]     in B and l[1] not in W:
			W.append(l[1])
		elif l[0] not in B and l[1]     in W:
			B.append(l[0])
		elif l[0]     in W and l[1] not in B:
			B.append(l[1])
		elif l[0] not in W and l[1]     in B:
			W.append(l[0])
for n in range(1, N+1):
	if n in B:
		print("1")
	else:
		print("0")

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

Solution code:

class UNION_FIND(object):
    def __init__(self,n):
        #親の番号を格納する。親だった場合は-(その集合のサイズ)
        #作るときはParentの値を全て-1にする
        #こうすると全てバラバラになる
        self.parent=[-1 for i in range(n)]
        
    def root(self,x):
        #Aがどのグループに属しているか調べる
        if self.parent[x]<0:
            return x
        else:
            self.parent[x]=self.root(self.parent[x])  #親を再帰で探知 再帰は最後に上のifにひっかかる
            return self.parent[x]
 
    def size(self,x):
        #自分のいるグループの頂点数を調べる
        return -self.parent[self.root(x)]   #親をとってきたい
        
    def union(self,x,y):
        #AとBをくっ付ける
        #AとBを直接つなぐのではなく、root(A)にroot(B)をくっつける
        #print(self.parent)
        x=self.root(x)
        y=self.root(y)
        #print(x,y)
        if x==y:   #すでにくっついてるからくっ付けない
            return False
            
        #大きい方(A)に小さいほう(B)をくっ付けたい
        #大小が逆だったらひっくり返しちゃう。
        if self.size(x)<self.size(y):
            x,y=y,x
        self.parent[x]+=self.parent[y]  #Aのサイズを更新する
        self.parent[y]=x   #Bの親をAに変更する
        return True
        
n=int(input())        
u=UNION_FIND(2*n)
for i in range(n-1):
    a,b,c=map(int,input().split())
    if c%2==0:
        u.union(2*(a-1),2*(b-1))
        u.union(2*(a-1)+1,2*(b-1)+1)
    else:
        u.union(2*(a-1),2*(b-1)+1)
        u.union(2*(a-1)+1,2*(b-1))
for i in reversed(range(n)):
    print(int(u.root(i)==u.root(2*i)))

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
n = int(input())
w_b = [0] * n
for i in range(n-1):
    p1, p2, distance = map(int, input().split())
    if distance % 2 == 1:
        w_b[p2-1] = 1 - w_b[p1-1]
for a in w_b:
    print(a)

Submission status: Wrong Answer

Solution code:
N = int(input())
dic = {}
for i in range(N):
    dic[i+1] = 0
for i in range(N-1):
    u, v, w = map(int, input().split())
    if w%2 == 0:
        dic[u] = 1
        dic[v] = 1
c = dic.values()
list(c)
d = ""
for j in c:
    d += str(j) + "\n"
print(d)

Submission status: Wrong Answer

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

reader = [i for i in range(n)]
member = [[i] for i in range(n)]
#print(reader)
#print(member)

for uvw in UVW:
    if reader[uvw[0]-1] != reader[uvw[1]-1] and uvw[2]%2 == 0:
        a = max(uvw[0],uvw[1])-1
        b = min(uvw[0],uvw[1])-1
        reader[a] = reader[b]
        member[reader[b]] += member[a]
        member[a] = []
      #  print(reader)
      #  print(member)
#print(reader)
#print(member)
ans = [0 for i in range(n)]
for i in member:
    if i != []:
        for j in i:
            ans[j] = 1
        break
#print(ans)
for i in ans:
    print(i)

Submission status: Wrong Answer

Solution code:
N = int(input())
bw = [-1 for i in range(N+1)]
ng = 0
for i in range(N-1):
    u, v, w = map(int, input().split())
    w = w % 2
    if i == 0:
        bw[u] = ng
        bw[v] = ng
        ng += 1
    elif bw[u] == -1 and bw[v] == -1:
        bw[u] = ng
        bw[v] = ng
        ng += 1
    elif w % 2 == 0:
        if bw[u] == -1 or bw[v] == -1:
            maxg = max(bw[u], bw[v])
            bw[u] = maxg
            bw[v] = maxg
        elif bw[u] != bw[v]:
            ming = min(bw[u], bw[v])
            bw[u] = ming
            bw[v] = ming
    else:
        if bw[u] == -1:
            bw[u] = ng
            ng += 1
        elif bw[v] == -1:
            bw[v] = ng
            ng += 1
for x in bw[1:]:
    print(x)

Submission status: Wrong Answer

Solution code:
from numpy import zeros
n = int(input())
difs = [list(map(int, input().split())) for i in range(n-1)]
ans = zeros(n)
for a, b, l in difs:
    if l%2 ==0:
        ans[a-1] = 1
        ans[b-1] = 1

for i in ans: print(i)

Submission status: Wrong Answer

Solution code:
from operator import itemgetter

N = int(input())
nodes = [tuple([int(x) for x in input().split(' ')]) for i in range(N-1)]
nodes.sort(key=itemgetter(1))
nodes.sort(key=itemgetter(0))

remain = list(range(2, N+1))
color = {1:0}

for u, v, w in nodes:
    if u in remain and v in remain:
        color[u] = 0
    elif u in remain:
        color[u] = (color[v] + int(w % 2)) % 2
        remain.remove(u)
    elif v in remain:
        color[v] = (color[u] + int(w % 2)) % 2
        remain.remove(v)
    if len(remain) == 0:
        break

out = list(color.items())
out.sort(key=itemgetter(0))
for i, c in out:
    print(c)

Submission status: Wrong Answer

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


def solve(N: int, adjacent):
    color = [0] * N
    visited = [False] * N

    visited[0] = True
    
    Q = queue.Queue()
    Q.put(0)
    while not Q.empty():
        u = Q.get()
        for v, w in adjacent[u]:
            if visited[v]:
                continue
            visited[v] = True
            if w == 0:
                color[v] = color[u]
            else:
                color[v] = (color[u] + 1) % 2
            Q.put(v)
    for c in color:
        print(c)


# 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
    adjacent = [[] for _ in range(N)]
    for i in range(N-1):
        u = int(next(tokens)) - 1
        v = int(next(tokens)) - 1
        w = int(next(tokens)) % 2
        adjacent[u].append((v, w))
        adjacent[w].append((u, w))
    solve(N, adjacent)

if __name__ == '__main__':
    main()

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 == 0:
                l[edge[i][1] - 1] = l[edge[i][0] - 1]
            else:
                l[edge[i][1] - 1] = 1 - l[edge[i][0] - 1]
        else:
            if edge[i][2] % 2 == 0:
                l[edge[i][0] - 1] = l[edge[i][1] - 1]
            else:
                l[edge[i][0] - 1] = 1 - l[edge[i][1] - 1]
    else:
        if l[edge[i][1] - 1] == -1:
            if edge[i][2] % 2 == 0:
                l[edge[i][1] - 1] = l[edge[i][0] - 1]
            else:
                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())
l=[[] for i in range(n)]
uvw=[]
for i in range(n-1):
    a=[int(j) for j in input().split()]
    uvw.append(a)
    l[a[0]-1].append([a[1]-1,a[2]%2])
p=[10]*n
for i in range(n):
    for j,k in l[i]:
        if k==1:
            if p[i]+p[j]==20:
                p[i]=0
                p[j]=1
            elif p[i]+p[j]==10:
                if p[i]==0:
                    p[j]=1
                else:
                    p[i]=1
            elif p[i]+p[j]==11:
                if p[i]==1:
                    p[j]=0
                else:
                    p[i]=0
            elif p[i]+p[j]==0:
                p[j]=1
            elif p[i]+p[j]==2:
                p[j]=0
        else:
            if p[i]+p[j]==20:
                p[i]=0
                p[j]=1
            elif p[i]+p[j]==10:
                if p[i]==0:
                    p[j]=1
                else:
                    p[i]=1
            elif p[i]+p[j]==11:
                if p[i]==1:
                    p[j]=0
            

for i in p:
    if i!=10:
        print(i)
    else:
        print(1)

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 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 height(self, x):
        return self.rank[x]

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

N = int(input())
u = []
v = []
w = []

for i in range(N-1):
    _u, _v, _w = map(int, input().split())
    u.append(_u)
    v.append(_v)
    w.append(_w)

union = UnionFind(N)

for i in range(N-1):
    if w[i] % 2 == 0:
        if not union.same_check(u[i], v[i]):
            union.union(u[i], v[i])
ans = []
for i in range(1, N+1):
    if i == union.find(i) and union.height(i) == 0:
        ans.append(0)
    else:
        ans.append(1)

for c in ans:
    print(c)

Submission status: Wrong Answer

Solution code:
def color(c):
    if c == 1:
        co = 0
    else:
        co = 1
    return co

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

Submission status: Wrong Answer

Solution code:
N = int(input())
uvw = [[int(x) for x in input().split()] for _ in range(N-1)]

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

def root(x):
    tmp = x
    while par[tmp]!=tmp:
        tmp = par[tmp]
    return tmp

def unite(x,y,z):
    rx = root(x)
    ry = root(y)
    if rx==ry:
        return
    else:
        par[rx] = ry
        dist[rx] = z%2

def dist_type(x):
    tmp_dist = dist[x]%2
    tmp_x = x
    while par[tmp_x] != tmp_x:
        tmp_x = par[tmp_x]
        tmp_dist += dist[tmp_x]
        tmp_dist %= 2
    return tmp_dist

for u,v,w in uvw:
    unite(u-1,v-1,w%2)

for i in range(N):
    print(dist_type(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())
uf = WeightedUnionFind(N)
for i in range(N-1):
    ui, vi, wi = map(int, input().split())
    uf.union(ui, vi, wi)
for i in uf.weight[1:]:
    print(i%2)

Submission status: Wrong Answer

Solution code:
n=int(input())
q=[list(map(int,input().split())) for i in range(n-1)]
odd=[x for x in q if x[2]%2==1]
even=[x for x in q if x[2]%2==0]
t=[{i} for i in range(n)]
bl=set()
wh=set()
for u,v,w in even:
    t[u-1].add(v-1)
    t[v-1].add(u-1)
for u,v,w in odd:
    if len(t[u-1]&wh)>0 or len(t[v-1]&bl)>0:
        wh=wh|t[u-1]
        bl=bl|t[v-1]
    else:
        wh=wh|t[v-1]
        bl=bl|t[u-1]
for i in range(n):
    print(0 if i in wh else 1)

Submission status: Wrong Answer

Solution code:
from collections import deque
N = input()
A = [[] for i in range(N)]
for i in range(N-1):
	a2,b2,c2 = map(int, raw_input().split())
	A[a2-1].append([b2-1,c2])
	A[b2-1].append([a2-1,c2])
print(A)
A2 = [-1]*N
A2[0] = 0
q = deque([0])
while q:
	c = q.popleft()
	l = A2[c]
	for c0,c1 in A[c]:
		if(A2[c0] != -1):
			continue
		else:
			A2[c0] = (l + c1)%2
			q.append(c0)
for t in A2:
	print(t)

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==1:
    list[v-1]+=1
for iii in range(len(list)):
  print(list[iii]%2)

Submission status: Wrong Answer

Solution code:
# coding: utf-8
import re
import bisect
from datetime import datetime as dt
N = input()
color = [-1 for i in range(N)]

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

for i in color:
    print i

Submission status: Wrong Answer

Solution code:

class UNION_FIND(object):
    def __init__(self,n):
        #親の番号を格納する。親だった場合は-(その集合のサイズ)
        #作るときはParentの値を全て-1にする
        #こうすると全てバラバラになる
        self.parent=[-1 for i in range(n)]
        
    def root(self,x):
        #Aがどのグループに属しているか調べる
        if self.parent[x]<0:
            return x
        else:
            self.parent[x]=self.root(self.parent[x])  #親を再帰で探知 再帰は最後に上のifにひっかかる
            return self.parent[x]
 
    def size(self,x):
        #自分のいるグループの頂点数を調べる
        return -self.parent[self.root(x)]   #親をとってきたい
        
    def union(self,x,y):
        #AとBをくっ付ける
        #AとBを直接つなぐのではなく、root(A)にroot(B)をくっつける
        #print(self.parent)
        x=self.root(x)
        y=self.root(y)
        #print(x,y)
        if x==y:   #すでにくっついてるからくっ付けない
            return False
            
        #大きい方(A)に小さいほう(B)をくっ付けたい
        #大小が逆だったらひっくり返しちゃう。
        if self.size(x)<self.size(y):
            x,y=y,x
        self.parent[x]+=self.parent[y]  #Aのサイズを更新する
        self.parent[y]=x   #Bの親をAに変更する
        return True
        
n=int(input())        
u=UNION_FIND(2*n)
for i in range(n-1):
    a,b,c=map(int,input().split())
    if c%2==0:
        u.union(2*(a-1),2*(b-1))
        u.union(2*(a-1)+1,2*(b-1)+1)
    else:
        u.union(2*(a-1),2*(b-1)+1)
        u.union(2*(a-1)+1,2*(b-1))
for i in range(n):
    print(int(u.root(i)==u.root(2*i)))

Submission status: Wrong Answer

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

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]
for a in ans:
    print(a)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python
N = int(input())
L = [[int(i) for i in input().split()] for i in range(N-1)] 
b, w = [], []

for l in L:
    if l[2] % 2 == 0:
        if l[0] in b or l[1] in b:
            b.append(l[0])
            b.append(l[1])
        elif l[0] in w or l[1] in w:
            w.append(l[0])
            w.append(l[1])
        else:
            b.append(l[0])
            b.append(l[1])
    else:
        if l[0] in b:
            w.append(l[1])
        elif l[0] in w:
            b.append(l[1])
        else:
            if l[1] not in b:
                b.append(l[1])
                w.append(l[0])
            else:
                b.append(l[0])
                w.append(l[1])
b = list(set(b))
w = list(set(w))
for i in range(1, N+1):
    if i in b:
        print('1')
    else:
        print('0')

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[u[i]-1] = 0

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

Submission status: Wrong Answer

Solution code:
# /usr/bin/python
# -*- coding: utf-8 -*-
import math
from collections import defaultdict


N = int(input())
route = defaultdict(set)
costs = [[0 for j in range(N)] for i in range(N)]
ans = [-1] * N
for _ in range(N-1):
  u,v,w = map(int, input().split())
  route[u-1].add(v-1)
  route[v-1].add(u-1)
  costs[u-1][v-1] = w%2


ans = [-1 for i in range(N)]
ans[0] = 0
pre = 0
p = 0
visited = 0
nxt = set([0])
while visited < N and len(nxt) > 0:
  pre = p
  p = nxt.pop()
  for q in route[p]:
    if q == pre:
      continue
    else:
      ans[q] = (ans[p]+costs[p][q]+costs[q][p])%2
      nxt.add(q)
      visited += 1

for a in ans:
  print(a)

Submission status: Wrong Answer

Solution code:
def solve():
    N = int(raw_input())
    ret = [0] * N
    for i in range(N - 1):
        ui,vi,wi = [int(_) for _ in raw_input().split()]
        if wi % 2 == 0:
            ret[vi - 1] = ret[ui - 1]
        else:
            ret[vi - 1] = (1 - ret[ui - 1])
    for i in range(N):
        print ret[i]

if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

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

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:
N = int(input())
UVW = [list(map(int, input().split())) for _ in range(N - 1)]

ans = [0] * (N + 1)
for uvw in UVW:
    u, v, w = uvw
    if w % 2 == 1:
        if ans[u] == ans[v]:
            if u > v:
                if ans[u] == 1:
                    ans[u] = 0
                else:
                    ans[u] = 1
            else:
                if ans[v] == 1:
                    ans[v] = 0
                else:
                    ans[v] = 1
for i in range(1, N + 1):
    print(ans[i])

Submission status: Wrong Answer

Solution code:
import collections


class BellmanFord():
    def __init__(self):
        self.edges = []

    def add(self, u, v, d, directed=False):
        if directed is False:
            self.edges.append([u, v, d])
            self.edges.append([v, u, d])
        else:
            self.edges.append([u, v, d])

    def BellmanFord_search(self, s):
        d = collections.defaultdict(lambda: float('inf'))
        d[s] = 0
        numEdges = len(self.edges)
        while True:
            update = False
            for i in range(numEdges):
                e = self.edges[i]
                if d[e[0]] != float("inf") and d[e[1]] > d[e[0]] + e[2]:
                    d[e[1]] = d[e[0]] + e[2]
                    update = True
            if not update:
                break
        return d

N = int(input())
uvw = []
tree = BellmanFord()
for i in range(N-1):
    uvw.append(list(map(int,input().split())))
    tree.add(uvw[i][0],uvw[i][1],uvw[i][2])


a = tree.BellmanFord_search(1)

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