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:
import sys
sys.setrecursionlimit(10 ** 7)


def func(v, color):
    if visited[v] == 1:
        return
    visited[v] = 1
    for next_v in range(n):
        if graph[v][next_v] != 0:  # vとnext_vが繋がっている場合
            if graph[v][next_v] % 2 == 0:
                func(next_v, color)
            else:
                func(next_v, color ^ 1)


n = int(input())
side = [list(map(int, sys.stdin.readline().split())) for _ in range(n-1)]
graph = [[0] * n for _ in range(n)]
visited = [0] * n

for u, v, w in side:
    graph[u-1][v-1] = w
    graph[v-1][u-1] = w

func(0, 0)

Submission status: Wrong Answer

Solution code:
N=int(input())
uvw=[list(map(int,input().split())) for _ in range(N-1)]
q=[[] for _ in range(N)]
max=10**15
dist=[0]+[max for i in range(N-1)]
for i in range(N-1):
    q[uvw[i][0]-1].append((uvw[i][1],uvw[i][2]))
    q[uvw[i][1]-1].append((uvw[i][0],uvw[i][2]))
now=0
now_d=0

while(True):
    if q[q[now][-1][0]-1]==[]:
        q[now].pop()
        if q[now]==[]:
            break
    posi=q[now][-1]
    if dist[posi[0]-1]==max:
        dist[posi[0]-1]=now_d+posi[1]
    now_d=dist[posi[0]-1]
    q[now].pop()
    now=posi[0]-1
    posi=q[posi[0]-1][0]
    
for i in range(N):
    if dist[i]%2==0:
        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)]
q=[[] for _ in range(N)]
max=10**15
dist=[0]+[max for i in range(N-1)]
for i in range(N-1):
    q[uvw[i][0]-1].append((uvw[i][1],uvw[i][2]))
    q[uvw[i][1]-1].append((uvw[i][0],uvw[i][2]))
now=0
now_d=0

while(True):
    print(q)
    if q[q[now][-1][0]-1]==[]:
        q[now].pop()
        if q[now]==[]:
            break
    posi=q[now][-1]
    if dist[posi[0]-1]==max:
        dist[posi[0]-1]=now_d+posi[1]
    now_d=dist[posi[0]-1]
    q[now].pop()
    now=posi[0]-1
    posi=q[posi[0]-1][0]

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

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)
        
        self.par = [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):
        tmpx,tmpy=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
            self.par[tmpy]  =tmpx

        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            self.par[tmpx]  = tmpy
            # 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)]


def cur(n):
    if memo[n]==-1: memo[n]=cur(tree.par[n])+1
    return memo[n]

N=int(input())
tree=UnionFind(N)


for i in range(N-1):
    u,v,w=map(int,input().split())
    tree.Unite(u,v)
    print(tree.par)

memo=[-1]*(N+1)
memo[tree.Find_Root(0)]=0
for i in range(1,N+1):
    if cur(i)%2==0: print(0)
    else: print(1)

Submission status: Wrong Answer

Solution code:
from collections import deque

N = int(input())

edge = [[] for _ in range(N)]
check = [False] * N
dist = [0] * N

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

q = deque([0])

while q :
    current = q.popleft()
    if check[current] :
        continue

    check[current] = True
    for ad , w in edge[current] :
        if not check[ad] :
            q.append(ad)
            dist[ad] += w

for w in dist :
    print(w % 2)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
import copy
import collections
from bisect import bisect_left
from bisect import bisect_right
from collections import defaultdict
from heapq import heappop, heappush
	
def main():
	N = int(input())
	MP = Graph()
	
	for i in range(N-1):
		u, v, w = map(int, input().split(" "))
		u -= 1
		v -= 1
		if w % 2 == 0:
			MP.add_edge(u, v, 0)
		else:
			MP.add_edge(u, v, 1)
	
	tmp = Dijkstra(MP, 0)
	
	for i in range(N):
		if i == 0:
			print(0)
			continue
			
		tmptmp = tmp.shortest_distance(i)
		if tmptmp % 2 == 0:
			print(0)
		else:
			print(1)
	
