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=[list(map(int,input().split())) for _ in range(n-1)]
uvw=[[u-1,v-1,w] for u,v,w in uvw]
uvw=sorted(uvw,key=lambda x:x[0])

res=[-1 for _ in range(n)]
j=True
for u,v,w in uvw:
    if w%2!=0:
        j=False
        res[u]=0
        res[v]=1
        break
if j:
    res[0]=0
for u,v,w in uvw:
    if w%2==0:
        if res[u]>=0:
            res[v]=res[u]
        elif res[v]>=0:
            res[u]=res[v]
for u,v,w in uvw:
    if w%2!=0:
        if res[u]==0:
            res[v]=1
        elif res[u]==1:
            res[v]=0
        elif res[v]==0:
            res[u]=1
        elif res[v]==1:
            res[u]=0
for u,v,w in uvw:
    if w%2==0:
        if res[u]>=0:
            res[v]=res[u]
        elif res[v]>=0:
            res[u]=res[v]
for u,v,w in uvw:
    if w%2!=0:
        if res[u]==0:
            res[v]=1
        elif res[u]==1:
            res[v]=0
        elif res[v]==0:
            res[u]=1
        elif res[v]==1:
            res[u]=0
for ans in res:
    print(ans)

Submission status: Wrong Answer

Solution code:
N=int(input())
t=1
u=[]
v=[]
w=[]
while t<N:
    a,b,c=(int(x) for x in input().split())
    u.append(a)
    v.append(b)
    w.append(c)
    t=t+1
ans=[0]*N
for n in range(N):
    for l in range(N-1):
        if w[l]==n:
            if w[l]%2==1:
                ans[v[l]-1]=1
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())

BLACK = -1
GRAY = 0
WHITE = 1
nodes = [GRAY] * N
nodes[0] = BLACK
neighbors = [[] for _ in range(N)]

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

for u in range(N):
    neiss = neighbors[u]
    for neis in neiss:
        v, w = neis
        if nodes[u] == GRAY and nodes[v] == GRAY:
            next
        if nodes[u] == GRAY:
            if w % 2 == 0:
                nodes[u] = nodes[v]
            else:
                nodes[u] = -nodes[v]
        if nodes[v] == GRAY:
            if w % 2 == 0:
                nodes[v] = nodes[u]
            else:
                nodes[v] = -nodes[u]

for u in range(N):
    neiss = neighbors[u]
    for neis in neiss:
        v, w = neis
        if nodes[u] == GRAY and nodes[v] == GRAY:
            next
        if nodes[u] == GRAY:
            if w % 2 == 0:
                nodes[u] = nodes[v]
            else:
                nodes[u] = -nodes[v]
        if nodes[v] == GRAY:
            if w % 2 == 0:
                nodes[v] = nodes[u]
            else:
                nodes[v] = -nodes[u]

for u in range(N):
    neiss = neighbors[u]
    for neis in neiss:
        v, w = neis
        if nodes[u] == GRAY and nodes[v] == GRAY:
            next
        if nodes[u] == GRAY:
            if w % 2 == 0:
                nodes[u] = nodes[v]
            else:
                nodes[u] = -nodes[v]
        if nodes[v] == GRAY:
            if w % 2 == 0:
                nodes[v] = nodes[u]
            else:
                nodes[v] = -nodes[u]

for n in nodes:
    if n == BLACK:
        print(0)
    else:
        print(1)

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]
bl=set()
wh=set()
for u,v,w in odd:
    if u in bl or v in wh:
        bl.add(u)
        wh.add(v)
    else:
        wh.add(u)
        bl.add(v)
for u,v,w in even:
    if u in bl or v in bl:
        bl.add(u)
        bl.add(v)
    else:
        wh.add(u)
        wh.add(v)
for i in range(1,n+1):
    print(0 if i in wh else 1)

Submission status: Wrong Answer

Solution code:
n = int(input())

N = []
ANS  = [1] *n
for i in range(n-1):
    a, b, c = map(int, input().split())
    if(c%2 == 0):
        ANS[a-1] = 0
        ANS[b-1] = 0
