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):
from collections import deque
N=int(input())
numbers=[[] for _ in range(N)]
for _ in range(N-1):
    u,v,w=map(int,input().split())
    u-=1
    v-=1
    numbers[u].append((v,w%2))
    numbers[v].append((u,w%2))
inf=pow(10,9)
visited_point=[inf for _ in range(N)]
visited_point[0]=0
stack=deque([0])
while len(stack)>0:
    n=stack.pop()
    for v,w in numbers[n]:
        if visited_point[v]==inf:
            stack.appendleft(v)
            if w%2==0:
                visited_point[v]=visited_point[n]
            else:
                visited_point[v]=visited_point[n]^1
for a in visited_point:
    print(a)

Solution (Python):
from collections import deque
n=int(input())
G=[[]for i in range(n)]
U=[0]*(n-1)
V=[0]*(n-1)
A=[0]*(n-1)
D=[]
for i in range(n-1):
  U[i],V[i],w=map(int,input().split())
  U[i]=U[i]-1
  V[i]=V[i]-1
  A[i]=U[i]*10**5+V[i]
  w=w%2
  G[U[i]].append([V[i],w])
  G[V[i]].append([U[i],w])
  D.append([A[i],0])
C=[0]*n
VV=[0]*n
d=deque([0])
while len(d)>0:
  x=d[0]
  d.popleft()
  for i in range(len(G[x])):
    if VV[G[x][i][0]]==0:
      VV[G[x][i][0]]=1
      d.append(G[x][i][0])
      if G[x][i][1]==0:
        C[G[x][i][0]]=C[x]
      else:
        C[G[x][i][0]]=(C[x]+1)%2
for i in range(n):
  print(C[i])

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

n = int(input())
edge = [[] for i in range(n)]
ans = [0 for i in range(n)]
for i 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])

def bfsC(pre, now, nowc):
    for node, weight in edge[now]:
        if node != pre:
            if weight:
                ans[node] = 1-nowc
                bfsC(now, node, 1-nowc)
            else:
                ans[node] = nowc
                bfsC(now, node, nowc)
bfsC(-1, 0, 0)
for i in range(n):
    print(ans[i])

Solution (Python):
from collections import deque
N = int(input())
E = [[] for _ in range(N+1)]
for i in range(N-1):
    u,v,w = map(int,input().split())
    E[u].append([u,v,w])
    E[v].append([v,u,w])
color = [-1]*(N+1)
color[1] = 0
e = deque(E[1])
while(e):
    v = e.popleft()
    if(color[v[1]] == -1):
        if(v[2]%2 == 0):
            color[v[1]] = color[v[0]]
        else:
            color[v[1]] = color[v[0]]^1
        for p in E[v[1]]:
            e.append(p)
for i in range(1,N+1):
    print(color[i])

Solution (Python):
n=int(input())
tree=[[] for i in range(n)]
for i in range(n-1):
  u,v,w=map(int,input().split())
  tree[u-1].append((v-1,w))
  tree[v-1].append((u-1,w))
color=[-1]*n
color[0]=0
q=[0]
while q:
  x=q.pop()
  for t,cost in tree[x]:
    if color[t]>=0:
      continue
    if cost%2==0:
      color[t]=color[x]
    else:
      color[t]=1-color[x]
    q.append(t)
print(*color,sep='\n')

Solution (Python):
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    
    from itertools import combinations, permutations, accumulate
    
    from bisect import bisect_left,bisect_right
    import heapq
    from math import floor, ceil
    

    inf = 10**17
    

    N = int(input())
    def dijkstra_heap(start,edge):
        
        d = [inf]*N
        used = [False]*N
        d[start] = 0
        used[start] = True
        edgelist = []
        
        for a,b in edge[start]:
            heapq.heappush(edgelist,a*(10**6)+b)

        while len(edgelist):
            
            minedge = heapq.heappop(edgelist)
            if used[minedge%(10**6)]:
                continue
            node = minedge%(10**6)
            d[node] = minedge//(10**6)
            used[node] = True

            for e in edge[node]:
                if not used[e[1]]:
                    heapq.heappush(edgelist,(e[0]+d[node])*(10**6)+e[1])
        return d

    
    edge = [[] for i in range(N)]
    
    for _ in range(N-1):
        x,y,z = map(int,input().split())
        edge[x-1].append((z,y-1))
        edge[y-1].append((z,x-1))
    d = dijkstra_heap(0, edge)

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


