Problem:


Score : 400 points

Problem Statement

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

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

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

Constraints

All values in input are integers.

1 \leq N \leq 10^5

1 \leq u_i < v_i \leq N

1 \leq w_i \leq 10^9

Input

Input is given from Standard Input in the following format:

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

Output

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

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

Sample Input 1

3
1 2 2
2 3 1

Sample Output 1

0
0
1

Sample Input 2

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

Sample Output 2

1
0
1
0
1



Sample input:
3
1 2 2
2 3 1


Sample output:
0
0
1

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(200000)

class UnionFind:
    def __init__(self,N):
        self.par = [i for i in range(N)]

    def root(self,x):
        if self.par[x] == x:
            return x
        self.par[x] = self.root(self.par[x])
        return self.par[x]

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

    def same(self,x,y):
        self.rx = self.root(x)
        self.ry = self.root(y)
        return self.rx == self.ry
N = int(input())
uf = UnionFind(N)

for _ in range(N-1):
    x,y,z = [int(i)-1 for i in input().split()]
    if z%2 != 0:
        uf.unite(x,y)

ans = [0]*N
for i in range(N):
    ans[i] = uf.root(i)

p = ans[0]
l = 0
print(l)
for i in range(1,N):
    if p == ans[i]:
        print(l)
    else:
        l = l^1
        print(l)
    p = ans[i]

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(200000)

class UnionFind:
    def __init__(self,N):
        self.par = [i for i in range(N)]

    def root(self,x):
        if self.par[x] == x:
            return x
        self.par[x] = self.root(self.par[x])
        return self.par[x]

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

    def same(self,x,y):
        self.rx = self.root(x)
        self.ry = self.root(y)
        return self.rx == self.ry
N = int(input())
uf = UnionFind(N)

for _ in range(N-1):
    x,y,z = [int(i)-1 for i in input().split()]
    if z%2 != 0:
        uf.unite(x,y)

print(uf.par)