for i in ANS:
    print(i)

Submission status: Wrong Answer

Solution code:
def gcd_core(a, b):
    if b == 0:
        return a
    else:
        return gcd_core(b, a % b)


def gcd(arr):
    g = gcd_core(arr[0], arr[1])
    for i in range(2, len(arr)):
        g = gcd_core(g, arr[i])
    return g

n = int(input())
color = {}
u,v,w = map(int,input().split())

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

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

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

Submission status: Wrong Answer

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

# 奇数のノードを色を変える
tree_color = [-1 for _ in range(N)]
color = 0
for uvw in UVW:
    u = uvw[0] - 1
    v = uvw[1] - 1
    w = uvw[2]
    if tree_color[u] == -1:
        tree_color[u] = color
    else:
        color = tree_color[u]
    if w % 2 == 1:
        color = 1 - color
    tree_color[v] = color
    #print(uvw, tree_color)

for tc in tree_color:
    print(tc)

Submission status: Wrong Answer

Solution code:
def printAns(ans):
    for i in range(len(ans)):
        print(ans[i])

n = int(input())
ans = [0 for k in range(n)]
u = []
v = []
for i in range(n-1):
    tmpU, tmpV, tmpW = map(int, input().split())
    if(tmpW%2!=0):
        u.append(tmpU)
        v.append(tmpV)

if(len(u)==0):
    printAns(ans)
else:
    for i in range(len(u)):
        if(ans[u[i]-1]==0):
            ans[v[i]-1] = 1
        else:
            ans[v[i]-1] = 0
    printAns(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
W = []
for _ in range(N - 1):
    u, v, w = map(int, input().split())
    W.append([u, v, w])
tree = [0] * N
for l in W:
    u, v, w = l
    a = max(u, v) - 1
    b = min(u, v) - 1
    if tree[a] == tree[b]:
        if w % 2 == 1:
            tree[a] = 1 if tree[b] == 0 else 0
    elif w % 2 == 0:
        tree[a] = tree[b]
for t in tree:
    print(t)

Submission status: Wrong Answer

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


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

    visited[0] = 1
    
    Q = queue.Queue()
    Q.put(0)
    while not Q.empty() > 0:
        u = Q.get()
        for v, w in adjacent[u]:
            if visited[v]:
                continue
            if w == 0:
                color[v] = color[u]
            else:
                color[v] = (color[u] + 1) % 2
            visited[v] = 1
            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())
oy = [0] * (n + 1)
dif = [0] * (n + 1)
hen = []
for i in range(n - 1):
    hen.append(list(map(int, input().split())))

hen.sort()

for i in range(n - 1):
    u = hen[i][0]
    v = hen[i][1]
    w = hen[i][2]
    if oy[u] == 0:
        if oy[v] == 0:
            oy[u] = v
            oy[v] = v
        else:
            oy[u] = oy[v]
        dif[u] = dif[v] + w
    else:
        if oy[v] == 0:
            oy[u] = u
            oy[v] = oy[u]
            dif[v] = dif[u] + w

for i in range(1, n + 1):
    print(dif[i] % 2)

Submission status: Wrong Answer

Solution code:
N=int(input())
color=[-1]*N
from collections import defaultdict
branch=defaultdict(dict)
check=[]
for i in range(N-1):
    u,v,w=map(int,input().split())
    branch[u-1][v-1]=w
    branch[v-1][u-1]=w
    if w%2==1:
        check+=[u-1,v-1]
check={0,}
visited=set()
color[0]=0
while len(check)>0:
    now=check.pop()
    visited|={now}
    for nex,w in branch[now].items():
        if nex in visited:
            continue
        check|={nex}
        if w%2==1:
            if color[now]==color[nex]==-1:
                color[now]=0
                color[nex]=1
            elif color[now]==-1:
                color[now]=(color[nex]+1)%2
            elif color[nex]==-1:
                color[nex]=(color[now]+1)%2
