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:
from collections import deque

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

colors = [-1 for _ in range(N)]
stack = deque()
stack.append(0)
colors[0] = 0

while stack:
    n = stack.pop()
    for _next, w in graph[n]:
        if colors[_next] == -1:
            continue
        colors[_next] = (colors[n] + w) % 2 
        stack.append([_next])

for c in colors:
    print(c)

Submission status: Wrong Answer

Solution code:
from collections import deque

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

colors = [-1 for _ in range(N)]
stack = deque()
if N != 1:
    stack.append([0, graph[0][0][0], graph[0][0][1]])
colors[0] = 0

while stack:
    prev, _next, w = stack.pop()
    if colors[_next] == -1:
        if w % 2 == 0:
            color = 0
        else:
            color = 1
        colors[_next] = color
    for v1, w1 in graph[_next]:
        if colors[v1] != -1:
            continue
        stack.append([_next, v1, w + w1])

for c in colors:
    print(c)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict, deque

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

colors = [-1 for _ in range(N + 1)]
stack = deque()
colors[1] = 0

while stack:
    prev, _next, w = stack.pop()
    if colors[_next] == -1:
        if w % 2 == 0:
            color = 0
        else:
            color = 1
        colors[_next] = color
    for v1, w1 in graph[_next]:
        if colors[v1] != -1:
            continue
        stack.append([_next, v1, w + w1])

for c in colors:
    print(c)

Submission status: Wrong Answer

Solution code:
from collections import deque

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

colors = [-1 for _ in range(N)]
stack = deque()
if N != 1:
    stack.append([0, graph[0][0][0], graph[0][0][1]])
colors[0] = 0

while stack:
    prev, _next, w = stack.popleft()
    if colors[_next] == -1:
        if w % 2 == 0:
            color = colors[prev]
        else:
            color = 1 if colors[prev] == 0 else 0
        colors[_next] = color
    for v1, w1 in graph[_next]:
        if colors[v1] != -1:
            continue
        stack.append([_next, v1, w1])

for c in colors:
    print(c)

Submission status: Wrong Answer

Solution code:
from collections import deque

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

colors = [-1 for _ in range(N)]
stack = deque()
stack.append([0, graph[0][0][0], graph[0][0][1]])
colors[0] = 0

while stack:
    prev, _next, w = stack.pop()
    if colors[_next] == -1:
        if w % 2 == 0:
            color = colors[prev]
        else:
            color = 1 if colors[prev] == 0 else 0
        colors[_next] = color
    for v1, w1 in graph[_next]:
        if colors[v1] != -1:
            continue
        stack.append([_next, v1, w1])

for c in colors:
    print(c)

Submission status: Wrong Answer

Solution code:
from collections import deque

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

colors = [-1 for _ in range(N)]
stack = deque()
stack.append([0, graph[0][0][0], graph[0][0][1]])
colors[0] = 0

while stack:
    prev, _next, w = stack.pop()
    if colors[_next] == -1:
        if w % 2 == 0:
            color = colors[prev]
        else:
            color = 1 if colors[prev] == 0 else 0
        colors[_next] = color
    for v1, w1 in graph[_next]:
        if colors[v1] != -1:
            continue
        stack.append([_next, v1, w+w1])

for c in colors:
    print(c)

Submission status: Wrong Answer

Solution code:
from collections import deque

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

colors = [-1 for _ in range(N)]
stack = deque()
stack.append([0, graph[0][0][0], graph[0][0][1]])
colors[0] = 0

while stack:
    prev, _next, w = stack.pop()
    if colors[_next] == -1:
        if w % 2 == 0:
            color = colors[prev]
        else:
            color = 1 if colors[prev] == 0 else 0
        colors[_next] = color
    for v1, w1 in graph[_next]:
        if colors[v1] != -1:
            continue
        stack.append([_next, v1, w1])

for c in colors:
    print(c)

Submission status: Wrong Answer

Solution code:
from collections import deque

N = int(input())
ki = [[] for _ in range(N)]
for _ in range(N-1):
    u, v, w = map(int, input().split())
    ki[u-1].append([v-1, w])
    ki[v-1].append([u-1, w])
f = [False]*N
f[0] = True
c = [0]*N

