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())
uvw = []
for i in range(n-1):
    uvw.append(list(map(int, input().split(' '))))
result = [0]*(n+1)
result[uvw[0][1]] = uvw[0][2]
s = uvw[0][0]
del uvw[0]
n_visit = []
for i in range(1, len(uvw)):
    if result[uvw[i][0]] == 0 and result[uvw[i][1]] != 0 and uvw[i][0] != s:
        result[uvw[i][0]] =  result[uvw[i][1]] + uvw[i][2]
    elif result[uvw[i][0]] != 0 and result[uvw[i][1]] == 0 and uvw[i][1] != s:
        result[uvw[i][1]] =  result[uvw[i][0]] + uvw[i][2]
    else:
        if uvw[i][1] != s:
            result[uvw[i][1]] = uvw[i][2]
        else:
            result[uvw[i][0]] = uvw[i][2]

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

Submission status: Wrong Answer

Solution code:
n = int(input())
uvw = []
for i in range(n-1):
    uvw.append(list(map(int, input().split(' '))))
result = [0]*(n+1)
result[uvw[0][1]] = uvw[0][2]
s = uvw[0][0]
del uvw[0]
n_visit = []
for i in range(len(uvw)):
    if result[uvw[i][0]] == 0 and result[uvw[i][1]] != 0 and uvw[i][0] != s:
        result[uvw[i][0]] =  result[uvw[i][1]] + uvw[i][2]
    elif result[uvw[i][0]] != 0 and result[uvw[i][1]] == 0 and uvw[i][1] != s:
        result[uvw[i][1]] =  result[uvw[i][0]] + uvw[i][2]
    else:
        if uvw[i][1] != s:
            result[uvw[i][1]] = uvw[i][2]
        else:
            result[uvw[i][0]] = uvw[i][2]

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

Submission status: Wrong Answer

Solution code:
n = int(input())
uvw = []
for i in range(n-1):
    uvw.append(list(map(int, input().split(' '))))
result = [0]*n
for i in range(n-1):
    if uvw[i][2]%2 == 0:
        result[uvw[i][0]-1] = 1
        result[uvw[i][1]-1] = 1
for i in result:
    print(i)

Submission status: Wrong Answer

Solution code:
N = int(input().strip())
colours = []
for i in range(N):
    colours.append(0)
uvw = []
uvwc = uvw.copy()
uvwc.reverse()
uvw.sort(key=lambda x: x[0])
for i in range(N-1):
    uvw.append(list(map(int, input().strip().split())))
allu = []
allv = []
allw = []
for i in uvw:
    allu.append(i[0])
    allv.append(i[1])
    allw.append(i[2])
for i in range(1, N+1):
    try:
        ind1 = uvwc.index(i)
        ind2 = uvw.index(i)
    except ValueError:
        ind1 = 1
        ind2 = 1
    for o in range(ind2, N-ind1):
        if colours[allv[o]-1] == colours[allu[o]-1]:
            if allw[o] % 2 == 1:
                colours[allv[o]-1] = 1
for i in colours:
    print(i)

Submission status: Wrong Answer

Solution code:
N = int(input().strip())
colours = []
for i in range(N):
    colours.append(0)
uvw = []
uvw.sort(key=lambda x: x[0])
for i in range(N-1):
    uvw.append(list(map(int, input().strip().split())))
allu = []
allv = []
allw = []
for i in uvw:
    allu.append(i[0])
    allv.append(i[1])
    allw.append(i[2])
for i in range(1, N+1):
    indices = [p for p, x in enumerate(allu) if x == i]
    for o in indices:
        if colours[allv[o]-1] == colours[allu[o]-1]:
            if allw[o] % 2 == 1:
                colours[allv[o]-1] = 1
for i in colours:
    print(i)

Submission status: Wrong Answer

Solution code:

N = int(input())

uvw = []
Nlis = [-1] * N
Ndic = {}

