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

Solution (Python):



input_list = lambda : list(map(int,input().split()))

from collections import Counter 
from collections import defaultdict
import itertools
import sys
sys.setrecursionlimit(10**6)

def sol(num,w,node,ans):
    now=node[num]
    
    for each in now:
        ne_n=each[0]
        ne_w=each[1]
        if ans[ne_n]!=-1:
            continue
        if ne_w==0:
            ans[ne_n]=ans[num]
        else:
            ans[ne_n]=1-ans[num]
        
        sol(ne_n,ne_w,node,ans)




n=int(input())
node=[[] for _ in range(n)]
for _ in range(n-1):
    u,v,w=input_list()
    w=w%2
    u-=1
    v-=1
    node[u].append([v,w])
    node[v].append([u,w])

ans=[-1 for _ in range(n)]
ans[0]=0
sol(0,0,node,ans)
for i in ans:
    print(i)

Solution (Python):
import sys
sys.setrecursionlimit(100000)

class Graph():
    def __init__(self):
        self.adjacency_dict = {}

    def add_vertex(self, v):
        self.adjacency_dict[v] = []
    
    def add_edge(self, v1, v2, dist):
        self.adjacency_dict[v1].append([v2, dist])
        self.adjacency_dict[v2].append([v1, dist])
    
    def next_edges(self, v):
        return self.adjacency_dict[v]

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

graph = Graph()
for i in range(1, N+1):
    graph.add_vertex(i)
for v1, v2, dist in dists:
    graph.add_edge(v1, v2, dist)

def dfs(start, group):
    if visited[start] is not None:
        return
    visited[start] = group
    for v, dist in graph.next_edges(start):
        if dist % 2 == 0:
            dfs(v, group)
        else:
            dfs(v, 1-group)

visited = [None]*(N+1)
dfs(1, 0)
for i in visited[1:]:
    print(i)

Solution (Python):
from collections import defaultdict
n = int(input())
d = defaultdict(list)
for i in range(n-1):
    u, v, w = map(int, input().split())
    d[u-1].append([v-1, w])
    d[v-1].append([u-1, w])
color = [0] * n
q = [0]
seen = set()
while q:
    parent = q.pop()
    for child in d[parent]:
        j, w = child
        if j not in seen:
            color[j] = color[parent]+w
            seen.add(j)
            q.append(j)
for cnt in color:
    if cnt%2 == 0:
        print('0')
    else:
        print('1')

Solution (Python):

import sys
import collections

sys.setrecursionlimit(10 ** 7)


N = int(input().rstrip())


A = list(map(int, input().rstrip().split()) for _ in range(N - 1))

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

for i in range(N - 1):
    a, b, w = A[i]
    items[a - 1].append((b - 1, w))
    items[b - 1].append((a - 1, w))

queue = collections.deque()
queue.append(0)
colors[0] = 0
while queue:
    v = queue.popleft()
    c = colors[v]
    for k, w in items[v]:
        cc = colors[k]
        if cc == -1:
            nc = c if w % 2 == 0 else not c
            colors[k] = nc
            queue.append(k)

















for c in colors:
    print(int(not c))

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

N = int(input())
G = [[] for i in range(N)]
temp = sys.stdin.readlines()
for line in temp:
    u, v, d = map(int, line.split())
    G[u-1].append([v-1, d])
    G[v-1].append([u-1, d])
    
def dfs(v, G, cur=0):
    
    color[v] = cur
        
    
    for next_v in G[v]:
        
        if color[next_v[0]] != -1:
            continue
            
        
        if next_v[1] % 2 == 0:
            dfs(next_v[0], G, cur)
        else:
            dfs(next_v[0], G, 1-cur)

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

Solution (Python):
N = int(input())
link = [set() for i in range(N)]
for i in range(N-1):
    u, v, w = map(int,input().split())
    link[u-1] |= {(v-1,w)}
    link[v-1] |= {(u-1,w)}
check = [(0, 0, -1)]
ans = [-1 for i in range(N)]
while check:
    now, d, From = check.pop()
    ans[now] = d % 2
    for next, dist in link[now]:
        if next == From:
            continue
        else:
            check.append((next, d + dist, now))
print('\n'.join(map(str,ans)))