p = uf.par[0]
l = 0
print(l)
for i in range(1,N):
    if p == uf.par[i]:
        print(l)
    else:
        l = l^1
        print(l)
    p = uf.par[i]

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
import itertools
sys.setrecursionlimit(10**5)
stdin = sys.stdin
bisect_left = bisect.bisect_left
bisect_right = bisect.bisect_right
def LI(): return list(map(int, stdin.readline().split()))
def LF(): return list(map(float, stdin.readline().split()))
def LI_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def II(): return int(stdin.readline())
def IF(): return float(stdin.readline())
def LS(): return list(map(list, stdin.readline().split()))
def S(): return list(stdin.readline().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')

#A
def A():
    n, k = LI()
    s = S()
    s[k-1] = s[k-1].lower()
    print("".join(s))

    return

#B
def B():
    s = S()
    a = int("".join(s[:2]))
    b = int("".join(s[2:]))
    if 0 < a <= 12:
        if 0 < b <= 12:
            print("AMBIGUOUS")
        else:
            print("MMYY")
    elif a == 0:
        if 0 < b <= 12:
            print("YYMM")
        else:
            print("NA")
    else:
        if 0 < b <= 12:
            print("YYMM")
        else:
            print("NA")
    return

#C
def C():
    n, k = LI()
    ans = 0
    if k == 1:
        print(1)
        return
    nibuiti = [None for i in range(int(math.log2(k) + 1))]
    for num in range(int(math.log2(k) + 1)):
        if num == 0:
            nibuiti[num] = 1 / 2
            continue
        nibuiti[num] = nibuiti[num-1]/2
        
    for i in range(1, n + 1):
        if i >= k:
            ans += 1
            continue
        b = nibuiti[int(math.log2((k - 1) // i))]
        ans += b
    print(ans/n)
    return

#D
def D():
    n = II()
    color = [0 for i in range(n)]
    edge = [[] for i in range(n)]
    for i in range(n - 1):
        v, u, w = LI_()
        if (w + 1) % 2:           
            edge[v].append(u)
            edge[u].append(v)
    check = [True for i in range(n)]
    for i in range(n):
        q = deque()
        q.append(i)
        
        while q:
            a = q.pop()
            if check:
                check[a] = False
                for k in edge[a]:
                    if check[k]:
                        q.append(k)
                        color[k] = color[a] ^ 1
    for c in color:
        print(c)
    return

#E
def E():
    return

#F
def F():
    return

#G
def G():
    return

#H
def H():
    return

#Solve
if __name__ == '__main__':
    D()

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
import itertools
sys.setrecursionlimit(10**5)
stdin = sys.stdin
bisect_left = bisect.bisect_left
bisect_right = bisect.bisect_right
def LI(): return list(map(int, stdin.readline().split()))
def LF(): return list(map(float, stdin.readline().split()))
def LI_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def II(): return int(stdin.readline())
def IF(): return float(stdin.readline())
def LS(): return list(map(list, stdin.readline().split()))
def S(): return list(stdin.readline().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')

#A
def A():
    n, k = LI()
    s = S()
    s[k-1] = s[k-1].lower()
    print("".join(s))

    return

#B
def B():
    s = S()
    a = int("".join(s[:2]))
    b = int("".join(s[2:]))
    if 0 < a <= 12:
        if 0 < b <= 12:
            print("AMBIGUOUS")
        else:
            print("MMYY")
    elif a == 0:
        if 0 < b <= 12:
            print("YYMM")
        else:
            print("NA")
    else:
        if 0 < b <= 12:
            print("YYMM")
        else:
            print("NA")
    return

#C
def C():
    n, k = LI()
    ans = 0
    if k == 1:
        print(1)
        return
    nibuiti = [None for i in range(int(math.log2(k) + 1))]
    for num in range(int(math.log2(k) + 1)):
        if num == 0:
            nibuiti[num] = 1 / 2
            continue
        nibuiti[num] = nibuiti[num-1]/2
        
    for i in range(1, n + 1):
        if i >= k:
            ans += 1
            continue
        b = nibuiti[int(math.log2((k - 1) // i))]
        ans += b
    print(ans/n)
    return

#D
def D():
    n = II()
    color = [0 for i in range(n)]
    edge = [[] for i in range(n)]
    for i in range(n - 1):
        v, u, w = LI_()
        if (w + 1) % 2:           
            edge[v].append(u)
            edge[u].append(v)
    q = deque()
    q.append(0)
    check = [True for i in range(n)]
    while q:
        a = q.pop()
        if check:
            check[a] = False
            for k in edge[a]:
                if check[k]:
                    q.append(k)
                    color[k] = color[a] ^ 1
    for c in color:
        print(c)
    return

#E
def E():
    return

#F
def F():
    return

#G
def G():
    return

#H
def H():
    return

#Solve
if __name__ == '__main__':
    D()

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
import itertools
sys.setrecursionlimit(10**5)
stdin = sys.stdin
bisect_left = bisect.bisect_left
bisect_right = bisect.bisect_right
def LI(): return list(map(int, stdin.readline().split()))
def LF(): return list(map(float, stdin.readline().split()))
def LI_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def II(): return int(stdin.readline())
def IF(): return float(stdin.readline())
def LS(): return list(map(list, stdin.readline().split()))
def S(): return list(stdin.readline().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')

#A
def A():
    n, k = LI()
    s = S()
    s[k-1] = s[k-1].lower()
    print("".join(s))

    return

#B
def B():
    s = S()
    a = int("".join(s[:2]))
    b = int("".join(s[2:]))
    if 0 < a <= 12:
        if 0 < b <= 12:
            print("AMBIGUOUS")
        else:
            print("MMYY")
    elif a == 0:
        if 0 < b <= 12:
            print("YYMM")
        else:
            print("NA")
    else:
        if 0 < b <= 12:
            print("YYMM")
        else:
            print("NA")
    return

#C
def C():
    n, k = LI()
    ans = 0
    if k == 1:
        print(1)
        return
    nibuiti = [None for i in range(int(math.log2(k) + 1))]
    for num in range(int(math.log2(k) + 1)):
        if num == 0:
            nibuiti[num] = 1 / 2
            continue
        nibuiti[num] = nibuiti[num-1]/2
        
    for i in range(1, n + 1):
        if i >= k:
            ans += 1
            continue
        b = nibuiti[int(math.log2((k - 1) // i))]
        ans += b
    print(ans/n)
    return

#D
def D():
    n = II()
    size = [1 for _ in range(n)]
    height = [1 for _ in range(n)]
    par = [i for i in range(n)]
    def find(x):
        if par[x] == x:
            return x
        else:
            par[x] = find(par[x])
            return par[x]
    def union(x, y):
        s1 = find(x)
        s2 = find(y)
        if s1 != s2:
            if height[s1] < height[s2]:
                par[s1] = s2
                size[s2] += size[s1]
                size[s1] = 0
            else:
                par[s2] = s1
                size[s1] += size[s2]
                size[s2] = 0
                if height[s1] == height[s2]:
                    height[s1] += 1

    for i in range(n - 1):
        u, v, w = LI_()
        w += 1
        if w % 2:
            continue
        else: 
            if find(u) != find(v):
                union(u, v)
    for p in par:
        find(p)
        
    a = par[0]
    for p in par:
        if p == a:
            print(0)
        else:
            print(1)

    return

#E
def E():
    return

#F
def F():
    return

#G
def G():
    return

#H
def H():
    return

#Solve
if __name__ == '__main__':
    D()

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
import itertools
sys.setrecursionlimit(10**5)
stdin = sys.stdin
bisect_left = bisect.bisect_left
bisect_right = bisect.bisect_right
def LI(): return list(map(int, stdin.readline().split()))
def LF(): return list(map(float, stdin.readline().split()))
def LI_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def II(): return int(stdin.readline())
def IF(): return float(stdin.readline())
def LS(): return list(map(list, stdin.readline().split()))
def S(): return list(stdin.readline().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')

#A
def A():
    n, k = LI()
    s = S()
    s[k-1] = s[k-1].lower()
    print("".join(s))

    return

#B
def B():
    s = S()
    a = int("".join(s[:2]))
    b = int("".join(s[2:]))
    if 0 < a <= 12:
        if 0 < b <= 12:
            print("AMBIGUOUS")
        else:
            print("MMYY")
    elif a == 0:
        if 0 < b <= 12:
            print("YYMM")
        else:
            print("NA")
    else:
        if 0 < b <= 12:
            print("YYMM")
        else:
            print("NA")
    return

#C
def C():
    n, k = LI()
    ans = 0
    if k == 1:
        print(1)
        return
    nibuiti = [None for i in range(int(math.log2(k) + 1))]
    for num in range(int(math.log2(k) + 1)):
        if num == 0:
            nibuiti[num] = 1 / 2
            continue
        nibuiti[num] = nibuiti[num-1]/2
        
    for i in range(1, n + 1):
        if i >= k:
            ans += 1
            continue
        b = nibuiti[int(math.log2((k - 1) // i))]
        ans += b
    print(ans/n)
    return

#D
def D():
    n = II()
    size = [1 for _ in range(n)]
    height = [1 for _ in range(n)]
    par = [i for i in range(n)]
    def find(x):
        if par[x] == x:
            return x
        else:
            par[x] = find(par[x])
            return par[x]
    def union(x, y):
        s1 = find(x)
        s2 = find(y)
        if s1 != s2:
            if height[s1] < height[s2]:
                par[s1] = s2
                size[s2] += size[s1]
                size[s1] = 0
            else:
                par[s2] = s1
                size[s1] += size[s2]
                size[s2] = 0
                if height[s1] == height[s2]:
                    height[s1] += 1

    for i in range(n - 1):
        u, v, w = LI_()
        w += 1
        if w % 2:
            continue
        else: 
            if find(u) != find(v):
                union(u, v)
    for p in par:
        union(p, find(p))
        
    a = par[0]
    for p in par:
        if p == a:
            print(0)
        else:
            print(1)

    return

#E
def E():
    return

#F
def F():
    return

#G
def G():
    return

#H
def H():
    return

#Solve
if __name__ == '__main__':
    D()

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
import itertools
sys.setrecursionlimit(10**5)
stdin = sys.stdin
bisect_left = bisect.bisect_left
bisect_right = bisect.bisect_right
def LI(): return list(map(int, stdin.readline().split()))
def LF(): return list(map(float, stdin.readline().split()))
def LI_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def II(): return int(stdin.readline())
def IF(): return float(stdin.readline())
def LS(): return list(map(list, stdin.readline().split()))
def S(): return list(stdin.readline().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')

#A
def A():
    n, k = LI()
    s = S()
    s[k-1] = s[k-1].lower()
    print("".join(s))

    return

#B
def B():
    s = S()
    a = int("".join(s[:2]))
    b = int("".join(s[2:]))
    if 0 < a <= 12:
        if 0 < b <= 12:
            print("AMBIGUOUS")
        else:
            print("MMYY")
    elif a == 0:
        if 0 < b <= 12:
            print("YYMM")
        else:
            print("NA")
    else:
        if 0 < b <= 12:
            print("YYMM")
        else:
            print("NA")
    return

#C
def C():
    n, k = LI()
    ans = 0
    if k == 1:
        print(1)
        return
    nibuiti = [None for i in range(int(math.log2(k) + 1))]
    for num in range(int(math.log2(k) + 1)):
        if num == 0:
            nibuiti[num] = 1 / 2
            continue
        nibuiti[num] = nibuiti[num-1]/2
        
    for i in range(1, n + 1):
        if i >= k:
            ans += 1
            continue
        b = nibuiti[int(math.log2((k - 1) // i))]
        ans += b
    print(ans/n)
    return

#D
def D():
    n = II()
    size = [1 for _ in range(n)]
    height = [1 for _ in range(n)]
    par = [i for i in range(n)]
    def find(x):
        if par[x] == x:
            return x
        else:
            par[x] = find(par[x])
            return par[x]
    def union(x, y):
        s1 = find(x)
        s2 = find(y)
        if s1 != s2:
            if height[s1] < height[s2]:
                par[s1] = s2
                size[s2] += size[s1]
                size[s1] = 0
            else:
                par[s2] = s1
                size[s1] += size[s2]
                size[s2] = 0
                if height[s1] == height[s2]:
                    height[s1] += 1
    for i in range(n - 1):
        u, v, w = LI_()
        w += 1
        if w % 2:
            continue
        else: 
            if find(u) != find(v):
                union(u, v)
    a = par[0]
    for p in par:
        if p == a:
            print(0)
        else:
            print(1)

    return

#E
def E():
    return

#F
def F():
    return

#G
def G():
    return

#H
def H():
    return

#Solve
if __name__ == '__main__':
    D()

Submission status: Wrong Answer

Solution code:
# cook your dish here
t=int(input())
dic={}
for _ in range(t-1):
    a,b,w=map(int,input().split())
    if w%2==0:
        if dic.get(a)==None and dic.get(b)==None:
            dic[a]=0
            dic[b]=0
        elif dic.get(a)!=None:
            dic[b]=dic[a]
        elif dic.get(b)!=None:
            dic[a]=dic[b]
    
    else:
        if dic.get(a)==None and dic.get(b)==None:
            dic[a]=1
            dic[b]=0
        elif dic.get(a)!=None:
            dic[b]=int(not dic[a])
        elif dic.get(b)!=None:
            dic[a]=int(not dic[b])
            
#print(dic)       
for i in range(1,t+1):
    print(dic[i])

Submission status: Wrong Answer

Solution code:
from queue import Queue

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

isChecked = [False for i in range(N)]
ans = [0 for i in range(N)]
q = Queue()
# [current v, sum length]
q.put([1, 0])
while not q.empty():
    v, l = q.get()
    print('v, l: ', v, l)
    if isChecked[v-1]:
        continue
    ans[v-1] = 0 if l%2 == 0 else 1
    isChecked[v-1] = True
    for u, w in d[v]:
        q.put([u, l+w])

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

Submission status: Wrong Answer

Solution code:
def getvalue(a, b, x):
    prev = x
    val = 0
    while a[prev] != -1:
        val += b[prev]
        prev = a[prev]
    return prev, val % 2


def putset(a, b, in1, val1, x, in2, val2, y, w):
    if in1 == in2:
        if a[x] == -1:
            a[y] = in1
            b[y] = w % 2
        elif a[y] == -1:
            a[x] = in2
            b[x] = w % 2
        else:
            a[x] = in1
            b[x] = val1
            a[y] = in1
            b[y] = (val1 + w) % 2
    else:
        a[in2] = in1
        b[in2] = (val2 + w) % 2
        a[y] = in1
        b[y] = w % 2
        if a[x] != -1:
            a[x] = in1
            b[x] = val1


N = int(input())
a = [-1] * (N + 1)
b = [0] * (N + 1)
c = []
for _ in range(N - 1):
    u, v, w = map(int, input().split())
    in1, val1 = getvalue(a, b, u)
    in2, val2 = getvalue(a, b, v)
    putset(a, b, in1, val1, u, in2, val2, v, w)

for i in range(1, N + 1):
    _, val = getvalue(a, b, i)
    print(val)

Submission status: Wrong Answer

Solution code:
N = int(input())
uvw = [list(map(int, input().split(' '))) for _ in range(N-1)]
uvw.sort(key=lambda x: (x[0], x[1]))
res = [False] * N
for u, v, w in uvw:
	print([u,v,w])
	res[v-1] = res[u-1] if w%2 == 0 else not res[u-1]
for b in res:
	print('01'[b])

Submission status: Wrong Answer

Solution code:
n = int(input())
v = [list(map(int,input().split())) for _ in range(n-1)]
g = {}
odd = []
for a,b,w in v:
    if a not in g:
        g[a] = []
    if b not in g:
        g[b] = []
    g[a].append(b)
    g[b].append(a)
    if w%2==1:
        odd.append(b)
        odd.append(a)
from collections import deque
if odd:
    queue = deque([[odd[0],0]])
    odd = set(odd)
    b = deque()
    done = []
    while queue:
        print(queue)
        q,o = queue.popleft()
        if o==1:
            b.appendleft(q)
        done.append(q)
        for new_q in g[q]:
            if new_q not in done:
                if new_q in odd:
                    no = 1
                else:
                    no = 0
                print(o,no)
                if (no==1 and o==1) or (no==0 and o==0):
                    queue.appendleft([new_q,0])
                else:
                    queue.appendleft([new_q,1])
    print(b)
    for i in range(1,n+1):
        if i in b:
            print(1)
        else:
            print(0)
else:
    for i in range(n):
        print(0)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
n = int(input())
g = [[] for i in range(n)]
c = [-1 for i in range(n)]

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


q = [0]
while (len(q) > 0):
    v = q.pop()
    for u, w in g[v]:
        if c[u] != -1:
            continue
        q.append(u)
        c[u] = c[v] ^ w

for v in c:
    print(v)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(20000000)

n = int(input())
g = [[] for i in range(n)]
c = [-1 for i in range(n)]

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


q = [0]
while (len(q) > 0):
    v = q.pop()
    for u, w in g[v]:
        if c[u] != -1:
            continue
        q.append(u)
        c[u] = c[v] ^ w

for v in c:
    print(v)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(20000000)

n = int(input())
g = [[] for i in range(n)]
c = [-1 for i in range(n)]

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


q = [0]
while (len(q) > 0):
    v = q.pop()
    for u, w in g[v]:
        if c[u] != -1:
            continue
        q.append(u)
        c[u] = c[v] + w

for v in c:
    print(v)

Submission status: Wrong Answer

Solution code:
def getroot(a, x):
    prev = x
    while a[prev][0] != -1:
        prev = a[prev][0]
    return prev


def getvalue(a, b, x):
    prev = x
    val = 0
    while a[prev] != -1:
        prev = a[prev]
        val += b[prev]
    return prev, val % 2


def putset(a, b, in1, val1, x, in2, val2, y, w):
    if in1 == in2:
        if a[x] == -1:
            a[y] = in1
            b[y] = w
        elif a[y] == -1:
            a[x] = in2
            b[x] = w
        else:
            a[x] = in1
            b[x] = val1
            a[y] = in1
            b[y] = (val1 + w) % 2
    else:
        a[in2] = in1
        b[in2] = (val1 + w + val2) % 2
        a[y] = in1
        b[y] = (val1 + w) % 2
        if a[x] != -1:
            a[x] = in1
            b[x] = val1


N = int(input())
a = [-1] * (N + 1)
b = [0] * (N + 1)
for _ in range(N - 1):
    u, v, w = map(int, input().split())
    if w % 2 == 1:
        in1, val1 = getvalue(a, b, u)
        in2, val2 = getvalue(a, b, v)
        putset(a, b, in1, val1, u, in2, val2, v, w % 2)

for c in b[1:]:
    print(c)

Submission status: Wrong Answer

Solution code:
class WeightedUnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n+1)]
        self.rank = [0] * (n+1)
        # 根への距離を管理
        self.weight = [0] * (n+1)

    # 検索
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            y = self.find(self.par[x])
            # 親への重みを追加しながら根まで走査
            self.weight[x] += self.weight[self.par[x]]
            self.par[x] = y
            return y

    # 併合
    def union(self, x, y, w):
        rx = self.find(x)
        ry = self.find(y)
        # xの木の高さ < yの木の高さ
        if self.rank[rx] < self.rank[ry]:
            self.par[rx] = ry
            self.weight[rx] = w - self.weight[x] + self.weight[y]
        # xの木の高さ ≧ yの木の高さ
        else:
            self.par[ry] = rx
            self.weight[ry] = -w - self.weight[y] + self.weight[x]
            # 木の高さが同じだった場合の処理
            if self.rank[rx] == self.rank[ry]:
                self.rank[rx] += 1

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

    # xからyへのコスト
    def diff(self, x, y):
        return self.weight[x] - self.weight[y]

N = int(input())
ps = [list(map(int, input().split())) for _ in range(N-1)]
ps.sort()
tree = WeightedUnionFind(N)
for i, j, d in ps:
    tree.union(i, j, d)
for i in range(1, N+1):
    if tree.diff(1, i) % 2 == 0:
        print(1)
    else:
        print(0)

Submission status: Wrong Answer

Solution code:
class WeightedUnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n+1)]
        self.rank = [0] * (n+1)
        # 根への距離を管理
        self.weight = [0] * (n+1)

    # 検索
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            y = self.find(self.par[x])
            # 親への重みを追加しながら根まで走査
            self.weight[x] += self.weight[self.par[x]]
            self.par[x] = y
            return y

    # 併合
    def union(self, x, y, w):
        rx = self.find(x)
        ry = self.find(y)
        # xの木の高さ < yの木の高さ
        if self.rank[rx] < self.rank[ry]:
            self.par[rx] = ry
            self.weight[rx] = w - self.weight[x] + self.weight[y]
        # xの木の高さ ≧ yの木の高さ
        else:
            self.par[ry] = rx
            self.weight[ry] = -w - self.weight[y] + self.weight[x]
            # 木の高さが同じだった場合の処理
            if self.rank[rx] == self.rank[ry]:
                self.rank[rx] += 1

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

    # xからyへのコスト
    def diff(self, x, y):
        return self.weight[x] - self.weight[y]

N = int(input())
ps = [list(map(int, input().split())) for _ in range(N-1)]
ps.sort()
tree = WeightedUnionFind(N)
for i, j, d in ps:
    tree.union(i, j, d)
for i in range(1, N+1):
    if tree.weight[i] % 2 == 0:
        print(1)
    else:
        print(0)

Submission status: Wrong Answer

Solution code:
def getvalue(a, b, x):
    prev = x
    val = 0
    while a[prev] != -1:
        prev = a[prev]
        val += b[prev]
    return prev, val % 2


def putset(a, b, in1, val1, x, in2, val2, y, w):
    if in1 == in2:
        if a[x] == -1:
            a[y] = in1
            b[y] = w
        elif a[y] == -1:
            a[x] = in2
            b[x] = w
        else:
            a[x] = in1
            b[x] = val1
            a[y] = in1
            b[y] = (val1 + w) % 2
    else:
        a[in2] = in1
        b[in2] = (val1 + w + val2) % 2
        a[y] = in1
        b[y] = (val1 + w) % 2
        if a[x] != -1:
            a[x] = in1
            b[x] = val1


N = int(input())
a = [-1] * (N + 1)
b = [0] * (N + 1)
for _ in range(N - 1):
    u, v, w = map(int, input().split())
    in1, val1 = getvalue(a, b, u)
    in2, val2 = getvalue(a, b, v)
    putset(a, b, in1, val1, u, in2, val2, v, w % 2)

for c in b[1:]:
    print(c)

Submission status: Wrong Answer

Solution code:
def solve(string):
    n, *uvw = map(int, string.split())
    g = [[]] * (n + 1)
    for u, v, w in zip(uvw[::3], uvw[1::3], uvw[2::3]):
        g[u].append((v, w))
        g[v].append((u, w))
    s = [(1, 0)]
    w = [-1] * (n + 1)
    while s:
        _s, _w = s.pop()
        w[_s] = _w % 2
        for _t, _w_ in g[_s]:
            if w[_t] == -1:
                s.append((_t, _w + _w_))
    return "\n".join(str(c) for c in w[1:])


if __name__ == '__main__':
    n = int(input())
    print(solve('{}\n'.format(n) + '\n'.join([input() for _ in range(n - 1)])))

Submission status: Wrong Answer

Solution code:
def solve(string):
    n, *uvw = map(int, string.split())
    uvw = list(zip(uvw[::3], uvw[1::3], uvw[2::3]))
    g = [[]] * (n + 1)
    for u, v, w in uvw:
        g[u].append((v, w))
        g[v].append((u, w))
    s = [(1, 0)]
    w = [-1] * (n + 1)
    while len(s) > 0:
        _s, _w = s.pop()
        w[_s] = _w % 2
        for _t, _w_ in g[_s]:
            if w[_t] == -1:
                s.append((_t, _w + _w_))
    return "\n".join(str(c) for c in w[1:])


if __name__ == '__main__':
    n = int(input())
    print(solve('{}\n'.format(n) + '\n'.join([input() for _ in range(n - 1)])))

Submission status: Wrong Answer

Solution code:
def solve(string):
    n, *uvw = map(int, string.split())
    uvw = list(zip(uvw[::3], uvw[1::3], uvw[2::3]))
    union = [-1] * (n + 1)
    color = [n + 1] * (n + 1)
    color[1] = 0

    def find(num):
        c = color[num]
        path = [num]
        while union[num] > 0:
            num = union[num]
            path.append(num)
            c = min(c, color[num])
        for p in path:
            color[p] = c
        return num, c

    tmp_color = 1
    for u, v, w in uvw:
        ru, cu = find(u)
        rv, cv = find(v)
        if w % 2 == 0:
            union[rv] = ru
            if tmp_color < min(cu, cv):
                color[ru] = tmp_color
                tmp_color += 1
        else:
            if tmp_color < cu:
                color[ru] = tmp_color
                tmp_color += 1
            if tmp_color < cv:
                color[rv] = tmp_color
                tmp_color += 1
    for i in range(1, n + 1):
        find(i)
    return "\n".join([str(c) for c in color[1:]])


if __name__ == '__main__':
    n = int(input())
    print(solve('{}\n'.format(n) + '\n'.join([input() for _ in range(n - 1)])))