class Graph(object):
    # 隣接リストによる有向グラフ
    def __init__(self):
        self.graph = defaultdict(list)

    def __len__(self):
        return len(self.graph)

    def add_edge(self, src, dst, weight=1):
        self.graph[src].append((dst, weight))

    def get_nodes(self):
        return self.graph.keys()


class Dijkstra(object):
    # ダイクストラ法（二分ヒープ）による最短経路探索
    def __init__(self, graph, start):
        self.g = graph.graph

        # startノードからの最短距離
        # startノードは0, それ以外は無限大で初期化
        self.dist = defaultdict(lambda: float('inf'))
        self.dist[start] = 0

        # 最短経路での1つ前のノード
        self.prev = defaultdict(lambda: None)

        # startノードをキューに入れる
        self.Q = []
        heappush(self.Q, (self.dist[start], start))

        while self.Q:
            # 優先度（距離）が最小であるキューを取り出す
            dist_u, u = heappop(self.Q)
            if self.dist[u] < dist_u:
                continue
            for v, weight in self.g[u]:
                alt = dist_u + weight
                if self.dist[v] > alt:
                    self.dist[v] = alt
                    self.prev[v] = u
                    heappush(self.Q, (alt, v))

    def shortest_distance(self, goal):
        # startノードからgoalノードまでの最短距離
        return self.dist[goal]

    def shortest_path(self, goal):
        # startノードからgoalノードまでの最短経路
        path = []
        node = goal
        while node is not None:
            path.append(node)
            node = self.prev[node]
        return path[::-1]
        
	
if __name__ == "__main__":
	main()

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
import copy
import collections
from bisect import bisect_left
from bisect import bisect_right
	
def main():
	N = int(input())
	MP = [[90000000000 for _ in range(N)] for _ in range(N)]
	
	for i in range(N-1):
		u, v, w = map(int, input().split(" "))
		u -= 1
		v -= 1
		if w % 2 == 0:
			MP[u][v] = 0
		else:
			MP[u][v] = 1
		
	MP = warshall_floyd(MP, N)
	
	for i in range(N):
		if i == 0:
			print(0)
			continue
		tmp = MP[0][i]
		if tmp % 2 == 0:
			print(0)
		else:
			print(1)
	
def warshall_floyd(d, n):
	#d[i][j]: iからjへの最短距離
	for k in range(n):
		for i in range(n):
			for j in range(n):
				d[i][j] = min(d[i][j], d[i][k] + d[k][j])
	return d
	
if __name__ == "__main__":
	main()

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
import copy
import collections
from bisect import bisect_left
from bisect import bisect_right
	
def main():
	N = int(input())
	UF = WeightedUnionFind(N)
	
	for i in range(N-1):
		u, v, w = map(int, input().split(" "))
		if w % 2 == 0:
			UF.union(u-1, v-1, 0)
		else:
			UF.union(u-1, v-1, 1)
			
	print(0)
	for i in range(N):
		if i == 0:
			continue
		tmp = UF.diff(0, i)
		if tmp % 2 == 0:
			print(0)
		else:
			print(1)

class WeightedUnionFind(object):
	def __init__(self, n=1):
		self.par = [i for i in range(n)]
		self.rank = [0 for _ in range(n)]
		# 親への重みを管理
		self.weight = [0 for _ in range(n)]
		
	# x が属するグループを探索
	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 self.par[x]
		
	# x と 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
	
	# x と y が同じグループがどうか
	def is_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]
		
	
if __name__ == "__main__":
	main()

Submission status: Wrong Answer

Solution code:
N = int(input())


# v0 o v1 o v2
# 1    0    1

# v0 e v1 o v2
# 1    1    0

# v0 e v1 e v2
# 1    1    1

# v0 o v1 e v2
# 1    0    0

class Color:
    def __init__(self, c):
        self.c = c

color = [None] * N
edge = []

for i in range(0, N-1):
    u, v, w = [int(x) for x in input().split()]
    if w & 1 == 0:
        edge.append((u-1, v-1, True))
    else:
        edge.append((u-1, v-1, False))

edge.sort()

for u, v, w in edge:
    cu = color[u]
    if cu:
        if w:
            color[v] = cu
        else:
            if color[v]:
                color[v].c = 1-cu.c
            else:
                color[v] = Color(1-cu.c)
    else:
        if w:
            if color[v]:
                color[u] = color[v]
            else:
                color[v] = Color(0)
                color[u] = color[v]
        else:
            if color[v]:
                color[u] = Color(1-color[v].c)
            else:
                color[v] = Color(0)
                color[u] = Color(1)
