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

N = int(input())
V = [list(map(int, line.split())) for line in sys.stdin.readlines()]

TABLE = [[-1] * N for _ in range(N)]

for v1, v2, w in V:
    TABLE[v1-1][v2-1] = w

def dfs(i, results):
    for j in range(N):
        if TABLE[i][j] >= 0 and TABLE[i][j] % 2 == 0:
            results[j] = results[i]
            TABLE[i][j] = -1
            results = dfs(j, results)

    return results

results = [0] * N
for i in range(N):
    if max(TABLE[i]) > 0:
        results[i] = 1
        for r in dfs(i, results):
            print(r)
        
        break

Submission status: Wrong Answer

Solution code:
import sys
import re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
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()
U = []
V = []
W = []
for i in range(N-1):
    u, v, w = MAP()
    U.append(u)
    V.append(v)
    W.append(w)

graph = [[] for _ in range(N)]
for u, v, w in zip(U, V, W):
    graph[u-1].append((v-1, w))
    graph[v-1].append((u-1, w))

c = [0] * N

for i in range(N):
    for j in range(len(graph[i])):
        if c[i] + c[graph[i][j][0]] == 0 and graph[i][j][1] % 2 == 1:
                c[graph[i][j][0]] = 1

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

Submission status: Wrong Answer

Solution code:
import sys

N = int(input())
V = [list(map(int, line.split())) for line in sys.stdin.readlines()]

TABLE = [[-1] * N for _ in range(N)]

for v1, v2, w in V:
    TABLE[v1-1][v2-1] = w

def dfs(i, results):
    for j in range(N):
        if TABLE[i][j] >= 0 and TABLE[i][j] % 2 == 0:
            results[j] = results[i]
            TABLE[i][j] = -1
            results = dfs(j, results)
            break

    return results

results = [0] * N
for i in range(N):
    if max(TABLE[i]) > 0:
        results[i] = 1
        for r in dfs(i, results):
            print(r)
        
        break

Submission status: Wrong Answer

Solution code:
import sys

N = int(input())
V = [list(map(int, line.split())) for line in sys.stdin.readlines()]

TABLE = [[-1] * N for _ in range(N)]

for v1, v2, w in V:
    TABLE[v1-1][v2-1] = w

def dfs(i, results):
    for j in range(N):
        if TABLE[i][j] >= 0 and TABLE[i][j] % 2 == 0:
            print(results, i, j, TABLE[i][j])
            results[j] = results[i]
            TABLE[i][j] = -1
            results = dfs(j, results)
            break

    return results

results = [0] * N
for i in range(N):
    if max(TABLE[i]) > 0:
        results[i] = 1
        for r in dfs(i, results):
            print(r)
        
        break

Submission status: Wrong Answer

Solution code:
import math
import fractions
import bisect
import collections
import itertools
import heapq
import string
import sys
import copy
from collections import deque
sys.setrecursionlimit(10**7)
MOD = 10**9+7
INF = float('inf') #無限大
def gcd(a,b):return fractions.gcd(a,b) #最大公約数
def lcm(a,b):return (a*b) // fractions.gcd(a,b) #最小公倍数
def iin(): return int(sys.stdin.readline()) #整数読み込み
def ifn(): return float(sys.stdin.readline()) #浮動小数点読み込み
def isn(): return sys.stdin.readline().split() #文字列読み込み
def imn(): return map(int, sys.stdin.readline().split()) #整数map取得
def imnn(): return map(lambda x:int(x)-1, sys.stdin.readline().split()) #整数-1map取得
def fmn(): return map(float, sys.stdin.readline().split()) #浮動小数点map取得
def iln(): return list(map(int, sys.stdin.readline().split())) #整数リスト取得
def iln_s(): return sorted(iln()) # 昇順の整数リスト取得
def iln_r(): return sorted(iln(), reverse=True) # 降順の整数リスト取得
def fln(): return list(map(float, sys.stdin.readline().split())) # 浮動小数点リスト取得
def join(l, s=''): return s.join(l) #リストを文字列に変換
def perm(l, n): return itertools.permutations(l, n) # 順列取得
def perm_count(n, r): return math.factorial(n) // math.factorial(n-r) # 順列の総数
def comb(l, n): return itertools.combinations(l, n) # 組み合わせ取得
def comb_count(n, r): return math.factorial(n) // (math.factorial(n-r) * math.factorial(r)) #組み合わせの総数
def two_distance(a, b, c, d): return ((c-a)**2 + (d-b)**2)**.5 # 2点間の距離
def m_add(a,b): return (a+b) % MOD