for i in range(N-1):

    u,v,w = map(int,input().split())
    
    if u not in Ndic:
        Ndic[u] = [[v,w]]

    else:
        Ndic[u].append([v,w])

    if v not in Ndic:
        Ndic[v] = [[u,w]]

    else:
        Ndic[v].append([v,w])


ends = [1]
Q = [1]
Nlis[0] = 0

while len(Q) > 0:

    now = Q.pop(0)

    for nw in Ndic[now]:

        if nw[0] not in ends:

            Q.append(nw[0])
            ends.append(nw[0])

            if nw[1] % 2 == 0:
                Nlis[nw[0]-1] =  Nlis[now-1]

            else:
                Nlis[nw[0]-1] = (Nlis[now-1] + 1) % 2

for i in Nlis:
    print(i)

Submission status: Wrong Answer

Solution code:
N = int(input().strip())
colours = []
for i in range(N):
    colours.append(0)
uvw = []
for i in range(N-1):
    uvw.append(list(map(int, input().strip().split())))
allu = []
allv = []
allw = []
for i in uvw:
    allu.append(i[0])
    allv.append(i[1])
    allw.append(i[2])
for i in range(1, N+1):
    indices = [p for p, x in enumerate(allu) if x == i]
    for o in indices:
        if colours[allv[o]-1] == colours[allu[o]-1]:
            if allw[o] % 2 == 1:
                colours[allu[o]-1] = 1
for i in colours:
    print(i)

Submission status: Wrong Answer

Solution code:
N = int(input().strip())
colours = []
for i in range(N):
    colours.append(0)
uvw = []
for i in range(N-1):
    uvw.append(list(map(int, input().strip().split())))
allu = []
allv = []
allw = []
for i in uvw:
    allu.append(i[0])
    allv.append(i[1])
    allw.append(i[2])
for i in range(1, N+1):
    indices = [p for p, x in enumerate(allu) if x == i]
    for o in indices:
        if colours[allv[o]-1] == colours[allu[o]-1]:
            if allw[o] % 2 == 1:
                colours[allv[o]-1] = 1
for i in colours:
    print(i)

Submission status: Wrong Answer

Solution code:
n,*uvw=map(int,open(0).read().split())
col = [0]*n
fix = [0]*n
for u,v,w in zip(uvw[::3],uvw[1::3],uvw[2::3]):
    if fix[u-1] == 1:
        col[v-1] = col[u-1]^(w%2)
        fix[v-1] = 1
    else:
        col[u-1] = col[v-1]^(w%2)
        fix[u-1] = 1
        fix[v-1] = 1
        
[print(i) for i in col]

Submission status: Wrong Answer

Solution code:
n,*uvw=map(int,open(0).read().split())
col = [0]*n
fix = [0]*n
for u,v,w in zip(uvw[::3],uvw[1::3],uvw[2::3]):
    if fix[u-1] == 1:
        col[v-1] = col[u-1]^(w%2)
        fix[v-1] == 1
    else:
        col[u-1] = col[v-1]^(w%2)
        fix[u-1] == 1
        fix[v-1] == 1
        
[print(i) for i in col]

Submission status: Wrong Answer

Solution code:
n,*uvw=map(int,open(0).read().split())
col = [0]*n
fix = [0]*n
for u,v,w in zip(uvw[::3],uvw[1::3],uvw[2::3]):
    if w%2 ==1:
        if fix[u-1] == 1:
            col[v-1] = col[u-1]^1
            fix[v-1] == 1
        else:
            col[u-1] = col[v-1]^1
            fix[u-1] == 1
            fix[v-1] == 1
[print(i) for i in col]

Submission status: Wrong Answer

Solution code:
from scipy.sparse.csgraph import csgraph_from_dense, dijkstra
import numpy as np

N = int(input())

G = [[float('inf')] * N for i in range(N)]

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

    # G2 = csgraph_from_dense(G, null_value=10**12)
    # d = dijkstra(G2, indices=0)

    # for dist in d:
    #     if dist % 2 == 0:
    #         print(1)
    #     else:
    #         print(0)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10 ** 5)