for u, v, w in edge:
    cu = color[u]
    if cu:
        if w:
            color[v] = cu
        else:
            if color[v]:
                color[v].c = 1-cu.c
            else:
                color[v] = Color(1-cu.c)
    else:
        if w:
            if color[v]:
                color[u] = color[v]
            else:
                color[v] = Color(0)
                color[u] = color[v]
        else:
            if color[v]:
                color[u] = Color(1-color[v].c)
            else:
                color[v] = Color(0)
                color[u] = Color(1)

for e in color:
    print(e.c)

Submission status: Wrong Answer

Solution code:
N = int(input())


# v0 o v1 o v2
# 1    0    1

# v0 e v1 o v2
# 1    1    0

# v0 e v1 e v2
# 1    1    1

# v0 o v1 e v2
# 1    0    0

class Color:
    def __init__(self, c):
        self.c = c

color = [None] * N
edge = []

for i in range(0, N-1):
    u, v, w = [int(x) for x in input().split()]
    if w & 1 == 0:
        edge.append((u-1, v-1, True))
    else:
        edge.append((u-1, v-1, False))

edge.sort()

for u, v, w in edge:
    cu = color[u]
    if cu:
        if w:
            color[v] = cu
        else:
            if color[v]:
                color[v].c = 1-cu.c
            else:
                color[v] = Color(1-cu.c)
    else:
        if w:
            if color[v]:
                color[u] = color[v]
            else:
                color[v] = Color(0)
                color[u] = color[v]
        else:
            if color[v]:
                color[u] = Color(1-color[v].c)
            else:
                color[v] = Color(0)
                color[u] = Color(1-color[v].c)

for e in color:
    print(e.c)

Submission status: Wrong Answer

Solution code:

N = int(input())
uvw = []
colors = [-1,]

for i in range(N-1):
    kari = list(map(int,input().split()))
    uvw.append(kari)
    colors.append(-1)


now_color = 0

uvw.sort()

colors[0] = 0
nokori = N-1

print (uvw)
print (colors)

while nokori>0:

    for i in range(len(uvw)):

        if colors[uvw[i][0]-1] != -1 :
            if uvw[i][2] % 2 == 0:
                colors[uvw[i][1]-1] = colors[uvw[i][0]-1]
                

            elif colors[uvw[i][0]-1]==0:
                colors[uvw[i][1]-1] = 1
               
            else:
                colors[uvw[i][1]-1] = 0

            del uvw[i]
            nokori -= 1
            break

        if colors[uvw[i][1]-1] != -1 :
            if uvw[i][2] % 2 == 0:
                colors[uvw[i][0]-1] = colors[uvw[i][1]-1]

            elif colors[uvw[i][1]-1]==0:
                colors[uvw[i][0]-1] = 1

            else:
                colors[uvw[i][0]-1] = 0

            del uvw[i]
            nokori -= 1
            break


for i in colors:
    print (i)

Submission status: Wrong Answer

Solution code:
N = int(input())
uvw = [list(map(int, input().split())) for _ in range(N-1)]
w ={uvw[0][0]}
b = set()
for i in range(N-1):
    if (uvw[i][0] in w or uvw[i][0] in b) and (uvw[i][1] in w or uvw[i][1] in b):
        continue
    elif uvw[i][0] in w:
        if uvw[i][2] % 2 == 0:
            w |= {uvw[i][1]}
        else:
            b |= {uvw[i][1]}
    elif uvw[i][0] in b:
        if uvw[i][2] % 2 == 0:
            b |= {uvw[i][1]}
        else:
            w |= {uvw[i][1]}
    elif uvw[i][1] in w:
        if uvw[i][2] % 2 == 0:
            w |= {uvw[i][0]}
        else:
            b |= {uvw[i][0]}
    elif uvw[i][1] in b:
        if uvw[i][2] % 2 == 0:
            b |= {uvw[i][0]}
        else:
            w |= {uvw[i][0]}
for i in range(1, N + 1):
    if i in w:
        print(0)
    else:
        print(1)