if __name__ == '__main__':
    main()

Solution (Python):
import sys
sys.setrecursionlimit(1000000)
n=int(input())
graph=[[] for i in range(n)]
color=[-1]*n
for i in range(n-1):
    a,b,c=map(int,input().split())
    graph[a-1].append([b-1,c%2])
    graph[b-1].append([a-1,c%2])
def coloring(pre,c):
  color[pre]=c
  for i,j in graph[pre]:
    if color[i]<0:
      coloring(i,color[pre]^j)
coloring(0,1)
for i in color:
  print(i)

Solution (Python):
import sys
sys.setrecursionlimit(pow(10, 9))

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

def dfs(v, dist):
  for nv, e_dist in G[v]:
    if ans[nv] == -1:
      ans[nv] = (dist + e_dist) % 2
      dfs(nv, dist + e_dist)

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
dfs(0, 0)

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

Solution (Python):
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 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])

Solution (Python):

n=int(raw_input())
t=[[] for i in range(n+1)]
for i in range(n-1):
 u,v,w=map(int,raw_input().split())
 t[u].append([v,w])
 t[v].append([u,w])
d=[-1]*(n+1)
d[1]=0
q=[1]
while q:
 now=q.pop()
 for ni,nl in t[now]:
  if d[ni]==-1:
   d[ni]=d[now]+nl
   q.append(ni)
for l in d[1:]:
 print l%2

Solution (Python):
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=[-1]*n
q=[[0,0]]


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

for c in C:
    print(c)

Solution (Python):
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]=0
    else:
        C[v]=1
    for pv,pw in X[v]:
        q.append([pv,pw+w])

for c in C:
    print(c)

Solution (Python):
import queue

n = int(input())
go = [[]for _ in range(n)]
ge = [[]for _ in range(n)]
 
for _ in range(n-1):
    x,y,z = map(int, input().split())
    if z % 2 == 0:
        ge[x-1].append(y-1)
        ge[y-1].append(x-1)
    else:
        go[x-1].append(y-1)
        go[y-1].append(x-1)

color = [0] * n
color[0] = 1

q = queue.Queue()

q.put(0)

while not q.empty():
    v = q.get()
    for i in range(len(go[v])):
        if color[go[v][i]] == 0:
            color[go[v][i]] = - color[v]
            q.put(go[v][i])
    for i in range(len(ge[v])):
        if color[ge[v][i]] == 0:
            color[ge[v][i]] = color[v]
            q.put(ge[v][i])

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

Solution (Python):
from collections import deque

def bfs(i):
    q = deque()
    q.append(i)
    c[i] = 1
    while q:
        p = q.popleft()
        f = G[p]
        z = W[p]
        for j in range(len(f)):
            if c[f[j]] == 0:
                q.append(f[j])
                c[f[j]] = 1
                d[f[j]] = d[p] + z[j]
    return

n = int(input())
G = [[] for _ in range(n)]
W = [[] for _ in range(n)]
c = [0] * n
d = [0] * n
for _ in range(n - 1):
    u, v, w = map(int, input().split())
    G[u - 1].append(v - 1)
    G[v - 1].append(u - 1)
    W[u - 1].append(w)
    W[v - 1].append(w)
bfs(0)
for i in d:
    print(i % 2)

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

N = int(input())
edge = [[] for _ in range(N+1)]
for i in range(N-1):
  u,v,w = map(int, input().split())
  edge[u].append([v,w%2])
  edge[v].append([u,w%2])
color = [0]*(N+1)
visited = [False]*(N+1)
def dfs(u):
  for v,w in edge[u]:
    if visited[v]==False:
      
      visited[v]=True
      color[v]=color[u]^w
      dfs(v)
  return 0
visited[1]=True
dfs(1)
ans = color[1:]
print(*ans,sep='\n')

Solution (Python):
from itertools import product