def sieves_of_e(n):
    is_prime = [True] * (n+1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5)+1):
        if not is_prime[i]: continue
        for j in range(i * 2, n+1, i): is_prime[j] = False
    return is_prime

N = iin()

edges = [[] for _ in range(N)]

for _ in range(N-1):
    u,v,w = imn()
    u -= 1
    v -= 1
    edges[u].append((v,w))
    edges[v].append((u,w))

colors = [None] * (N)

def set_color(vertex, color):
    if colors[vertex] != None: return

    colors[vertex] = color
    for v, w in edges[vertex]:
        set_color(v, w%2)

set_color(0, 0)

for c in colors:
    print(c)

Submission status: Wrong Answer

Solution code:
import math
import fractions
import bisect
import collections
import itertools
import heapq
import string
import sys
import copy
from collections import deque
sys.setrecursionlimit(10**7)
MOD = 10**9+7
INF = float('inf') #無限大
def gcd(a,b):return fractions.gcd(a,b) #最大公約数
def lcm(a,b):return (a*b) // fractions.gcd(a,b) #最小公倍数
def iin(): return int(sys.stdin.readline()) #整数読み込み
def ifn(): return float(sys.stdin.readline()) #浮動小数点読み込み
def isn(): return sys.stdin.readline().split() #文字列読み込み
def imn(): return map(int, sys.stdin.readline().split()) #整数map取得
def imnn(): return map(lambda x:int(x)-1, sys.stdin.readline().split()) #整数-1map取得
def fmn(): return map(float, sys.stdin.readline().split()) #浮動小数点map取得
def iln(): return list(map(int, sys.stdin.readline().split())) #整数リスト取得
def iln_s(): return sorted(iln()) # 昇順の整数リスト取得
def iln_r(): return sorted(iln(), reverse=True) # 降順の整数リスト取得
def fln(): return list(map(float, sys.stdin.readline().split())) # 浮動小数点リスト取得
def join(l, s=''): return s.join(l) #リストを文字列に変換
def perm(l, n): return itertools.permutations(l, n) # 順列取得
def perm_count(n, r): return math.factorial(n) // math.factorial(n-r) # 順列の総数
def comb(l, n): return itertools.combinations(l, n) # 組み合わせ取得
def comb_count(n, r): return math.factorial(n) // (math.factorial(n-r) * math.factorial(r)) #組み合わせの総数
def two_distance(a, b, c, d): return ((c-a)**2 + (d-b)**2)**.5 # 2点間の距離
def m_add(a,b): return (a+b) % MOD

def sieves_of_e(n):
    is_prime = [True] * (n+1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5)+1):
        if not is_prime[i]: continue
        for j in range(i * 2, n+1, i): is_prime[j] = False
    return is_prime

N = iin()

edges = [[] for _ in range(N)]

for _ in range(N-1):
    u,v,w = imn()
    u -= 1
    v -= 1
    edges[u].append((v,w))
    edges[v].append((u,w))

colors = [None] * (N)

def set_color(vertex, color):
    colors[vertex] = color
    for v, w in edges[vertex]:
        if colors[v] == None:
            set_color(v, w%2)

set_color(0, 0)

for c in colors:
    print(c)

Submission status: Wrong Answer

