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):
import sys
sys.setrecursionlimit(100002)
n=int(input())
point=[]
answer=[]
already=[]
for i in range(n):
    point.append([])
    answer.append(0)
    already.append(0)
for i in range(n-1):
    u,v,w=map(int,input().split())
    point[u-1].append((v-1,w))
    point[v-1].append((u-1,w))
def dfs(now,c):
    answer[now]=c
    already[now]=1
    for i in point[now]:
        if already[i[0]]==1:
            pass
        else:
            if i[1]%2==0:
                dfs(i[0],c)
            else:
                if c==0:
                    dfs(i[0],1)
                else:
                    dfs(i[0],0)
dfs(0,0)
for i in answer:
    print(i)

Solution (Python):
N=int(input())
M=N-1
graph=[[]  for i in range(N+1)]
weight={}
for _ in range(M):
    a,b,c=list(map(int,input().strip().split(' ')))
    graph[a]+=[b]
    graph[b]+=[a]
    weight[(a,b)]=c
    weight[(b,a)]=c
checked={}
paint=[0]*(N+1)
def dfs(root):
    connected=[]
    stack=[]
    stack+=[root]
    parent={}
    parent[root]=-1
    checked[root]=1
    while stack:
        v=stack.pop()
        for node in graph[v]:
            if node!=parent[v] and node not in checked:
                if weight[(node,v)]%2==0:
                    paint[node]=paint[v]
                else:
                    paint[node]=paint[v]^1    
                checked[node]=1
                parent[node]=v
                stack+=[node]
    return stack
dfs(1)
for i in range(1,len(paint)):
    print(paint[i])

Solution (Python):





from collections import defaultdict 

N = int(input())
K = []
bridge = defaultdict(list)
for n in range(N-1):
    k = [ int(x) for x in input().split() ]
    K.append(k)
    bridge[k[0]].append([k[1], k[2]])
    bridge[k[1]].append([k[0], k[2]])

color = [ None for i in range(N + 1)]

queue = []
queue.append(1)
color[1] = 1


while queue:
    point = queue.pop()
    for b in bridge[point]:
        if not color[b[0]]:
            queue.append(b[0])
            if b[1] % 2 == 0:
                color[b[0]] = color[point]
            else:
                color[b[0]] = color[point] * -1

ans = []
for c in color[1:]:
    if c == 1:
        ans.append("1")
    else:
        ans.append("0")
print("\n".join(ans))

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

nVertices = int(input())
edges = [[] for _ in range(nVertices + 1)]
length = {}
for _ in range(nVertices - 1):
    u, v, l = map(int, input().split())
    edges[u].append(v)
    edges[v].append(u)
    if u > v:
        u, v = v, u
    length[(u, v)] = l
color = [None] * (nVertices + 1)
color[1] = 0

def dfs(par, v):
    for child in edges[v]:
        if child != par:
            key = (min(v, child), max(v, child))
            if length[key] & 1 == 0:
                color[child] = color[v]
            else:
                color[child] = color[v] ^ 1
            dfs(v, child)

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

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

n = int(input())
nodes = [[] for _ in range(n)]
visited = [False for _ in range(n)]
dist = [0 for _ in range(n)]

def dfs(i, d):
  dist[i] = d
  for cn, c in nodes[i]:
    if not visited[cn]:
      visited[cn] = True
      dfs(cn, d+c)

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

visited[0] = True
dfs(0, 0)

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

Solution (Python):
from collections import defaultdict

N = int(input())

colors = [0] * (N+1)
vertices = defaultdict(bool)
edges = defaultdict(dict)
for i in range(1, N):
    u, v, w = map(int, input().split())
    edges[u][v] = w % 2 == 0
    edges[v][u] = w % 2 == 0
    vertices[u] = False
    vertices[v] = False

queue = []
for v in edges[u].keys():
    queue.append((u, v))
vertices[u] = True

