Problem:


Score : 400 points

Problem Statement

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

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

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

Constraints

All values in input are integers.

1 \leq N \leq 10^5

1 \leq u_i < v_i \leq N

1 \leq w_i \leq 10^9

Input

Input is given from Standard Input in the following format:

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

Output

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

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

Sample Input 1

3
1 2 2
2 3 1

Sample Output 1

0
0
1

Sample Input 2

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

Sample Output 2

1
0
1
0
1



Sample input:
3
1 2 2
2 3 1


Sample output:
0
0
1

Submission status: Wrong Answer

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

d=[10**15]*N
d[u[0][0]-1]=0
d[u[0][1]-1]=u[0][2]

for i in range(1,N-1):
    if d[u[i][0]-1]>d[u[i][1]-1]:
        d[u[i][0]-1]=d[u[i][1]-1]+u[i][2]
    else:
        d[u[i][1]-1]=d[u[i][0]-1]+u[i][2]
        
for D in d:
    print(D%2)

Submission status: Wrong Answer

Solution code:
N=int(input())
u=[]
v=[]
w=[]
for _ in range(N-1):
    U,V,W=map(int,input().split())
    u.append(U-1)
    v.append(V-1)
    w.append(W)
d=[10**6]*N
d[u[0]]=0
d[v[0]]=w[0]

for i in range(1,N-1):
    if d[u[i]]>d[v[i]]:
        d[u[i]]=d[v[i]]+w[i]
    else:
        d[v[i]]=d[u[i]]+w[i]

ans=[0]*N
for j in range(N):
    if d[j]%2==1:
        ans[j]=1
for a in ans:
    print(a)

Submission status: Wrong Answer

Solution code:
N=int(input())
d=[0 for _ in range(N)]
for _ in range(N-1):
    u,v,w=map(int,input().split())
    if w%2==1:
        d[v-1]=1
for D in d:
    print(D)

Submission status: Wrong Answer

Solution code:
N = int(input())
v = sorted([list(map(int, input().split())) for i in range(N-1)], key=lambda x: (x[0], x[1]))
dist = [0]*(N+1)

for i in range(N-1):
    a, b, w = v[i]
    if a == 1 or dist[a] > 0:
        dist[b] = dist[a] + w
    elif b == 1 or dist[b] > 0:
        dist[a] = dist[b] + w

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

Submission status: Wrong Answer

Solution code:
def main():
    import collections
    import sys
    input = sys.stdin.readline
    N = int(input())
    uvw = [map(int, input().split()) for i in range(N-1)]

    G = [set() for i in range(N)]
    for u, v, w in uvw:
        u -= 1
        v -= 1
        G[u].add((u, w))
        G[v].add((v, w))
    q = collections.deque()
    q.append((0, 0))
    s = set(range(1, N))
    ans = [0]*N
    while(q):
        x, a = q.popleft()
        tmp = set()
        for y, b in G[x]:
            if y in s:
                q.append((y, a+b))
                ans[y] = (a+b) % 2
                tmp.add(y)
        s -= tmp
    print(*ans, sep="\n")


main()

Submission status: Wrong Answer

Solution code:
N = int(input())

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())

G = UnionFind(N)
for i in range(N-1):
    a, b, w = list(map(int, input().split()))
    if w % 2 == 0:
        G.union(a-1, b-1)

a = None
b = None
for i in range(N):
    p = G.find(i)
    if a is None or a == p:
        a = p
        print(0)
    elif b is None or b == p:
        b = p
        print(1)

Submission status: Wrong Answer

Solution code:
from collections import deque
N=int(input())
numbers=[]
for _ in range(N-1):
    u,v,w=map(int,input().split())
    numbers.append([u-1,v-1,w])
inf=pow(10,9)
route=[[inf for _ in range(N)] for _ in range(N)]
for a in numbers:
    route[a[0]][a[1]]=a[2]
    route[a[1]][a[0]]=a[2]