Solution code:
import math
import fractions
import bisect
import collections
import itertools
import heapq
import string
import sys
import copy
from collections import deque
sys.setrecursionlimit(10**7)
MOD = 10**9+7
INF = float('inf') #無限大
def gcd(a,b):return fractions.gcd(a,b) #最大公約数
def lcm(a,b):return (a*b) // fractions.gcd(a,b) #最小公倍数
def iin(): return int(sys.stdin.readline()) #整数読み込み
def ifn(): return float(sys.stdin.readline()) #浮動小数点読み込み
def isn(): return sys.stdin.readline().split() #文字列読み込み
def imn(): return map(int, sys.stdin.readline().split()) #整数map取得
def imnn(): return map(lambda x:int(x)-1, sys.stdin.readline().split()) #整数-1map取得
def fmn(): return map(float, sys.stdin.readline().split()) #浮動小数点map取得
def iln(): return list(map(int, sys.stdin.readline().split())) #整数リスト取得
def iln_s(): return sorted(iln()) # 昇順の整数リスト取得
def iln_r(): return sorted(iln(), reverse=True) # 降順の整数リスト取得
def fln(): return list(map(float, sys.stdin.readline().split())) # 浮動小数点リスト取得
def join(l, s=''): return s.join(l) #リストを文字列に変換
def perm(l, n): return itertools.permutations(l, n) # 順列取得
def perm_count(n, r): return math.factorial(n) // math.factorial(n-r) # 順列の総数
def comb(l, n): return itertools.combinations(l, n) # 組み合わせ取得
def comb_count(n, r): return math.factorial(n) // (math.factorial(n-r) * math.factorial(r)) #組み合わせの総数
def two_distance(a, b, c, d): return ((c-a)**2 + (d-b)**2)**.5 # 2点間の距離
def m_add(a,b): return (a+b) % MOD

def sieves_of_e(n):
    is_prime = [True] * (n+1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5)+1):
        if not is_prime[i]: continue
        for j in range(i * 2, n+1, i): is_prime[j] = False
    return is_prime

N = iin()

edges = [[] for _ in range(N+1)]

for _ in range(N-1):
    u,v,w = imn()
    u -= 1
    v -= 1
    edges[u].append((v,w%2))
    edges[v].append((u,w%2))

colors = [None] * (N)

def set_color(vertex, color):
    colors[vertex] = color
    for v, w in edges[vertex]:
        if colors[v] == None:
            set_color(v, w)

set_color(0, 0)

for c in colors:
    print(c)

Submission status: Wrong Answer

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

n=int(input())
a= [list(map(int, input().split())) for i in range(n-1)]

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

for i in range(n-1):
    b[a[i][0]-1].append((a[i][1]-1,a[i][2]))

import collections
from collections import deque

INF = -10 ** 9
dis = [INF for i in range(n)]
ans = [0]*n
def bfs(s):
    d = deque()
    d.append(s)
    dis[s]=0
    ans[s]=0
    flag = True

    while len(d):
        x = d.popleft()

        for i in range(len(b[x])):
            y=b[x][i][0]
            if dis[y] == INF:
                d.append(y)
                dis[y]=dis[x]+b[x][i][1]
                if dis[y]%2==0:
                    ans[y]=0
                else:
                    ans[y]=1
    return ans
z=bfs(0)

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

Submission status: Wrong Answer

Solution code:
N = int(input())

node_edges = {i: {} for i in range(1, N + 1)}
node_colors = {i: None for i in range(1, N + 1)}

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

def paint(i):
    if node_colors[i] is None:
        node_colors[i] = 0

    for u, w in node_edges[i].items():
        if node_colors[u] is None:
            if w == 0:
                node_colors[u] = node_colors[i]
            else:
                node_colors[u] = abs(node_colors[i] - 1)

node_colors[1] = 0
for i in range(1, N + 1):
    paint(i)
    print(node_colors[i])

Submission status: Wrong Answer

Solution code:
N = int(input())

node_edges = {i: {} for i in range(1, N + 1)}
node_colors = {i: None for i in range(1, N + 1)}

for i in range(1, N):
    u, v, w = map(int, input().split())
    node_edges[u][v] = w % 2
    # node_edges[v][u] = w % 2

# print(node_edges)
# print(node_colors)

def dfs(i):
    if node_colors[i] is None:
        node_colors[i] = 0

    for u, w in node_edges[i].items():
        # print(f"i={i}, u={u}, w={w}")
        if node_colors[u] is None:
            if w == 0:
                node_colors[u] = node_colors[i]
            else:
                node_colors[u] = abs(node_colors[i] - 1)
        
    # print(node_colors)

node_colors[1] = 0
for i in range(1, N + 1):
    dfs(i)
    print(node_colors[i])

Submission status: Wrong Answer

Solution code:
"""
3
1 2 2
2 3 1
"""

N = int(input())

