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

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

Submission status: Wrong Answer

Solution code:
from collections  import deque

n = int(input())
vw = [list(map(int,input().split())) for _ in range(n-1)]
tree = [[]]*n
color = [0]*n
visited = [False]*n
d = deque()
d.append((0,0))
for i in vw:
    tree[i[0]-1].append((i[1]-1,i[2]))
    tree[i[1]-1].append((i[0]-1,i[2]))
while d:
    p = d.pop()
    for i in tree[p[0]]:
        if not visited[i[0]]:
            visited[i[0]] =True
            if i[1]%2 ==0:
                d.appendleft((i[0],p[1]))
                color[i[0]] = p[1]
            elif i[1]%2 ==1  and p[1] == 1:
                d.appendleft((i[0],0))
                color[i[0]] = 0
            else:
                d.appendleft((i[0],1))
                color[i[0]] = 1

for c in color:
  print(c)

Submission status: Wrong Answer

Solution code:
n = int(input())
vw = [list(map(int,input().split())) for _ in range(n-1)]
tree = [[]]*n
color = [0]*n
visited = [False]*n
q = [(0,0)]
for i in vw:
    tree[i[0]-1].append((i[1]-1,i[2]))
    tree[i[1]-1].append((i[0]-1,i[2]))
while q:
    p = q.pop()
    for i in tree[p[0]]:
        if not visited[i[0]]:
            visited[i[0]] =True
            if i[1]%2 ==0:
                q.append((i[0],p[1]))
                color[i[0]] = p[1]
            elif i[1]%2 ==1  and p[1] == 1:
                q.append((i[0],0))
                color[i[0]] = 0
            else:
                q.append((i[0],1))
                color[i[0]] = 1

for c in color:
  print(c)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
input = lambda: sys.stdin.readline()[:-1]
sys.setrecursionlimit(10**8)

class UnionFind:
    __slots__ = ['id','sz']

    def __init__(self, n):
        self.id = [-1] * n
        self.sz = n

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

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

    def union(self, x, y):
        s1, s2 = self.root(x), self.root(y)
        if s1 != s2:
            if self.id[s1] <= self.id[s2]:
                self.id[s1] += self.id[s2]
                self.id[s2] = s1
            else:
                self.id[s2] += self.id[s1]
                self.id[s1] = s2
            self.sz-=1
            return True
        return False

n=int(input())
uf=UnionFind(n)
l=[[] for i in range(n)]
used=[0]*n
color=[0]*n
for i in range(n-1):
    u,v,w=map(int,input().split())
    if w%2==0:
        l[min(u,v)-1].append((max(u,v),1))
    else:
        l[min(u,v)-1].append((max(u,v),0))
# print(l)
for i in range(n):
    if used[i]:
        print(color[i])

        continue
    for le in l[i]:
        color[le[0]-1]=color[i] if le[1] else (color[i]+1)%2
        used[le[0]-1]=1
    print(color[i])
    used[i]=1

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
input = lambda: sys.stdin.readline()[:-1]
sys.setrecursionlimit(10**8)

class UnionFind:
    __slots__ = ['id','sz']

    def __init__(self, n):
        self.id = [-1] * n
        self.sz = n

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

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

    def union(self, x, y):
        s1, s2 = self.root(x), self.root(y)
        if s1 != s2:
            if self.id[s1] <= self.id[s2]:
                self.id[s1] += self.id[s2]
                self.id[s2] = s1
            else:
                self.id[s2] += self.id[s1]
                self.id[s1] = s2
            self.sz-=1
            return True
        return False

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

Submission status: Wrong Answer

Solution code:
# 2019/10/10

n=int(input())
node=[None]*n
    

def chk(u,v,w):
    global node
    if node[u] is not None:return
    if w%2:
        node[u]=0 if node[v] else 1
    else:node[u]=node[v]

flag=True
for i in range(n-1):
    u,v,w=map(int,input().split())
    u-=1;v-=1
    if flag:node[u]=0
    chk(u,v,w)
    chk(v,u,w)
    flag=False