visited_point=[inf for _ in range(N)]
visited_point[0]=0
stack=deque([0])
while len(stack)>0:
    n=stack.popleft()
    number=0
    for z in route[n]:
        if z==inf:
            number+=1
            continue
        if visited_point[number]==inf:
            visited_point[number]=visited_point[n]+z
            stack.append(number)
        number+=1

Submission status: Wrong Answer

Solution code:
from _collections import deque
N=int(input())
numbers=[]
for _ in range(N-1):
    u,v,w=input().split()
    numbers.append([int(u)-1,int(v)-1,int(w)])
inf=pow(10,9)
route=[[inf for _ in range(N)] for _ in range(N)]
for a in numbers:
    route[a[0]][a[1]]=a[2]
    route[a[1]][a[0]]=a[2]
visited_point=[inf for _ in range(N)]
visited_point[0]=0
stack=deque([0])
while len(stack)>0:
    n=stack.pop()
    number=0
    for z in route[n]:
        if z==inf:
            number+=1
            continue
        if visited_point[number]==inf and z%2==0:
            visited_point[number]=visited_point[n]
            stack.appendleft(number)
        number+=1
for a in range(N):
    if visited_point[a]==inf:
        visited_point[a]=1
for a in visited_point:
    print(a)

Submission status: Wrong Answer

Solution code:
N=int(input())
E=[[] for _ in range(N)]
for i in range(N-1):
  u,v,w=map(int,input().split())
  u-=1
  v-=1
  E[u].append((v,w))
  E[v].append((u,w))
color=[-1]*N
color[0]=0
stack=[0]
while stack:
  u=stack.pop()
  for v,w in E[u]:
    if color[v]==-1:
      stack.append(v)
      if (color[u]+w)%2==0:
        color[v]=color[u]
      else:
        color[v]=1 if color[u]==0 else 0
for i in range(N):
  print(color[i])

Submission status: Wrong Answer

Solution code:
from collections import deque
n=int(input())
X=[[] for _ in range(n)]
for i in range(n-1):
    u,v,w=map(int,input().split())
    X[u-1].append([v-1,w])
    X[v-1].append([u-1,w])
C=[0]*n
q=deque([])
for v,w in X[0]:
    q.append([v,w])
visited=[0]*n

while q:
    v,w=q.popleft()

    if visited[v]==1:
        continue
    visited[v]=1
    if w%2==0:
        C[v]=C[u]
    else:
        if C[u]==0:
            C[v]=1
        else:
            C[v]=0
    for pv,pw in X[v]:
        q.append([pv,pw])

for c in C:
    print(c)

Submission status: Wrong Answer

Solution code:
from collections import deque
n=int(input())
X=[[] for _ in range(n)]
for i in range(n-1):
    u,v,w=map(int,input().split())
    X[u-1].append([v-1,w])
    X[v-1].append([u-1,w])
C=[0]*n
q=deque()
for i in range(len(X[0])):
    q.append(X[0][i])
visited=[0]*n
while q:
    v,w=q.popleft()
    if visited[v]==1:
        continue
    visited[v]=1
    if w%2==0:
        C[v]=C[u]
    else:
        if C[u]==0:
            C[v]=1
        else:
            C[v]=0
    for pv,pw in X[v]:
        q.append([pv,pw])

for c in C:
    print(c)

Submission status: Wrong Answer

Solution code:
from collections import deque
n=int(input())
X=[[] for _ in range(n)]
for i in range(n-1):
    u,v,w=map(int,input().split())
    X[u-1].append([v-1,w])
C=[0]*n
q=deque()
for i in range(len(X[0])):
    q.append(X[0][i])

while q:
    v,w=q.popleft()
    if w%2==0:
        C[v]=C[u]
    else:
        if C[u]==0:
            C[v]=1
        else:
            C[v]=0
    for pv,pw in X[v]:
        q.append([pv,pw])

for c in C:
    print(c)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