while len(queue) > 0:
    u, v = queue.pop(0)
    if vertices[v]:
        continue
    vertices[v] = True
    if colors[u] == colors[v]:
        if not edges[u][v]:
            colors[v] = 1 - colors[u]
    else:
        if edges[u][v]:
            colors[v] = colors[u]

    for nv in edges[v].keys():
        if not vertices[nv]:
            queue.append((v, nv))

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

Solution (Python):
import queue

N = int(input())

u, v, w = [0 for _ in range(N-1)], [0 for _ in range(N-1)], [0 for _ in range(N-1)]

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

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

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

q = queue.Queue()
q.put((0, 0))
c = 0

while(not q.empty()):
    a = q.get()
    col[a[0]] = a[1]

    for e in adli[a[0]]:
        if col[e[0]] == -1:
            q.put((e[0], (a[1]+e[1])%2))

for ans in col:
    print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(10**5+1)
n = int(input())
if n==1:
  print(0)
  exit()
from collections import defaultdict
edge = defaultdict(list)
for i in range(n-1):
  u, v, w = list(map(int, input().split()))
  edge[u].append((v, w))
  edge[v].append((u, w))
graph = [-1 for i in range(n+1)]

def dfs(x, c):
  nexts = edge.get(x)
  if nexts is None:
    return
  if graph[x]!=-1:
    return
  else:
    graph[x] = c
  for y, w in nexts:
    if w%2:
      dfs(y, not c)
    else:
      dfs(y, c)

dfs(1, 0)
for i in range(1, n+1):
  print(int(graph[i]))

Solution (Python):
from collections import defaultdict

N = int(input())

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

colorDict = defaultdict(int)
stack = [1]
colorDict[1] = 1
while(stack):
    key = stack.pop() 
    for ew in dd[key]:
        e, w = ew
        if colorDict[e] == 0:
            if colorDict[key] == 1:
                colorDict[e] = 1 if w % 2 == 0 else 2
            else:
                colorDict[e] = 2 if w % 2 == 0 else 1
            stack.append(e)

for k, v in sorted(colorDict.items()):
    print(str(v - 1))

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

N=int(input())
edges = [[] for i in range(N)]
colors = [-1]*N
for i in range(N-1):
    u,v,w=[int(a) for a in input().split()]
    edges[u-1].append((v-1,w))
    edges[v-1].append((u-1,w))
 
diff = lambda n: 1 if n==0 else 0
 
def dfs(prev,curr):
    for node,d in edges[curr]:
        if node==prev:
            continue
        colors[node] = colors[curr] if d%2==0 else diff(colors[curr])
        dfs(curr,node)
 
colors[0]=0
dfs(1000000,0)
for i in range(N):
    print(colors[i])

Solution (Python):
import queue
q=queue.Queue()
N=int(input())
searched=set()
info=list()
edges={}
dict={}

for i in range(N):
    edges[i]=[]

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

dict[0]=0

q.put(0)

while not q.empty():
    a=q.get()
    if a in searched:
        continue

    tmplist=edges[a]
    for l in tmplist:
        if l[0] not in searched:
            v,w=l
            q.put(v)
            if w%2==0:
                dict[v]=dict[a]
            else:
                dict[v]=(dict[a]+1)%2
    searched.add(a)


di=sorted(dict.items(), key=lambda x:x[0])

for d in di:
    print(d[1])

Solution (Python):
from collections import deque

N=input()

nl=[ [] for i in range(N+1) ]

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

Visit=[ None for i in range(N+1) ] 
Visit[1]=0

q=deque()
q.append(1)

while q:
	x=q.popleft()
	for to,kyori in nl[x]:
		if Visit[to] is None:
			if kyori%2==0:
				Visit[to]=Visit[x]
			else:
				Visit[to]=(Visit[x]+1)%2
			q.append(to)
			

for i in Visit[1:]:
	print i

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 5 + 1)