for e in node:
    print(e)

Submission status: Wrong Answer

Solution code:
# 2019/10/10

n=int(input())
node=[None]*n
node[0]=0
for i in range(n-1):
    u,v,w=map(int,input().split())
    u-=1;v-=1
    color=1 if w%2 else 0
    if node[u] is None:node[u]=color
    if node[v] is None:node[v]=color
for e in node:
    print(e)

Submission status: Wrong Answer

Solution code:
# 2019/10/10

n=int(input())
node=[None]*n

for i in range(n-1):
    u,v,w=map(int,input().split())
    u-=1;v-=1
    color=1 if w%2 else 0
    if node[u] is None:node[u]=color
    if node[v] is None:node[v]=color
for e in node:
    print(e)

Submission status: Wrong Answer

Solution code:
n=int(input())
ls=[[int(s) for s in input().split()] for _ in range(n-1)]
ans=[-1]*(n+1)
ans[1]=0
position=1
v_num=1
check_ls=[0]*(n+1)
ko_ls=[[] for _ in range(n+1)]
pan=[0]
while v_num<n:
  if check_ls[position]==0:
    lenls=len(ls)
    for i in range(lenls):
      if ls[lenls-i-1][0]==position:
        ko_ls[position].append([ls[lenls-i-1][1],ls[lenls-i-1][2]])
        ls.pop(lenls-i-1)
      elif ls[lenls-i-1][1]==position:
        ko_ls[position].append([ls[lenls-i-1][0],ls[lenls-i-1][1]])
        ls.pop(lenls-i-1)
  if ko_ls[position]==[]:
    position=pan[-1]
    pan.pop(-1)
  else:
    nex,d=ko_ls[position][0]
    ko_ls[position].pop(0)
    ans[nex]=(ans[position]+d)%2
    pan.append(position)
    position=nex
    v_num+=1
for i in range(1,n+1):
  print(ans[i])

Submission status: Wrong Answer

Solution code:
N=int(input())
uvw=[[0,0,0] for _ in range(N-1)]
U=[]
for i in range(N-1):
  u,v,w=list(map(int,input().split()))
  u,v=min(u,v),max(u,v)
  uvw[i]=[u,v,w]
  if u not in U:
    U.append(u)
lst=[None]*N

def find(s):
  lst=[s]
  for i in range(N-1):
    if uvw[i][0]==s:
      t=uvw[i][1]
      if uvw[i][2]%2==0:
        lst.append(t)
      else:
        pass
  return lst
tmp=U.pop(0)
l1=find(tmp)
for i in U:
  if len(l1)<len(find(i)):
    l1=find(i)
    
for i in l1:
  lst[i-1]=0
  
for i in range(N):
  if lst[i]!=None:
    print(0)
  else:
    print(1)

Submission status: Wrong Answer

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

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

for i in range(N-1):
    u, v, w = map(int, input().split())
    if w % 2 == 0:
        edges[u-1].append((v-1, 1))
        edges[v-1].append((u-1, 1))
    else:
        edges[u-1].append((v-1, -1))
        edges[v-1].append((u-1, -1))

colors = [None] * N
def set_color(x, c):
    colors[x] = c
    for y, sgn in edges[x]:
        if colors[y] == None:
            set_color(y, c*sgn)
set_color(1, 1)
for z in colors:
    print(z)

Submission status: Wrong Answer

Solution code:
from operator import itemgetter
import sys
sys.setrecursionlimit(10**6)

N = int(input())
UVW = sorted([list(map(int, input().split())) for _ in range(N-1)], key=itemgetter(0))
graph = [[-1] * N for _ in range(N)]


for u, v, w in UVW:
    graph[u-1][v-1] = w % 2
    graph[v-1][u-1] = w % 2
d = [-1] * N
d[0] = 0
def f(i):
    for j in range(N):
        if i == j:
            continue
        if d[i] != -1 and d[j] == -1 and graph[i][j] != -1 :
            d[j] = (d[i] + graph[i][j]) % 2
            f(j)
    print(d)            