def main():
    n = int(input())
    adj = [{} for i in range(n)]
    dist = [-1] * n
    for _ in range(n-1):
        u, v, w = [int(i) for i in input().split()]
        adj[u-1][v-1] = w
        adj[v-1][u-1] = w
    dist[0] = 0
    visited = 1
    cand = [0]
    while visited < n:
        pos = cand.pop()
        for i, v in adj[pos].items():
            if dist[i] < 0:
                dist[i] = (dist[pos] + v)%2
                visited += 1
                cand.append(i)
    for d in dist:
        print(d)

if __name__ == '__main__':
    main()

Solution (Python):
from collections import defaultdict
from sys import stdin
def main():
    N = int(stdin.readline())
    edge = defaultdict(list)
    for _ in range(N-1):
        u,v,w = map(int,stdin.readline().split())
        u -= 1;v -= 1
        edge[u].append([v,w])
        edge[v].append([u,w])
    stack = [0]
    color = [-1 for _ in range(N)]
    color[0] = 0
    while stack:
        u = stack.pop()
        for e in edge[u]:
            v,dist = e
            if dist%2==0 and color[v] == -1:
                color[v] = color[u]
                stack.append(v)
            elif dist%2==1 and color[v] == -1:
                if color[u] == 1:
                    color[v] = 0
                else:
                    color[v] = 1
                stack.append(v)
            else:continue
    for c in color:
        print(c)

if __name__ == "__main__":
    main()

Solution (Python):




import heapq
import sys

input = sys.stdin.readline

def dijkstra_heap(s,edge):
    
    d = [10**20] * 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




n = int(input()); w = n - 1;s = 0 

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

for i in range(w):
    x,y,z = map(int,input().split())
    x -= 1
    y -= 1
    edge[x].append([z,y])
    edge[y].append([z,x]) 

d = dijkstra_heap(s,edge)





print("\n".join([str(t%2) for t in d]))

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

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

    

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

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

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

if __name__ == '__main__':
    main()

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

d = [-1 for _ in range(N+1)]
d[1] = 0
q = [1]

while q:
    cur = q.pop()
    for n,l in tree[cur]:
        if d[n] == -1:
            d[n] = d[cur] + l
            q.append(n)

for l in d[1:]:
    print(l%2)

Solution (Python):
n=int(input())
tree=[[]for _ in range(n+1)]
for _ in range(n-1):
    u,v,w=map(int,input().split())
    tree[u].append([v,w])
    tree[v].append([u,w])
d=[-1]*(n+1)
d[1]=0
q=[1]
while q:
    now=q.pop()
    for n_i,n_l in tree[now]:
        if d[n_i]==-1:
            d[n_i]=d[now]+n_l
            q.append(n_i)
for l in d[1:]:
    print(l%2)

Solution (Python):
from collections import deque

N = int(input())
S = [[]for i in range(N)]
for i in range(N-1):
    u,v,w = map(int,input().split())
    S[u-1].append([v-1,w])
    S[v-1].append([u-1,w])
Node = [None]*N
Node[0] = True
queue = deque([0])
while queue != deque([]):
    p = queue.popleft()
    for u,w in S[p]:
        if Node[u] == None:
            queue.append(u)
            Node[u] = (Node[p])^(w%2==1)
for i in range(N):
    print([0,1][Node[i]])

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

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


d = [-1]*(n+1)
d[1] = 0
q = [1]
while q:
  now = q.pop()
  for n_i,n_l in tree[now]:
    if d[n_i] == -1:
      d[n_i] = d[now] + n_l
      q.append(n_i)

for l in d[1:]:
  print(l%2)

Solution (Python):
from collections import deque
def bfs(cur):
    q=deque()
    q.append(cur)
    while q:
        cur=q.popleft()
        for nx,e_dist in G[cur]:
            if ans[nx]!=-1:continue
            ans[nx]=(ans[cur]+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)
print(*ans,sep='\n')

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

def dfs(node,dist):
    for nx_node,e_dist in G[node]:
        if ans[nx_node]==-1:
            ans[nx_node]=(dist+e_dist)%2
            dfs(nx_node,dist+e_dist)

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
dfs(0,0)
print(*ans,sep='\n')