N = int(input())

C = [-1] * N  # Colors
E = [[]] * N  # Edges
swap = {0: 1, 1: 0}


def coloring(v, c):
    C[v] = c
    for e in E[v]:
        if C[e[0]] == -1:
            coloring(e[0], c if e[1] % 2 == 0 else swap[c])


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

coloring(0, 0)

for c in C:
    print(c)

Submission status: Wrong Answer

Solution code:
N = int(input())

color = [0]*N

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

for u, v, w in uvw:
    if w % 2 == 1:
        color[v-1] = int(not color[u-1])

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

Submission status: Wrong Answer

Solution code:
N = int(input())

color = [0]*N

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

for u, v, w in uvw:
    if w % 2 == 1:
        color[v-1] = int(not color[u-1])

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

Submission status: Wrong Answer

Solution code:
N = int(input())

color = [0]*N

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

for u, v, w in uvw:
    if w % 2 == 1:
        color[v-1] = int(not color[u-1])

print(color)

Submission status: Wrong Answer

Solution code:
import numpy as np
import sys
sys.setrecursionlimit(10**5)
max = 10**5+5

def dk(start,node,edge):
  ans = [0] * node
  q = [start]
  
  while(len(q) != 0):
    i = q.pop()
    for j, cost in edge[i]:
      ans[j] = (ans[i] + cost)%2
      q.append(j)
  return ans

#入力
N = int(input())
#エッジ
E = [[] for _ in [0]*(max)]

for i in range(N-1):
  a,b,w = (int(x) for x in input().split())
  E[a-1].append((b-1, w))

ans = dk(0, N, E)

#出力
print(*ans, sep = "\n")

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
write = lambda x: sys.stdout.write(str(x))
LMIIS = lambda : list(map(int,input().split()))
II = lambda : int(input())
dbg = lambda *something : print(*something) if DEBUG is True else 0
DEBUG = True

def main():

    N = II()
    t = [-1] * N
    E = [0] * (N-1)
    for _ in range(N-1):
        u,v,w = LMIIS()
        u -=1
        v -=1
        E[_] = (u,v,w)
    

    E.sort()
    for u,v,w in E:
        if t[u] == -1:
                t[u] = 0
        t[v] = t[u] if w % 2 == 0 else t[u]^1



    for i in t:
        write(i)
        write(' ')






    pass
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

E = [{} for _ in [0]*N]
for u,v,c in UVW:
    E[u-1][v-1] = c
    E[v-1][u-1] = c

def dist_dfs_tree(N,E,root):
    d = [0]*N
    q = [root]
    while q:
        i = q.pop()
        ci = d[i]
        for j,cj in E[i].items():
            if d[j] !=-1:continue
            d[j] = ci+cj
            q.append(j)
    return d

d = dist_dfs_tree(N,E,0)
print(*[l%2 for l in d],sep="\n")

Submission status: Wrong Answer

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

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

que = [(1, 0)]

colors = [0] * (n + 1)
while que:
    now, color = que.pop(0)
    colors[now] = color

    for b, w in graph[now]:
        que.append((b, (color + (w & 1)) & 1))
print("\n".join(map(str, colors[1:])))

Submission status: Wrong Answer

Solution code:
n=int(input())
graph=[[False]*n for i in range(n)] #点の隣接連結を示す
distance=[-1]*n
distance[0]=0
visited=[False]*n #dfsを書くときに訪問した点を記録する
for i in range(n-1):
    a,b,c=map(int,input().split())
    c%=2
    graph[a-1][b-1],graph[b-1][a-1]=[True,c],[True,c]
def dfs(v):
    visited[v]=True
    for i in range(n):
        if graph[v][i]==False:continue
        if visited[i]==True:continue
        distance[i]=distance[v]+graph[v][i][1]
        dfs(i)#訪問済みでなく辺によってつながれている頂点に対して同じ操作を繰り返す
dfs(0)
for i in distance:
  print(i)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(5000)

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

