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):
N, *m=map(int, open(0).read().split())

im = iter(m)
UVW = list(zip(im, im, im))



colors = {i:-1 for i in range(1,N+1)}
u,v,w = UVW[0]
colors[u] = 0

def opposite(u, v):
    if v == -1:
        return u
    if v == 0:
        return 1
    if v == 1:
        return 0

def same(u, v):
    if v == -1:
        return u
    else:
        return v

while -1 in colors.values():
    next_UVW = []
    for u, v, w in UVW:
        if colors[u] == -1 and colors[v] == -1:
            next_UVW.append((u, v, w))
            continue

        if w % 2 == 0:
            colors[u] = same(colors[u], colors[v])
            colors[v] = same(colors[v], colors[u])

        if w % 2 == 1:
            colors[u] = opposite(colors[u], colors[v])
            colors[v] = opposite(colors[v], colors[u])

        if colors[u] == -1 or colors[v] == -1:
            next_UVW.append((u,v,w))

    UVW = next_UVW



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

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

for i 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])

col = [-1]*n
visited = [0]*n

def dfs(i,c):
    visited[i]=1
    col[i] = c
    for j in edge[i]:
        if not visited[j[0]]:
            if j[1]%2==0:
                dfs(j[0],c)
            else:
                dfs(j[0],-1*c)


def main():
    dfs(0,1)
    for i in range(n):
        print(max(col[i],0))



if __name__ == '__main__':
    main()

Solution (Python):
import sys
import itertools

import time
import math

sys.setrecursionlimit(10 ** 7)

from collections import defaultdict

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

n = int(readline())

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


visited = [False for _ in range(n)]
dist = [0 for _ in range(n)]
def dfs(x, depth):
    if visited[x]:
        return
    visited[x] = True
    dist[x] = depth
    for y in adj[x]:
        dfs(y[1], depth + y[0])

dfs(0, 0)


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

Solution (Python):


import heapq
from collections import defaultdict

class Dijkstra:
    def __init__(self, rote_map, start_point, goal_point=None):
        self.rote_map = rote_map
        self.start_point = start_point
        self.goal_point = goal_point

    def execute(self):
        num_of_city = len(self.rote_map)
        dist = [float("inf") for _ in range(num_of_city)]
        prev = [float("inf") for _ in range(num_of_city)]

        dist[self.start_point] = 0
        heap_q = []
        heapq.heappush(heap_q, (0, self.start_point))
        while len(heap_q) > 0:
            prev_cost, src = heapq.heappop(heap_q)

            if dist[src] < prev_cost:
                continue

            for dest, cost in self.rote_map[src].items():
                if cost != float("inf") and dist[dest] > dist[src] + cost:
                    dist[dest] = dist[src] + cost
                    heapq.heappush(heap_q, (dist[dest], dest))
                    prev[dest] = src
        return dist

    def get_path(self, goal, prev):
        path = [goal]
        dest = goal
        while prev[dest] != float("inf"):
            path.append(prev[dest])
            dest = prev[dest]
        return list(reversed(path))

n = int(input())
route_map = [dict() for _ in range(n)]
for i in range(n - 1):
    u, v, wi = map(int, input().split())
    u, v = u - 1, v - 1
    route_map[u][v] = wi
    route_map[v][u] = wi

d = Dijkstra(route_map, 0).execute()
for k in range(n):
    if d[k] % 2 == 0:
        print(0)
    else:
        print(1)

Solution (Python):
n=int(input())
e=[[] for _ in range(n)]
for _ in range(n-1):
    xi,yi,wi=map(int, input().split())
    xi-=1;yi-=1
    e[yi].append((xi,wi))
    e[xi].append((yi,wi))

c=[0]*n
used=[0]*n

from collections import deque

q=deque()
q.append(0)
while q:
    u=q.popleft()
    for v,w in e[u]:
        if not used[v]:
            c[v]=(c[u]+w)%2
            used[v]=1
            q.append(v)