Solution (Python):
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
 
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
 
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N = INT()
uvw = [LIST() for i in range(N-1)]
color = [0] * N

graph = defaultdict(list)

for u, v, w in uvw:
    graph[u-1].append((v-1, w))
    graph[v-1].append((u-1, w))

color[0] = 1
q = [0]

while q:
    a = q.pop()
    

    
    
        
    for node, w in graph[a]:
        if color[node] == 0:
            
            if w % 2 == 0:
                color[node] = color[a]
            else:
                color[node] = color[a] * (-1)
            q.append(node)
for c in color:
    if c == -1:
        print(1)
    else:
        print(0)

Solution (Python):
import heapq
import sys

input = sys.stdin.readline

def dijkstra_heap(s,edge):
    
    d = [10**20] * 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

n=int(input()) 
w=n-1
edge = [[] for i in range(n)]

for i in range(w):
    x,y,z = map(int,input().split())
    edge[x-1].append([z,y-1])
    edge[y-1].append([z,x-1]) 

for i in dijkstra_heap(0,edge):
    if i%2==0:
        print(0)
    else:
        print(1)

Solution (Python):
import sys
sys.setrecursionlimit(10**7)
n = int(input())
B = [[] for _ in range(n+1)]
for i in range(n-1):
    v,w,dist = map(int, input().split())
    B[v].append((w,dist))
    B[w].append((v,dist))
color = [-1]*(n+1)
def dfs(a, col):
    if color[a] == -1:
        color[a] = col
    for next_V, dis in B[a]:
        if color[next_V] == -1:
            tmp = col
            if dis%2 != 0:
                tmp = 1-col
            dfs(next_V, tmp)
dfs(1,0)
[print(color[i]) for i in range(1,n+1)]

Solution (Python):
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)


def dfs(a, col):
    tmp = -1
    if color[a] == -1:
        color[a] = col

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

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


def Graph():
    G=[[] for i in range(n)]
    
    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


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

    return dis_l


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

Solution (Python):
import collections


def main():
    import sys
    input = sys.stdin.readline
    N = int(input())
    color = [-1]*N
    G = [set() for i in range(N)]
    for i in range(N-1):
        u, v, w = map(int, input().split())
        u -= 1
        v -= 1
        G[u].add((v, w))
        G[v].add((u, w))
    root = 0

    color[0] = 0
    q = collections.deque()
    q.append((root, 0))
    while(q):
        x, W = q.popleft()
        for y, w in G[x]:
            if color[y] < 0:
                if (W+w) % 2 == 0:
                    color[y] = 0
                else:
                    color[y] = 1
                q.append((y, W+w))
            else:
                continue
    print(*color, sep="\n")


main()

Solution (Python):
def main():
    import sys
    input = sys.stdin.buffer.readline
    N = int(input())
    edge = [[] for _ in range(N)]
    for i in range(N-1):
        a, b, c = (int(i) for i in input().split())
        edge[a-1].append((c % 2, b-1))
        edge[b-1].append((c % 2, a-1))

    dist = [-1]*N
    color = [-1]*N

    def dfs(v, G):
        todo = []
        dist[v] = 0
        color[v] = 0
        todo.append((v, 0)) 
        while todo:
            u, s = todo.pop() 
            if s == 0:
                
                todo.append((u, 1)) 
                for c, next_v in G[u]:
                    if dist[next_v] != -1:
                        continue
                    dist[next_v] = dist[u] + c
                    if dist[next_v] % 2 == 1:
                        color[next_v] = 1
                    else:
                        color[next_v] = 0
                    todo.append((next_v, 0))
                    
            
            

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


if __name__ == '__main__':
    main()

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

def dfs(i):
    
    
    color = visited[i]
    for nextIdx, wgt in graph[i]:
        if visited[nextIdx] == -1:
            if wgt % 2 == 0:
                visited[nextIdx] = color
            else:
                visited[nextIdx] = int(not color)
            dfs(nextIdx)

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

visited = [-1] * n
visited[0] = 0
dfs(0)
for v in visited:
    print(v)

Solution (Python):
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))