Solution (Python):
import sys
input=sys.stdin.buffer.readline
sys.setrecursionlimit(10**9)

N = int(input())


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

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

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

def dfs(x):
    for v, w in edge[x]:
        if color[v] == -1:
            color[v] = (w + color[x])%2
            dfs(v)



dfs(0)
print(*color, sep="\n")

Solution (Python):
import sys
input=sys.stdin.buffer.readline
sys.setrecursionlimit(10**9)
n=int(input())
edges=[[] for i in range(n)]
for i in range(n-1):
    a,s,w=map(int,input().split())
    edges[a-1].append([s-1,w]);edges[s-1].append([a-1,w])
colors=[-1]*n
colors[0]=1
def dfs(now):
    for to,cost in edges[now]:
        if colors[to]==-1:
            colors[to]=(cost+colors[now])%2
            dfs(to)

dfs(0)
print(*colors,sep="\n")

Solution (Python):

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

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

d = [-1 for _ in range(N)]
src = 0
d[src] = 0
buf = [src]

while buf:
    src = buf.pop()
    for dst, w in graph[src].items():
        if d[dst] == -1:
            d[dst] = d[src] + w
            buf.append(dst)

for n in d:
    if n % 2:
        print(0)
    else:
        print(1)

Solution (Python):
import sys
input=sys.stdin.buffer.readline
sys.setrecursionlimit(10**9)
n=int(input())
edges=[[] for i in range(n)]
for i in range(n-1):
    a,s,w=map(int,input().split())
    edges[a-1].append([s-1,w]);edges[s-1].append([a-1,w])
colors=[-1]*n
colors[0]=1
def dfs(now):
    for to,cost in edges[now]:
        if colors[to]==-1:
            colors[to]=(cost+colors[now])%2
            dfs(to)

dfs(0)
print(*colors,sep="\n")

Solution (Python):
n=int(input())
edges=[[] for i in range(n)]
import sys

sys.setrecursionlimit(10**7)
for i in range(n-1):
    a,s,w=map(int,input().split())
    edges[a-1].append([s-1,w]);edges[s-1].append([a-1,w])
colors=[-1]*n
colors[0]=1
def dfs(now):
    for to,cost in edges[now]:
        if colors[to]==-1:
            colors[to]=(cost+colors[now])%2
            dfs(to)

dfs(0)
print(*colors,sep="\n")

Solution (Python):
n=int(input())
edges=[[] for i in range(n)]
import sys

sys.setrecursionlimit(10**9)
for i in range(n-1):
    a,s,w=map(int,input().split())
    edges[a-1].append([s-1,w]);edges[s-1].append([a-1,w])
colors=[-1]*n
colors[0]=1
def dfs(now):
    for to,cost in edges[now]:
        if colors[to]==-1:
            colors[to]=(cost+colors[now])%2
            dfs(to)

dfs(0)
print(*colors,sep="\n")

Solution (Python):
import sys

sys.setrecursionlimit(10**6)

n = int(input())
if n == 1:
    print(1)
else:
    edge=[[] for _ in range(n)]
    for _ in range(n-1):
        u,v,w = map(int,input().split())
        edge[u-1].append((v-1,w%2))
        edge[v-1].append((u-1,w%2))
 
    color =[-1]*n
    def dfs(node,edge):
        for next_node,w in edge[node]:
            if color[next_node] != -1:
                continue
            if w == 1:
                color[next_node] = color[node]^1
            elif w == 0:
                color[next_node] = color[node]
            dfs(next_node,edge)
        
        
    color[0] = 0
    dfs(0,edge)
    print(*color,sep="\n")

Solution (Python):
import sys
from collections import deque
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
n = int(input())
edges = [[]for _ in range(n)]
for _ in range(n-1):
    u, v, w = map(int, input().split())
    edges[u-1].append((w, v-1))
    edges[v-1].append((w, u-1))

next_v = deque([(0, 0)])
color = [-1]*n
while next_v:
    d, v = next_v.popleft()
    color[v] = d & 1
    for d2, v2 in edges[v]:
        if color[v2] != -1:
            continue
        next_v.append((d+d2, v2))
print(*color, sep='\n')