n = int(input())
# 任意のノードから探索して辺の長さがodd　である辺を挟んで色を変更すれば条件を満たす
# 証明は、木構造なので、サイクルは存在しない、
# ある辺を考えて辺を挟んだ反対側の木構造までの距離を考えると、必ずその辺を一度通る
# 辺の長さがodd で色を変えると、色が変わる回数と同じ回数だけodd の辺を通ることになる
# 頂点１からbfs　で辺の長さが奇数なら色を変え、偶数なら色同じにしていけば良い
odd = [[] for _ in range(n+1)]
even = [[] for _ in range(n+1)]
for i in range(n-1):
    u,v,w = map(int,input().split())
    if u > v: 
        u,v = v,u
    if w % 2: 
        odd[u].append(v)
    else: 
        even[u].append(v)
ret = [0]*(n+1)# 頂点1の色を黒とする
def bfs(u):
    # 頂点uが辺を持つ、全ての頂点vに対して探索する。
    # ただし、頂点１から探索するので、u<vとする
    if len(odd[u]) == 0 and len(even[u]) == 0:
        return
    else:
        for i in odd[u]:
            ret[i] = ret[u] ^1#同じ色
            bfs(i)
        for j in even[u]:
            ret[j] = ret[u] 
            bfs(j)
bfs(1)
for i in range(n):
    print(ret[i+1])

Submission status: Wrong Answer

Solution code:
from collections import deque
def bfs(cur,dist):
    q=deque()
    q.append(cur)
    while q:
        cur=q.popleft()
        for nx,e_dist in G[cur]:
            if ans[nx]==-1:
                ans[nx]=(dist+e_dist)%2
                q.append(nx)

n=int(input())
G=[[] for _ 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])
ans=[-1]*n
bfs(0,0)
print(*ans,sep='\n')

Submission status: Wrong Answer

Solution code:
from collections import deque
def bfs(cur,dist):
    q=deque()
    q.append(cur)
    while q:
        nx=q.popleft()
        for nx,e_dist in G[nx]:
            if ans[nx]==-1:
                ans[nx]=(dist+e_dist)%2
                q.append(nx)

n=int(input())
G=[[] for _ 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])
ans=[-1]*n
bfs(0,0)
print(*ans,sep='\n')

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**7)
n = int(input())
G = [[] for _ in range(n+1)]
for i in range(n-1):
    v,w,dist = map(int, input().split())
    G[v].append((w,dist))
    G[w].append((v,dist))
color = [-1]*(n+1)

tmp = -1
def dfs(a, col):
    if color[a] == -1:
        color[a] = col
    tmp = col
    for next_V,dis in G[a]:
        if color[next_V] != -1:
            continue
        if dis%2 !=0:
            tmp = 1-col
        dfs(next_V, tmp)
dfs(1,0)
[print(color[i]) for i in range(1,n+1)]

Submission status: Wrong Answer

Solution code:
import sys
input=sys.stdin.readline
n=int(input())

#グラフの連結成分を調べる
def Graph():
    G=[[] for i in range(n)]
    #up_G=[0]*n#up_G[i]=頂点iの親
    for i in range(n-1):
        a,b,c=map(int,input().split())
        c=0 if c%2==0 else 1
        G[a-1].append((b,c))
        G[b-1].append((a,c))
    return G

#木上のDFSテンプレ
from collections import deque
def dfs(G,v,p):
    q=deque()
    q.append((v,p))
    dis=0
    dis_l=[-1]*n
    dis_l[0]=0
    while q:
        V,P=q.pop()
        for new_v in G[V-1]:
            v0,v1=new_v
            #new_vが頂点の時はアウト
            if v0==P:continue
            if dis_l[v0-1]>=0:continue
            dis=(dis_l[V-1]+v1)%2
            dis_l[v0-1]=dis
            q.append((v0,V))
            break

    return dis_l


log=Graph()
ans=dfs(log,1,-1)
print(*ans,sep='\n')