Submission status: Wrong Answer

Solution code:
N = int(input())
w = set()
b = set()
for i in range(N-1):
    uvw = list(map(int, input().split()))
    if len(w) == 0:
        w |={uvw[0]}
    if (uvw[0] in w or uvw[0] in b) and (uvw[1] in w or uvw[1] in b):
        continue
    elif uvw[0] in w:
        if uvw[2] % 2 == 0:
            w |= {uvw[1]}
        else:
            b |= {uvw[1]}
    elif uvw[0] in b:
        if uvw[2] % 2 == 0:
            b |= {uvw[1]}
        else:
            w |= {uvw[1]}
    elif uvw[1] in w:
        if uvw[2] % 2 == 0:
            w |= {uvw[0]}
        else:
            b |= {uvw[0]}
    elif uvw[1] in b:
        if uvw[2] % 2 == 0:
            b |= {uvw[0]}
        else:
            w |= {uvw[0]}
for i in range(1, N + 1):
    if i in w:
        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)]
w = set()
b = set()
for i in range(N-1):
    if len(w) == 0:
        w |={uvw[i][0]}
    if (uvw[i][0] in w or uvw[i][0] in b) and (uvw[i][1] in w or uvw[i][1] in b):
        continue
    elif uvw[i][0] in w:
        if uvw[i][2] % 2 == 0:
            w |= {uvw[i][1]}
        else:
            b |= {uvw[i][1]}
    elif uvw[i][0] in b:
        if uvw[i][2] % 2 == 0:
            b |= {uvw[i][1]}
        else:
            w |= {uvw[i][1]}
    elif uvw[i][1] in w:
        if uvw[i][2] % 2 == 0:
            w |= {uvw[i][0]}
        else:
            b |= {uvw[i][0]}
    elif uvw[i][1] in b:
        if uvw[i][2] % 2 == 0:
            b |= {uvw[i][0]}
        else:
            w |= {uvw[i][0]}
for i in range(1, N + 1):
    if i in w:
        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)]
w = set()
b = set()
for i in range(N-1):
    if len(w) == 0:
        w |={uvw[i][0]}
    if uvw[i][0] in w:
        if uvw[i][2] % 2 == 0:
            w |= {uvw[i][1]}
        else:
            b |= {uvw[i][1]}
    elif uvw[i][0] in b:
        if uvw[i][2] % 2 == 0:
            b |= {uvw[i][1]}
        else:
            w |= {uvw[i][1]}
    elif uvw[i][1] in w:
        if uvw[i][2] % 2 == 0:
            w |= {uvw[i][0]}
        else:
            b |= {uvw[i][0]}
    elif uvw[i][1] in b:
        if uvw[i][2] % 2 == 0:
            b |= {uvw[i][0]}
        else:
            w |= {uvw[i][0]}
for i in range(1, N + 1):
    if i in w:
        print(0)
    else:
        print(1)

Submission status: Wrong Answer

Solution code:
n = int(input())
uvw_array = [[int(x) for x in input().split()] for y in range(n - 1)]
color = [0 for x in range(n)]
# 同じ色の距離が偶数(黒(= 1)にする)
for u, v, w in uvw_array:
    if w % 2 == 0:
        color[v-1] = 1
        color[u-1] = 1

for i in color:
    print(i)

Submission status: Wrong Answer

Solution code:
res = None
G = None

def dfs(jibun_v, p, jibun_c):
    global res
    global G

    res[jibun_v] = jibun_c

    tonari_nodes = G[jibun_v]
    for tonari_v, w in tonari_nodes:
        if tonari_v == p:
            continue

        if w % 2 == 0:
            tonari_c = jibun_c
        else:
            tonari_c = 1 - jibun_c

        dfs(tonari_v, w, tonari_c)
    

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

    global G
    G = [[] for _ in range(N)]

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

    global res
    res = [-1 for _ in range(N)]
    
    jibun_v = 0
    p = -1
    jibun_c = 0
    dfs(jibun_v, p, jibun_c)

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

main()

Submission status: Wrong Answer

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

d = [-1] * N
known = [array[0][0]]
d[known[0]-1] = 0

def dis(u, v, w):
    d[v-1] = (d[u-1] + w) % 2
    known.append(v)