color=[i if i!=-1 else 0 for i in color]
for i in range(N):
    print(color[i])

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
N = int(input())
g = defaultdict(list)
ans = [None] * N
for i in range(N-1):
    u, v, w = map(int, input().split())
    if w % 2 == 0:
        if ans[u-1] is None and ans[v-1] is None:
            ans[u-1] = ans[v-1] = 1
        elif ans[u-1] is not None:
            ans[v-1] = ans[u-1]
        elif ans[v-1] is not None:
            ans[u-1] = ans[v-1]
        else:
            pass
    else:
        if ans[u-1] is None and ans[v-1] is None:
            ans[u-1] = 1
            ans[v-1] = 0
        elif ans[u-1] is not None:
            ans[v-1] = (ans[u-1] + 1) % 2
        elif ans[v-1] is not None:
            ans[u-1] = (ans[v-1] + 1) % 2
        else:
            pass
        
for a in ans:
    print(a)

Submission status: Wrong Answer

Solution code:
N = int(input())-1
vw = [list(map(int, input().split())) for _ in range(N)]
a = set()
for i in range(N):
    if vw[i][2] % 2 == 1:
        a.add(vw[i][0])
        a.add(vw[i][1])

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

Submission status: Wrong Answer

Solution code:
N = int(input())
tree = {}
for i in range(N-1):
    u, v, w = map(int, input().split())
    tree[u, v] = w % 2
bw = [0 for i in range(N+1)]
flag = True
isodd = -1
for key, value in tree.items():
    if flag:
        flag = False
        isodd = value
        bw[key[0]] = 1
        bw[key[1]] = 1
    elif value == isodd:
        bw[key[0]] = 1
        bw[key[1]] = 1
for x in bw[1:]:
    print(x)

Submission status: Wrong Answer

Solution code:
N = int(input())
T = [tuple(map(int, input().split())) for _ in range(N-1)]
V = [[] for _ in range(N+1)]
check = [0]*(N+1)
color = [0]*(N+1)
for u, v, w in T:
    V[u].append((v, w))
    V[v].append((u, w))

color[1] = 1
check[1] = 1
queue = V[1]
last_color = 1
while queue:
    u, w = queue.pop()
    if check[u]:
        continue
    else:
        check[u] = 1
        if w % 2:
            if last_color:
                last_color = 0
            else:
                last_color = 1
        color[u] = last_color
        for next_u, next_w in V[u]:
            queue.append((next_u, next_w))

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

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

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

N = int(input())
ans = [0]*N
done = [True]*N
for _ in range(N-1):
    u,v,w = [int(i) for i in input().split()]
    if w%2 == 0:
        if done[u-1]:
            ans[u-1] = ans[v-1]
        else:
            ans[v-1] = ans[u-1]
    else:
        if done[u-1]:
            ans[u-1] = ans[v-1]^1
        else:
            ans[v-1] = ans[u-1]^1
    done[u-1] = False
    done[v-1] = False

[print(i) for i in ans]

Submission status: Wrong Answer

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

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

N = INT()
uvw = [LIST() for _ in range(N-1)]
uvw.sort(key=lambda x:(x[0], x[1]))
color = [0]*N
searched = [0]*N
color[0] = -1  # 0番目のノードを-1で初期化
searched[0] = 1
for u, v, w in uvw:
	# print(u, v, w)
	if searched[v-1] == 1:
		u, v = v, u
	if w % 2 == 0:
		color[v-1] = color[u-1]
		searched[v-1] = 1
	else:
		color[v-1] = color[u-1] * -1
		searched[v-1] = 1
# print(color)
for i in color:
	if i == -1:
		print(0)
	else:
		print(1)

Submission status: Wrong Answer

Solution code:
n = int(input())

N = []
ANS  = [1] *n
for i in range(n-1):
    a, b, c = map(int, input().split())
    if(c%2 == 0):
        ANS[a-1] = 0
        ANS[b-1] = 0
print(ANS)

Submission status: Wrong Answer