ans = [0] * (N+1)
def search(num, root, dis):
    nodes = tuple(filter(lambda x:x[0] == num or x[1] == num, W))
    for node in nodes:
        if node[0] != root and node[1] != root:
            idx = node[1] if node[0] == num else node[0]
            dis += node[2]%2
            if dis%2 != 0:
                ans[idx] = 1
            search(idx, num, dis)
        # else:
        #     dis += node[2]%2
        #     if dis%2 != 0:
        #         idx = node[1] if node[0] == num else node[0]
        #         ans[idx] = 1

search(1, 0, 0)
for answer in ans[1:]:
    print(answer)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(5000)

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

ans = [0] * (N+1)
def search(num, root, dis):
    nodes = tuple(filter(lambda x:x[0] == num or x[1] == num, W))
    for node in nodes:
        if node[0] != root and node[1] != root:
            idx = node[1] if node[0] == num else node[0]
            dis += node[2]
            if dis%2 != 0:
                ans[idx] = 1
            search(idx, num, dis)
        else:
            dis += node[2]
            if dis%2 != 0:
                idx = node[1] if node[0] == num else node[0]
                ans[idx] = 1

search(1, 0, 0)
for answer in ans[1:]:
    print(answer)

Submission status: Wrong Answer

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

ans = [0]*n
for i in range(n-1):
    b = l[i][0] -1
    s = l[i][1] -1
    if l[i][2] % 2 ==0:
        ans[s] = ans[b]
    else:
        if ans[b] == 0:
            ans[s] = 1
        else:
            ans[s] = 0
for i in range(n):
    print(ans[i])

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(5000)

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

ans = [0] * (N+1)
def search(num, root):
    nodes = tuple(filter(lambda x:x[0] == num or x[1] == num, W))
    if len(nodes) == 1:
        if nodes[0][0] != root and nodes[0][1] != root:
            idx = nodes[0][1] if nodes[0][0] == num else nodes[0][0]
            search(idx, num)
        else:
            if nodes[0][2]%2 != 0:
                # idx = nodes[0][1] if nodes[0][0] == num else nodes[0][0]
                # print(idx)
                ans[num] = 1
    else:
        for node in nodes:
            if node[0] != root and node[1] != root:
                idx = node[1] if node[0] == num else node[0]
                search(idx, num)
search(1, 0)
for answer in ans[1:]:
    print(answer)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(5000)

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

W.sort(key=lambda x:x[0])
ans = [0] * (N+1)
def search(num, root):
    nodes = list(filter(lambda x:x[0] == num or x[1] == num, W))
    if len(nodes) == 1:
        if nodes[0][0] != root and nodes[0][1] != root:
            idx = nodes[0][1] if nodes[0][0] == num else nodes[0][0]
            search(idx, num)
        else:
            if nodes[0][2]%2 != 0:
                idx = nodes[0][1] if nodes[0][0] == num else nodes[0][0]
                ans[idx] = 1
    else:
        for node in nodes:
            if node[0] != root and node[1] != root:
                idx = node[1] if node[0] == num else node[0]
                search(idx, num)
search(1, 0)
for answer in ans[1:]:
    print(answer)

Submission status: Wrong Answer

Solution code:
import sys
from queue import Queue


def main():
    input = sys.stdin.readline
    N = int(input())
    tree = [[] for _ in range(N)]
    for _ in range(N-1):
        u, v, w = map(int, input().split())
        tree[u-1].append([v-1, w])
        tree[v-1].append([u-1, w])

    color = [None] * N
    v_que = Queue()
    v_que.put(0)
    
    c = True
    c_que = Queue()
    c_que.put(c)

    while not v_que.empty():
        v = v_que.get()
        c = c_que.get()
        if color[v] is not None:
            continue
        print(v)
        color[v] = c
        for e in tree[v]:
            v_que.put(e[0])
            c_que.put(c if e[1] % 2 == 0 else not c)

    for c in color:
        print(int(c))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import numpy as np