while array:
    top = known[0]
    tmp = []
    for a in array:
        if a[0] == top:
            dis(a[0], a[1], a[2])
            tmp.append(a)
            
        elif a[1] == top:
            dis(a[1], a[0], a[2])
            tmp.append(a)
    
    for b in tmp:
        array.remove(b)
    
    known.pop(0)

Submission status: Wrong Answer

Solution code:
N = int(input())

q = []
visited = [0] * N
ans = [0] * N
A = [[] for _ in range(N)]  # tree
W = [[] for _ in range(N)]  # weight

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

q.append(0)  # start
for _ in range(N):
    u = q.pop(0)
    visited[u] = 1
    k = 0
    for v in A[u]:
        if visited[v]==0:
            q.append(v)
            ans[v] = ans[u] + W[u][k]
        k += 1

for a in ans:
    print(a%2)

Submission status: Wrong Answer

Solution code:
N = int(input())

q = []
visited = [0] * N
ans = [0] * N
A = [[] for _ in range(N)]  # tree
W = [[] for _ in range(N)]  # weight

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

q.append(0)  # start
for _ in range(N):
    u = q.pop(0)
    visited[u] = 1
    k = 0
    for v in A[u]:
        if visited[v]==0:
            q.append(v)
            ans[v] = ans[u] + W[u][k]
        k += 1

for a in ans:
    print(a%2)

Submission status: Wrong Answer

Solution code:
N = int(input())
node_array = [list(map(int, input().split())) for i in range(N - 1)]
# print(node_array)
tree_num_array = [-1] * N
# print(tree_num_array)

tree_num_max = -1
tree = {}
last_tree_num = -1
for node in node_array:
    i, j, w = node
    i = i - 1
    j = j - 1
    if tree_num_array[i] == -1 and tree_num_array[j] == -1:
        tree_num_max += 1
        tree[tree_num_max] = {i: 0, j: w}
        tree_num_array[i] = tree_num_max
        tree_num_array[j] = tree_num_max
        last_tree_num = tree_num_max
        continue
    elif tree_num_array[i] == -1:
        tree_num_added = tree_num_array[j]
        tree[tree_num_added][i] = tree[tree_num_added][j] + w
        tree_num_array[i] = tree_num_added
        last_tree_num = tree_num_added
    elif tree_num_array[j] == -1:
        tree_num_added = tree_num_array[i]
        tree[tree_num_added][j] = tree[tree_num_added][i] + w
        tree_num_array[j] = tree_num_added
        last_tree_num = tree_num_added
    else:
        tree_num_added = tree_num_array[i]
        tree_num_united = tree_num_array[j]
        tree_value_i = tree[tree_num_added][i]
        tree_value_j = tree[tree_num_united][j]
        for key, value in tree[tree_num_united].items():
            tree[tree_num_added][
                key] = tree_value_i + w + abs(value - tree_value_j)
        last_tree_num = tree_num_added
# print(tree[last_tree_num])
ans_dict = sorted(tree[last_tree_num].items(), key=lambda x: int(x[0]))

for distance in ans_dict:
    print(distance[1] % 2)

Submission status: Wrong Answer

Solution code:
N = int(input())
node_array = [list(map(int, input().split())) for i in range(N - 1)]
# print(node_array)
tree_num_array = [-1] * N
# print(tree_num_array)

tree_num_max = -1
tree = {}
last_tree_num = -1
for node in node_array:
    i, j, w = node
    i = i - 1
    j = j - 1
    if tree_num_array[i] == -1 and tree_num_array[j] == -1:
        tree_num_max += 1
        tree[tree_num_max] = {i: 0, j: w}
        tree_num_array[i] = tree_num_max
        tree_num_array[j] = tree_num_max
        last_tree_num = tree_num_max
        continue
    elif tree_num_array[i] == -1:
        tree_num_added = tree_num_array[j]
        tree[tree_num_added][i] = tree[tree_num_added][j] + w
        tree_num_array[i] = tree_num_added
        last_tree_num = tree_num_added
    elif tree_num_array[j] == -1:
        tree_num_added = tree_num_array[i]
        tree[tree_num_added][j] = tree[tree_num_added][i] + w
        tree_num_array[j] = tree_num_added
        last_tree_num = tree_num_added
    else:
        tree_num_added = tree_num_array[i]
        tree_num_united = tree_num_array[j]
        tree_value_i = tree[tree_num_added][i]
        tree_value_j = tree[tree_num_united][j]
        for key, value in tree[tree_num_united].items():
            tree[tree_num_added][
                key] = tree_value_i + w + abs(value - tree_value_j)
        last_tree_num = tree_num_added