def dfs(i, V, E):
    for k in E[i].keys():
        if V[k] >= 0:
            continue
        if E[i][k] % 2:
            V[k] = 1 - V[i]
        else:
            V[k] = V[i]
        V = dfs(k, V, E)
    return V

n = int(input())
E = {}
for i in range(n - 1):
    ui, vi, wi = map(int, input().split())
    if ui in E.keys():
        E[ui][vi] = wi
    else:
        E[ui] = {vi: wi}
    if vi in E.keys():
        E[vi][ui] = wi
    else:
        E[vi] = {ui: wi}
V = [-1 for _ in range(n + 1)]
V[1] = 0
V = dfs(1, V, E)
for vi in V[1:]:
    print(vi)

Solution (Python):
import heapq

N = int(input())
graph = {i:[] for i in range(1, N+1)}
route = [10**20 for i in range(N+1)]
visited = [False for i in range(N+1)]

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

for key, value in graph.items():
    if len(value):
        start = key
        route[start] = 0
        visited[start] = True
        q = []
        for v, w in value:
            route[v] = min(route[v], w)
            heapq.heappush(q, (w, v))
        break

while len(q):
    w, v = heapq.heappop(q)
    if not visited[v]:
        visited[v] = True
        for u, c in graph[v]:
            if route[u] > route[v] + c:
                route[u] = route[v] + c
                heapq.heappush(q, (c, u))

for n in route[1:]:
    if n % 2:
        print('1')
    else:
        print('0')

Solution (Python):
def BFS(K,edges,N):
  roots=[ [] for i in range(N)]
  for a,b,c in edges:
    roots[a-1]+=[(b-1,c)]
    roots[b-1]+=[(a-1,c)]
  dist=[-1]*N
  stack=[]
  stack.append(K)
  dist[K]=0
  while stack:
    label=stack.pop(-1)
    for i,c in roots[label]:
      if dist[i]==-1:
        dist[i]=dist[label]+c
        stack+=[i]
  return [i%2 for i in dist]
N = int(input())
edges = []
for n in range(N-1):
    a,b,c = map(int, input().split())
    edges.append([a,b,c])
ans = BFS(0,edges,N)
for a in ans:
    print (a)

Solution (Python):
if __name__ == '__main__':
    import sys
    input = sys.stdin.readline

    n = int(input())

    parent = {x:[] for x in range(1,n+1)}

    ans = [None]*n

    ans[0] = 1

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

    base = [1]


    while True:
        pop_num = base.pop()
        for i in parent[pop_num]:
            abs_i = abs(i)
            ans[abs_i-1] = ans[pop_num-1]*(i/abs_i)
            parent[abs_i].remove(pop_num*(i/abs_i))
            base.append(abs_i)
        if len(base) == 0:
            break

    for i in ans:
        if i == 1:
            print('1')
        else:
            print('0')

Solution (Python):
import sys
sys.setrecursionlimit(10000000)
n=int(input())
s=[[]for i in range(n+1)]
g=[0]*(n+1)
h=[True]*(n+1)
for i in range(n-1):
    a,b,c=map(int,input().split())
    s[a].append([b,c])
    s[b].append([a,c])
def dfs(x):
    h[x]=False
    for i in s[x]:
        if h[i[0]]:
            g[i[0]]=g[x]+i[1]
            dfs(i[0])
dfs(1)
for i in range(1,n+1):
    if g[i]%2==0:
        print(0)
    else:
        print(1)

Solution (Python):
from collections import defaultdict, deque

def main():
    n = int(input())
    edges = defaultdict(list)

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

def solve(edges, n):
    vertexes = [None for _ in range(n)]
    vertexes[0] = 0

    q = deque()
    q.append(0)

    while q:
        u = q.popleft()

        for v, w in edges[u]:
            if vertexes[v] is not None:
                continue
            if w % 2 == 0:
                vertexes[v] = vertexes[u]
            else:
                vertexes[v] = 1 - vertexes[u]
            q.append(v)
    
    return vertexes
    