q = deque([0])
while q:
    now = q.popleft()
    for nxt, w in ki[now]:
        if f[nxt]:
            continue
        if w&1:
            c[nxt] = c[now]^1
        else:
            c[nxt] = c[now]
        q.append(nxt)
        f[nxt] = True

print(f)

for a in c:
    print(a)

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())
uf=WeightedUnionFind(N)
for i in range(N-1):
  a,b,w=map(int,input().split())
  uf.union(a-1,b-1,w%2)
for i in range(N):
  print(uf.diff(0,i)%2)

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())
uf=WeightedUnionFind(N)
for i in range(N-1):
  a,b,w=map(int,input().split())
  uf.union(a-1,b-1,w)
for i in range(N):
  print(uf.diff(0,i)%2)

Submission status: Wrong Answer

Solution code:
N = int(input())
G = [-1]*(N+1)
G[1] = 0
edges = [list(map(int, input().split())) for _ in range(N-1)]
for u, v, w in edges:
    if w%2 == 0:
        if G[u] != -1:
            G[v] = G[u]
        elif G[v] != -1:
            G[u] = G[v]
        else:
            G[u] = 0
            G[v] = 0
    else:
        if G[u] != -1:
            G[v] = (G[u]+1)%2
        elif G[v] != -1:
            G[u] = (G[v]+1)%2
        else:
            G[u] = 0
            G[v] = 1

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

Submission status: Wrong Answer

Solution code:
N = int(input())
G = [-1]*(N+1)
G[1] = 0
edges = [list(map(int, input().split())) for _ in range(N-1)]
for u, v, w in edges:
    if w%2 == 0:
        if G[u] != -1:
            G[v] = G[u]
        elif G[v] != -1:
            G[u] = G[v]
        else:
            G[u] = 0
            G[v] = 0
    else:
        if G[u] != -1:
            G[v] = (G[u]+1)%2
        elif G[v] != -1:
            G[u] = (G[v]+1)%2
        else:
            G[u] = 0
            G[v] = 1

for v in G:
    print(v)

Submission status: Wrong Answer

Solution code:
from collections import deque

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

graph = {}
for u, v, w in u_v_w_l:
    u, v = u - 1, v - 1
    u_set = graph.get(u, set())
    u_set.add((v, w))
    v_set = graph.get(v, set())
    v_set.add((u, w))
    graph[u] = u_set
    graph[v] = v_set

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

for n in range(N):
    for next_n, w in graph.get(n, set()):
        if colors[next_n] != -1:
            continue
        if colors[n] == -1:
            colors[n] = 0
        if w % 2 == 0:
            color = colors[n]
        else:
            color = 1 if colors[n] == 0 else 0
        colors[next_n] = color

for c in colors:
    print(c)

Submission status: Wrong Answer

Solution code:
from collections import deque
import sys
def input(): return sys.stdin.readline().rstrip()

N = int(input())


# vlist = [[] for _ in range(N)]
vlist = [[]] * N

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

ans = [-1] * N
q = deque()

ans[0] = 0
q.append(0)

while q:
    new = q.popleft()
    for node, weight in vlist[new]:
        if ans[node] != -1:
            continue
        ans[node] = (ans[new] + weight) % 2
        q.append(node)
    
for i in ans:
    print(i)

Submission status: Wrong Answer

Solution code:
from collections import deque

N = int(input())


# vlist = [[] for _ in range(N)]
vlist = [[]] * N

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

ans = [-1] * N
q = deque()

ans[0] = 0
q.append(0)

while q:
    new = q.popleft()
    for node, weight in vlist[new]:
        if ans[node] != -1:
            continue
        ans[node] = (ans[new] + weight) % 2
        q.append(node)
    
for i in ans:
    print(i)

Submission status: Wrong Answer

Solution code:
from collections import deque

N = int(input())


vlist = [[]] * N

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

ans = [-1] * N
q = deque()

ans[0] = 0
q.append(0)

while q:
    new = q.popleft()
    for node, weight in vlist[new]:
        if ans[node] != -1:
            continue
        ans[node] = (ans[new] + weight) % 2
        q.append(node)
    
for i in ans:
    print(i)

Submission status: Wrong Answer

Solution code:
from collections import deque

N = int(input())


to = [[]] * N
cost = [[]] * 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(w)
    cost[b].append(w)