for x in d:
    print(x)

Submission status: Wrong Answer

Solution code:
n=int(input())
edge=[[]for i in range(n+1)]
for i in range(n-1):
    a,b,c=map(int,input().split())
    if c%2==0:
        edge[a].append((b,1))
        edge[b].append((a,1))
    else:
        edge[a].append((b,-1))
        edge[b].append((a,-1))
        

ans=[None]*(n+1)
check=1

for i in range(1,n+1):
    for j in edge[i]:
        if ans[j[0]] is None:
            ans[j[0]]=check*j[1]
            check*=j[1]
            
for i in ans[1:]:
    print((i+1)//2)

Submission status: Wrong Answer

Solution code:
n=int(input())
edge=[[]for i in range(n+1)]
for i in range(n-1):
    a,b,c=map(int,input().split())
    if c%2==0:
        edge[a].append((b,1))
        edge[b].append((a,1))
    else:
        edge[a].append((b,-1))
        edge[b].append((a,-1))
        

ans=[None]*(n+1)
check=1
print(edge)
for i in range(1,n+1):
    for j in edge[i]:
        if ans[j[0]] is None:
            ans[j[0]]=check*j[1]
            check*=j[1]
            
for i in ans[1:]:
    print((i+1)//2)

Submission status: Wrong Answer

Solution code:
n=int(input())
edge=[[]for i in range(n+1)]
for i in range(n-1):
    a,b,c=map(int,input().split())
    if c%2==0:
        edge[a].append((b,1))
        edge[b].append((a,1))
    else:
        edge[a].append((b,-1))
        edge[b].append((a,-1))
        

ans=[None]*(n+1)
check=1
for i in range(1,n+1):
    for j in edge[i]:
        if ans[j[0]] is None:
            ans[j[0]]=j[1]*check
            check=j[1]
            
for i in ans[1:]:
    print((i+1)//2)

Submission status: Wrong Answer

Solution code:
n=int(input())
edge=[[]for i in range(n+1)]
for i in range(n-1):
    a,b,c=map(int,input().split())
    c=c%2
    edge[a].append((b,c))
    edge[b].append((a,c))

ans=[None]*(n+1)
ans[1]=0
for i in range(1,n+1):
    for j in edge[i]:
        if ans[j[0]] is None:
            if j[1]==0:
                ans[j[0]]=ans[i]
            else:
                if ans[i]==1:
                    ans[j[0]]=0
                else:
                    ans[j[0]]=1
            
for i in ans[1:]:
    print(i)

Submission status: Wrong Answer

Solution code:
n=int(input())
edge=[[]for i in range(n+1)]
for i in range(n-1):
    a,b,c=map(int,input().split())
    c=c%2
    edge[a].append((b,c))
    edge[b].append((a,c))

ans=[None]*(n+1)
for i in range(1,n+1):
    for j in edge[i]:
        if ans[j[0]] is None:
            ans[j[0]]=j[1]
            
for i in ans[1:]:
    print(i)

Submission status: Wrong Answer

Solution code:
n = int(input())
tree = [list(map(int, input().split())) for _ in range(n-1)]
for i in range(n-1):
    tree[i][:2] = sorted(tree[i][:2])
tree = sorted(tree, key=lambda x:x[0])
ans = [0 for _ in range(n)]

for i in range(n-1):
    if tree[i][2]%2 == 0:
        ans[tree[i][1]-1] = ans[tree[i][0]]
    else:
        ans[tree[i][1]-1] = ~ans[tree[i][0]]
for i in range(n):
    print(ans[i]*-1)

Submission status: Wrong Answer

Solution code:
import heapq
import sys

input = sys.stdin.readline

def dijkstra_heap(s,edge,N):
    d = [float('inf')] * N
    used = [True] * N
    d[s] = 0
    used[s] = False
    edgelist = []
    for a,b in edge[s]:
        heapq.heappush(edgelist, a*(10**6)+b)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        if not used[minedge%(10**6)]:
            continue
        v = minedge%(10**6)
        d[v] = minedge//(10**6)
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,(e[0]+d[v])*(10**6)+e[1])
    return d

def main():
    N = int(input())
    edge = [[] for i in range(N)]

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

    D = dijkstra_heap(0,edge,N)
    print(D)
    first = D[0]
    for d in D:
        if abs(d - first) % 2 == 0:
            print(0)
        else:
            print(1)

main()

Submission status: Wrong Answer

Solution code:
import math
import collections
import itertools
import sys
import bisect
from heapq import heappop,heappush,heapify
sys.setrecursionlimit(10**6)
def MAP(): return list(map(int,input().split()))
def INT(): return int(input())
def FLOAT(): return float(input())
MOD = 10**9+7


N = INT()
G = [dict() for _ in range(N)]
for i in range(N-1):
    u,v,w=map(int,input().split())
    G[u-1][v-1]=w
    G[v-1][u-1]=w
color=[-1 for _ in range(N)]
dist=[-1 for _ in range(N)]
dist[0]=0
q=[0]
while q:
    r=q.pop()
    for p in G[r]:
        print(p)
        if dist[p]!=-1:
            continue
        dist[p]=dist[r]+G[r][p]
        q.append(p)
for i in range(N):
    color[i]=dist[i]%2
for ans in color:
    print(ans)

Submission status: Wrong Answer

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

global color 
global adlist
color = [0 for _ in range(100001)] 

def make_adlist(N, uvw):
  global adlist
  adlist = [[] for _ in range(N)]
  for u, v, w in uvw:
    adlist[u-1] += [[v-1, w%2]]
  return adlist 

def dfs(v, c):
  global color
  global adlist
  color[v] = c
  for next_v, w in adlist[v]:
    if color[next_v] == 0 and w % 2 != 0:
      dfs(next_v, -c)
    elif color[next_v] == 0 and w % 2 == 0:
      dfs(next_v, c)

  return 


def main():
  N = int(input())
  uvw = [list(map(int, input().split())) for _ in range(N-1)]
  adlist = make_adlist(N, uvw)
  dfs(0, 1)
  for c in color[:N]:
    if c == 1:
      print(1)
    else:
      print(0)


if __name__ == "__main__":
  main()

Submission status: Wrong Answer

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

global color 
global adlist
color = [0 for _ in range(100001)] 

def make_adlist(N, uvw):
  global adlist
  adlist = [[] for _ in range(N)]
  for u, v, w in uvw:
    adlist[u-1] += [[v-1, w%2]]
  return adlist 

def dfs(v, c, dis):
  global color
  global adlist
  color[v] = c
  for next_v, w in adlist[v]:
    if color[next_v] == 0 and w % 2 != 0:
      dfs(next_v, -c, (dis+w)%2)
    elif color[next_v] == 0 and w % 2 == 0:
      dfs(next_v, c, (dis+w)%2)

  return 


def main():
  N = int(input())
  uvw = [list(map(int, input().split())) for _ in range(N-1)]
  adlist = make_adlist(N, uvw)
  for i in range(N):
    if color[i] == 0:
      dfs(i, 1, 0)
  for c in color[:N]:
    if c == 1:
      print(1)
    else:
      print(0)


if __name__ == "__main__":
  main()

Submission status: Wrong Answer

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

global color 
global adlist
color = [0 for _ in range(100001)] 

def make_adlist(N, uvw):
  global adlist
  adlist = [[] for _ in range(N)]
  for u, v, w in uvw:
    adlist[u-1] += [[v-1, w%2]]
  return adlist 

def dfs(v, c, dis):
  global color
  global adlist
  color[v] = c
  for next_v, w in adlist[v]:
    if color[next_v] == 0 and (dis+w) % 2 != 0:
      dfs(next_v, -c, (dis+w)%2)
    elif color[next_v] == 0 and (dis+w) % 2 == 0:
      dfs(next_v, c, (dis+w)%2)

  return 


def main():
  N = int(input())
  uvw = [list(map(int, input().split())) for _ in range(N-1)]
  adlist = make_adlist(N, uvw)
  for i in range(N):
    if color[i] == 0:
      dfs(i, 1, 0)
  for c in color[:N]:
    if c == 1:
      print(1)
    else:
      print(0)


if __name__ == "__main__":
  main()

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(1000000)

global color 
global adlist
color = [0 for _ in range(100001)] 

def make_adlist(N, uvw):
  global adlist
  adlist = [[] for _ in range(N)]
  for u, v, w in uvw:
    adlist[u-1] += [[v-1, w%2]]
  return adlist 

def dfs(v, c, dis):
  global color
  global adlist
  color[v] = c
  for next_v, w in adlist[v]:
    if color[next_v] == 0 and (dis+w) % 2 != 0:
      dfs(next_v, -c, (dis+w)%2)
    elif color[next_v] == 0 and (dis+w) % 2 == 0:
      dfs(next_v, c, (dis+w)%2)

  return 


def main():
  N = int(input())
  uvw = [list(map(int, input().split())) for _ in range(N-1)]
  adlist = make_adlist(N, uvw)
  for i in range(N):
    if color[i] == 0:
      dfs(i, 1, 0)
  for c in color[:N]:
    if c == 1:
      print(1)
    else:
      print(0)


if __name__ == "__main__":
  main()

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(1000000)

global color 
global adlist
color = [0 for _ in range(100001)] 

def make_adlist(N, uvw):
  global adlist
  adlist = [[] for _ in range(N)]
  for u, v, w in uvw:
    adlist[u-1] += [[v-1, w]]
  return adlist 

def dfs(v, c, dis):
  global color
  global adlist
  color[v] = c

  for next_v, w in adlist[v]:

    if color[next_v] == c:
      return False
    if color[next_v] == 0 and (dis+w) % 2 != 0:
      return dfs(next_v, -c, dis+w)
    elif color[next_v] == 0 and (dis+w) % 2 == 0:
      return dfs(next_v, c, dis+w)
    elif color[next_v] == -c and (dis+w) % 2 == 0:
      return True 
    else:
      return False

  return True


def main():
  N = int(input())
  uvw = [list(map(int, input().split())) for _ in range(N-1)]
  adlist = make_adlist(N, uvw)
  for i in range(N):
    if color[i] == 0:
      dfs(i, 1, 0)
  for c in color[:N]:
    if c == 1:
      print(1)
    else:
      print(0)


if __name__ == "__main__":
  main()

Submission status: Wrong Answer

Solution code:
import sys,queue,copy
sys.setrecursionlimit(10**8)
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())

N = int(input())

Wlist = list()

for _ in range(N-1):
    Wlist.append(inpl())

anslist = [-1]*(N+1)

for u,v,w in Wlist:
    if anslist[u] == -1 and anslist[v] == -1:
        if w%2==0:
            anslist[u]=1
            anslist[v]=1
        else:
            anslist[u]=1
            anslist[v]=0
    elif anslist[u] != -1 or anslist[v] != -1:
        if w%2==0:
            if anslist[u] == -1:
                anslist[u] = anslist[v]
            elif anslist[v] == -1:
                anslist[v] = anslist[u]
        else:
            if anslist[u] == -1:
                anslist[u] = anslist[v]+1
            elif anslist[v] ==-1:
                anslist[v] = anslist[u]+1

for a in anslist:
    if a == -1:
        continue
    print(a%2)

Submission status: Wrong Answer

Solution code:
def main():
    N = int(input())
    G = [[] for i in range(N + 1)]
    for i in range(N-1):
        u, v, w = (int(i) for i in input().split())
        G[u].append((v,w))
        G[v].append((u,w))
    def is_bipartite_by_dfs(G,v,color):
        todo = []
        cur = 0
        color[v] = cur
        todo.append(v)
        while todo:
            u = todo[-1]
            for next_v,w in G[u]:
                if color[next_v] != -1: 
                    continue
                if w&1:
                    cur = (cur + 1) % 2
                color[next_v] = cur
                todo.append(next_v)
                break
            else:
                todo.pop()
    color = [-1] * (N + 1) # 0: white, 1: black, -1: undefined
    is_bipartite_by_dfs(G,1,color)
    for i in range(1,N+1):
        print(color[i])
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
n = int(input())
Edges = [list(map(int,input().split())) for i in range(n-1)]
for edge in Edges:
    edge[0] -= 1
    edge[1] -= 1
    edge[2] %= 2

Graph = [[] for i in range(n)]
for edge in Edges:
    Graph[edge[0]].append([edge[1],edge[2]])
    Graph[edge[1]].append([edge[0],edge[2]])

Color = [-1 for i in range(n)]
Color[0] = 0

stack = [0]

while stack:
    node = stack.pop()
    for adj in Graph[node]:
        if Color[adj[0]] == -1:
            if Color[node] == adj[1]:
                Color[adj[0]] = Color[node]
            elif Color[node] == 0:
                Color[adj[0]] = 1
            else:
                Color[adj[0]] = 0
            stack.append(adj[0])
            
for color in Color:
    print(color)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
from operator import itemgetter

def main():
    N = int(input())

    A = []
    white = {}
    black = {}
    for _ in range(N - 1):
        u = [int(x) for x in input().split()]
        if u[1] < u[0]:
            A.append([u[1], u[0], u[2]])
        else:
            A.append(u)

    A_sorted = sorted(A)

    answer = [-1] * N

    for a in A_sorted:
        i = a[0] - 1
        j = a[1] - 1
        if a[2] % 2 == 0:
            if answer[i] != -1:
                answer[j] = answer[i]
            elif answer[j]  != -1:
                answer[i] = answer[j]
            else:
                answer[i] = 1
                answer[j] = 1
        else:
            if answer[i] == 1:
                answer[j] = 0
            elif answer[i] == 0:
                answer[j] = 1
            elif answer[j] == 0:
                answer[i] = 1
            elif answer[j] == 0:
                answer[j] = 1
            else:
                answer[i] = 1
                answer[j] = 0

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


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

ans = [None for _ in range(N)]

for e in VW:
    if ans[e[0]-1] == None and ans[e[1]-1] == None:
        if e[2] % 2 == 0:
            ans[e[0]-1] = True
            ans[e[1]-1] = True
        else:
            ans[e[0]-1] = True
            ans[e[1]-1] = False
    if e[2] % 2 == 0:
        if ans[e[0]-1] == True:
            ans[e[1]-1] = True
        elif ans[e[0]-1] == False:
            ans[e[1]-1] = False
        if ans[e[1]-1] == True:
            ans[e[0]-1] = True
        elif ans[e[1]-1] == False:
            ans[e[0]-1] = False
    else:
        if ans[e[0]-1] == True:
            ans[e[1]-1] = False
        elif ans[e[0]-1] == False:
            ans[e[1]-1] = True
        if ans[e[1]-1] == True:
            ans[e[0]-1] = False
        elif ans[e[1]-1] == False:
            ans[e[0]-1] = True

for e in ans:
    if e:
        print(0)
    else:
        print(1)

Submission status: Wrong Answer

Solution code:
from collections import deque
N = int(input())
A = [list(map(int, input().split())) for _ in range(N-1)]

T = [[] for _ in range(N)]
for i in range(N-1):
    u, v = A[i][0] - 1, A[i][1] - 1
    d = A[i][2] % 2 
    T[u].append([v, d])
    T[v].append([u, d])

visited = [True] + [False] * (N-1)
ans = [0] * N
que = deque([0]) 
while len(que) > 0:
    q = que.popleft()
    for v, d in T[q]:
        if visited[v]:
            pass
        else:
            que.append(v)
            visited[v] = True
            ans[v] = d
            
for a in ans:
    print(a)

Submission status: Wrong Answer

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

T = [[] for _ in range(N)]
for i in range(N-1):
    u, v = A[i][0] - 1, A[i][1] - 1
    d = A[i][2] % 2 
    T[u].append([v, d])
    T[v].append([u, d])

visited = [True] + [False] * (N-1)
ans = [0] * N
for i in range(N):
    if visited[i]:
        for t in T[i]:
            if visited[t[0]]:
                pass
            else:
                ans[t[0]] = t[1]
                visited[t[0]] = True
            
            
for a in ans:
    print(a)

Submission status: Wrong Answer

Solution code:
import sys
from collections import Counter, deque, defaultdict
from math import factorial
import heapq, bisect
import math
import itertools
sys.setrecursionlimit(10 ** 5 + 10)
INF = 10*5
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()))