Solution code:
n = int(input())
l = list("0" * n)
l1 = []
for i in range(n-1):
  u, v, w = map(int,input().split())
  if w % 2 == 0:
    l[u-1] = "0"
    l[v-1] = "0"
    l1.append(u)
    l1.append(v)
  else:
    if u in l1:
      l[u-1] = "0"
      l[v-1] = "1"
    elif v in l1:
      l[u-1] = "1"
      l[v-1] = "0"
for i in l:
  print(i)

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

Solution code:
N = int(input())

BLACK = -1
GRAY = 0
WHITE = 1
nodes = [GRAY] * N
nodes[0] = BLACK
neighbors = [[] for _ in range(N)]

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

for u in range(N):
    neiss = neighbors[u]
    for neis in neiss:
        v, w = neis
        if nodes[u] == GRAY and nodes[v] == GRAY:
            next
        if nodes[u] == GRAY:
            if w % 2 == 0:
                nodes[u] = nodes[v]
            else:
                nodes[u] = -nodes[v]
        if nodes[v] == GRAY:
            if w % 2 == 0:
                nodes[v] = nodes[u]
            else:
                nodes[v] = -nodes[u]

for n in nodes:
    if n == BLACK:
        print(0)
    else:
        print(1)

Submission status: Wrong Answer

Solution code:
class UnionFind(object):

    def __init__(self, N):
        self.tree = [i for i in range(N)]
        self.rank = [0] * (N + 1)

    def find(self, x):
        if self.tree[x] == x:
            return x
        else:
            self.tree[x] = self.find(self.tree[x])  # 経路圧縮
            return self.tree[x]

    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)

        # ランクを考慮しない場合はどちらが親になっても良い
        if self.rank[x] < self.rank[y]:
            self.tree[x] = y
        else:
            self.tree[y] = x

        if self.rank[x] == self.rank[y]:
            self.rank[x] += 1

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


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

unionfind = UnionFind(N + 1)
for u, v, w in UVW:
    if w % 2 == 0:
        unionfind.unite(u, v)

color = unionfind.tree[1]
for num in unionfind.tree[1:]:
    if num == color:
        print(0)
    else:
        print(1)

Submission status: Wrong Answer

Solution code:
n=int(input())
q=[list(map(int,input().split())) for i in range(n-1)]
bl=set()
wh=set()
for u,v,w in q:
    if w%2==0:
        if u in bl or v in bl:
            bl.add(u)
            bl.add(v)
        else:
            wh.add(u)
            wh.add(v)
    else:
        if u in bl or v in wh:
            bl.add(u)
            wh.add(v)
        else:
            wh.add(u)
            bl.add(v)

for i in range(1,n+1):
    print(0 if i in wh else 1)

Submission status: Wrong Answer

Solution code:

from collections import defaultdict


def main():
    num = int(input())
    color_dic = [-1 for i in range(num + 1)]

    data_dic = defaultdict(set)

    for i in range(num - 1):
        u, v, w = map(int, input().split())
        if w % 2 == 1:
            max_data, min_data = max(u, v), min(u, v)
            data_dic[min_data].add(max_data)

    change_dic = {1:0, 0:1}

    # print(data_dic)

    for i in range(1, num + 1):
        if i in data_dic:

            list_data = data_dic[i]

            my_color = 0
            aite_color = 1

            for ele in list_data:
                if color_dic[ele] != -1:
                    aite_color = color_dic[ele]
                    my_color = change_dic[aite_color]
                    break

            for ele in list_data:
                color_dic[ele] = aite_color
            color_dic[i] = my_color
        else:
            if color_dic[i] == -1:
                color_dic[i] = 0

    # print(color_dic)

    for i in range(num):
        print(color_dic[i + 1])






if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
N = int(input())
Vs = []
for _ in range(N-1):
    Vs.append([int(i) for i in input().split()])