Submission status: Wrong Answer

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

N = int(input())
INF = 10**18
edges = [[] for _ in range(N)]

for _ in range(N - 1):
    fr, to, w = map(int, input().split())
    fr -= 1
    to -= 1
    edges[fr].append((to, w))
    edges[to].append((fr, w))

dist = [INF] * N
que = deque([(0, 0)])

while que:
    now, d = que.pop()

    if dist[now] <= d:
        continue
    dist[now] = d
    for to, w in edges[now]:
        que.append((to, w))

ans = [dist[i] % 2 for i in range(N)]
print(*ans, sep='\n')

Submission status: Wrong Answer

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

#グラフの連結成分を調べる
def Graph(ab):
    log=[0]*n
    G=[[] for i in range(n)]
    #up_G=[0]*n#up_G[i]=頂点iの親
    for a,b,c in ab:
        G[a-1].append(b)
        G[b-1].append(a)
        if c%2==0:
            log[a-1]=1
            log[b-1]=1
        #up_G[b-1]=a
    return log #,up_G

log=Graph(uvw)
print(*log,sep='\n')

Submission status: Wrong Answer

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

def dfs(v, p, c):
    color[v] = c
    for vi, wi in g[v]:
        if vi == p: continue
        if wi % 2: dfs(vi, v, 1)
        else: dfs(vi, v, 0)
    return color

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

color = [0 for _ in range(n)]
for i in dfs(0, -1, 0):
  print(i)

Submission status: Wrong Answer

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

def dfs(v, p, c):
    color[v] = c
    for vi, wi in g[v]:
        if vi == p: continue
        if wi % 2: dfs(vi, v, 0)
        else: dfs(vi, v, 1)
    return color

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

color = [0 for _ in range(n)]
for i in dfs(0, -1, 0):
  print(i)

Submission status: Wrong Answer

Solution code:
inputs = open(0).readlines()
n = int(inputs[0])
uvw = [list(map(int, uvw.split())) for uvw in inputs[1:]]

def dfs(root, option):
    nodes, stack = {}, [(root, 0)]
    while stack:
        current_node, color = stack.pop()
        if current_node in nodes:
            continue
        nodes[current_node] = color
        for n, w in get_next_nodes(current_node):
            if n not in nodes:
                stack.append((n, w % 2))
    return nodes

def get_next_nodes(node):
    return lst[node].items()

lst = [{} for _ in range(n)]
for u, v, w in uvw:
    lst[u-1][v-1] = lst[v-1][u-1] = w

dct = dfs(0, get_next_nodes)
for i in range(max(dct)+1):
    print(dct[i])

Submission status: Wrong Answer

Solution code:
#!/usr/bin/python3
# -*- coding: utf-8 -*-

import sys
import numpy
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import dijkstra

def input():
    return sys.stdin.readline().rstrip('\n')

N = int(input())

# めちゃくちゃ遅くて TLE
#V = [[0]*N for _ in range(N)]
#
#for i in range(N-1):
#    u,v,w = list(map(int, input().split()))
#    V[u-1][v-1] = w

U = numpy.zeros(N, dtype=numpy.int32)
V = numpy.zeros(N, dtype=numpy.int32)
W = numpy.zeros(N, dtype=numpy.int32)

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

matrix = csr_matrix((W,(U,V)), shape=(N,N))

D = dijkstra(matrix, directed=False, indices=0)

sys.exit()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/python3
# -*- coding: utf-8 -*-

import sys
import numpy
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import dijkstra

def input():
    return sys.stdin.readline().rstrip('\n')

N = int(input())

# めちゃくちゃ遅くて TLE
#V = [[0]*N for _ in range(N)]
#
#for i in range(N-1):
#    u,v,w = list(map(int, input().split()))
#    V[u-1][v-1] = w

U = numpy.zeros(N, dtype=numpy.int32)
V = numpy.zeros(N, dtype=numpy.int32)
W = numpy.zeros(N, dtype=numpy.int32)

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