main()

Solution (Python):
from collections import defaultdict, deque
n = int(input())
data = [list(map(int, input().split())) for _ in range(n-1)]
tree = defaultdict(list)
for u, v, w in data:
    if w % 2 == 0:
        tree[u].append((v, "ok"))
        tree[v].append((u, "ok"))
    else:
        tree[u].append((v, "ng"))
        tree[v].append((u, "ng"))

queue = deque()
queue.append(1)
visited = set()
ans = [None for _ in range(n)]
ans[0] = 1
while len(queue):
    now = queue.popleft()
    opps = tree[now]
    
    for opp in opps:
        if opp[0] not in visited:
            queue.append(opp[0])
            
            if opp[1] == "ok":
                ans[opp[0]-1] = ans[now-1]
            else:
                ans[opp[0]-1] = -ans[now-1]
        visited.add(opp[0])
for value in ans:
    if value == 1:
        print(1)
    else:
        print(0)

Solution (Python):
N = int(input())
import sys
graph = [dict() for _ in range(N)]

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

color = [-1] * N

import sys
sys.setrecursionlimit(10 ** 9)

def dfs(i, col):
    color[i] = col
    for k, v in graph[i].items():
        if color[k] == -1:
            if v % 2 == 0:
                dfs(k, col)
            else:
                dfs(k, 1-col)

dfs(0, 1)




for c in color:
    print(c)

Solution (Python):
import queue
from queue import Queue

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




c = [-1]*(n+1)
c[1] = 0

q = Queue()
q.put(1)

while not q.empty():
  x = q.get()
  for y in g[x]:
    if c[y] == -1:
      q.put(y)
      c[y] = c[x]
  for y in k[x]:
    if c[y] == -1:
      q.put(y)
      c[y] = (c[x]+1)%2
    
for i in range(1,n+1):
  print(c[i])

Solution (Python):
n=int(input())
s=[None for i in range(n)]
l=[[] for i in range(n)]
for i in range(n-1):
  x,y,w=map(int,input().split())
  x-=1
  y-=1
  l[x]+=[[y,w%2]]
  l[y]+=[[x,w%2]]

s[0]=0
p=[0]
while p:
  q=p.pop()
  for t,w in l[q]:
    if s[t] == None:
      if w==1:
        s[t]=(s[q]+1)%2
      else:
        s[t]=s[q]
      p+=[t]
for i in s:
  print(i)

Solution (Python):
import collections
N = int(input())
UVW = [[int(_) for _ in input().split()] for _ in range(N - 1)]
cd = collections.defaultdict
G = cd(lambda: cd(int))
for u, v, w in UVW:
    G[u][v] = G[v][u] = w
ans = [-1] * (N + 1)
ans[1] = 0
stack = [1]
while stack:
    f = stack.pop()
    for t in G[f].keys():
        if ans[t] == -1:
            stack += [t]
            if G[f][t] % 2:
                ans[t] = 1 - ans[f]
            else:
                ans[t] = ans[f]
print(*ans[1:], sep='\n')

Solution (Python):
from collections import defaultdict

N = int(input())

D = defaultdict(list) 
S = {} 
for i in range(1,N+1):S[i] = -1
R = defaultdict(int) 
for i in range(N-1):
    u,v,w = map(int,input().split())
    D[u].append(v)
    D[v].append(u)
    R["{}-{}".format(u,v)] = w
    R["{}-{}".format(v,u)] = w
    
T = [(1,0)]
S[1] = 0
while T:
    n,w = T.pop()
    for d in D[n]:
        wr = R["{}-{}".format(n,d)]
        if S[d]>=0:continue
        else: S[d] = (w+wr)%2
        T.append((d,(w+wr)%2))
        
for k in range(1,N+1):
    print(S[k] if S[k]>=0 else 0)

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