Ws = [None for _ in range(N)]
Ws[Vs[0][0]] = True
for ui, vi, wi in Vs:
    ui, vi = ui-1, vi-1
    if Ws[ui] != None and Ws[vi] == None:
        if wi % 2 == 0:
            Ws[vi] = Ws[ui]
        else:
            Ws[vi] = not Ws[ui]
    elif Ws[ui] == None and Ws[vi] != None:
        if wi % 2 == 0:
            Ws[ui] = Ws[vi]
        else:
            Ws[ui] = not Ws[vi]
for w in Ws:
    if w:
        print(0)
    else:
        print(1)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict 
                
N = int(input()) 
 
dd = defaultdict(list)
for _ in range(N-1): 
    u, v, w = map(int, input().split())
    dd[u].append((v, w)) 
    dd[v].append((u, w))
 
colorDict = defaultdict(int)
for i, key in enumerate(dd):
    if i == 0:
        colorDict[key] = 1 
    for ew in dd[key]:
        e, w = ew
        if colorDict[e] == 0:
            colorDict[e] = 1 if w % 2 == 0 else 2

for k, v in sorted(colorDict.items()):
    print(str(v - 1))

Submission status: Wrong Answer

Solution code:
from collections import deque
import sys
import math
sys.setrecursionlimit(10**6)
from collections import defaultdict

#n,k=map(int,input().split())from collections import deque
n=int(input())
g=[[] for i in range(1+n)]
v=[0]*(1+n)
c=[0]*(1+n)
flg=False
for i in range(n-1):
    a,b,w=map(int,input().split())
    g[a].append((b,w))
    g[b].append((a,w))
    if w%2==1:
        flg=True
#print(c,v,g)

def bfs(x):
    if v[x]!=0:
        return
    q=deque()
    q.append(x)
    v[x]=1
    while len(q)>0:
        cur=q.popleft()
        #v[ch][cw]=1
    
        for nei in g[cur]:
            y=nei[0]
            d=nei[1]
            if v[y]==0:
                q.append(y)
                v[y]=1
                if d%2==1:
                    c[y]=1-c[x]
                else:
                    c[y]=c[x]
        #print('xy=',x,y,'d=',d,'c=',c)

c[1]=0
bfs(1)

for i in range(1,n+1):
    print(c[i])
#print(c,v)

Submission status: Wrong Answer

Solution code:
N = int(input())
edges = [list(map(int, input().split(" ")))
         for _ in range(N - 1)]
colors = [None] * N
colors[0] = 0

while edges:
    remains = []
    for m, n, l in edges:
        if colors[m - 1] is None and colors[n - 1] is None:
            remains.append([m, n, l])
        if colors[m - 1] is not None:
            i, j = n - 1, m - 1
        else:
            i, j = m - 1, n - 1
        if l % 2 == 0:
            colors[i] = colors[j]
        else:
            colors[i] = int(not colors[j])
    edges = remains

for c in colors:
    print(c)

Submission status: Wrong Answer

Solution code:
from collections import deque
d = {}
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])%2

n = int(input())
uni = WeightedUnionFind(n)
for i in range(n-1):
    a,b,c=map(int,input().split())
    uni.union(a-1,b-1,c)
for i in range(n):
    print(uni.diff(0,i))

Submission status: Wrong Answer

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

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

zero = set()
one = set()

for i in range(n-1):
    zero.add(i+1)
    for j in graph[i]:
        if graph[i][j]%2 == 0:
            zero.add(j)
        else:
            one.add(j)

for i in range(1, n+1):
    if i in zero:
        print(0)
    else:
        print(1)

Submission status: Wrong Answer

Solution code:
n = int(input())

edges = []
for i in range(n-1):
	edges.append(list(map(int, input().split())))
edges = sorted(edges, key=lambda x: x[0])

colors = [-1]*n
for edge in edges:
	u, v, w = edge
	if colors[u-1]==-1:
		colors[u-1]=0

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

for i in colors:
	if i==-1:
		print(0)
	else:
		print(i)

Submission status: Wrong Answer

Solution code:
n = int(input())

N = []
ANS  = [0] *n
for i in range(n-1):
    a, b, c = map(int, input().split())
    if(c%2 == 0):
        ANS[a-1] = 1
        ANS[b-1] = 1