ans = [-1] * N
q = deque()

ans[0] = 0
q.append(0)

while q:
    new = q.popleft()
    for node, weight in zip(to[new],cost[new]):
        if ans[node] != -1:
            continue
        ans[node] = (ans[new] + weight) % 2
        q.append(node)
    
for i in ans:
    print(i)

Submission status: Wrong Answer

Solution code:
from collections import deque

N = int(input())


to = [[]] * N
cost = [[]] * 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(w)
    cost[b].append(w)

ans = [-1] * N
q = deque()

ans[0] = 0
q.append(0)

while not q:
    new = q.popleft()
    for node, weight in zip(to[new],cost[new]):
        if ans[node] != -1:
            continue
        ans[node] = (ans[new] + weight) % 2
        q.append(node)
    
for i in ans:
    print(i)

Submission status: Wrong Answer

Solution code:
import queue

N = int(input())


to = [[]] * N
cost = [[]] * 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(w)
    cost[b].append(w)

ans = [-1] * N
q = queue.Queue()

ans[0] = 0
q.put(0)

while not q.empty():
    new = q.get()
    for node, weight in zip(to[new],cost[new]):
        if ans[node] != -1:
            continue
        ans[node] = (ans[new] + weight) % 2
        q.put(node)
    
for i in ans:
    print(i)

Submission status: Wrong Answer

Solution code:
n = int(input())

g = [[] for _ in range(n)]

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

from collections import deque

que = deque()
seen = [0] + [-1]*(n-1)
que.append(0)
while que:
    s = que.popleft()
    for v,w in g[s]:
        if seen[v] != -1:continue
        seen[v] = seen[s]^(w%2)
        que.append(v)
print(seen)

Submission status: Wrong Answer

Solution code:
n = int(input())
set0=set([0])
set1 =set()
explored = set()
next = [[]for _ in range(n)]
 
from collections import deque
ls = []
for i in range(n-1):
    u, v, w= map(int, input().split())
    ls.append((u-1, v-1, w%2))
 
    next[u-1].append(i)
    next[v-1].append(i)
 
ans = [-1] * n
 
x,y,z=ls[0]
ans[x] = 0
if z==0:
    ans[y] =0
else:
    ans[y] = 1
explored.add(x)
explored.add(y)
exploring = deque([])
exploring.extend(next[x])
exploring.extend(next[y])
now=0
while exploring:
    i = exploring.popleft()
    u,v,w= ls[i]
    if u not in explored:
        exploring.extend(next[u])
    if v not in explored:
        exploring.extend(next[v])
    explored.add(u)
    explored.add(v)
    if w == 0: # same
        if u in set0 or v in set0:
            #set0 |= set([u, v])
            set0.add(u)
            set0.add(v)
            ans[u]=0
            ans[v]=0
        elif u in set1 or v in set1:
            #set1 |= set([u, v])
            set1.add(u)
            set1.add(v)
            ans[u] = 1
            ans[v] = 1
    else:#different
        if u in set0:
            set1.add(v)
            ans[v] =1
        elif v in set0:
            set1.add(u)
            ans[u] =1
        elif v in set1:
            set0.add(u)
            ans[u] =0
        elif u in set1:
            set0.add(v)
            ans[v] =0
 
 
for i in ans:
    print(i)

Submission status: Wrong Answer

Solution code:
n = int(input())
set0=set([0])
set1 =set()
explored = set()
next = [[]for _ in range(n)]

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

    next[u-1].append(i)
    next[v-1].append(i)

ans = [-1] * n

x,y,z=ls[0]
ans[x] = 0
if z==0:
    ans[y] =0
else:
    ans[y] = 1
explored.add(0)
explored.add(1)
exploring = deque([])
exploring.extend(next[x])
exploring.extend(next[y])
now=0
while exploring:
    i = exploring.popleft()
    u,v,w= ls[i]
    if u not in explored:
        exploring.extend(next[u])
    if v not in explored:
        exploring.extend(next[v])
    explored.add(u)
    explored.add(v)
    if w == 0: # same
        if u in set0 or v in set0:
            #set0 |= set([u, v])
            set0.add(u)
            set0.add(v)
            ans[u]=0
            ans[v]=0
        elif u in set1 or v in set1:
            #set1 |= set([u, v])
            set1.add(u)
            set1.add(v)
            ans[u] = 1
            ans[v] = 1
    else:#different
        if u in set0:
            set1.add(v)
            ans[v] =1
        elif v in set0:
            set1.add(u)
            ans[u] =1
        elif v in set1:
            set0.add(u)
            ans[u] =0
        elif u in set1:
            set0.add(v)
            ans[v] =0