n = INT()
edges = [(0,0,0)]*(n-1)
for i in range(n-1):
    u, v, w = MAP()
    edges[i] = (u-1, v-1, w%2)

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

for edge in edges:
    if edge[2] == 1:
        G[edge[0]].append(edge[1])
        G[edge[1]].append(edge[0])

for edge in edges:
    if edge[2] == 0:
        if len(G[edge[0]]) != 0:
            G[edge[1]].append(G[edge[0]][0])
            G[G[edge[0]][0]].append(edge[1])
        elif len(G[edge[1]]) != 0:
            G[edge[0]].append(G[edge[1]][0])
            G[G[edge[1]][0]].append(edge[0])

color = [-1]*n

def dfs(v,c):
    color[v] = c
    for v_next in G[v]:
        if color[v_next] == -1:
            dfs(v_next,(c+1)%2)

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

Submission status: Wrong Answer

Solution code:
import sys
from collections import Counter, deque, defaultdict
from math import factorial
import heapq, bisect
import math
import itertools
sys.setrecursionlimit(10 ** 5 + 10)
INF = 10*5
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()))

n = INT()
edges = [(0,0,0)]*(n-1)
for i in range(n-1):
    u, v, w = MAP()
    edges[i] = (u-1, v-1, w%2)

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

for edge in edges:
    if edge[2] == 1:
        G[edge[0]].append(edge[1])
        G[edge[1]].append(edge[0])