Solution (Python):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
n = int(input())
edges = [[]for _ in range(n)]
for _ in range(n-1):
    u, v, w = map(int, input().split())
    edges[u-1].append((w, v-1))
    edges[v-1].append((w, u-1))


color = [-1]*n


def dfs(v, d, parent):
    color[v] = d & 1
    for d2, v2 in edges[v]:
        if v2 == parent:
            continue
        dfs(v2, d+d2, v)


dfs(0, 0, -1)
print(*color, sep='\n')

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N=int(readline())
m=map(int,read().split())
UVW=zip(m,m,m)

graph =[[] for i in range(N+1)]
for u,v,w in UVW:
    graph[u].append((v,w))
    graph[v].append((u,w))

color=[0]*(N+1)
parent=[0]*(N+1)
stack=[1]
while stack:
    x=stack.pop()
    for dst,w in graph[x]:
        if (dst==parent[x]):
            continue
        stack.append(dst)
        color[dst]=color[x]^(w&1)
        parent[dst]=x

print('\n'.join(map(str,color[1:])))

Solution (Python):
import sys
sys.setrecursionlimit(10**6)
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N=int(readline())
m=map(int,read().split())
UVW=zip(m,m,m)

graph =[[] for i in range(N+1)]
for u,v,w in UVW:
    graph[u].append((v,w))
    graph[v].append((u,w))
color=[0]*(N+1)

def dfs(cur,par,dist):
    color[cur]=dist
    for dst,w in graph[cur]:
        if (dst==par):
            continue
        dfs(dst,cur,dist^(w&1))
dfs(1,-1,0)
print('\n'.join(map(str,color[1:])))

Solution (Python):
import sys
readline = sys.stdin.readline
from heapq import heapify, heappush, heappop

def dijkstra(path, N, a):
    visited = [False] * N
    que = [(0, a)]
    heapify(que)  
    dist = [-1] * N  
    dist[a] = 0  
    while que:
        d, v = heappop(que)  
        visited[v] = True  
        
        for d, to in path[v]:
            cost = dist[v] + d
            if dist[to] < 0 or cost < dist[to]:
                dist[to] = cost
                if not visited[to]:
                    heappush(que, (cost, to))

    return dist

def main():
    N = int(input())
    path = [[] for _ in range(N)]
    for _ in range(N-1):
        u, v, w = map(int, readline().rstrip().split())
        path[u-1].append((w, v-1))
        path[v-1].append((w, u-1))
    
    G = dijkstra(path, N, 0)
    for i in range(N):
        if G[i] % 2 == 0:
            print(0)
        else:
            print(1)

if __name__ == '__main__':
    main()

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

n = int(input())
G = [[] for _ in range(n)]
for i in range(n-1):
  uvw = list(map(int, input().split()))
  u = uvw[0]-1
  v = uvw[1]-1
  w = uvw[2]
  G[u].append([v, w])
  G[v].append([u, w])
  
color = [-1]*n
def dfs(G, v, cur = 0):
  if color[v] == -1:
    
    color[v] = cur
    for next_v, w in G[v]:
     
      if color[next_v]==-1:
        if (w % 2 != 0):
          dfs(G, next_v, 1-cur)
        if (w% 2 == 0):
          dfs(G, next_v, cur)
        continue
      


        

for v in range(n):
  if color[v] != -1:
    continue
  else:
    dfs(G, v)


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

Solution (Python):
"""
created 2020-05-11
"""
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

def main():
    N,*uvw = map(int, read().split())

    E = [[] for _ in range(N+1)]
    for u, v, w in zip(*[iter(uvw)]*3):
        E[u].append((v, w))
        E[v].append((u, w))
    
    color = [-1] * (N+1)
    color[1] = 0
    
    d = [-1] * (N+1)
    d[1] = 0
    def dfs(s):
        stack = [s]

        while stack:
            v = stack.pop()
            for e, w in E[v]:
                if d[e] == -1:
                    d[e] = d[v] + w
                    if d[e] % 2 == 0:
                        color[e] = 0
                    else:
                        color[e] = 1
                    stack.append(e)
    
    dfs(1)

    print(*color[1:], sep="\n")


if __name__ == "__main__":
    main()

Solution (Python):
N = int(input())