for i in c:
    print(i)

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

    d=[0]*(n+1)
    flags=[False]*(n+1)
    flags[1]=True
    q=deque([1])
    while len(q)>0:
        now=q.popleft()
        for nex in G[now]:
            if flags[nex[0]]==False:
                flags[nex[0]]=True
                q.append(nex[0])
                d[nex[0]]=d[now]+nex[1]

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

if __name__=="__main__":
    main()

Solution (Python):
import collections

N = int(input())

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


ans = [-1] * N

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


for u, v, w in UVW:
    A[u - 1].append([v - 1, w % 2])
    A[v - 1].append([u - 1, w % 2])

q = collections.deque()
q.append(0)

ans[0] = 0
while q:
    c = q.popleft()

    for ni, nd in A[c]:
        if ans[ni] != -1:
            continue

        if nd == 0:
            ans[ni] = ans[c]
        else:
            ans[ni] = ans[c] ^ 1

        q.append(ni)

if sum(ans) == 0:
    ans[0] = 1

for a in ans:
    print(a)

Solution (Python):
import unittest

import collections


def solve(n, tree):
    cl = [0] * n
    visited = [False]*n
    stack = []
    stack.append((0, 0))
    while stack:
        v, c = stack.pop()
        if visited[v]:
            continue
        cl[v] = c
        visited[v] = True
        for nv, w in tree[v]:
            if visited[nv]:
                continue
            stack.append((nv, (c + w) % 2))

    return '\n'.join([str(c) for c in cl])


def main():
    n = int(input())
    tree = [[] for i in range(n)]
    for _ in range(n-1):
        u, v, w = map(int, input().split())
        tree[v-1].append((u-1, w % 2))
        tree[u-1].append((v-1, w % 2))
    result = solve(n, tree)
    print(result)


if __name__ == "__main__":
    main()

Solution (Python):
import sys
input = sys.stdin.readline
from collections import deque
def main():
    N = int( input())
    E = [[] for _ in range(N)]
    for _ 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))
    V = [-1]*N
    V[0] = 0
    d = deque([(0,0)])
    while d:
        u, l = d.popleft()
        for v,w in E[u]:
            if V[v] == -1:
                V[v] = (l+w)%2
                d.append((v, (l+w)%2))
    print("\n".join( map( str, V)))
    
    
if __name__ == '__main__':
    main()

Solution (Python):
import sys
sys.setrecursionlimit(10**8)
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 = [None] * N
ans[0] = 0

def dfs(v,p=-1):
    for to,d in es[v]:
        if to==p: continue
        ans[to] = ans[v] ^ (d%2)
        dfs(to,v)
dfs(0)

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

Solution (Python):
from collections import deque

n = int(input())

u = [0] * n
v = [0] * n
w = [0] * n

dist = [-1] * n
adj_list = [[] for _ in range(n)]

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

    adj_list[u].append([v, w])
    adj_list[v].append([u, w])

q = deque()
dist[0] = 0
q.append(0)

while len(q) > 0:
    node = q.popleft()

    for next, d in adj_list[node]:
        if dist[next] > 0:
            continue

        if dist[next] == -1 or dist[next] > dist[node] + d:
            dist[next] = dist[node] + d
            q.append(next)

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

Solution (Python):
N = int(input())
g = [[] for i in range(N)]

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

    g[u].append((w, v))
    g[v].append((w, u))

from heapq import heappush, heappop, heapify
INF = float('inf')

dist = [INF] * N
visited = [False] * N

q = g[0]
heapify(q)
dist[0] = 0
visited[0] = True

while q:
    c, v = heappop(q)

    if visited[v]: continue
    visited[v] = True
    dist[v] = c

    for w, u in g[v]:
        if visited[u]: continue
        heappush(q, (c+w, u))

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

Solution (Python):
from collections import deque
N = int(input())
E = [[] for i in range(N + 1)]
ans = [-1]*(N+1)
ans[1] = 0
for i in range(N - 1):
    u, v, w = map(int, input().split((' ')))
    E[u].append((u, v, w % 2))
    E[v].append((v, u, w % 2))