# print(tree[last_tree_num])
ans_dict = sorted(tree[last_tree_num].items(), key=lambda x: x[0])

for distance in ans_dict:
    print(distance[1] % 2)

Submission status: Wrong Answer

Solution code:
#coding:utf-8
from collections import defaultdict
import sys
from Queue import Queue
N=input()
U=[];V=[];W=[]
G=defaultdict(list)
Dist={}
for _ in range(N-1):
    u,v,w=map(int,raw_input().split())
    u,v=min(u,v),max(u,v)
    U.append(u);V.append(v);W.append(w)    
    G[u].append(v)
    G[v].append(u)
    Dist[(u,v)]=Dist[(v,u)]=w

vis=[False]*(10**5+1)
color=[None]*(10**5+1)
q=Queue()
vis[1]=True
color[1]=0
curCol=1
for u in G[1]:q.put(u)
print(G)
while not q.empty():
    child=q.get()
    vis[child]=True
    par=None
    for n in G[child]:
        if vis[n]: 
            par=n;break
    dist=Dist[(par,child)]
    if dist%2==0: color[child]=color[par]
    else: color[child]=color[par]^1
    for ch in G[child]:
        if not vis[ch]: q.put(ch)

for c in color[1:N+1]:print(c)

Submission status: Wrong Answer

Solution code:
n = int(input())

info = [[0,0,0]]

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

infos = sorted(info)

col = [0] * (n+1)
for j in range(1,n):
    if infos[j][2] % 2 == 1:
        col[infos[j][1]] = abs(1-col[infos[j][0]])
    else:
        col[infos[j][1]] = col[infos[j][0]]

for k in range(1,n+1):
    print(col[k])

Submission status: Wrong Answer

Solution code:
n = int(input())

info = [[0,0,0]]

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

infos = sorted(info)

col = [0] * (n+1)
for j in range(1,n):
    if info[j][2] % 2 == 1:
        col[info[j][1]] = abs(1-col[info[j][0]])
    else:
        col[info[j][1]] = col[info[j][0]]

for k in range(1,n+1):
    print(col[k])

Submission status: Wrong Answer

Solution code:
import heapq

def dijkstra(graph,node,start):
    dist = [float("inf") for _ in range(node)]
    dist[start] = 0
    q = []
    heapq.heappush(q,[0,start])

    while(q):
        cost, cur_node = heapq.heappop(q)
        if dist[cur_node] < cost:
            continue
        for next_const, next_node in graph[cur_node]:
            dist_cand = dist[cur_node]+next_node
            if dist_cand < dist[next_node]:
                dist[next_node] = dist_cand
                heapq.heappush(q,(dist[next_node],next_node))
    return dist
    

n  = int(input())
adj = [[] for _ in range(n)]
for i in range(n-1):
    u,v,w = map(int,input().split())
    u -= 1
    v -= 1
    adj[u].append((w,v))
    adj[v].append((w,u))
shortest = dijkstra(adj,n,0)
for i in shortest:
    print(i%2)

Submission status: Wrong Answer

Solution code:
n = int(input())
node = [[0 for j in range(n)] for i in range(n)]
for i in range(n-1):
    u,v,w = map(int,input().split())
    node[u-1][v-1] = w
    node[v-1][u-1] = w

ans = [0 for i in range(n)]
pos = [[0,1]]
visited = []
#print(node)
while(pos):
    now,new = pos.pop()
    visited.append(now)
    if node[now][new]%2==0:
        ans[new] = 0
    else:
        ans[new] = 1
    for j in range(len(node[new])):
        if node[new][j] != 0 and j not in visited:
            pos.append([new,j])
print("\n".join(list(map(str,ans))))

Submission status: Wrong Answer

Solution code:
#from queue import LifoQueue

'''
allinputs = iter(input().splitlines())
input = lambda : next(allinputs)
#'''