node_edges = {i: {} for i in range(1, N + 1)}
node_colors = {i: None for i in range(1, N + 1)}

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


def dfs(i):
    if node_colors[i] is None:
        node_colors[i] = 0

    for u, w in node_edges[i].items():
        if w == 0:
            node_colors[u] = node_colors[i]
        else:
            node_colors[u] = abs(node_colors[i] - 1)

node_colors[1] = 0
for i in range(1, N + 1):
    dfs(i)
    print(node_colors[i])

Submission status: Wrong Answer

Solution code:
"""
3
1 2 2
2 3 1
"""

N = int(input())

node_edges = {i: {} for i in range(1, N + 1)}
node_colors = {i: None for i in range(1, N + 1)}

for i in range(1, N):
    u, v, w = map(int, input().split())
    # 両方向記録した方がいいかもしれない
    node_edges[u][v] = w
    node_edges[v][u] = w


def dfs(i):
    if node_colors[i] is not None:
        color = node_colors[i]
    else:
        color = 0
        node_colors[i] = color

    for u, w in node_edges[i].items():
        if w % 2 == 0:
            node_colors[u] = color
        else:
            node_colors[u] = abs(color - 1)

node_colors[1] = 0
for i in range(1, N + 1):
    dfs(i)

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

Submission status: Wrong Answer

Solution code:
# 全探索 行列だとNがでかすぎて死にそうなのでリストでやる
# 偶奇だけわかればいいので%2する（必要ないけど）
# w=奇数のとき両辺のとりうるのは(1,0)か(0,1)で、ここからキメたほうがよさそう?
# 距離をどういうデータ構造でもてばいいのかわからんぞ....
# あ？偶数と奇数をわけて最初に偶数をキメて次に奇数をキメるのでいいのか？
n = int(input())
arr = [-1 for _ in range(n)]
odd, even = [], []
for _ in range(n - 1):
    u, v, w = map(int, input().split())
    if w % 2 == 0:
        even.append([u - 1, v - 1])
    else:
        odd.append([u - 1, v - 1])

for e in even:
    arr[e[0]] = 0
    arr[e[1]] = 0

while len(odd) > 0:
    rest = []
    for o in odd:
        x, y = o
        if arr[x] < 0 and arr[y] < 0:
            rest.append(o)
        elif arr[x] == 0:
            arr[y] = 1
        elif arr[x] == 1:
            arr[y] = 0
        elif arr[y] == 0:
            arr[x] = 1
        elif arr[y] == 1:
            arr[x] = 0
        else:
            print("fuck")
            print(4 / 0)
    odd = rest
for a in arr:
    print(a)

Submission status: Wrong Answer

Solution code:
# 全探索 行列だとNがでかすぎて死にそうなのでリストでやる
# 偶奇だけわかればいいので%2する（必要ないけど）
# w=奇数のとき両辺のとりうるのは(1,0)か(0,1)で、ここからキメたほうがよさそう?
# 距離をどういうデータ構造でもてばいいのかわからんぞ....
# あ？偶数と奇数をわけて最初に偶数をキメて次に奇数をキメるのでいいのか？
n = int(input())
arr = [-1 for _ in range(n)]
odd, even = [], []
for _ in range(n - 1):
    u, v, w = map(int, input().split())
    if w % 2 == 0:
        even.append([u - 1, v - 1])
    else:
        odd.append([u - 1, v - 1])

for e in even:
    arr[e[0]] = 0
    arr[e[1]] = 0

while len(odd) > 0:
    rest = []
    for o in odd:
        x, y = o
        if arr[x] < 0 and arr[y] < 0:
            rest.append(o)
        elif arr[x] == 0:
            arr[y] = 1
        elif arr[x] == 1:
            arr[y] = 0
    odd = rest
for a in arr:
    print(a)

Submission status: Wrong Answer

Solution code:
import math
from collections import deque

class UnionFind:
    def __init__(self,size):
        super().__init__()
        self.size = size
        self.par = [-1]*size
    
    def root(self,x):
        return x if self.par[x] == -1 else self.root(self.par[x])

    def unite(self, x, y):
        if self.root(x) != self.root(y):
            self.par[x] = self.root(y)

    def isSame(self,x,y):
        return self.root(x) == self.root(y)