dfs = deque(E[1])
while dfs:
    p = (dfs.popleft())
    f, t, w = p
    if ans[t] != -1:
        continue
    if w == 0:
        ans[t] = ans[f]
    else:
        ans[t] = 0 if ans[f] else 1
    for i in E[t]:
        dfs.append(i)
for i in ans[1:]:
    print(i)

Solution (Python):
import collections
def resolve():
    N = int(input())
    VVW = [list(map(int, input().split())) for _ in range(N-1)]
    adjs = [[] for _ in range(N)]
    for vvw in VVW:
        adjs[vvw[0]-1].append([vvw[1]-1, vvw[2]])
        adjs[vvw[1]-1].append([vvw[0]-1, vvw[2]])

    result = [None for _ in range(N)]
    deq = collections.deque([[0, 0]])
    result[0] = "0"

    while deq:
        node, cost = deq.popleft()
        for adj in adjs[node]:
            nextnode, nextcost = adj[0], adj[1]
            if result[nextnode] is not None:
                continue
            if nextcost%2 == 0:
                result[nextnode] = result[node]
            else:
                result[nextnode] = "1" if result[node] == "0" else "0"
            deq.append([nextnode, nextcost])
    
    [print(r) for r in result]



if '__main__' == __name__:
    resolve()

Solution (Python):

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


que = [1]
color[1] = 0
while len(que) != 0:
  nowv = que.pop(0)
  nowc = color[nowv]
  
  for nx in graph[nowv]:
    if color[nx[0]] != -1:
      continue
    que.append(nx[0])
    if nx[1] % 2 == 1:
      color[nx[0]] = 1 - nowc
    else:
      color[nx[0]] = nowc


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

Solution (Python):
import sys
from collections import Counter
from collections import deque
import heapq
import math
import fractions
import bisect
import itertools
def input(): return sys.stdin.readline().strip()
def mp(): return map(int,input().split())
def lmp(): return list(map(int,input().split()))

n=int(input())
tree=[[] for i in range(n+1)]
for i in range(n-1):
    a,b,c=mp()
    tree[a].append([a,b,c])
    tree[b].append([b,a,c])
ans=[-1]*(n+1)
ans[1]=0
que=deque()
que.append(tree[1])
while len(que):
    q=que.popleft()
    for x,y,z in q:
        if ans[y]==-1:
            ans[y]=(ans[x]+z)%2
            que.append(tree[y])
print(*ans[1:],sep="\n")

Solution (Python):
import sys
from collections import Counter
from collections import deque
import heapq
import math
import fractions
import bisect
import itertools
def input(): return sys.stdin.readline().strip()
def mp(): return map(int,input().split())
def lmp(): return list(map(int,input().split()))

n=int(input())
tree=[[] for i in range(n+1)]
for i in range(n-1):
    a,b,c=mp()
    tree[a].append([a,b,c])
    tree[b].append([b,a,c])
ans=[-1]*(n+1)
ans[1]=0
que=deque()
que.append(tree[1])
while len(que):
    q=que.popleft()
    for x,y,z in q:
        if ans[y]==-1:
            ans[y]=(ans[x]+z)%2
            que.append(tree[y])
print(*ans[1:],sep="\n")

Solution (Python):
import sys
input = lambda : sys.stdin.readline().rstrip()

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


import heapq
def dijkstra(s):
    
    d = [float('inf')]*n
    d[s] = 0
    
    used = [False]*n
    used[s] = True
    
    que = []
    for e in edge[s]:
        heapq.heappush(que, e)
    while que:
        minedge = heapq.heappop(que)
        if used[minedge[1]]:
            continue
        v = minedge[1]
        d[v] = minedge[0]
        used[v] = True
        for e in edge[v]:
            if not used[e[1]]:
                heapq.heappush(que, [e[0] + d[v], e[1]])
    return d

d = dijkstra(0)
ans = [0]*n

for i in range(n):
    if d[i] % 2 == 1:
        ans[i] = 1

for i in ans:
    print(i)

Solution (Python):
import sys
input = lambda : sys.stdin.readline().rstrip()

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