u_list = []
v_list = []
w_list = []

for _ in range(N-1):
  u, v, w = map(int, input().split())
  u_list.append(u-1)
  v_list.append(v-1)
  w_list.append(w)
  
color_dict = dict()
uvw_list = list(zip(u_list, v_list, w_list))
color_dict[u_list[0]] = 1

def eval_single(u, v, w, color_dict):
  skip = True

  if u in color_dict:
    color_dict[v] = assign_color(color_dict[u], w)
    skip = False
    
  if v in color_dict:
    color_dict[u] = assign_color(color_dict[v], w)
    skip = False
    
  return skip, color_dict
  

def assign_color(color, w):
  if w%2==0:
    return color
  else:
    return color*(-1)+1
  
while True:
  ind_list = []
  for ind, (u, v, w) in enumerate(uvw_list):
    skip, color_dict = eval_single(u, v, w, color_dict)
    
    if skip:
      ind_list.append(ind)

  uvw_list = [uvw_list[ind] for ind in ind_list]
  
  if len(color_dict) == N:
    break

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

Solution (Python):
import sys
input = sys.stdin.readline
def main():
  n=int(input())
  uvw=[list(map(int,input().split())) for _ in range(n-1)]
  ki=[[] for _ in range(n)]
  for u,v,w in uvw:
    ki[u-1].append((v-1,w))
    ki[v-1].append((u-1,w))
  todo=[0]
  seen=[-1]*n
  seen[0]=0
  while len(todo)>0:
    a=todo.pop()
    l=ki[a]
    for li in l:
      if seen[li[0]]==-1:
        seen[li[0]]=seen[a] if li[1]%2==0 else (seen[a]+1)%2
        todo.append(li[0])
  for s in seen:
    print(s)
if __name__=='__main__':
  main()

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

graph = [[] for _ in range(N+1)]
for u,v,w in uvw:
    graph[u].append((v,w))
    graph[v].append((u,w))

ans = [0] * (N+1)

from collections import deque
todo = deque([(1,0)])
seen = [-1] * (N+1)

while todo:
    v,d = todo.pop()
    seen[v] = 0
    if d % 2 == 0:
        ans[v] = 0
    else:
        ans[v] = 1
    for u,w in graph[v]:
        if seen[u]== 0:
            continue
        todo.append((u,d+w))

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

Solution (Python):
from collections import deque

N = int(input())
connected = [[] for _ in range(N)]
for i in range(N-1):
    u,v,w = (int(x) for x in input().split())
    connected[u-1].append((v-1,w))
    connected[v-1].append((u-1,w))
colors = [None] * N
colors[0] = 0
d = deque()
parents = deque()
for edge in connected[0]:
    if edge[1] % 2 == 0:
        colors[edge[0]] = 0
        d.append((edge[0],0))
    else:
        colors[edge[0]] = 1
        d.append((edge[0],1))
    parents.append(0)
while d:
    temp = d.popleft()
    parent = parents.popleft()
    for edge in connected[temp[0]]:
        if edge[0] != parent:
            if edge[1] % 2 == 0:
                colors[edge[0]] = temp[1]
                d.append((edge[0],temp[1]))
            else:
                if temp[1] == 0:
                    colors[edge[0]] = 1
                    d.append((edge[0],1))
                else:
                    colors[edge[0]] = 0
                    d.append((edge[0],0))
            parents.append(temp[0])
for x in colors:
    print(x)

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

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

def dfs(v, p, c): 
    color[v] = c 
    for i in g[v]:
        nv, w = i[0], i[1]
        if nv == p: continue 
        else:
            if w % 2 == 1: 
                dfs(nv, v, 1-c) 
            else:
                dfs(nv, v, c) 
    

color = [-1]*(N+1) 
dfs(1,-1,1) 

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

Solution (Python):
from collections import deque



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

road = [[] for i in range(n)]
cost = [[] for i in range(n)]

for i in li:
  i[0]-=1
  i[1]-=1
  road[i[0]].append(i[1])
  road[i[1]].append(i[0])
  cost[i[0]].append(i[2]%2)
  cost[i[1]].append(i[2]%2)

dist = [-1]*n
que  = deque()
dist[0] = 0
que.append(0)