matrix = csr_matrix((W,(U,V)), shape=(N,N))

sys.exit()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/python3
# -*- coding: utf-8 -*-

import sys
import numpy
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import dijkstra

def input():
    return sys.stdin.readline().rstrip('\n')

N = int(input())

# めちゃくちゃ遅くて TLE
#V = [[0]*N for _ in range(N)]
#
#for i in range(N-1):
#    u,v,w = list(map(int, input().split()))
#    V[u-1][v-1] = w

U = numpy.zeros(N, dtype=numpy.int32)
V = numpy.zeros(N, dtype=numpy.int32)
W = numpy.zeros(N, dtype=numpy.int32)

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

sys.exit()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/python3

import sys
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import dijkstra

def input():
    return sys.stdin.readline().rstrip('\n')

N = int(input())

V = [[0]*N for _ in range(N)]

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

sys.exit()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/python3

import sys
#from collections import deque
#from copy import copy
#from bisect import bisect_right, bisect_left
#import array
from scipy.sparse.csgraph import dijkstra

N = int(input())

V = [[0]*N for _ in range(N)]

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

D = dijkstra(V, directed=False, indices=0)
print(D)

for i in range(0,N):
    if D[i] % 2 == 0: #even
        print(0)
    else:
        print(1)

Submission status: Wrong Answer

Solution code:
N=int(input())
U=[]
V=[]
W=[]
ans=[0]*(N+1)
for i in range(N-1):
  u,v,w=map(int,input().split())
  U.append(u)
  V.append(v)
  W.append(w)
for i in range(N-1):
  if W[i]%2!=0 :
    if ans[U[i]]==ans[V[i]] and ans[U[i]]==0:
      ans[U[i]]=1
    elif ans[U[i]]==ans[V[i]] and ans[U[i]]==1:
      ans[U[i]]=0
for i in range(N):
  print(ans[i])

Submission status: Wrong Answer

Solution code:
N=int(input())
U=[]
V=[]
W=[]
ans=[0]*(N+1)
for i in range(N-1):
  u,v,w=map(int,input().split())
  U.append(u)
  V.append(v)
  W.append(w)
for i in range(N-1):
  if W[i]%2!=0 :
    if ans[U[i]]==ans[V[i]]:
      ans[U[i]]=1
for i in range(N):
  print(ans[i])

Submission status: Wrong Answer

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

N=int(input())
Graph=[[] for _ in range(N)]
color=[-1]*N

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

def dfs(Graph,v,cur):
    global color
    color[v]=cur
    for next_v_t in Graph[v]:
        next_v=next_v_t[0]
        w=next_v_t[1]
        if color[next_v]!=-1:
            continue
        #ここをcurのまますると答えが間違う
        cur=cur
        if w%2==1:
            cur=1-cur
        dfs(Graph,next_v,cur)

#探索
for v in range(N):
    if color[v]==-1:
        dfs(Graph,v,0)
for i in color:
    print(i)

Submission status: Wrong Answer

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

N=int(input())
Graph=[[] for _ in range(N)]
color=[-1]*N

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

def dfs(Graph,v,cur=0):
    global color
    color[v]=cur
    for next_v_t in Graph[v]:
        next_v=next_v_t[0]
        w=next_v_t[1]
        if color[next_v]!=-1:
            continue
        if w%2==1:
            cur=1-cur
        dfs(Graph,next_v,cur)

#探索
for v in range(N):
    if color[v]==-1:
        dfs(Graph,v)
for i in color:
    print(i)

Submission status: Wrong Answer

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

N=int(input())
Graph=[[] for _ in range(N)]
color=[-1]*N

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

def dfs(Graph,v,cur=0):
    global color
    color[v]=cur
    for next_v_t in Graph[v]:
        next_v=next_v_t[0]
        w=next_v_t[1]
        if color[next_v]!=-1:
            continue
        if w%2==1:
            cur=1-cur
        dfs(Graph,next_v,cur)