def main():
    n = int(input())
    node = UnionFind(n)

    for _ in range(n-1):
        u,v,w = tuple([int(x) for x in input().split()])
        if w%2==0:
            node.unite(u-1,v-1)

    for i in range(n):
        print('1' if node.isSame(0,i) else '0')

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque
input = sys.stdin.readline

def main():
    n=int(input())
    l=[[] for _ in range(n+1)]
    for _ in range(n-1):
        u,v,w=map(int,input().split())
        u-=1
        v-=1
        l[u].append([v,w])
        l[v].append([u,w])
    ans=[-1]*(n+1)
    chk=[(0,0,-1)]
    while chk:
        v,d,p=chk.pop()
        if d%2==0:
            ans[v]=0
        else:
            ans[v]=1
        for u,w in l[v]:
            if u==p:
                continue
            chk.append((u,d+w,v))
    [print(i) for i in ans[1:]]

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque
input = sys.stdin.readline

def main():
    n=int(input())
    l=[[] for _ in range(n+1)]
    for _ in range(n-1):
        u,v,w=map(int,input().split())
        l[u].append([v,w])
        l[v].append([u,w])
    ans=[0]*(n+1)
    chk=[(1,0,0)]
    while chk:
        x,d,p=chk.pop()
        if (d+w)%2==0:
            ans[x]=0
        else:
            ans[x]=1
        for v,w in l[x]:
            if v==p:
                continue
            chk.append((v,d+w,x))
    [print(i) for i in ans[1:]]

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque
input = sys.stdin.readline

def main():
    n=int(input())
    l=[[] for _ in range(n+1)]
    for _ in range(n-1):
        u,v,w=map(int,input().split())
        l[u].append([v,w])
    ans=[0]*(n+1)
    chk=[(1,0)]
    while chk:
        x,d=chk.pop()
        for v,w in l[x]:
            chk.append((v,d+w))
            if (d+w)%2==0:
                ans[v]=0
            else:
                ans[v]=1
    [print(i) for i in ans[1:]]

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque
input = sys.stdin.readline

def main():
    n=int(input())
    l=[[] for _ in range(n+1)]
    for _ in range(n-1):
        u,v,w=map(int,input().split())
        l[u].append([v,w])
    ans=[0]*(n+1)
    chk=deque()
    chk.append(1)
    while chk:
        x=chk.popleft()
        for v,w in l[x]:
            chk.append(v)
            if w%2==0:
                ans[v]=ans[x]
            else:
                ans[v]=(ans[x]+1)%2
    [print(i) for i in ans[1:]]

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque
input = sys.stdin.readline

def main():
    n=int(input())
    l=[[] for _ in range(n+1)]
    for _ in range(n-1):
        u,v,w=map(int,input().split())
        v=v*((-1)**(w%2))
        l[u].append(v)
    ans=[0]*(n+1)
    chk=deque()
    chk.append(1)
    while chk:
        x=chk.popleft()
        for i in l[x]:
            chk.append(abs(i))
            if i<0:
                ans[abs(i)]=(ans[x]+1)%2
            else:
                ans[abs(i)]=ans[x]
    [print(i) for i in ans[1:]]

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
N=int(input())
G=[set() for _ in [0]*N]
#print(G)
u=[]
v=[]
w=[]
for i in range(1,N):
    a,b,c=map(int,input().split())
    a-=1
    b-=1
    G[a].add((b,c))
    G[b].add((a,c))
#print(G)
ans=[-1]*N
#ルートでは親はいないから-1
q=[(0,0,-1)]
"""
Q=[(0,0,-1)]
a,b,c=Q.pop()
print(a)
print(b)
print(c)
"""
#print(q)
while q:
    #v：現在見ている点
    #p：vの親のノード
    #d：距離
    v,d,p=q.pop()
    """
    if d%2==0:
        ans[v]=0
    else:
        ans[v]=1
    """
    ans[v]=d
    for u,w in G[v]:
        #逆流を防ぐ
        if u==p:
            continue
        if w%2==0:
            pass
        else:
            d=1-d
        q.append((u,d,v))
    #print(q)
print("\n".join(map(str,ans)))

Submission status: Wrong Answer