N=int(input())
edges = [[] for i in range(N)]
colors = [-1]*N
for i in range(N-1):
    u,v,w=[int(a) for a in input().split()]
    edges[u-1].append((v-1,w))
    edges[v-1].append((u-1,w))
 
diff = lambda n: 1 if n==0 else 0
 
def dfs(prev,curr):
    for node,d in edges[curr]:
        if node==prev:
            continue
        colors[node] = colors[curr] if d%2==0 else diff(colors[curr])
        dfs(curr,node)
 
colors[0]=0
dfs(1000000,0)
for i in range(N):
    print(colors[i])

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

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

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

import sys
sys.setrecursionlimit(10000000)
def f(i, color):
    for t, w in data[i]:
        if ans[t] is not None:
            continue
        ans[t] = color^w
        f(t, color^w)

f(0, 0)

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

Solution (Python):


def readInts():
  return [int(s) for s in input().split(" ")]

def main():
  N = readInts()[0]
  links = {}
  for i in range(N-1):
    u, v, w = readInts()
    if not u in links:
      links[u] = {}
    if not v in links:
      links[v] = {}
    links[u][v] = w
    links[v][u] = w

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

  nodes = [(1, False)]
  while len(nodes) > 0:
    v, color = nodes.pop()
    colors[v - 1] = '1' if color else '0'

    for u, w in links[v].items():
      if colors[u - 1]: continue
      if w % 2 == 0:
        nodes.append((u, color))
      else:
        nodes.append((u, not(color)))
  for n in range(N):
    print(colors[n])

if __name__ == "__main__":
  main()

Solution (Python):
from collections import deque
N = int(input())
X = [list(map(int, input().split())) for _ in range(N - 1)]
class UnionFind:
    def __init__(self, n=1):
        self.par = [i for i in range(n)]
    def find(self, x):
        if self.par[x] == x:
            return x
        self.par[x] = self.find(self.par[x])
        return self.par[x]
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x != y:
            self.par[y] = x
    def is_same(self, x, y):
        return self.find(x) == self.find(y)
uf = UnionFind(N)
next_ = [[] for _ in range(N)]
for u, v, w in X:
    next_[u - 1].append((v - 1, w))
    next_[v - 1].append((u - 1, w))
    uf.union(u - 1, v - 1)
now = min(set(uf.par))
result = ["" for _ in range(N)]
result[now] = "0"
ver = deque([now])
while len(ver) > 0:
    now = ver.pop()
    color = result[now]
    for n, w in next_[now]:
        if result[n] != "":
            continue
        if w % 2 == 0:
            result[n] = color
        else:
            result[n] = "1" if color == "0" else "0"
        ver.append(n)
print("\n".join(result))

Solution (Python):
from itertools import*
from math import*
from collections import*
from heapq import*
from bisect import bisect_left,bisect_right
from copy import deepcopy
inf = 10**18
mod = 10**9+7
from functools import reduce
import sys
sys.setrecursionlimit(10**7)

n = int(input())
G = defaultdict(set)
color = [0]*(n)
for i in range(n-1):
    a, b, c = map(int, input().split())
    G[a-1].add((b-1, c))
    G[b-1].add((a-1, c))
def dijkstra(v):
    d = [inf] * n
    d[v] = 0
    hq =[(0,v)]

    while hq:
        u = heappop(hq)[1]
        for (v,c) in G[u]:
            if d[v] > d[u] + c:
                d[v] = d[u] +c
                heappush(hq,(d[u]+c,v))
    return d
d = dijkstra(0)
for i in range(n):
    if d[i] % 2==0:
        color[i]=0
    else:
        color[i]=1
for i in range(n):
    print(color[i])

Solution (Python):
from collections import defaultdict, deque

def bfs(s):
    queue = deque([s])
    cv = [0] * n
    cv[s] = 1
    while queue:
        u = queue.popleft()
        for nxt, w in adj[u]:
            if not cv[nxt]:
                if w % 2 == 1:
                    color[nxt] = color[u] ^ 1
                else:
                    color[nxt] = color[u]
                queue.append(nxt)
                cv[nxt] = 1