import heapq
def dijkstra(s):
    
    d = [float('inf')]*n
    d[s] = 0
    
    used = [False]*n
    used[s] = True
    
    que = []
    for e in edge[s]:
        heapq.heappush(que, e)
    while que:
        minedge = heapq.heappop(que)
        if used[minedge[1]]:
            continue
        v = minedge[1]
        d[v] = minedge[0]
        used[v] = True
        for e in edge[v]:
            if not used[e[1]]:
                heapq.heappush(que, [e[0] + d[v], e[1]])
    return d

d = dijkstra(0)
ans = [0]*n

for i in range(n):
    if d[i] % 2 == 1:
        ans[i] = 1

for i in ans:
    print(i)

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

def dfs(node,distance):
  for next_node,edge_distangce in G[node]:
    if ans[next_node]==-1:
      ans[next_node]=(distance+edge_distangce)%2
      dfs(next_node,distance+edge_distangce)

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
sys.setrecursionlimit(10**7)
from collections import defaultdict
def dfs(node_i, oe):
    if ans[node_i] != -1:
        return
    next_nodes = graph[node_i]
    ans[node_i] = oe
    for next_i, cost in next_nodes:
        dfs(next_i, (oe+cost)%2)
        

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

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

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

def dfs(curr_v, pare_v, curr_sum, visited, g):
    if curr_sum%2 == 0:
        visited[curr_v] = 0
    else:
        visited[curr_v] = 1
    for neib_vw in g[curr_v]:
        if neib_vw[0] == pare_v: continue
        dfs(neib_vw[0], curr_v, curr_sum+neib_vw[1], visited, g)
    

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

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

dfs(1, -1, 0, visited, g)
for p in visited[1:]:
    print(p)

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

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))
color = [-1]*(N+1)
def dfs(n,p,c):
    color[n]=c
    for nx,w in edges[n]:
        if nx != p:
            if w % 2 == 0:
                nxC = c
            else:
                nxC = (c+1)%2
            dfs(nx,n,nxC)

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

Solution (Python):
from collections import deque

N = int(input())

edge = [[int(s) - 1 for s in input().split()] for _ in range(N-1)]
graph = [[] for _ in range(N)]
weight_odd = {}

for i, j, w in edge:
    graph[i].append(j)
    graph[j].append(i)
    weight_odd[(i, j)] = (w % 2 != 0)
    weight_odd[(j, i)] = (w % 2 != 0)

dq = deque([0])
visited = [False] * N
color = [1] * N
while(dq):
    search_obj = dq.pop()
    col1 = color[search_obj]
    col2 = 0 if col1 == 1 else 1
    for candidate_obj in graph[search_obj]:
        if not visited[candidate_obj]:
            if weight_odd[(candidate_obj, search_obj)]:
                color[candidate_obj] = col1
            else:
                color[candidate_obj] = col2
            dq.appendleft(candidate_obj)
            visited[candidate_obj] = True

for c in color:
    print(c)

Solution (Python):
import sys
readline = sys.stdin.readline


N = int(readline())
G = [[] for i in range(N)]

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

ans = [-1] * N

stack = []

stack.append([0,0])
while stack:
  v,color = stack.pop()
  if ans[v] != -1:
    continue
  ans[v] = color
  for child in G[v]:
    col = color
    if child[1] % 2 == 1:
      col ^= 1
    stack.append([child[0], col])

for a in ans:
  print(a)

Solution (Python):
import sys
n = int(input())
sys.setrecursionlimit(2*n)
graph = [[] for _ in range(n)]
for _ in range(n-1):
    u, v, w = map(int, input().split())
    graph[u-1].append((v-1, w))
    graph[v-1].append((u-1, w))
colors = [None]*n
colors[0] = 0
def DFS(node):
    for c_node, l in graph[node]:
        if colors[c_node] is not None:
            continue
        colors[c_node] = (l+colors[node])%2
        DFS(c_node)
DFS(0)
for i in colors:
    print(i)