N = int(input())
#A =  [[0 for i in range(N)] for j in range(N)]
#q = LifoQueue()
#b = [-1 for i in range(N)]
c = [0 for i in range(N)]
l = [0 for i in range(N)]

for i in range(N-1):
	u, v, w = map(int,input().split())
	u = u - 1
	v = v - 1
	#A[u-1][v-1] = w
	#A[v-1][u-1] = w
	if c[u] == 0 and c[v] == 0:
		c[u] = 1
		l[u] = 0
		c[v] = 1
		l[v] = w
	elif c[u] == 0 and c[v] == 1:
		c[u] = 1
		l[u] = l[v] + w
	elif c[u] == 1 and c[v] == 0:
		c[v] = 1
		l[v] = l[u] + w
'''
q.put(0)
while not q.empty():
	i = q.get()
	c[i] = 1
	for j in range(N):
		if A[i][j] > 0 and c[j] == 0:
			q.put(j)
			#b[j] = i
			l[j] = l[i] + A[i][j]
'''
for i in l:
	print('{}'.format(i%2))

Submission status: Wrong Answer

Solution code:
n = int(input())

l = [2] * n
d = []
for i in range(n - 1):
    u, v, w = map(int, input().split())
    d.append([u, v, w])

d.sort()
for i in range(n - 1):
    u, v, w = d[i]
    u -= 1
    v -= 1
    if w % 2 == 0:
        if l[u] == 0 or l[u] == 1:
            l[v] = l[u]
        elif l[v] == 0 or l[v] == 1:
            l[u] = l[v]
        else:
            l[u] = 0
            l[v] = 0
    else:
        if l[u] == 0:
            l[v] = 1
        elif l[u] == 1:
            l[v] = 0
        elif l[v] == 0:
            l[u] = 1
        elif l[v] == 1:
            l[u] = 0
        else:
            l[u] = 0
            l[v] = 1

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

Submission status: Wrong Answer

Solution code:
n = int(input())

l = [2] * n

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

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

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(100000000)

n = int(input())

ulist = []

for _ in range(n+1):
    ulist.append([])

vlist = [False]*(n+1)

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

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

def check(checkV, fromV):
    for data in ulist[checkV]:
        if data[0] != fromV:
            vlist[data[0]] = vlist[checkV] if data[1] % 2 == 0 else not vlist[checkV]
            check(data[0], checkV)

check(1, 0)

for i in range(1,n+1):
    print(1 if vlist[i] else 0)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10000000)
N = int(input())
JU = [-1] * N

LI = [[] for _ in range(N)]
for _ in range(N-1):
    u,v,w = map(int,input().split())
    W = w%2
    LI[u-1].append([v-1,W])
    LI[v-1].append([u-1,W])
def dfs(x):
    for i in range(len(LI[x])):
        j = LI[x][i][0]
        k = LI[x][i][1]
        if JU[j] == -1:
            if JU[i] == 0:
                if k == 0:
                    JU[j] = 0
                    dfs(j)
                else:
                    JU[j] = 1
                    dfs(j)
            else:
                if k == 0:
                    JU[j] = 1
                    dfs(j)
                else:
                    JU[j] = 0
                    dfs(j)

JU[0] = 0
dfs(0)
for i in range(N):
    print(JU[i])

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

class Tree:
  def __init__(self):
    self.edges = defaultdict(set)
  
  def add(self, x, y, w):
    self.edges[x].add((y, w))
    self.edges[y].add((x, w))
  
  def traverse(self, start):
    return self._traverse(start, 0, set([start]), [(start, 0)])
  
  def _traverse(self, start, dist, already_visited, result):
    out_nodes = self.edges[start]
    for out_node, w in out_nodes:
      if out_node in already_visited:
        continue
      new_dist = dist + w
      yield (out_node, new_dist)
      self._traverse(out_node, new_dist, already_visited | set([out_node]), result)
    #return result
      
n = int(input())
tree = Tree()
for _ in range(n-1):
  xyw = list(map(int, input().split()))
  tree.add(*xyw)

start = 1
node_dists = list(tree.traverse(start))
node_dists = sorted(node_dists, key=lambda x: x[0])

for node, dist in node_dists:
  print(1 if dist % 2 == 0 else 0)