n = int(input())
adj = defaultdict(list)
for _ in range(n - 1):
    u, v, w = [int(item) for item in input().split()]
    u -= 1
    v -= 1
    adj[u] += [(v, w)]
    adj[v] += [(u, w)]

color = [0] * n
bfs(0)

for x in color:
    print(x)

Solution (Python):
from bisect import bisect_left, bisect_right
from collections import Counter, defaultdict, deque, OrderedDict
from copy import deepcopy
from fractions import gcd
from functools import lru_cache, reduce
from math import ceil, floor
from sys import setrecursionlimit

import heapq as hq
import itertools as its
import operator as op



inf = float('inf')
N = 0


def set_inputs():
    global N
    return


def main():
    setrecursionlimit(100000)
    set_inputs()
    
    n = get_int()
    u, v, w = get_data(n - 1, [int, int, int])
    d = defaultdict(list)
    for ui, vi, wi in zip(u, v, w):
        d[ui].append((vi, wi))
        d[vi].append((ui, wi))
    color = [-1] * n
    q = deque()
    color[1-1] = 0
    q.append(1)
    while len(q) > 0:
        ui = q.popleft()
        for vi, wi in d[ui]:
            if color[vi-1] >= 0:
                continue
            color[vi-1] = (color[ui-1] + wi) % 2
            q.append(vi)
    for c in color:
        print(c)
    return


def get_int():
    return int(input())


def get_float():
    return float(input())


def get_str():
    return input().strip()


def get_li():
    return [int(i) for i in input().split()]


def get_lf():
    return [float(f) for f in input().split()]


def get_lc():
    return list(input().strip())


def get_data(n, types, sep=None):
    if len(types) == 1:
        return [types[0](input().strip()) for _ in range(n)]
    return list(zip(*(
        [t(x) for t, x in zip(types, input().strip().split(sep=sep))]
        for _ in range(n)
    )))


if __name__ == '__main__':
    main()

Solution (Python):
N = int(input())
edge = [[] for i in range(N)]
for i in range(N-1):
  u,v,w = map(int, input().split())
  edge[u-1] += [[u-1,v-1, w%2]]
  edge[v-1] += [[v-1,u-1, w%2]]
  
group = [0]+ [-1]* (N-1)
cnt = N-1
path = edge[0]
while path:
  uv = path.pop()
  if group[uv[1]] == -1:
    group[uv[1]] = (group[uv[0]] + uv[2])%2
    for e in edge[uv[1]]:
      path.append(e)

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

Solution (Python):

N = int(input())
graph = [[] for i in range(N)]

for i in range(N-1):
    u, v, w = map(int, input().split())
    u, v = u-1, v-1
    graph[u].append([v, w])
    graph[v].append([u, w])
d = [0 for i in range(N)]
visited = [False for i in range(N)]
def bfs(v):
    Q = []
    visited[v] = True
    Q.append(v)
    while len(Q) > 0:
        v = Q.pop(0)
        for u, w in graph[v]:
            if not visited[u]:
                visited[u] = True
                d[u] = d[v] + w
                Q.append(u)
bfs(0)
for i in range(N):
    if d[i] % 2 == 0:
        print('1')
    else:
        print('0')

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

color = [-1] * N
color[0] = 0
nextlist = [0]
while nextlist:
    tmp = []
    for proc in nextlist:
        for n in nlist[proc]:
            if color[n[0]] != -1:
                continue
            color[n[0]] = (color[proc] + n[1]) % 2
            tmp.append(n[0])
    nextlist = tmp

for c in color:
    print(c)

Solution (Python):


import collections


class Node(object):

  def __init__(self):
    self.edges = []
    self.color = None