n = int(input())
edge = []
ans = [-1 for i in range(n)]

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

edge.sort(key=lambda x:[-x[3],x[0],x[1]])
# print(edge)

for e in edge:
    l = e[0]-1
    r = e[1]-1
    # print(l,r)
    if e[3] == 1:
        if ans[l] == -1:
            ans[l] = 0
            ans[r] = 1
        else:
            if ans[l] == 1:
                ans[r] = 0
            else:
                ans[r] = 1
    else:
        if ans[l] == -1:
            if ans[r] == -1:
                ans[l] = 0
                ans[r] = 0
            else:
                ans[l] = ans[r]
        else:
            ans[r] = ans[l]
    # print(ans)

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

Submission status: Wrong Answer

Solution code:
import numpy as np

n = int(input())
edge = []
ans = [-1 for i in range(n)]

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

edge.sort(key=lambda x:[-x[3],x[0],x[1]])
print(edge)

for e in edge:
    l = e[0]-1
    r = e[1]-1
    # print(l,r)
    if e[3] == 1:
        if ans[l] == -1:
            ans[l] = 0
            ans[r] = 1
        else:
            if ans[l] == 1:
                ans[r] = 0
            else:
                ans[r] = 1
    else:
        if ans[l] == -1:
            if ans[r] == -1:
                ans[l] = 0
                ans[r] = 0
            else:
                ans[l] = ans[r]
        else:
            ans[l] = ans[r]
    # print(ans)

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

Submission status: Wrong Answer

Solution code:
N = int(input())
tree = []
for i in range(0, N-1):
	inpt = list(map(int, input().split()))
	tree.append([inpt[0]-1, inpt[1]-1, inpt[2]])
treelist = []
for i in range(0, N):
	treelist.append([])
for i in range(0, N-1):
	treelist[tree[i][0]].append([tree[i][1], tree[i][2]])
grp = []
for i in range(0, N):
	grp.append(i)
for i in range(0, N-1):
	rootA = tree[i][0]
	que1 = []
	while True:
		if grp[rootA] == rootA:
			break
		que1.append(rootA)
		rootA = grp[rootA]
	for j in range(0, len(que1)):
		grp[que1.pop(0)] = rootA
	rootB = tree[i][1]
	que2 = []
	while True:
		if grp[rootB] == rootB:
			break
		que2.append(rootB)
		rootB = grp[rootB]
	for j in range(0, len(que2)):
		grp[que2.pop(0)] = rootB
	grp[rootA] = rootB
colors = []
for i in range(0, N):
	colors.append(-1)
for i in range(0, N):
	d = 0
	if i != grp[i]:
		queue = []
		goal = -1
		if i < grp[i]:
			queue.append([i, 0])
			goal = grp[i]
		else:
			queue.append([grp[i], 0])
			goal = i
		while queue != []:
			now = queue.pop(0)
			if now[0] == goal:
				d = now[1]
				break
			for j in range(0, len(treelist[now[0]])):
				queue.append([treelist[now[0]][j][0], now[1]+treelist[now[0]][j][1]])
	if d % 2 == 0 and d != 0:
		if colors[i] == -1:
			if colors[grp[i]] == -1:
				colors[i] = 0
				colors[grp[i]] = 0
			else:
				colors[i] = colors[grp[i]]
		else:
			colors[grp[i]] = colors[i]
	else:
		if colors[i] == -1:
			if colors[grp[i]] == -1:
				colors[i] = 0
				colors[grp[i]] = 1
			else:
				colors[i] = (colors[grp[i]]+1)%2
		else:
			colors[grp[i]] = (colors[grp[i]]+1)%2
for i in range(0, N):
	print(colors[i])

Submission status: Wrong Answer

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