for i in ans:
    print(i)

Submission status: Wrong Answer

Solution code:
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

N = int(input())
graph = [{} for _ in range(N)]

for _ in range(N-1):
    u, v, w = mapint()
    graph[u-1][v-1] = w%2
    graph[v-1][u-1] = w%2

from collections import deque
stack = deque([0])

colors = [-1]*N
colors[0] = 0
while stack:
    v = stack.pop()
    for nx in graph[v].keys():
        if colors[nx]==-1:
            w = graph[v][nx]
            colors[nx] = colors[v]^1
            stack.append(nx)

for a in colors:
    print(a)

Submission status: Wrong Answer

Solution code:
N=int(input())
e=set()
o=set()
r=[]
ans = [0]*(N)

for i in range(N-1):
    v,u,l = map(int, input().split())
    if l % 2 == 0:
        e.add(v)
        e.add(u)
        ans[v-1]=1
        ans[u-1]=1
    else:
        r.append((u,v))

for u,v in r:
    if u in e and v in e:
        print("err")
        exit()
    if u in e:
        o.add(v)
        ans[v-1]=0
    elif v in e:
        o.add(u)
        ans[u-1]=0
    else:
        o.add(v)
        o.add(u)
        ans[u-1]=0
        ans[v-1]=0

for i in ans:
    print(i)

Submission status: Wrong Answer

Solution code:
from collections import deque
N=int(input())
visited=[-1]*N
l=[[] for i in range(N)]
for i in range(N-1):
   a,b,c=map(int,input().split())
   a-=1;b-=1
   l[a].append((b,c%2))
   l[b].append((a,c%2))
def ans(node,dis):
   visited[node]=0
   que=deque(l[node])
   while que:
      node,dis=que.popleft()
      for i,j in l[node]:
         if visited[i]==-1:
            visited[i]=(dis+j)%2
            que.append((i,(dis+j)%2))
ans(0,0)
for i in visited:
   print(i)

Submission status: Wrong Answer

Solution code:
from collections import deque
N=int(input())
visited=[-1]*N
l=[[] for i in range(N)]
for i in range(N-1):
   a,b,c=map(int,input().split())
   a-=1;b-=1
   l[a].append((b,c%2))
   l[b].append((a,c%2))
def ans(node,dis):
   visited[node]=0
   que=deque(l[node])
   while que:
      node,dis=que.popleft()
      for i,j in l[node]:
         if visited[i]==-1:
            visited[i]=(dis+j)%2
            que.append((i,(dis+j)%2))
ans(0,0)
print(visited)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**8)
N = int(input())
graph = [[] for _ in range(N)]

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

color = [0 for _ in range(N)]

def dfs(prev:int, now:int):

    res = True
    for adj in graph[now]:
        v, dist = adj
        if prev == v:
            continue

        if dist % 2 == 0 and color[v] != 0 and color[v] != color[now]:
            return False

        if dist % 2 != 0 and color[v] != 0 and color[v] == color[now]:
            return False

        if dist % 2 == 0 and color[v] != 0 and color[v] == color[now]:
            return True

        if dist % 2 != 0 and color[v] != 0 and color[v] != color[now]:
            return True

        if dist % 2 == 0 and color[v] == 0:
            color[v] = color[now]
        elif dist % 2 == 1 and color[v] == 0:
            color[v] = -1 * color[now]

        res = res and dfs(now, v)
        return res

    return True

for start in range(N):
    if color[start] == 0:
        color[start] = 1
        dfs(-1, start)

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

Submission status: Wrong Answer

Solution code:
from collections import deque
N = int(input())
#隣接リスト
g = [[] for i in range(N)]
for i in range(N-1):
  u,v,w = map(int,input().split())
  u -= 1
  v -= 1
  g[u].append([v,w])
  g[v].append([u,w])