for edge in edges:
    if edge[2] == 0:
        if len(G[edge[0]]) != 0:
            G[edge[1]].append(G[edge[0]][0])
            G[G[edge[0]][0]].append(edge[1])
        elif len(G[edge[1]]) != 0:
            G[edge[0]].append(G[edge[1]][0])
            G[G[edge[1]][0]].append(edge[0])

print(G)
color = [-1]*n

def dfs(v,c):
    color[v] = c
    for v_next in G[v]:
        if color[v_next] == -1:
            dfs(v_next,(c+1)%2)

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

Submission status: Wrong Answer

Solution code:
n = int(input())
tree = [list(map(int, input().split())) for _ in range(n-1)]
color = [0] * (n+1)
#print(tree)
tree.sort(key=lambda x: x[1])
tree.sort(key=lambda x: x[0])
#print(tree)

for i in range(n-1):
    if color[tree[i][0]] == 0 and color[tree[i][1]] == 0:
        color[tree[i][0]] = 1
        if tree[i][2] % 2 == 0:
            color[tree[i][1]] = color[tree[i][0]]
        else:
            color[tree[i][1]] = color[tree[i][0]] * (-1)
    elif color[tree[i][1]] == 0:
        if tree[i][2] % 2 == 0:
            color[tree[i][1]] = color[tree[i][0]]
        else:
            color[tree[i][1]] = color[tree[i][0]] * (-1)
    elif color[tree[i][0]] == 0:
        if tree[i][2] % 2 == 0:
            color[tree[i][0]] = color[tree[i][1]]
        else:
            color[tree[i][0]] = color[tree[i][1]] * (-1)