while(len(que)!=0):
  
  v = que.popleft()
  for i,r in enumerate(road[v]):
    if dist[r]!=-1:
      continue
    dist[r] = (dist[v]+cost[v][i])%2
    que.append(r)

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

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

def main():
    N = int(input())
    edge = [[] for _ in range(N)]
    for _ in range(N-1):
        u, v, w = map(int, input().split())
        edge[u-1].append([v-1, w])
        edge[v-1].append([u-1, w])
    
    def dfs(x, co):
        if c[x] != -1:
            return
        c[x] = co
        directions = edge[x]
        for d in directions:
            t, w = d
            if w%2 != 0:
                nextco = abs(1-co)
            else:
                nextco = co
            dfs(t, nextco)
        
    c = [-1 for _ in range(N)]
    dfs(0, 0)
    for ans in c:
        print(ans)

main()

Solution (Python):
from collections import deque
def main():
    N = int(input())
    edge = [[] for _ in range(N)]
    for _ in range(N-1):
        u, v, w = map(int, input().split())
        edge[u-1].append([u-1, v-1, w])
        edge[v-1].append([v-1, u-1, w])
    
    
    c = [-1 for _ in range(N)]
    c[0] = 0
    que = deque(edge[0])
    while que:
        f, t, w = que.pop()
        if w%2 == 0:
            c[t] = c[f]
        else:
            c[t] = abs(1 - c[f])
        
        directions = edge[t]
        for d in directions:
            if c[d[1]] == -1:
                que.append(d)
            else:
                continue
    for ans in c:
        print(ans)
main()

Solution (Python):
from collections import deque
import sys
input = sys.stdin.readline
N=int(input())
ki=[[] for f in range(N)]
for i in range(N-1):
 u,v,w = map(int,input().split())
 ki[u-1].append([v-1,w%2])
 ki[v-1].append([u-1,w%2])
stack = deque([[0,0]])
check = [0]*N 
ans=[2]*N
ans[0]=0
while stack != deque([]) :
 a=stack.pop()
 ne=a[0]
 if check[ne]==0:
  check[ne]=1
  for i in range(len(ki[ne])):
   eda=ki[ne][i][0]
   edanum=ki[ne][i][1]
   edaans=(edanum+ans[ne])%2
   if check[eda]==0:
    stack.append([eda,edaans])
    ans[eda]=edaans
for i in ans:
 print(i)

Solution (Python):
from collections import deque
import sys
input = sys.stdin.readline
N=int(input())
ki=[[] for f in range(N)]
for i in range(N-1):
 u,v,w = map(int,input().split())
 ki[u-1].append([v-1,w%2])
 ki[v-1].append([u-1,w%2])
stack = deque([[0,0]])
check = [0]*N 
ans=[2]*N
ans[0]=0
while stack != deque([]) :
 a=stack.pop()
 ne=a[0]
 if check[ne]==0:
  check[ne]=1
  for i in range(len(ki[ne])):
   eda=ki[ne][i][0]
   edanum=ki[ne][i][1]
   edaans=(edanum+ans[ne])%2
   if check[eda]==0:
    stack.append([eda,edaans])
    ans[eda]=edaans
for i in ans:
 print(i)

Solution (Python):
import sys
input = sys.stdin.readline
N=int(input())
ki=[[] for f in range(N)]
for i in range(N-1):
 u,v,w = map(int,input().split())
 ki[u-1].append([v-1,w%2])
 ki[v-1].append([u-1,w%2])
stack = [[0,0]]
check = [0]*N 
ans=[2]*N
ans[0]=0
while stack != [] :
 a=stack.pop()
 ne=a[0]
 if check[ne]==0:
  check[ne]=1
  for i in range(len(ki[ne])):
   eda=ki[ne][i][0]
   edanum=ki[ne][i][1]
   edaans=(edanum+ans[ne])%2
   if check[eda]==0:
    stack.append([eda,edaans])
    ans[eda]=edaans
for i in ans:
 print(i)

Solution (Python):
import sys
input = sys.stdin.readline
N=int(input())
ki=[[] for f in range(N)]
for i in range(N-1):
 u,v,w = map(int,input().split())
 ki[u-1].append([v-1,w%2])
 ki[v-1].append([u-1,w%2])