print(ANS)

Submission status: Wrong Answer

Solution code:
N = int(input())

sss = []
for _ in range(N - 1):
    u, v, w = [int(s) for s in input().split()]
    sss.append((u, v, w))
sss = sorted(sss)

vec = [None for _ in range(N)]
for u, v, w in sss:
    u, v = u - 1, v - 1
    if vec[u] is None and vec[v] is None:
        vec[u] = False
    elif vec[u] is None:
        u, v = v, u
    vec[v] = vec[u] ^ (w % 2 == 1)

for v in vec:
    print(1 if v else 0)

Submission status: Wrong Answer

Solution code:
N=int(input())
color=[-1]*N
from collections import defaultdict
branch=defaultdict(dict)
check=[]
for i in range(N-1):
    u,v,w=map(int,input().split())
    branch[u-1][v-1]=w
    branch[v-1][u-1]=w
    if w%2==1:
        check+=[u-1,v-1]
check={0,}
visited=set()
color[0]=0
while len(check)>0:
    now=check.pop()
    visited|={now}
    for nex,w in branch[now].items():
        if nex in visited:
            continue
        check|={nex}
        color[nex]=(color[now]+1)%2
color=[i if i!=-1 else 0 for i in color]
for i in range(N):
    print(color[i])

Submission status: Wrong Answer

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

for _ in range(n-1):
    u, v, w = map(int, input().split())
    graph[u-1][v] = w
print(graph)
zero = set()
one = set()

for i in range(n-1):
    zero.add(i+1)
    for j in graph[i]:
        if graph[i][j]%2 == 0:
            zero.add(j)
        else:
            one.add(j)

for i in range(1, n+1):
    if i in zero:
        print(0)
    else:
        print(1)

Submission status: Wrong Answer

Solution code:
N=int(input())
tree=[]
diff=[]
ans=[0 for i in range(N+1)]
for i in range(N-1):
    tmp=list(map(int,input().split()))
    if tmp[2]%2==1:
        tree.append(tmp[:2])
        ans[tmp[1]]=1-ans[tmp[0]]
        
for i in ans[1:]:
    print(i)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict 
                
N = int(input()) 
 
dd = defaultdict(list)
for _ in range(N-1): 
    u, v, w = map(int, input().split())
    dd[u].append((v, w)) 
    dd[v].append((u, w))
 
colorDict = defaultdict(int)
for i, key in enumerate(dd):
    if i == 0:
        colorDict[key] = 0
    for ew in dd[key]:
        e, w = ew
        if colorDict[e] == 0:
            colorDict[e] = 1 if w % 2 == 0 else 2

for k, v in sorted(colorDict.items()):
    print(str(v - 1))

Submission status: Wrong Answer

Solution code:
N = int(input())

inputs = []
for n in range(0, N - 1):
	inputs.append(list(map(int,input().split())))


tree = {}
for i in inputs:
	if i[0] in tree:
		tree[i[0]].append({'to': i[1], 'w': i[2]})
	else:
		tree[i[0]] = [{'to': i[1], 'w': i[2]}]


result = [0] * N

for k in tree.keys():
	for leaf in tree[k]:
		if leaf['w'] % 2 == 0:
			result[k - 1] = 1
			result[leaf['to'] - 1] = 1

for r in result:
	print(r)

Submission status: Wrong Answer

Solution code:
# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math

mod = 10**9+7

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

tree = [[] for i in range(N-1)]
for i in range(N-1):
    tree[i] = [u[i],v[i],w[i]]

# print(tree)
tree.sort()
color = [False for i in range(N)]
color[0] = True
for i in range(N-1):
    # print(color)
    if tree[i][2] % 2 == 0:
        color[tree[i][1]-1] = color[tree[i][0]-1]
    else:
        color[tree[i][1]-1] = not(color[tree[i][0]-1])

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

Submission status: Wrong Answer

Solution code:
from collections import deque