class UnionFind:
    def __init__(self, n):
        # 親要素のノード番号を格納。par[x] == xの時そのノードは根
        self.par = [i for i in range(n+1)]
        # 木の高さを格納する（初期状態では0）
        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 same_check(self, x, y):
        return self.find(x) == self.find(y)

    # 併合
    def union(self, x, y):
        # 根を探す
        x = self.find(x)
        y = self.find(y)
        # 木の高さを比較し、低いほうから高いほうに辺を張る
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            # 木の高さが同じなら片方を1増やす
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

uf=UnionFind(n)
for i in range(n-1):
    if vvw[i][2]%2==1:
        uf.union(vvw[i][0], vvw[i][1])

# for i in range(1,n+1):
    # print(uf.find(i))
ans=[100]*n
for i in range(1,n+1):
    # print(ans)
    if uf.find(i)==i:
        print(0)
        ans[i-1]=0
    else:
        if ans[uf.find(i)-1]==100:
            ans[i-1]=0
        # print(uf.par[i])
        if ans[uf.find(i)-1]==0:
            print(1)
            ans[i-1]=1
        else:
            print(0)
            ans[i-1]=0

Submission status: Wrong Answer

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

class UnionFind:
    def __init__(self, n):
        # 親要素のノード番号を格納。par[x] == xの時そのノードは根
        self.par = [i for i in range(n+1)]
        # 木の高さを格納する（初期状態では0）
        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 same_check(self, x, y):
        return self.find(x) == self.find(y)

    # 併合
    def union(self, x, y):
        # 根を探す
        x = self.find(x)
        y = self.find(y)
        # 木の高さを比較し、低いほうから高いほうに辺を張る
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            # 木の高さが同じなら片方を1増やす
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

uf=UnionFind(n)
for i in range(n-1):
    if vvw[i][2]%2==1:
        uf.union(vvw[i][0], vvw[i][1])

# for i in range(1,n+1):
    # print(uf.find(i))
ans=[100]*n
for i in range(1,n+1):
    # print(ans)
    if uf.find(i)==i:
        print(0)
        ans[i-1]=0
    else:
        # print(uf.par[i])
        if ans[uf.find(i)-1]==0:
            print(1)
            ans[i-1]=1
        else:
            print(0)
            ans[i-1]=0

Submission status: Wrong Answer

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

class UnionFind:
    def __init__(self, n):
        # 親要素のノード番号を格納。par[x] == xの時そのノードは根
        self.par = [i for i in range(n+1)]
        # 木の高さを格納する（初期状態では0）
        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 same_check(self, x, y):
        return self.find(x) == self.find(y)

    # 併合
    def union(self, x, y):
        # 根を探す
        x = self.find(x)
        y = self.find(y)
        # 木の高さを比較し、低いほうから高いほうに辺を張る
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            # 木の高さが同じなら片方を1増やす
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

uf=UnionFind(n)
for i in range(n-1):
    if vvw[i][2]%2==1:
        uf.union(vvw[i][0], vvw[i][1])

ans=[100]*n
for i in range(1,n+1):
    # print(ans)
    if uf.find(i)==i:
        print(0)
        ans[i-1]=0
    else:
        # print(uf.par[i])
        if ans[uf.find(i)-1]==1:
            print(1)
            ans[i-1]=1
        else:
            print(0)
            ans[i-1]=0

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(1000000)

n = int(input())
lis = [[] for i in range(n)]

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

li = [-1] * n

def calc(i,c):
    li[i] = c
    for j, w in lis[i]:
        if li[j] < 0:
            calc(j, li[i]^w)

calc(0,0)
print(li)
for d in li:
    print(d)

Submission status: Wrong Answer

Solution code:
N = int(input())
INF = 10**10
dis = [INF]*N
dis[0] = 0
G = [[] for _ in range(N)]
for _ in range(N-1):
	u, v, w = map(int, input().split())
	u -= 1
	v -= 1
	G[u].append((v, w))
	G[v].append((u, w))

queue = [0]
idx = 1

while queue:
	u = queue.pop()
	for v, w in G[u]:
		if dis[v] > dis[u] + w:
			idx += 1
			queue.append(v)
			dis[v] = dis[u] + w