Solution (Python):
def main():
    from collections import deque, defaultdict
    n, *uvw = map(int, open(0).read().split())
    l = defaultdict(dict)
    g = [[] for _ in range(n + 1)]

    for u, v, w in zip(uvw[::3], uvw[1::3], uvw[2::3]):
        g[u].append(v)
        g[v].append(u)
        l[u].update({v: w % 2})

    l[0].update({1: 0})

    vis = [False] * (n + 1)
    col = [0] * (n + 1)

    q = deque()
    q.append([0, 1, 0])

    while q:
        i, j, k = q.popleft()
        if vis[j]:
            continue
        vis[j] = True
        c = k if l[min(i, j)][max(i, j)] == 0 else 1 - k
        col[j] = c

        for x in g[j]:
            q.appendleft([j, x, c])

    print(*col[1:], sep='\n')


if __name__ == '__main__':
    main()

Solution (Python):
def main():
    from collections import deque, defaultdict
    n, *uvw = map(int, open(0).read().split())
    l = defaultdict(dict)
    g = [[] for _ in range(n + 1)]

    for u, v, w in zip(uvw[::3], uvw[1::3], uvw[2::3]):
        g[u].append(v)
        g[v].append(u)
        l[u].update({v: w % 2})
        l[v].update({u: w % 2})

    l[0].update({1: 0})

    vis = [False] * (n + 1)
    col = [0] * (n + 1)

    q = deque()
    q.append([0, 1, 0])

    while q:
        i, j, k = q.popleft()
        if vis[j]:
            continue
        vis[j] = True
        c = k if l[i][j] == 0 else 1 - k
        col[j] = c

        for x in g[j]:
            q.appendleft([j, x, c])

    ans = '\n'.join(map(str, col[1:]))
    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
def main():
    from collections import deque, defaultdict
    n, *uvw = map(int, open(0).read().split())
    l = defaultdict(dict)
    g = [[] for _ in range(n + 1)]

    for u, v, w in zip(uvw[::3], uvw[1::3], uvw[2::3]):
        g[u].append(v)
        g[v].append(u)
        l[u].update({v: w % 2})

    l[0].update({1: 0})

    vis = [False] * (n + 1)
    col = [0] * (n + 1)

    q = deque()
    q.append([0, 1, 0])

    while q:
        i, j, k = q.popleft()
        if vis[j]:
            continue
        vis[j] = True
        c = k if l[min(i, j)][max(i, j)] == 0 else 1 - k
        col[j] = c

        for x in g[j]:
            q.appendleft([j, x, c])

    ans = '\n'.join(map(str, col[1:]))
    print(ans)


if __name__ == '__main__':
    main()

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

from collections import defaultdict, deque
g = defaultdict(list)
for u, v, w in uvw:
    g[u-1].append((v - 1, w))
    g[v-1].append((u - 1, w))

ans = [-1] * n
ans[0] = 0
q = deque([0])

while q:
    cur = q.popleft()
    for target, w in g[cur]:
        if ans[target] == -1:
            if w % 2 == 0:
                ans[target] = ans[cur]
            else:
                ans[target] = 1 - ans[cur]
            q.append(target)

for a in ans:
    print(a)

Solution (Python):

from collections import deque

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

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


queue = deque([0])
ans = [0]*n
checked = [0]*n

while queue:
    x =queue.popleft()
    checked[x] = -1
    dis = ans[x]
    for tup in arr[x]:
        if checked[tup[0]]> -1:
            ans[tup[0]]=(dis+tup[1])%2
            queue.append(tup[0])
print(*ans,sep='\n')

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

que=deque([0])
ans=[0]*n
visited=[0]*n

while que:
    x=que.popleft()
    visited[x]=-1
    dis=ans[x]
    for tup in arr[x]:
        if visited[tup[0]]>-1:
            ans[tup[0]]=(dis+tup[1])%2
            que.append(tup[0])
print(*ans,sep='\n')

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

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

color = [None] * N
def dfs(n,l):
  if l%2==0:
    color[n] = 1
  else:
    color[n] = 0

  for nei, nl in adj[n]:
    if color[nei] is not None:
      if (l+nl) % 2 == 0 and color[nei] != 1:
        return False
      if (l+nl) % 2 == 1 and color[nei] != 0:
        return False
    else:
      dfs(nei, l+nl)

  return True