#探索
for v in range(N):
    if color[v]!=-1:
        dfs(Graph,v)
for i in color:
    print(i)

Submission status: Wrong Answer

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

N=int(input())
Graph=[[] for _ in range(N)]
color=[-1]*N

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

def dfs(v,cur=0):
    color[v]=cur
    for next_v,w in Graph[v]:
        if color[next_v]!=-1:
            continue
        if w%2==1:
            cur=1-cur
        dfs(next_v,cur)
#探索
dfs(0)
for i in color:
    print(i)

Submission status: Wrong Answer

Solution code:
#
import sys
sys.setrecursionlimit(10**7)

N=int(input())
Graph=[[] for _ in range(N)]
color=[-1]*N

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

def dfs(v,cur=0):
    global color
    color[v]=cur
    for next_v_t in Graph[v]:
        next_v=next_v_t[0]
        w=next_v_t[1]
        if color[next_v]!=-1:
            continue
        if w%2==1:
            cur=1-cur
        dfs(next_v,cur)

#探索
dfs(0)
for i in color:
    print(i)

Submission status: Wrong Answer

Solution code:
#
import sys
sys.setrecursionlimit(10**7)

N=int(input())
Graph=[[] for _ in range(N+1)]
color=[-1]*(N+1)

for _ in range(N-1):
    a,b,c=map(int,input().split())

    Graph[a].append((b,c))
    Graph[b].append((a,c))

def dfs(Graph,v,cur=0):
    global color
    color[v]=cur
    for next_v_t in Graph[v]:
        next_v=next_v_t[0]
        w=next_v_t[1]
        if color[next_v]!=-1:
            continue
        if w%2==1:
            cur=1-cur
        dfs(Graph,next_v,cur)

#探索
dfs(Graph,1)
for i in color[1:]:
    print(i)

Submission status: Wrong Answer

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

N=int(input())
Graph=[[] for _ in range(N)]
color=[-1]*N

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

def dfs(Graph,v,cur=0):
    global color
    color[v]=cur
    for next_v_t in Graph[v]:
        next_v=next_v_t[0]
        w=next_v_t[1]
        if color[next_v]!=-1:
            continue
        if w%2==1:
            cur=1-cur
        dfs(Graph,next_v,cur)

#探索
dfs(Graph,0)
for i in color:
    print(i)

Submission status: Wrong Answer

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

N=int(input())
Graph=[[] for _ in range(N)]
color=[-1]*N

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

def dfs(Graph,v,cur=0):
    global color
    color[v]=cur
    for next_v_t in Graph[v]:
        next_v=next_v_t[0]
        w=next_v_t[1]
        if color[next_v]!=-1:
            continue
        if w%2==1:
            cur=1-cur
        dfs(Graph,next_v,cur)

#探索
dfs(Graph,0)
for i in color:
    print(i)

Submission status: Wrong Answer

Solution code:
#
import sys
sys.setrecursionlimit(10**8)

N=int(input())
Graph=[[] for _ in range(N)]
color=[-1]*N

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

def dfs(Graph,v,cur=0):
    global color
    color[v]=cur
    for next_v_t in Graph[v]:
        next_v=next_v_t[0]
        w=next_v_t[1]
        if color[next_v]!=-1:
            continue
        if w%2==1:
            cur=1-cur
        dfs(Graph,next_v,cur)

#探索
is_bipartite=[True for _ in range(N)]
for v in range(N):
    if color[v]!=-1:
        continue
    if not dfs(Graph,v):
        is_bipartite[v]=False
if is_bipartite:
    for i in color:
        print(i)

Submission status: Wrong Answer

Solution code:
#
import sys
sys.setrecursionlimit(10**8)

N=int(input())
Graph=[[] for _ in range(N)]
color=[-1]*N

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