for i in dis:
	print(i % 2)

Submission status: Wrong Answer

Solution code:
N = int(input())
INF = 10**10
dis = [INF]*N
dis[0] = 0
G = [[] for _ in range(N)]
for _ in range(N-1):
	u, v, w = map(int, input().split())
	u -= 1
	v -= 1
	G[u].append((v, w))
	G[v].append((u, w))

queue = [0]
idx = 1

while queue:
	u = queue.pop()
	for v, w in G[u]:
		if dis[v] > dis[u] + w:
			idx += 1
			queue.append(v)
			dis[v] = dis[u] + w
		if idx == N:
			break
	if idx == N:
		break

for i in dis:
	print(i % 2)

Submission status: Wrong Answer

Solution code:
N = int(input())
e = []
d = [0] * N
for _ in range(N - 1):
  e.append(list(map(int, input().split())))
e.sort(key = lambda x: x[0])
temp = 0
for i in range(1, N):
  #print(i)
  for j in range(temp, N - 1):
    #print(i, j)
    if e[j][0] == i:
      if i == j + 1:
        d[e[j][1] - 1] = e[j][2]
      else:
        d[e[j][1] - 1] = e[i - 1][2] + e[j][2]
      #print(j, d[j])
    else:
      temp = j
      break
#print(d)
for x in d:
  if x % 2 == 0:
    print(0)
  else:
    print(1)

Submission status: Wrong Answer

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

A = [0] * (N+1)
L.sort()
for i in L:
    if i[2]%2 != 0 and A[i[0]] == A[i[1]]:
        A[i[1]] = (A[i[1]]+1)%2
    elif i[2]%2 == 0:
        A[i[1]] = A[i[0]]
for i in A[1::]:
    print(i)

Submission status: Wrong Answer

Solution code:
n = int(input())
array = [0] * n
dic = {}
distance = {}

def main():
  for i in range(n-1):
    a, b, c = map(int, input().split())
    if (a-1) in dic:
      dic[a-1].append(b-1)
    else:
      dic[a-1] = [b-1]
    
    distance[','.join(map(str,([a-1, b-1])))] = c
      
  func(dic[0],0)
  
  for i in array:
    print(i)
    
  
def func(arr, num):
  for i in arr:
    if distance[','.join(map(str,([num, i])))] % 2 == 0:
      array[i] = array[num]
    else:
      array[i] = (array[num]+1) % 2
    
    if i in dic:
      func(dic[i], i)
  
    
main()

Submission status: Wrong Answer

Solution code:
def main():
  n = int(input())
  array = [0] * n
  
  for i in range(n-1):
    a, b, c = map(int, input().split())
    if c % 2 == 0:
      array[b-1] = array[a-1]
    else:
      array[b-1] = (array[a-1]+1) % 2
  
  for i in array:
    print(i)
    
main()

Submission status: Wrong Answer

Solution code:
n = int(input())
l = []
c = [0]*n
for i in range(n-1):
    u = list(map(int,input().split()))
    if u[2] % 2 == 1:
        l.append(u)
l.sort(key=lambda x:x[0])
for i in range(len(l)):
    if c[l[i][0]] == 0:
        c[l[i][1]-1] = 1
    else:
        c[l[i][1]-1] == 0
for i in range(n):
    print(c[i])

Submission status: Wrong Answer

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

for u, v, w in uvw:
    if w % 2 == 0:
        tree[u - 1] = 1
        tree[v - 1] = 1

for i in tree:
    print(i)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
def ii(): return int(input())
def mi(): return map(int, input().rstrip().split())
def lmi(): return list(map(int, input().rstrip().split()))
def li(): return list(input().rstrip())
# template