dist = [-1] * N
dist[0] = 0
stack = [0]
while stack:
    u = stack.pop()
    d = dist[u]

    for v,w in edge[u]:
        if dist[v] > 0:
            continue
        dist[v] = d + w
        stack.append(v)

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

Solution (Python):
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))

dist = [-1] * N
dist[0] = 0
que = [0]
while que:
    u = que.pop()
    d = dist[u]

    for v,w in edge[u]:
        if dist[v] > 0:
            continue
        dist[v] = d + w
        que.append(v)

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

Solution (Python):
def main():
    import sys
    from collections import deque
    input = sys.stdin.buffer.readline
    N = int(input())
    edge = [[] for _ in range(N)]
    for i in range(N-1):
        a, b, c = (int(i) for i in input().split())
        edge[a-1].append((c, b-1))
        edge[b-1].append((c, a-1))

    dist = [-1]*N
    color = [-1]*N

    def dfs(v, G):
        todo = deque()
        dist[v] = 0
        color[v] = 0
        todo.append(v)
        while todo:
            u = todo.pop()
            for c, next_v in G[u]:
                if dist[next_v] != -1:
                    continue
                dist[next_v] = dist[u] + c
                if dist[next_v] % 2 == 1:
                    color[next_v] = 1
                else:
                    color[next_v] = 0
                todo.append(next_v)

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


if __name__ == '__main__':
    main()

Solution (Python):
def main():
    import sys
    input = sys.stdin.buffer.readline
    N = int(input())
    edge = [[] for _ in range(N)]
    for _ in [0]*(N-1):
        a, b, c = (int(i) for i in input().split())
        edge[a-1].append((c % 2, b-1))
        edge[b-1].append((c % 2, a-1))

    from collections import deque
    dist = [-1]*N
    color = [-1]*N

    def bfs(s, G):
        que = deque()
        dist[s] = 0
        color[s] = 0
        que.append(s)
        while que:
            u = que.popleft()
            for c, v in G[u]:
                if dist[v] != -1:
                    continue
                dist[v] = (dist[u] + c) % 2
                if dist[v] % 2 == 1:
                    color[v] = 1
                else:
                    color[v] = 0
                que.append(v)

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


if __name__ == '__main__':
    main()

Solution (Python):
import sys

if sys.getrecursionlimit()<10**7:
    sys.setrecursionlimit(10**7)

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

def dfs(i,col):
    his[i]=col
    for j,w in ver[i]:
        if his[j]==-1:
            if w%2==0:
                dfs(j,col)
            else:
                dfs(j,(col+1)%2)

dfs(0,0)            
for i in range(N):
    print(his[i])

Solution (Python):
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, d + w))

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

Solution (Python):
import sys
sys.setrecursionlimit(10**9)
N = int(input())
edge = [[] for _ in range(N)]

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

ret = [0] * N
def dfs(pv, v, dist):
    ret[v] = dist
    for nv, w in edge[v]:
        if nv == pv:
            continue
        dfs(v, nv, (dist+w)%2)

dfs(-1,0,0)
print(*ret, sep="\n")

Solution (Python):
from collections import deque
n = int(input())
edge = []
for i in range(n+1):
    edge.append([])
for i in range(n-1):
    u,v,w = map(int,input().split())
    edge[u].append([v,w])
    edge[v].append([u,w])
ans = [0] * (n+1)


def breadth_first_search(edge):
    work_q = deque([1])
    visited = set()
    visited.add(1)
    while work_q:
        here = work_q.popleft()
        col = ans[here]
        for i in edge[here]:
            if i[0] not in visited:
                work_q.append(i[0])
                visited.add(i[0])
                if i[1] % 2 == 0 and col == 0:
                    ans[i[0]] = 0
                elif i[1] % 2 != 0 and col == 0:
                    ans[i[0]] = 1
                elif i[1] % 2 == 0 and col == 1:
                    ans[i[0]] = 1
                elif i[1] % 2 != 0 and col == 1:
                    ans[i[0]] = 0


breadth_first_search(edge)
for i in range(1,n+1):
    print(ans[i])

Solution (Python):
import sys