q = deque([])
ans = [-1] * N
check = [0] * N
check[0] = 1
q.append(0)
ans[0] = 0
while len(q) > 0:
  e = q.popleft()
  for i,j in g[e]:
    if check[i] == 1:
      continue
    ans[i] = (ans[e] + w) %2
    check[i] = 1
    q.append(i)
for i in range(N):
  print(ans[i])

Submission status: Wrong Answer

Solution code:
from collections import deque
N = int(input())
#隣接リスト
g = [[] for i in range(N)]
for i in range(N-1):
  u,v,w = map(int,input().split())
  u -= 1
  v -= 1
  g[u].append([v,w])
  g[v].append([u,w])
q = deque([])
ans = [-1] * (N)
q.append(0)
ans[0] = 0
while len(q) > 0:
  e = q.popleft()
  for i in g[e]:
    path = i[0]
    cost = i[1]
    if (ans[path] != -1):
      continue
    ans[path] = (ans[e]+w) % 2
    q.append(path)
for i in range(len(ans)):
  print(ans[i])

Submission status: Wrong Answer

Solution code:
from collections import deque
N = int(input())
g = [[] for i in range(N)]
for i in range(N-1):
  u,v,w = map(int,input().split())
  u -= 1
  v -= 1
  g[u].append([v,w])
  g[v].append([u,w])
q = deque([])
ans = [-1] * N
q.append(0)
ans[0] = 0
while len(q) > 0:
  e = q.popleft()
  for i in g[e]:
    if ans[i[0]] > -1:
      continue
    ans[i[0]] += i[1]
    ans[i[0]] = ans[i[0]] % 2
    q.append(i[0])
for i in range(len(ans)):
  if ans[i]%2 == 1:
    print(1)
    continue
  print(0)

Submission status: Wrong Answer

Solution code:
from collections import deque
N = int(input())
g = [[] for i in range(N)]
for i in range(N-1):
  u,v,w = map(int,input().split())
  g[u-1].append([v-1,w])
  g[v-1].append([u-1,w])
q = deque([])
ans = [-1] * N
q.append(0)
while len(q) > 0:
  e = q.popleft()
  for i in g[e]:
    if ans[i[0]] > -1:
      continue
    ans[i[0]] += i[1]
    ans[i[0]] = ans[i[0]] % 2
    q.append(i[0])
for i in range(len(ans)):
  if ans[i]%2 == 1:
    print(1)
    continue
  print(0)

Submission status: Wrong Answer

Solution code:
from collections import deque
N = int(input())
g = [[] for i in range(N)]
for i in range(N-1):
  u,v,w = map(int,input().split())
  g[u-1].append([v-1,w])
  g[v-1].append([u-1,w])
q = deque([])
ans = [-1] * N
q.append(0)
while len(q) > 0:
  e = q.popleft()
  for i in g[e]:
    if ans[i[0]] > -1:
      continue
    ans[i[0]] += i[1]
    q.append(i[0])
for i in range(len(ans)):
  if ans[i]%2 == 1:
    print(1)
    continue
  print(0)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**8)
N = int(input())
graph = [[] for _ in range(N)]

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

color = [0 for _ in range(N)]
color[0] = 1

def dfs(prev:int, now:int):

    res = True
    for adj in graph[now]:
        v, dist = adj
        if prev == v:
            continue

        if dist % 2 == 0 and color[v] != 0 and color[v] != color[now]:
            return False

        if dist % 2 != 0 and color[v] != 0 and color[v] == color[now]:
            return False

        if dist % 2 == 0 and color[v] != 0 and color[v] == color[now]:
            return True

        if dist % 2 != 0 and color[v] != 0 and color[v] != color[now]:
            return True

        if dist % 2 == 0 and color[v] == 0:
            color[v] = color[now]
        elif dist % 2 == 1 and color[v] == 0:
            color[v] = -1 * color[now]

        res &= dfs(now, v)
        return res

    return True

print(*color)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**8)
N = int(input())
graph = [[] for _ in range(N)]

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

color = [0 for _ in range(N)]
color[0] = 1