Solution code:
from collections import deque

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

q = deque()
q.append(0)
ans = [-1] * n
ans[0] = 0

while len(q):
    v = q.pop()
    for i in range(len(to[v])):
        u = to[v][i]
        w = cost[v][i]

        if ans[u] != -1:
            continue
        ans[u] = (ans[v] + w) % 2
        q.append(u)
for i in range(n):
    print(ans[i])

Submission status: Wrong Answer

Solution code:
n = int(input())

node = {}
for i in range(n-1):
    u,v,w = map(int,input().split())
    if w % 2== 0:
        if u in node.keys() and not v in node.keys():
            node[v] = node[u]
        elif v in node.keys() and not u in node.keys():
            node[u] = node[v]
        elif not u in node.keys() and not v in node.keys():
            node[u] = node[v] = 0
    else:
        if u in node.keys() and not v in node.keys():
            node[v] = (node[u]+1)%2
        elif v in node.keys() and not u in node.keys():
            node[u] = (node[v]+1)%2
        elif not u in node.keys() and not v in node.keys():
            node[u] = 0
            node[v] = 1
sort_node = sorted(node.items(), key=lambda x:x[0])
for i in range(n):
    print(sort_node[i][1])

Submission status: Wrong Answer

Solution code:
# N:頂点数, M:辺数
N = int(input())

# G:Graph
G = [[] for _ in range(N)]
# W[a][b]=aからbのながさ
W = [[0]*N for _ in range(N)]
for i in range(N-1):
    u, v, w = map(int, input().split())
    # 調整
    u -= 1
    v -= 1
    G[u].append(v)
    G[v].append(u)
    W[u][v]=w
    W[v][u]=w

# 1(黒),0(白),-1(未訪問)とする
# 未訪問で初期化する
color = [-1]*N

def dfs(G, v, cur=0):
    color[v] = cur
    for next_v in G[v]:
        # 隣接頂点がすでに色確定していた場合
        if color[next_v] != -1:
            # 同じ色が隣接していたらダメなのでFalse
            if color[next_v] == cur and W[v][next_v]&1:
                return False
            continue
        # 隣接頂点の色を変えて、再帰的に探索(一回でもFalseを返したらFalse)
        if not(dfs(G, next_v, 1-cur)):
            return False
    return True

# 探索
is_bipartite = True
for v in range(N):
    # 探索済みならスルー
    if color[v] != -1:
        continue
    if not(dfs(G, v)):
        is_bipartite = False

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

Submission status: Wrong Answer

Solution code:
N=int(input())
Path=[[-1]*N for i in range(N)]
for i in range(N-1):
  u,v,w=map(int,input().split())
  Path[u-1][v-1]=w
  Path[v-1][u-1]=w
ans=[-1]*N
def search(p,pcolor):
  global Path,ans
  i=0
  if ans[p]!=-1:
    return
  else:
    ans[p]=pcolor
  while i<N:
    if Path[p][i]==-1:
      i+=1
      continue
    else:
      if Path[p][i]%2==0:
        search(i,pcolor)
      else:
        search(i,pcolor+1%2)
    i+=1
search(0,0)
#print('\n'.join(ans))
for a in ans:
  print(a)

Submission status: Wrong Answer

Solution code:
N=int(input())
Path=[[-1]*N for i in range(N)]
for i in range(N-1):
  u,v,w=map(int,input().split())
  Path[u-1][v-1]=w
ans=['1']*N
def search0(p):
  global Path,ans
  i=p+1
  if ans[p]=='0':
    return
  else:
    ans[p]='0'
  while i<N:
    if ans[i]=='0':
      i+=1
      continue
    if Path[p][i]==-1:
      pass
    elif Path[p][i]%2==0:
      search0(i)
    else:
      pass
    i+=1
search0(0)
print('\n'.join(ans))

Submission status: Wrong Answer

Solution code:
N=int(input())
#UVW=[list(map(int,input().split())) for i in range(N)]
Path=[[-1]*N for i in range(N)]
for i in range(N-1):
  u,v,w=map(int,input().split())
  Path[u-1][v-1]=w
ans=[1]*N
def search0(p):
  global Path,ans
  i=p+1
  while i<N:
    if Path[p][i]==-1:
      pass
    elif Path[p][i]%2==0:
      ans[i]=0
      search0(i)
    else:
      pass
    i+=1