# BEGIN CUT HERE
from queue import Queue
def bfs(field, sy, sx, wall, dir):
    h = len(field)
    w = len(field[0])
    dp = [[-1 for _j in range(w)] for _i in range(h)]
    q = Queue()

    dp[sy][sx] = 0
    q.put((sy, sx))
    
    dy = [1, -1, 0, 0, 1, 1, -1, -1]
    dx = [0, 0, 1, -1, 1, -1, 1, -1]
    def isin(x,y): return 0 <= y and y < h and 0 <= x and x < w
    
    while not q.empty():
        y, x = q.get()
        for k in range(dir):
            ny,nx = y+dy[k],x+dx[k]
            if not isin(nx, ny) or field[ny][nx] == wall:
                continue
            elif dp[ny][nx] != -1:
                continue
            dp[ny][nx] = dp[y][x] + 1
            q.put((ny,nx))
        
    return dp
    
# END CUT HERE

def ABC088_D():
    h, w = mi()
    s = [['' for _j in range(w)] for _i in range(h)]
    for i in range(h):
        s[i] = li()
    dp = bfs(s, 0, 0, '#', 4)
    if dp[h - 1][w - 1] < 0:
        print(-1)
    else:
        cnt = 0
        for i in range(h):
            for j in range(w):
                cnt += s[i][j] == '.'
        print(cnt - (dp[h - 1][w - 1] + 1)) # 0-indexed
# verified on 2019/06/13
# Python3:29ms https://atcoder.jp/contests/abc088/submissions/5898220
# Pypy3:239ms https://atcoder.jp/contests/abc088/submissions/5898207
# https://atcoder.jp/contests/abc088/tasks/abc088_d

def ATC002_A():
    R, C = mi()
    sy, sx = mi()
    gy, gx = mi()
    s = [['' for _j in range(C)] for _i in range(R)]
    for i in range(R):
        s[i] = li()
    dp = bfs(s, sy-1, sx-1, '#', 4) # 0-indexed
    print(dp[gy-1][gx-1]) # 0-indexed

# グリッドでないbfs
def ABC126_D():
    N= ii()
    G = [[] for i in range(N)]
    for i in range(N-1):
        a, b, w = mi()
        a -= 1
        b -= 1
        if w%2==1:
            G[a].append(b)
            G[b].append(a)
    is_bipartite = True
    dist = [-1 for _ in range(N)]
    que = Queue()
    for v in range(N):
        if dist[v] != -1:
            # v が探索済ならスルー
            continue
        dist[v] = 0
        que.put(v)
        while not que.empty():
            v = que.get()
            for nv in G[v]:
                if dist[nv] == -1:
                    dist[nv] = dist[v] + 1
                    que.put(nv)
                else:
                    # 二部グラフであることの整合性を確認
                    # 隣接するノードの偶奇が同じ場合はマズい（distの差はせいぜい1なので，偶奇判定は一致判定と同値）
                    if dist[v] == dist[nv]:
                        is_bipartite = False
    for i in dist:
        if i % 2 == 0:
            print(0)
        else:
            print(1)


if __name__ == '__main__':
    # ABC088_D()
    # ATC002_A()
    ABC126_D()

Submission status: Wrong Answer

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

for i in range(N-1):
    inf = input().split()
    u = int(inf[0])
    v = int(inf[1])
    w = int(inf[2])
    dic[u] += [(v,w)]
    dic[v] += [(u,w)]


k = 1
dist = [-1 for i in range(N)]
stack = []
dist[0] = 0

stack += [k]

while stack:
    u = stack.pop(-1)
    for inf in dic[u]:
        if dist[inf[0]-1]==-1:
            dist[inf[0]-1] += dist[u-1]+inf[1]
            stack.append(inf[0])

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

Submission status: Wrong Answer

Solution code:
import sys
from operator import itemgetter

input = sys.stdin.readline
N = int(input().strip())

querys = []
for i in range(N-1):
    u, v, w = map(int, input().strip().split())
    querys.append((min(u, v), max(u, v), w % 2))
querys.sort(key=itemgetter(0))
ans = [0] * (N+1)

for u, v, w in querys:
    if w == 0:
        pass
    else:
        ans[v] = (ans[u]+1) % 2

for color in ans[1:]:
    print(color)