for i in range(N):
  if color[i] is None:
    if not dfs(i,0):
      print(-1)
      exit()

for c in color: print(c)

Solution (Python):
from collections import deque

n = int(input())

color = [-1]*(n+1)
rel = [{} for i in range(n+1)]

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

def f(n):
    color[n] = 0
    stack = deque()
    stack.append(n)
    while stack:
        new = stack.pop()
        for ver in rel[new]:
            if color[ver] == -1:
                color[ver] = 1-color[new] if rel[new][ver]&1 else color[new]
                stack.append(ver)

for i in range(1, n+1):
    if color[i] != -1: continue
    f(n)

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

Solution (Python):
import sys
from collections import deque
readline = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7

def main():
    N = int(readline())
    tree = [[] for _ in range(N)]
    for i in range(N-1):
        u, v, w = map(int, readline().split())
        u, v = u-1, v-1
        tree[u].append((v,w))
        tree[v].append((u,w))
    color = [-1]*N
    color[0]=0

    que = deque([0])
    while que:
        index = que.popleft()
        for next_, weight in tree[index]:
            if color[next_]==-1:
                if weight%2==0:
                    color[next_] = color[index]
                else:
                    color[next_] = color[index]^1
                que.append(next_)
    for c in color:
        print(c)


if __name__ == '__main__':
    main()

Solution (Python):


n = int(input())

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

    tree[u].append((v, w))
    tree[v].append((u, w))

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


queue = [0]
while(len(queue) > 0):
    index = queue.pop()
    tree_tmp = tree[index]
    for next_, weight in tree_tmp:
        
        if color[next_] == -1:
            if weight % 2 == 0:
                color[next_] = color[index]
            else:
                color[next_] = (color[index]+1) % 2
            queue.append(next_)


[print(i) for i in color]

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

n = int(input())

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


ans = [-1]*n

def dfs(node, dist):
    for next_node, edge_size in graph[node]:
        if ans[next_node] == -1:
            ans[next_node] = (dist+edge_size) % 2
            dfs(next_node, dist+edge_size)


dfs(0, 0)
print(*ans, sep='\n')

Solution (Python):
import sys

def IS(): return sys.stdin.readline().rstrip()
def II(): return int(IS())
def MII(): return list(map(int, IS().split()))
def MIIZ(): return list(map(lambda x: x-1, MII()))
from collections import deque

def main():
    n = II()
    graph = [[] for _ in range(n)]
    for i in range(n-1):
        u,v,w = MII()
        graph[u-1].append((w, v-1))
        graph[v-1].append((w, u-1))
    dq = deque()
    color = [-1]*n
    dist = [-1]*n
    dq.append((0,0))
    color[0] = 0
    dist[0] = 0
    while dq:
        prev_cost, src = dq.popleft()
        for cost, dst in graph[src]:
            if dist[dst] != -1:
                continue
            if prev_cost%2 == cost%2:
                color[dst] = 0
            else:
                color[dst] = 1
            dist[dst] = dist[src] + cost
            dq.append((dist[dst], dst))
    print(*color, sep='\n')

if __name__ == '__main__':
    main()

Solution (Python):
from collections import deque
from sys import stdin
nii=lambda:map(int,stdin.readline().split())

n=int(input())

tree=[[] for i in range(n)]
for i in range(n-1):
  u,v,w=nii()
  u-=1
  v-=1
  tree[u].append([v,w])
  tree[v].append([u,w])

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

que=deque()
que.append(0)

while que:
  x=que.popleft()
  for i in tree[x]:
    nx=i[0]
    nw=i[1]
    if ans[nx]==-1:
      que.append(nx)
      if nw%2==0:
        ans[nx]=ans[x]
      else:
        ans[nx]=(ans[x]+1)%2

for i in ans:
  print(i)

Solution (Python):
from collections import deque
N = int(input())
UVW = [list(map(int, input().split())) for _ in range(N-1)]
G = [{} for _ in range(N+1)]
for u, v, w in UVW:
    G[u-1][v-1] = w
    G[v-1][u-1] = w