ans[0]=0
search0(0)
for a in ans:
  print(a)

Submission status: Wrong Answer

Solution code:
#https://note.nkmk.me/python-union-find/
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

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

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

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

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

n=int(input())
uf = UnionFind(n)
for i in range(n-1):
    u,v,w=map(int,input().split())
    if w%2==0:
        uf.union(u-1,v-1)

zero=[]
roots=uf.roots()
for i in range(len(roots)):
    if i%2==0:
        zero+=uf.members(roots[i])

zero=set(zero)
for i in range(n):
    if i in zero:
        print(0)
    else:
        print(1)

Submission status: Wrong Answer

Solution code:
#https://note.nkmk.me/python-union-find/
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

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

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

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

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

n=int(input())
uf = UnionFind(n)
for i in range(n-1):
    u,v,w=map(int,input().split())
    if w%2==0:
        uf.union(u-1,v-1)

zero=set()
roots=uf.roots()
for i in range(len(roots)):
    if i%2==0:
        zero=zero.union(set(uf.members(roots[i])))

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

Submission status: Wrong Answer

Solution code:
#https://note.nkmk.me/python-union-find/
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

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

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

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

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

n=int(input())
uf = UnionFind(n)
for i in range(n-1):
    u,v,w=map(int,input().split())
    if w%2==0:
        uf.union(u-1,v-1)

zero=set(uf.members(0))
for i in range(n):
    if i in zero:
        print(0)
    else:
        print(1)

Submission status: Wrong Answer

Solution code:
import math
import copy
from copy import deepcopy
import sys
import fractions
import numpy as np
from functools import reduce
# import statistics
import heapq
sys.setrecursionlimit(100001)

# input = sys.stdin.readline
# sys.setrecursionlimit(10**6)

# ===FUNCTION===

def getInputInt():
    inputNum = int(input())
    return inputNum


def getInputListInt():
    outputData = []
    inputData = input().split()
    outputData = [int(n) for n in inputData]

    return outputData


def getSomeInputInt(n):
    outputDataList = []
    for i in range(n):
        inputData = int(input())
        outputDataList.append(inputData)

    return outputDataList


def getSomeInputListInt(n):
    inputDataList = []
    outputDataList = []
    for i in range(n):
        inputData = input().split()
        inputDataList = [int(n) for n in inputData]
        outputDataList.append(inputDataList)

    return outputDataList


# ===CODE===

n = int(input())

data = getSomeInputListInt(n-1)

ans = [-1]*n

def searcher(num):
    for i in range(n-1):
        l = data[i][0]
        r = data[i][1]
        w = data[i][2]

        if l == num and ans[r-1] == -1:
            if w % 2 == 0:
                ans[r-1] = ans[num-1]
            else:
                ans[r-1] = (ans[num-1]+1) % 2
            searcher(r)

        if r == num and ans[l-1] == -1:
            if w % 2 == 0:
                ans[l-1] = ans[num-1]
            else:
                ans[l-1] = (ans[num-1]+1) % 2
            searcher(l)


l = data[0][0]
r = data[0][1]
w = data[0][2]

if w % 2 == 0:
    ans[r-1] = 0
    ans[l-1] = 0
else:
    ans[r-1] = 1
    ans[l-1] = 1

searcher(r)
searcher(l)

for a in ans:
    print(a)

Submission status: Wrong Answer

Solution code:
from collections import deque

def bfs(colors, links):
    q = deque([(0, 0)])
    
    while q:
        v, current = q.popleft()

        if current % 2 == 0:
            colors[v] = 0
        else:
            colors[v] = 1

        for next_v, distance in links[v]:
            if colors[next_v] != -1: continue

            q.append((next_v, current + distance))
        
def solve():
    N = int(input())
    A = [list(map(int, input().split())) for _ in range(N-1)]
    cs = [-1] * N
    cs[0] = 0

    links = [[] for _ in range(N)]
    for u, v, w in A:
        v -= 1
        u -= 1
        links[v].append((u, w))
        links[u].append((v, w))

    bfs(cs, links)

    print('\n'.join(map(str, cs)))

print(solve())