def dfs(Graph,v,cur=0):
    global color
    color[v]=cur
    for next_v_t in Graph[v]:
        next_v=next_v_t[0]
        w=next_v_t[1]
        if color[next_v]!=-1:
            if w%2==1 and color[next_v] == cur:
                return False
            if w%2==0 and color[next_v] != cur:
                return False
            continue
        if w%2==1:
            cur=1-cur
        if not dfs(Graph,next_v,cur):
            return False
    return True

#探索
is_bipartite=[True for _ in range(N)]
for v in range(N):
    if color[v]!=-1:
        continue
    if not dfs(Graph,v):
        is_bipartite[v]=False
if is_bipartite:
    for i in color:
        print(i)

Submission status: Wrong Answer

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import 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()
e = [[] for _ in range(N)]

for _ in range(N-1):
    t = LIST()
    e[t[0]-1].append([t[1]-1, t[2]%2])
    e[t[1]-1].append([t[0]-1, t[2]%2])

a = [0] * N
f = []

"""
for edge in G:
    if edge[2]%2 == 1:
        a[edge[1]-1] = 1 - a[edge[0]-1]
    else:
        a[edge[1]-1] = a[edge[0]-1]
"""
def r(n):
    f.append(n)
    for nn in e[n]:
        if nn[0] not in f:
            continue
        if nn[1] == 0:
            a[nn[0]] = a[n]
            r(nn[0])
        else:
            a[nn[0]] = 1 - a[n]
            r(nn[0])

r(0)
for item in a:
    print(item)

Submission status: Wrong Answer

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import 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()
e = [[] for _ in range(N)]

for _ in range(N-1):
    t = LIST()
    e[t[0]-1].append([t[1]-1, t[2]%2])

a = [0] * N

"""
for edge in G:
    if edge[2]%2 == 1:
        a[edge[1]-1] = 1 - a[edge[0]-1]
    else:
        a[edge[1]-1] = a[edge[0]-1]
"""
def r(n):
    for nn in e[n]:
        if nn[1] == 0:
            a[nn[0]] = a[n]
            r(nn[0])
        else:
            a[nn[0]] = 1 - a[n]
            r(nn[0])

r(0)
for item in a:
    print(item)

Submission status: Wrong Answer

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import 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()
e = [[] for _ in range(N)]

for _ in range(N-1):
    t = LIST()
    e[t[0]-1].append([t[1]-1, t[2]%2])

a = [0] * N

"""
for edge in G:
    if edge[2]%2 == 1:
        a[edge[1]-1] = 1 - a[edge[0]-1]
    else:
        a[edge[1]-1] = a[edge[0]-1]
"""
print(e)
def r(n):
    for nn in e[n]:
        if nn[1] == 0:
            a[nn[0]] = a[n]
            r(nn[0])
        else:
            a[nn[0]] = 1 - a[n]
            r(nn[0])

r(0)
for item in a:
    print(item)

Submission status: Wrong Answer

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import 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()
G = []

for _ in range(N-1):
    G.append(LIST())

G.sort(key=lambda x: x[0])
a = [0] * N
node_idx = 1

for edge in G:
    if edge[2]%2 == 1:
        a[edge[1]-1] = 1 - a[edge[0]-1]
    else:
        a[edge[1]-1] = a[edge[0]-1]

for _ in a:
    print(_)

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, c):
    results[i] = c
    for j in range(N):
        if TABLE[i][j] >= 0:
            if TABLE[i][j] % 2 == 0:
                TABLE[i][j] = -1
                results = dfs(j, results, c)
            else:
                TABLE[i][j] = -1
                results = dfs(j, results, 0 if c == 1 else 1)

    return results

results = [0] * N
for i in range(N):
    if max(TABLE[i]) > 0:
        for r in dfs(i, results, 1):
            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]]) % 2 == 0 and graph[i][j][1] % 2 != 0:
                if c[graph[i][j][0]] == 0:
                    c[graph[i][j][0]] = 1
                elif c[graph[i][j][0]] == 1:
                    c[graph[i][j][0]] = 0

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