stack = [[0,0]]
check = [0]*N 
ans=[2]*N
ans[0]=0
while stack != [] :
 a=stack.pop()
 ne=a[0]
 if check[ne]==0:
  check[ne]=1
  for i in range(len(ki[ne])):
   if check[ki[ne][i][0]]==0:
    stack.append([ki[ne][i][0],(ki[ne][i][1]+ans[ne])%2])
    ans[ki[ne][i][0]]=(ki[ne][i][1]+ans[ne])%2
for i in ans:
 print(i)

Solution (Python):
import sys
input = sys.stdin.readline
N=int(input())
ki=[[] for f in range(N)]
for i in range(N-1):
 u,v,w = map(int,input().split())
 ki[u-1].append([v-1,w%2])
 ki[v-1].append([u-1,w%2])
stack = [[0,0]]
check = [0]*N 
ans=[2]*N
ans[0]=0
while stack != [] :
 a=stack.pop()
 if check[a[0]]==0:
  check[a[0]]=1
  for i in range(len(ki[a[0]])):
   if check[ki[a[0]][i][0]]==0:
    stack.append([ki[a[0]][i][0],(ki[a[0]][i][1]+ans[a[0]])%2])
    ans[ki[a[0]][i][0]]=(ki[a[0]][i][1]+ans[a[0]])%2
for i in ans:
 print(i)

Solution (Python):
import sys
input = sys.stdin.readline
N=int(input())
ki=[[] for f in range(N)]
for i in range(N-1):
 u,v,w = map(int,input().split())
 ki[u-1].append([v-1,w%2])
 ki[v-1].append([u-1,w%2])
stack = [[0,0]]
check = [0]*N 
ans=[2]*N
ans[0]=0
while stack != [] :
 a=stack.pop()
 if check[a[0]]==0:
  check[a[0]]=1
  for i in range(len(ki[a[0]])):
   if check[ki[a[0]][i][0]]==0:
    stack.append([ki[a[0]][i][0],(ki[a[0]][i][1]+ans[a[0]])%2])
    ans[ki[a[0]][i][0]]=(ki[a[0]][i][1]+ans[a[0]])%2
for i in ans:
 print(i)

Solution (Python):
import sys
sys.setrecursionlimit(200000)
n = int(input())
graph = {i: [] for i in range(1, n + 1)}
for _ in range(n - 1):
    u, v, ww = map(int, input().split())
    graph[u].append([v,ww])
    graph[v].append([u,ww])
color = [-1] * n

def dfs(x):
    for sub in graph[x]:
        next = sub[0]
        lon = sub[1]
        if color[next - 1] != -1:
            continue
        if lon % 2 == 0:
            color[next - 1] = color[x - 1]
        else:
            if color[x - 1] == 1:
                color[next - 1] = 0
            else:
                color[next - 1] = 1
        dfs(next)

color[0] = 0
dfs(1)
for i in color:
    print(i)

Solution (Python):
from collections import defaultdict
import sys
sys.setrecursionlimit(10**5)
def solve():
    N = int(input())
    G = defaultdict(list)
    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))

    res = [0] * N
    dfs(0,-1,1,G,res)

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

def dfs(v,p,c,G,res):
    res[v] = c

    for e in G[v]:
        if e[0] == p:
            continue
        if e[1] % 2 == 0:
            dfs(e[0],v,c,G,res)
        else:
            dfs(e[0],v,1-c,G,res)
        
if __name__ == '__main__':
    solve()

Solution (Python):
from collections import defaultdict
import sys
sys.setrecursionlimit(10**5)
def solve():
    N = int(input())
    G = defaultdict(list)
    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))

    res = [0] * N

    dfs(0,-1,1,G,res)

    print(*res, sep='\n')
def dfs(v,p,c,G,res):
    res[v] = c
    for e in G[v]:
        if e[0] == p:
            continue
        if e[1] % 2 != 0:
            dfs(e[0], v, 1-c,G,res)
        else:
            dfs(e[0],v,c,G,res)
        
if __name__ == '__main__':
    solve()