for i in range(1, n+1):
  if color[i] < 0:
    print(0)
  else:
  	print(1)

Submission status: Wrong Answer

Solution code:
n = int(input())
tree = [list(map(int, input().split())) for _ in range(n-1)]
color = [0] * (n+1)
#print(tree)
tree.sort(key=lambda x: x[0])
#print(tree)

for i in range(n-1):
    if color[tree[i][0]] == 0:
        color[tree[i][0]] = 1
    
    if tree[i][2] % 2 == 0:
        color[tree[i][1]] = color[tree[i][0]]
    else:
        color[tree[i][1]] = color[tree[i][0]] * (-1)

for i in range(1, n+1):
  if color[i] < 0:
    print(0)
  else:
  	print(1)

Submission status: Wrong Answer

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

def main():
    N = int(input())

    A = []
    for _ in range(N - 1):
        A.append([int(x) for x in input().split()])

    answer = [-1] * N

    for a in A:
        if a[2] % 2 == 0:
            if answer[a[0] - 1] != -1:
                answer[a[1] - 1] = answer[a[0] - 1]
            elif answer[a[1] - 1] != -1:
                answer[a[0] - 1] = answer[a[1] - 1]
            else:
                answer[a[0] - 1] = 1
                answer[a[1] - 1] = 1
        else:
            if answer[a[0] - 1] == 1:
                answer[a[1] - 1] = 0
            elif answer[a[0] - 1] == 0:
                answer[a[1] - 1] = 1
            elif answer[a[1] - 1] != 1:
                answer[a[0] - 1] = 0
            elif answer[a[1] - 1] != 0:
                answer[a[0] - 1] = 1
            else:
                answer[a[0] - 1] = 1
                answer[a[1] - 1] = 0

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


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