def main():
  nodes = [Node() for _ in range(int(input()))]

  for _ in range(len(nodes) - 1):
    u, v, w = map(int, input().split())

    nodes[u - 1].edges.append((nodes[v - 1], w))
    nodes[v - 1].edges.append((nodes[u - 1], w))

  queue = collections.deque()

  nodes[0].color = 0
  queue.append(nodes[0])

  while len(queue) != 0:
    node = queue.pop()

    for e, w in node.edges:
      if e.color is not None:
        continue

      if w % 2 == 0:
        e.color = node.color
      else:
        e.color = 1 - node.color

      queue.append(e)

  for node in nodes:
    print(node.color)


if __name__ == '__main__':
  main()

Solution (Python):

"""
D - Even Relation
https://atcoder.jp/contests/abc126/tasks/abc126_d

"""
import sys

from heapq import heappush, heappop


def dijkstra(adj, s):
    N = len(adj)
    WHITE, GRAY, BLACK = 0, 1, 2
    color = [WHITE] * N
    d = [float('inf')] * N
    d[s] = 0
    pq = []
    heappush(pq, (0, s))
    while pq:
        cost, u = heappop(pq)
        color[u] = BLACK
        if d[u] < cost:
            continue
        for v, cost in adj[u]:
            if color[v] == BLACK:
                continue
            if d[v] > d[u] + cost:
                d[v] = d[u] + cost
                heappush(pq, (d[v], v))
                color[v] = GRAY
    return d


def solve(N, path):
    adj = [[] for _ in range(N+1)]
    for f, t, w in path:
        adj[f].append([t, w])
        adj[t].append(([f, w]))
    dist = dijkstra(adj, 1)
    ans = []
    for d in dist[1:]:
        if d%2 == 0:
            ans.append(0)
        else:
            ans.append(1)
    return ans


def main(args):
    N = int(input())
    path = [[int(i) for i in input().split()] for _ in range(N-1)]
    ans = solve(N, path)
    print(*ans, sep='\n')


if __name__ == '__main__':
    main(sys.argv[1:])

Solution (Python):


from sys import stdout
from bisect import bisect_left as binl
from copy import copy, deepcopy
from collections import defaultdict


mod = 1


def intin():
    input_tuple = input().split()
    if len(input_tuple) <= 1:
        return int(input_tuple[0])
    return tuple(map(int, input_tuple))


def intina():
    return [int(i) for i in input().split()]


def intinl(count):
    return [intin() for _ in range(count)]


def modadd(x, y):
    global mod
    return (x + y) % mod


def modmlt(x, y):
    global mod
    return (x * y) % mod


def lcm(x, y):
    while y != 0:
        z = x % y
        x = y
        y = z
    return x


def combination(x, y):
    assert(x >= y)

    if y > x // 2:
        y = x - y

    ret = 1

    for i in range(0, y):
        j = x - i
        i = i + 1

        ret = ret * j
        ret = ret // i

    return ret