input = sys.stdin.readline

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

from collections import deque
s = deque()
s.append(0)
visit = [-1]*n
visit[0] = 0
while s:
    u = s.pop()
    for v, w in g[u]:
        if visit[v] == -1:
            if w%2 == 0:
                visit[v] = visit[u]
            else:
                visit[v] = 1 - visit[u]
            s.append(v)
for i in range(n):
    print(visit[i])

Solution (Python):
from collections import deque

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

dist = [-1] * N
dist[0] = 0
que = deque([0])
while que:
    u = que.popleft()
    d = dist[u]

    for v,w in edge[u]:
        if dist[v] > 0:
            continue
        dist[v] = d + w
        que.append(v)

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

Solution (Python):
import sys
def main():
    input = sys.stdin.readline
    N = int(input())
    G = [[] for _ in range(N)]
    for _ in range(N-1):
        u,v,w = map(int, input().split())
        u,v = u-1,v-1
        G[u].append((v,w))
        G[v].append((u,w))

    ans = [-1] * N
    ans[0] = 0
    stack = [(0,0)]
    while stack:
        v, w = stack.pop()
        for to, to_w in G[v]:
            if ans[to] >= 0: continue
            ans[to] = 1 if (w + to_w) & 1 else 0
            stack.append((to, w + to_w))
    
    for a in ans: print(a)

if __name__ == '__main__':
    main()

Solution (Python):
import sys
from collections import deque

def solve():
    input = sys.stdin.readline
    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))

    Col = [-1] * N
    q = deque()
    q.append((0, 0, 0)) 
    while q:
        nn, pn, dist = q.pop()
        if Col[nn] == -1:
            Col[nn] = dist % 2
            for nextN, addW in Edge[nn]:
                if pn != nextN:
                    q.append((nextN, nn, dist + addW))
    print("\n".join(map(str, Col)))

    return 0

if __name__ == "__main__":
    solve()

Solution (Python):
import sys
sys.setrecursionlimit(10**7)
N = int(input())
UVW = [tuple(map(int,input().split())) for i in range(N-1)]
es = [[] for _ in range(N)]
for u,v,w in UVW:
    u,v = u-1,v-1
    es[u].append((v,w))
    es[v].append((u,w))

ans = [-1]*N
ans[0] = 0
def dfs(v,p=-1):
    for to,d in es[v]:
        if to==p: continue
        if d%2:
            ans[to] = 1 - ans[v]
        else:
            ans[to] = ans[v]
        dfs(to,v)
dfs(0)
print(*ans, sep='\n')

Solution (Python):
from collections import deque
from collections import Counter
from itertools import product, permutations,combinations
from operator import itemgetter
from heapq import heappop, heappush
import math
import sys
input = sys.stdin.readline

sys.setrecursionlimit(2147483647)

def main():
  N = int(input())
  G = [[] for i in range(N)]
  C = [-1] * N
  C[0] = 0
  for i in range(N-1):
    u, v, w = map(int, input().split())
    u, v = u-1, v-1
    G[u].append((v,w))
    G[v].append((u,w))
  def dfs(now):
    for ne_xt, w in G[now]:
      if C[ne_xt]==-1:
        C[ne_xt]=(C[now]+w)%2
        dfs(ne_xt)
  dfs(0)
  for i in range(N):
    print(C[i])
  
  
if __name__ == '__main__':
  main()

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

readline = sys.stdin.readline
n = int(readline())
G = [[] for _ in range(n)]
ans = [-1] * n
for _ in range(n-1):
    u, v, w = map(int, readline().split())
    u -= 1
    v -= 1
    G[u].append((v, w))
    G[v].append((u, w))
q = [0]
ans[0] = 1
while q:
    x = q.pop()
    for i, d in G[x]:
        if ans[i] != -1:
            continue
        if d % 2:
            ans[i] = int(not ans[x])
        else:
            ans[i] = ans[x]
        q.append(i)
print(*ans, sep='\n')

Solution (Python):
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-c)
        else: dfs(vi, v, c)
    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)

Solution (Python):
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 == 0: dfs(vi, v, c)
        else: dfs(vi, v, 1-c)
    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)