#print(uvw)

ans = [0 for i in range(n)]
def ki(a,k,ans):
    count = 0
    for i in range(n-1):
        if uvw[i][0] == a:
            count += 1
            ans[a-1] = k
    #        print(ans)
            ki(uvw[i][1],k+uvw[i][2],ans)
    if count == 0:
        ans[a-1] = k
ki(1,0,ans)
#print(ans)
for i in range(n):
    print(ans[i]%2)

Submission status: Wrong Answer

Solution code:
#D
n=int(input())
uvw=[list(map(int,input().split())) for _ in range(n-1)]
data=[0 for i in range(n+1)]
uvw.sort()
for i in range(n-1):
    if uvw[i][2]%2==1:
        if data[uvw[i][0]]==0:
            data[uvw[i][1]]=1
    else:
        if data[uvw[i][0]]==1:
            data[uvw[i][1]]=1
for i in range(1,n+1):
    print(data[i])

Submission status: Wrong Answer

Solution code:
n = int(input())
lv = [[] for i in range(n+1)]
for i in range(n-1):
	u, v, w = map(int, input().split())
	lv[u].append([v, w])
	lv[v].append([u, w])

ln = [0] * (n+1)
visited = [False] * (n+1)
visited[1] = True

for i in range(1, n+1):
	for v in lv[i]:
		node = v[0]
		w = v[1]
		
		if not visited[node]:
			if w % 2 == 0:
				ln[node] = ln[i]
			else:
				if ln[i] == 0:
					ln[node] = 1
				else:
					ln[node] = 0
		visited[node] = True
		
for i in range(1, n+1):
	print(ln[i])

Submission status: Wrong Answer

Solution code:
def solve():
	n,*l=map(int,open(0).read().split())
	con=[[] for _ in range(n)]
	dist=[None]*n
	dist[0]=0
	for a,b,c in zip(*[iter(l)]*3):
		con[a-1].append((b-1,c%2))
		con[b-1].append((a-1,c%2))
 
	stk=[0]
	while stk:
		cur=stk.pop()
		for nxt,d in con[cur]:
			if dist[nxt]==None:
				stk.append(nxt)
				dist[nxt]=(dist[cur]+d)%2

	print(*dist,sep="\n")