Solution (Python):
import sys
sys.setrecursionlimit(10**9)
n = int(input())
graph = [[]for i in range(n)]
for i in range(n-1):
    pre = list(map(int,input().split()))
    graph[pre[0]-1].extend([pre[1]-1,pre[2]])
    graph[pre[1]-1].extend([pre[0]-1,pre[2]])
seen = [0 for i in range(n)]
color = [-1 for i in range(n)]

def DFS(x):
    if seen[x] == 1:
        return 0
    else:
        pass
    seen[x] = 1
    for i in range(len((graph[x]))//2):
        if graph[x][2*i+1] % 2 == 0:
            color[graph[x][2*i]] = color[x]
        else:
            color[graph[x][2*i]] = not color[x]

    for i in range(len((graph[x]))//2):
        DFS(graph[x][2*i])

color[0] = True
DFS(0)
for i in range(n):
    print(int(color[i]))

Solution (Python):
printn = lambda x: print(x,end='')
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True 
BIG = 10**18
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)

n = inn()
dst = [{} for i in range(n+1)]
for i in range(n-1):
    u,v,w = inm()
    dst[u][v] = dst[v][u] = w
q = [1]
d = [BIG]*(n+1)
d[1] = 0
while len(q)>0:
    x = q.pop()
    for y in dst[x]:
        if d[y]==BIG:
            d[y] = d[x]+dst[x][y]
            q.append(y)
for i in range(1,n+1):
    print(d[i]%2)

Solution (Python):
import sys
sys.setrecursionlimit(500*500)

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

nbors = [[] for _ in range(N+1)]
for uvw in UVW:
    u,v,w = uvw[0], uvw[1], uvw[2]
    nbors[u].append((v, w))
    nbors[v].append((u, w))

dist = [-1] * (N+1)
dist[1] = 0
def dfs(now, nxt, w):
    if dist[nxt] >= 0:
        return
    dist[nxt] = dist[now] + w
    for nbor in nbors[nxt]:
        nxt2, w = nbor[0], nbor[1]
        dfs(nxt, nxt2, w)

for nbor in nbors[1]:
    nxt, w = nbor[0], nbor[1]
    dfs(1, nxt, w)

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

Solution (Python):
import sys
sys.setrecursionlimit(500*500)
N = int(sys.stdin.readline())
edges = [list(map(int,sys.stdin.readline().split())) for _ in range(N - 1)]
A = [[] for _ in range(N + 1)]
 
for edge in edges:
    A[edge[0]].append([edge[1],edge[2]])
    A[edge[1]].append([edge[0],edge[2]])
 
depth = [-1] * (N + 1)
depth[1] = 0
 
def dfs(A,s):
    for v in A[s]:
        if depth[v[0]] == -1:
            depth[v[0]] = depth[s] + v[1]
            dfs(A,v[0])    
dfs(A,1)
for d in depth[1:]:
    if d % 2 == 0:
        print(0)
    else:
        print(1)

Solution (Python):
def main():
    import sys
    input = sys.stdin.readline
    import heapq

    N = int(input())
    edges = [[] for _ in range(N+1)]
    for _ in range(N-1):
        u,v,w = map(int,input().split())
        edges[u].append((v,w))
        edges[v].append((u,w))
    
    colors = [-1]*(N+1)
    que = [(0,1)]
    heapq.heapify(que)
    while que:
        c,n = heapq.heappop(que)
        if colors[n] == -1:
            colors[n] = c
            for nx,w in edges[n]:
                if w%2==0:
                    nxC = c
                else:
                    nxC = (c+1)%2
                heapq.heappush(que,(nxC,nx))

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

main()

Solution (Python):
import sys
input = sys.stdin.buffer.readline
from collections import deque

def main():
    N = int(input())
    edge = [[] for _ in range(N)]
    dist = [-1]*N
    dist[0] = 0
    
    for _ in range(N-1):
        a,b,c = map(int,input().split())
        edge[a-1].append((b-1,c))
        edge[b-1].append((a-1,c))
        
    que = deque([0])
    while que:
        now = que.pop()
        for fol,d in edge[now]:
            if dist[fol] != -1:
                continue
            dist[fol] = dist[now]+d
            que.append(fol)
            
    for i in range(N):
        print(dist[i]%2)

if __name__ == "__main__":
    main()

Solution (Python):
import sys
sys.setrecursionlimit(10**9)
n = int(input())
T = [[] for _ in range(n)]
for _ in range(n-1):
    u,v,w = map(int,input().split())
    u -= 1
    v -= 1
    w %= 2
    T[u].append((v,w))
    T[v].append((u,w))

ans = [0]*n
def dfs(u,p=-1,c=0):
    for v,w in T[u]:
        if v == p: continue
        nc = (c+1)%2 if w else c 
        ans[v] = nc
        dfs(v,u,nc)
dfs(0)

print("\n".join(map(str,ans)))

Solution (Python):

n = int(input())
tree = [[] for _ in range(n)]

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



color = [-1] * n
q = [(0, 0)]

while q:  
    a, b = q.pop()
    color[a] = b  
    for c, d in tree[a]:
        if color[c] == -1:  
            q += [(c, b ^ d)] 
print(*color, sep='\n')

Solution (Python):
from collections import defaultdict


def main():
    N = int(input())
    adj_nodes = defaultdict(list)
    weights = defaultdict(int)
    for _ in range(N - 1):
        u, v, w = list(map(int, input().split(' ')))
        u -= 1
        v -= 1
        adj_nodes[u].append(v)
        adj_nodes[v].append(u)
        weights[(u, v)] = w
        weights[(v, u)] = w
    
    frontier = [0]
    dist = [0 for _ in range(N)]
    explored = [0 for _ in range(N)]
    while len(frontier) > 0:
        node = frontier.pop()
        explored[node] = 1
        for next_node in adj_nodes[node]:
            if explored[next_node] == 1:
                continue
            frontier.append(next_node)
            dist[next_node] = dist[node] + weights[(node, next_node)]
    
    for node in range(N):
        print(dist[node] % 2)


if __name__ == '__main__':
    main()

Solution (Python):
from collections import deque

N = int(input())

A = []
while True:
    try:
        temp=list(map(int,input().split()))
        A.append(temp)
    except:
        break;

To = [[] for i in range(N)]
Cost = [[] for i in range(N)]
for i in range(len(A)):
  
  To[A[i][0]-1].append(A[i][1]-1)
  To[A[i][1]-1].append(A[i][0]-1)
  Cost[A[i][0]-1].append(A[i][2])
  Cost[A[i][1]-1].append(A[i][2])


ans = [-1]*N 
ans[0] = 0  
Queue = deque([])
Queue.append(0) 

while Queue:
  v = Queue.popleft() 
  for i in range(len(To[v])): 
    u = To[v][i] 
    w = Cost[v][i] 
    if ans[u] != -1: 
      continue
    ans[u] = (ans[v]+w)%2
    Queue.append(u)
print(*ans, sep="\n")

Solution (Python):
import sys
sys.setrecursionlimit(10**6)
N = int(input())
edg = [list(map(int,input().split())) for _ in range(N-1)]
vtx = [[] for _ in range(N)]
for e in edg:
    v1,v2,w = e
    vtx[v1-1].append([v2-1,w])
    vtx[v2-1].append([v1-1,w])

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

def dfs(vtx,i=0,p=-1,c=1): 
    colors[i] = c
    for v,w in vtx[i]:
        if v == p:
            continue
        dfs(vtx,v,i,1-c if w%2 != 0 else c)
dfs(vtx)

for v in colors:
    print(v)

Solution (Python):


from collections import deque

N = int(input())

distance = {}
edge = [[] for _ in range(N + 1)]

for _ in range(N - 1):
    u, v, w = map(int, input().split())
    edge[u].append(v)
    edge[v].append(u)
    distance[str(u) + "_" + str(v)] = w
    distance[str(v) + "_" + str(u)] = w

color = [0 for _ in range(N + 1)]
q = deque([1]) 
done = [0 for _ in range(N + 1)]
done[1] = 1

while q:
    parent = q.pop()
    for e in edge[parent]:
        if e != parent and done[e] == 0:
            d = distance[str(parent) + "_" + str(e)]
            if d % 2 == 0:
                color[e] = color[parent]
            else:
                color[e] = 0 if color[parent] == 1 else 1
            q.append(e)
            done[e] = 1

print("\n".join(map(str, color[1:])))