def get_divisors(x):
    retlist = []
    for i in range(1, int(x**0.5) + 3):
        if x % i == 0:
            retlist.append(i)
            retlist.append(x // i)
    return retlist


def get_factors(x):
    retlist = []
    for i in range(2, int(x**0.5) + 3):
        while x % i == 0:
            retlist.append(i)
            x = x // i
    retlist.append(x)
    return retlist


def make_linklist(xylist):
    linklist = {}
    for a, b in xylist:
        linklist.setdefault(a, [])
        linklist.setdefault(b, [])
        linklist[a].append(b)
        linklist[b].append(a)
    return linklist


def calc_longest_distance(linklist, v=1):
    distance_list = {}
    distance_count = 0
    distance = 0
    vlist_previous = []
    vlist = [v]
    nodecount = len(linklist)

    while distance_count < nodecount:
        vlist_next = []
        for v in vlist:
            distance_list[v] = distance
            distance_count += 1
            vlist_next.extend(linklist[v])
        distance += 1
        vlist_to_del = vlist_previous
        vlist_previous = vlist
        vlist = list(set(vlist_next) - set(vlist_to_del))

    max_distance = -1
    max_v = None
    for v, distance in distance_list.items():
        if distance > max_distance:
            max_distance = distance
            max_v = v

    return (max_distance, max_v)


def calc_tree_diameter(linklist, v=1):
    _, u = calc_longest_distance(linklist, v)
    distance, _ = calc_longest_distance(linklist, u)
    return distance


class UnionFind:

    def __init__(self, n):
        self.parent = [i for i in range(n)]

    def root(self, i):
        if (self.parent[i] == i):
            return i
        self.parent[i] = self.root(self.parent[i])
        return self.parent[i]

    def unite(self, i, j):
        rooti = self.root(i)
        rootj = self.root(j)
        if rooti == rootj:
            return
        if i < j:
            self.parent[rootj] = rooti
        else:
            self.parent[rooti] = rootj

    def same(self, i, j):
        return self.root(i) == self.root(j)





def make_wlinklist(xyzlist):
    linklist = {}
    for a, b, c in xyzlist:
        linklist.setdefault(a, [])
        linklist.setdefault(b, [])
        linklist[a].append((b, c))
        linklist[b].append((a, c))
    return linklist


def main():
    n = intin()
    if n == 1:
        print(0)
        return
    uvwlist = intinl(n - 1)

    linklist = make_wlinklist(uvwlist)
    anslist = {1: 0}
    anscount = 1
    search = [(1, 0)]

    while anscount < n:
        search_next = []
        for u, color in search:

            

            for v, w in linklist[u]:
                if w & 1:
                    ans = 0 if color else 1
                else:
                    ans = 1 if color else 0
                if v not in anslist:
                    anslist[v] = ans
                    anscount += 1
                    search_next.append((v, ans))
        search = search_next

        


    

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


if __name__ == '__main__':
    main()

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

used = [False]*N
verts = [[[], None] for i in range(N)] 

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

q = [(0, 0)] 
verts[0][1] = 1 
used[0] = True
while q != []:
    v, c = q.pop(0)
    vert = verts[v]
    for w,d in vert[0]:
        if not used[w]:
            used[w] = True
            if (c+d) % 2 == 0:
                verts[w][1] = 1
            else:
                verts[w][1] = 0
            q.append((w, c+d))
for i in range(N):
    print(verts[i][1])

Solution (Python):
from collections import deque


def solve(N, UVWs):
    vertexes = {}

    for u, v, w in UVWs:
        vertexes.setdefault(u, []).append((v, w % 2))
        vertexes.setdefault(v, []).append((u, w % 2))

    colors = [-1 for _ in range(N + 1)]
    colors[1] = 0
    que = deque()
    que.append((1, colors[1]))
    while que:
        u, c = que.popleft()
        for v, w in vertexes[u]:
            if colors[v] == -1:
                colors[v] = (c + w) % 2
                que.append((v, colors[v]))
    return "\n".join(str(c) for c in colors[1:])


if __name__ == "__main__":
    N = int(input())
    UVWs = [tuple(map(int, input().split(" "))) for _ in range(N - 1)]
    print(solve(N, UVWs))

Solution (Python):



def BFS(K,edges,N):
  roots=[ [] for i in range(N)]
  for a,b,c in edges:
    roots[a-1]+=[(b-1,c)]
    roots[b-1]+=[(a-1,c)]
  dist=[-1]*N
  stack=[]
  stack.append(K)
  dist[K]=0
  while stack:
    label=stack.pop(-1)
    for i,c in roots[label]:
      if dist[i]==-1:
        dist[i]=dist[label]+c
        stack+=[i]
        
  return dist
        
n = int(input()) 


d = []

for i in range(n-1):
    
    
    
    
    
    d.append(list(map(int,input().split())))




dist = BFS(0,d,n)

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