N = int(input())
adj = [[] for _ in range(N)]
for _ in range(N-1):
    u,v,w = map(lambda x:int(x)-1, input().split())
    w += 1
    adj[u].append((v,w))
    adj[v].append((u,w))

visited = [False]*N
q = deque([0])
while q:
    cur = q.popleft()
    # print(cur, q)
    if visited[cur]:
        continue
    visited[cur] = True
    for nex, w in adj[cur]:
        if (not visited[nex]) and (w%2==0):
            q.append(nex)

for v in visited:
    print(1 if v else 0)

Submission status: Wrong Answer

Solution code:
N = int(input())
l = list("k"*N)
for  i in range(N-1):
        a,b,c=map(int, input().split())
        if l[a-1]=="k" and l[b-1]=="k":
                if c%2==0:
                        l[a-1]=0
                        l[b-1]=0
                else:
                        l[a-1]=0
                        l[b-1]=1
        elif l[a-1]=="k":
                if c%2==0:
                        l[a-1]=l[b-1]
                else:
                        l[a-1]=abs(l[b-1]-1)
        elif l[b-1]=="k":
                if c%2==0:
                        l[b-1]=l[a-1]
                else:
                        l[b-1]=abs(l[a-1]-1)
for i in l:
        print(i)

Submission status: Wrong Answer

Solution code:
from sys import stdin
import math
import fractions
from collections import deque

INF = 10 ** 10
WHITE = 0
BLACK = 1

# N <= 10^5
N = int(stdin.readline().rstrip())
data = [list(map(int, stdin.readline().rstrip().split())) for _ in range(N-1)]
color = [0] * (N+1)
data.sort(key=lambda x: (x[0], x[1]))

# 同じ色に塗られた任意の2頂点について、その距離が偶数である
for u, v, w in data:
    # 距離が偶数
    if w % 2 == 0:
        color[v] = color[u]
    else:
        color[v] = (color[u] + 1) % 2

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

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

N = int(input())

D = defaultdict(list) 
S = defaultdict(lambda: -1) #STEPD
R = defaultdict(int) #ROOT
for i in range(N-1):
    u,v,w = map(int,input().split())
    D[u].append(v)
    D[v].append(u)
    R["{}-{}".format(u,v)] = w
    
T = [(1,0)]
S[1] = 0
while T:
    n,w = T.pop()
    for d in D[n]:
        wr = R["{}-{}".format(n,d)]
        if S[d]>=0:continue
        else: S[d] = (w+wr)%2
        T.append((d,(w+wr)%2))
        
for k in sorted(S.keys()):
    print(S[k])

Submission status: Wrong Answer

Solution code:
#paint black(1)

n = int(input())

ans = [0] * n

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

Submission status: Wrong Answer

Solution code:
N = int(input())
edges = [list(map(int,input().split())) for _ in range(N-1)]
adj_dict = {i:{} for i in range(1,N+1)}

for edge in edges:
    adj_dict[edge[0]][edge[1]] = edge[2]
    adj_dict[edge[1]][edge[0]] = edge[2]

color_dict = {}
flag = 0

for node0 in adj_dict:
    if node0 not in color_dict:
        color_dict[node0] = 0

    # if flag == 0:
    #     color_dict[node0] = 0
    #     flag = 1
    for node1 in adj_dict[node0]:
        if node1 not in color_dict:
            if adj_dict[node0][node1] % 2 == 0:
                color_dict[node1] = color_dict[node0]
            else:
                color_dict[node1] = (color_dict[node0]+1)%2
            if len(color_dict) == N:
                break

for node in color_dict:
    print(color_dict[node])

Submission status: Wrong Answer

Solution code:
N = int(input())
edge = sorted([tuple(map(int, input().split())) for _ in range(N-1)])
color = [0]*N

for u, v, w in edge:
    if w % 2 == 1 and color[u-1] == color[v-1]:
        color[v-1] ^= 1
    elif w % 2 == 0 and color[u-1] != color[v-1]:
        color[v-1] ^= 1

print(*color, sep='\n')