def dfs(prev:int, now:int):

    res = True
    for adj in graph[now]:
        v, dist = adj
        if prev == v:
            continue

        if dist % 2 == 0 and color[v] != color[now]:
            return False

        if dist % 2 != 0 and color[v] == color[now]:
            return False

        if dist % 2 == 0 and color[v] == color[now]:
            return True

        if dist % 2 != 0 and color[v] != color[now]:
            return True

        if dist % 2 == 0 and color[v] == 0:
            color[v] = color[now]
        elif dist % 2 == 1 and color[v] == 0:
            color[v] = -1 * color[now]

        res &= dfs(now, v)
        return res

    return True

print(*color)

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 unite(self, x, y, w):
        rx = self.find(x)
        ry = self.find(y)
        if self.rank[rx] < self.rank[ry]:
            self.par[rx] = ry
            self.weight[rx] = w - self.weight[x] + self.weight[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 find_root(self,x):
        return self.find(x)

    def diff(self, x, y):
        return self.weight[x] - self.weight[y]

N=int(input())
wuf=WeightedUnionFind(N+1)
for _ in [0]*(N-1):
    wuf.unite(*(map(int,input().split())))

root=wuf.find_root(1)
for i in range(N):
    if wuf.diff(root,i+1)%2:
        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 unite(self, x, y, w):
        rx = self.find(x)
        ry = self.find(y)
        if self.rank[rx] < self.rank[ry]:
            self.par[rx] = ry
            self.weight[rx] = w - self.weight[x] + self.weight[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 find_root(self,x):
        return self.find(x)

    def diff(self, x, y):
        return self.weight[x] - self.weight[y]

N=int(input())
wuf=WeightedUnionFind(N+1)
for _ in [0]*(N-1):
    wuf.unite(*(map(int,input().split())))

root=wuf.find_root(1)
for i in range(N):
    if wuf.diff(1,i+1)%2:
        print(1)
    else:
        print(0)

Submission status: Wrong Answer

Solution code:
from sys import stdin
import sys
import math
from functools import reduce
import functools
import itertools
from collections import deque,Counter,defaultdict
from operator import mul
import copy
# ! /usr/bin/env python
# -*- coding: utf-8 -*-
import heapq
sys.setrecursionlimit(10**6)
# INF =  float("inf")
INF = 10**18
import bisect
import statistics
mod = 10**9+7
# mod = 998244353

N = int(input())

al = [[] for i in range(N+1)]
for i in range(N-1):
    a, b, c = map(int, input().split())
    al[a].append((b,c))


seen = [0 for i in range(N+1)]
ans = [0 for i in range(N+1)]

def bfs(u):
    stack = deque([u])
    seen[u] = 1
    ans[u] = 0

    while len(stack) > 0:
        v = stack.popleft()

        for w in al[v]:
            if seen[w[0]] == 0:
                stack.append(w[0])
                if w[1] % 2 == 0:
                    ans[w[0]] = ans[v]
                else:
                    ans[w[0]] = 1 - ans[v]
                seen[w[0]] = 1

bfs(1)

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

Submission status: Wrong Answer

Solution code:
# coding: utf-8
import sys
import copy

sys.setrecursionlimit(10 ** 9)


def dfs(seen, n, uvw, ui, vi, wi):
    if seen[ui-1] != -1 and seen[vi-1] != -1:
        pass
    elif seen[ui-1] != -1:
        seen[vi-1] = abs(seen[ui-1] - (wi % 2))
    elif seen[vi-1] != -1:
        seen[ui-1] = abs(seen[vi-1] - (wi % 2))
    else:
        seen[ui-1] = 0
        seen[vi-1] = abs(seen[ui-1] - (wi % 2))
        
    for i in range(n-1):
        if vi == uvw[i][0]:
            dfs(seen, n, uvw, *uvw[i])
            # dfs(senn, uvw[i][0], uvw[i][1], uvw[2])
        
    

def main():
    n = int(input())
    uvw = [tuple(map(int, input().split())) for _ in range(n-1)]
    
    seen = [-1 for _ in range(n)]
    
    for i in range(n-1):
        ui, vi, wi = uvw[i]
        dfs(seen, n, uvw, *uvw[i])
        # dfs(seen, ui, vi, wi)
        
    print(*seen, sep='\n')
        
main()

Submission status: Wrong Answer

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

stack = [0]
color = [-1]*N
color[0] = 0
while stack:
    v = stack.pop()
    for child, w in adj[v]:
        if color[child] < 0:
            color[child] = (color[v] + w) % 2

for i in color:
    print(i)