distance = [-1] * N

que = deque([(0, 0)])
while que:
    c, d = que.popleft()
    distance[c] = d

    for n, w in G[c].items():
        if distance[n] == -1:
            que.append((n, d+w))


print(*[d % 2 for d in distance], sep='\n')

Solution (Python):
import sys

def tree_path():
    def walk(i,c):
        if d[i] == -1:
            d[i] = c
            for node, dist in path[i]:
                walk(node, c+dist)
    sys.setrecursionlimit(100007)
    n = int(input())
    path = [[] for _ in range(n+1)]
    for _ in range(n-1):
        u , v , w = map(int,input().split())
        path[u].append([v,w])
        path[v].append([u,w])
    
    d = [-1] * (n+1)
    walk(1,0)
    for item in d[1:]:
        print(item % 2)
tree_path()

Solution (Python):
import sys
input = sys.stdin.readline
from collections import deque
def bfs(now):
    plan = deque()
    plan.append(now)
    while plan:
        now = plan.popleft()
        color = COLOR[now]
        for bady, l in LINK[now]:
            if COLOR[bady] != -1:
                continue
            plan.append(bady)
            if l%2:
                COLOR[bady] = 1 - color
            else:
                COLOR[bady] = color

if __name__ == '__main__':
    N = int(input())
    LINK = [[]*(N+1) for i in range(N+1)]
    
    for i in range(N-1):
        a, b, l = map(int, input().split())
        LINK[a].append([b, l])
        LINK[b].append([a, l])
    
    
    
    COLOR= [-1]*(N+1)
    COLOR[1] = 1
    bfs(1)
    for i in range(1,N+1):
        print(COLOR[i])

Solution (Python):
import queue
N = int(input())
ans = [-1]*N
odd = [[] for _ in range(N)]
even = [[] for _ in range(N)]
for i in range(N-1):
    u,v,w = map(int,input().split())
    if w % 2 == 0:
        even[u-1].append(v-1)
        even[v-1].append(u-1)
    else:
        odd[u-1].append(v-1)
        odd[v-1].append(u-1)

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

while (not q.empty()):
    now = q.get()
    nowa = ans[now]
    for i in odd[now]:
        if ans[i] == -1:
            if nowa == 0:
                ans[i] = 1
            else:
                ans[i] = 0
            q.put(i)
    for j in even[now]:
        if ans[j] == -1:
            ans[j] = nowa
            q.put(j)

for i in ans:
    print(i)

Solution (Python):
def d_even_relation_dfs():
    import sys
    sys.setrecursionlimit(10**6)
    N = int(input())
    Edges = [[int(i) for i in input().split()] for j in range(N - 1)]

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

    def distance_from_root(parent, current, distance, ret=None):
        """根 (頂点 0) から各頂点への距離"""
        if ret is None:
            ret = [0] * N

        ret[current] = distance
        for next_vertex, dist in graph[current]:
            if next_vertex != parent:
                distance_from_root(current, next_vertex, distance + dist, ret)
        return ret
    ans = (0 if d % 2 else 1 for d in distance_from_root(-1, 0, 0))  
    return ' '.join(map(str, ans))

print(d_even_relation_dfs())

Solution (Python):
def d_even_relation_bfs():
    from collections import deque
    N = int(input())
    Edges = [[int(i) for i in input().split()] for j in range(N - 1)]

    graph = [[] for _ in range(N)]
    for u, v, w in Edges:  
        graph[u - 1].append((v - 1, w))
        graph[v - 1].append((u - 1, w))
    distance_from_root = [0] * N  

    queue = deque([(-1, 0, 0)])  
    while queue:
        parent, current, distance = queue.pop()
        distance_from_root[current] = distance
        for next_vertex, dist in graph[current]:
            if parent != next_vertex:  
                queue.appendleft((current, next_vertex, distance + dist))
    ans = (1 if d % 2 == 0 else 0 for d in distance_from_root)
    return ' '.join(map(str, ans))

print(d_even_relation_bfs())