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())
Graph = [[] for i 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))

used = [0]*N
Q = deque([0])
used[0] = 1
ans = [0]*N
while Q:
  i = Q.popleft()
  j = ans[i]
  for uv, w in Graph[i]:
    if used[uv]:
      continue
    if w%2 != 0:
      ans[uv] = j^1
    else:
      ans[uv] = j
    Q.append(uv)
    used[uv] = 1

print(*ans)

Solution (Python):
n = int(input())
node = {i:[] for i in range(1, n+1)}
ans = {i:0 for i in range(1, n+1)}

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

stack = [1]
memory = set()

while stack:
  x = stack.pop()
  memory.add(x)
  
  for node_i, len_i in node[x]:
    if node_i not in memory:
      if len_i%2==0:
        ans[node_i] = ans[x]
      else:
        ans[node_i] = 1-ans[x]
      stack.append(node_i)  
    
for v in ans.values():
  print(v)

Solution (Python):

import sys

def solve(N: int, u: "List[int]", v: "List[int]", w: "List[int]"):

    G=[dict() for i in range(N)]
    for i in range(N-1):
        ui,vi,wi=u[i],v[i],w[i]
        G[ui-1][vi-1]=wi
        G[vi-1][ui-1]=wi

    dist = [-1]*N
    p = [0]
    dist[0] = 0

    while (len(p)>0):
        k = p.pop()
        for n in G[k]:
            if dist[n]==-1:
                dist[n] = dist[k] + G[k][n]
                p.append(n)
    
    for x in dist:
        print(x%2)

    return



def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  
    u = [int()] * (N - 1)  
    v = [int()] * (N - 1)  
    w = [int()] * (N - 1)  
    for i in range(N - 1):
        u[i] = int(next(tokens))
        v[i] = int(next(tokens))
        w[i] = int(next(tokens))
    solve(N, u, v, w)

if __name__ == '__main__':
    main()

Solution (Python):
from collections import deque

N = int(input())
lines = [[] for _ in range(N+1)]
for _ in range(N-1):
    u, v, w = map(int, input().split())
    lines[u].append([v, w%2])
    lines[v].append([u, w%2])
q = deque([1])
color = [0]*(N+1)
d = [0]*(N+1)
parent = [0]*(N+1)
while q:
    x = q.popleft()
    dis = d[x]
    for y, w in lines[x]:
        if y == parent[x]:
            continue
        if (dis+w)%2 == 1:
            color[y] = 1
        parent[y] = x
        d[y] = (dis+w)%2
        q.append(y)
for i in range(1, N+1):
    print (color[i])

Solution (Python):

import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N = ir()
graph = [[] for _ in range(N+1)] 
for _ in range(N-1):
    a, b, w = lr()
    graph[a].append((b, w&1))
    graph[b].append((a, w&1))

color = [None] * (N+1)
color[1] = 0
root = 1
parent = [0] * (N+1)
stack = [(root, 0)]
while stack:
    cur, c = stack.pop()
    for next, weight in graph[cur]:
        if next == parent[cur]:
            continue
        parent[next] = cur
        color[next] = c^weight
        stack.append((next, color[next]))

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

Solution (Python):
from collections import deque, defaultdict

def main():
    n = int(input())
    UVW = [[int(e) for e in input().split()] for i in range(n - 1)]

    D = defaultdict(list)
    for uvw in UVW:
        u, v, w = uvw
        D[u].append([v, w])
        D[v].append([u, w])

    A = [''] * (n + 1)
    A[UVW[0][0]] = '0'

    Q = deque()
    Q.append(UVW[0][0])

    while True:
        if len(Q) == 0:
            break

        qe = Q.pop()
        for de in D[qe]:
            if A[de[0]] == '':
                Q.append(de[0])

            if de[1] % 2 == 0:
                A[de[0]] = A[qe]
            else:
                if A[qe] == '0':
                    A[de[0]] = '1'
                else:
                    A[de[0]] = '0'

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

if __name__ == "__main__":
    main()

Solution (Python):
from collections import deque
n = int(input())
graph = [[] for _ in range(n+1)]
for _ in range(n-1):
    u,v,w = map(int,input().split())
    graph[u].append((v,w))
    graph[v].append((u,w))
q = deque([1])
ans = [0] * (n+1)
parent = [0]*(n+1)
while q:
    x = q.popleft()
    for y,w in graph[x]:
        if y == parent[x]:
            continue
        parent[y] = x
        ans[y] = ans[x]^(w&1)
        q.append(y)
for i in range(1,n+1):
    print(ans[i])

Solution (Python):
from collections import deque, defaultdict

def search(g, v):
  visited = [False] * len(g)
  visited[v] = True
  ans = [False] * len(g) 
  
  q = deque([v])
  ans[v] = False
  while q:
    s = q.popleft()
    for t,w in g[s]:
      if not visited[t]:
        q.append(t)
        ans[t] = ans[s]^(True if w%2==1 else False)
        visited[t] = True
  return ans

N = int(input())
g = {i:[] for i 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))
print("\n".join(["1" if i else "0" for i in search(g,0)]))

Solution (Python):

import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N = ir()
graph = [[] for _ in range(N+1)] 
for _ in range(N-1):
    a, b, w = lr()
    graph[a].append((b, w%2))
    graph[b].append((a, w%2))

color = [None] * (N+1)
color[1] = 0
root = 1
parent = [0] * (N+1)
stack = [(root, 0)]
while stack:
    cur, c = stack.pop()
    for next, weight in graph[cur]:
        if next == parent[cur]:
            continue
        parent[next] = cur
        if weight == 0:
            color[next] = c
        else:
            color[next] = 1 - c
        stack.append((next, color[next]))

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

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

import heapq


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


n = int(readline())
edge = [[] for i in range(n)]
for i in range(n - 1):
    u, v, w = map(int, readline().split())
    if i == 0:
        s = [u, v]
    edge[u - 1].append([w, v - 1])
    edge[v - 1].append([w, u - 1])
d = dijkstra_heap(0)
for k in d:
    if k % 2 == 0:
        print('0')
    else:
        print('1')

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


N = int(input())

tree = []
for i in range(N):
    tree.append([])


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


    
color = []
for i in range(N):
    color.append(0)
    color[0] = 1


distance = 0

def poyo(x):
    global tree
    global color
    for i in tree[x]:
        if color[i[0]] == 0:
            if i[1] == 0:
                color[i[0]] = color[x]
            else:
                color[i[0]] = color[x] * (-1)
            
            poyo(i[0])


poyo(0)

for i in color:
    if i == -1:
        i = 0
        
    print(i)

Solution (Python):
from collections import deque
N=int(input())
tree=[[] for _ 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])

dist=[-1]*N
v=0
d=deque()
d.append(v)
dist[0]=0
determined=[0]
while len(determined)<N:
    v=d.popleft()
    for i in tree[v]:
        if dist[i[0]]==-1:
            
            dist[i[0]]=dist[v]+i[1]
            d.append(i[0])
            determined.append(i[0])
    
    
for i in range(N):
    print(dist[i]%2)

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


def BFS():
    color=["white" for _ in range(n)]
    D=[0]*n
    M=[[] for _ in range(n)]

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

    D[0]=1
    color[0]="gray"
    queue=deque([0])

    while len(queue)>0:
        u=queue.popleft()
        for i,j in M[u]:
            if color[i]=="white":
                if j%2==0:D[i]=D[u]
                elif j%2==1:D[i]=-D[u]
                color[i]="gray"
                queue.append(i)
        color[u]="black"

    return D


n=int(input())
UVW=[list(map(int,input().split())) for _ in range(n-1)]
for i in BFS():
    if i==-1:print(0)
    else:print(i)

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


def BFS():
    color=["white" for _ in range(n)]
    D=[0]*n
    M=[[] for _ in range(n)]

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

    D[0]=1
    color[0]="gray"
    queue=deque([0])

    while len(queue)>0:
        u=queue.popleft()
        for i,j in M[u]:
            if color[i]=="white":
                if j%2==0:D[i]=D[u]
                elif j%2==1:D[i]=-D[u]
                color[i]="gray"
                queue.append(i)
        color[u]="black"

    return D


n=int(input())
UVW=[list(map(int,input().split())) for _ in range(n-1)]
for i in BFS():
    if i==-1:print(0)
    else:print(i)

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

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

    if v in my_dict:
        my_dict[v].append((u, w))
    else:
        my_dict[v] = [(u, w)]

visited = set()
white = set()
black = set()
candidate = [1]

white.add(1)

while candidate:
    item = candidate.pop()

    for val in my_dict[item]:
        if val[0] not in visited:
            if item in white:
                if val[1] % 2 == 0:
                    white.add(val[0])
                else:
                    black.add(val[0])
            else:
                if val[1] % 2 == 0:
                    black.add(val[0])
                else:
                    white.add(val[0])
        if val[0] not in visited:
            candidate.append(val[0])

    visited.add(item)

for i in range(n):
    if (i + 1) in white:
        print(0)
    else:
        print(1)

Solution (Python):
from collections import deque


def BFS():
    color=["white" for _ in range(n)]
    D=[0]*n
    M=[[] for _ in range(n)]

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

    D[0]=1
    color[0]="gray"
    queue=deque([0])

    while len(queue)>0:
        u=queue.popleft()
        for i,j in M[u]:
            if color[i]=="white":
                if j%2==0:D[i]=D[u]
                elif j%2==1:D[i]=-D[u]
                color[i]="gray"
                queue.append(i)
        color[u]="black"

    return D


n=int(input())
UVW=[list(map(int,input().split())) for _ in range(n-1)]
for i in BFS():
    if i==-1:print(0)
    else:print(i)

Solution (Python):
import heapq
import sys

N = int(input())
a = [[] for i in range(N)]
for i in range(N - 1):
	u, v, w = map(int, input().split())
	a[u - 1].append([v - 1, w])
	a[v - 1].append([u - 1, w])
b = [[0, 0]]
c = [False] * N
d = [sys.maxsize] * N
d[0] = 0
while len(b):
	e = heapq.heappop(b)
	c[e[1]] = True
	for i in a[e[1]]:
		if c[i[0]]:
			continue
		if d[e[1]] + i[1] < d[i[0]]:
			d[i[0]] = d[e[1]] + i[1]
			heapq.heappush(b, [d[i[0]], i[0]])
for i in d:
	print(i % 2)

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

N = int(input())
uvw = []
for _ in range(N-1):
    uvw.append(tuple(map(int, input().split())))


H=[[] for _ in range(N+1)]
for el in uvw:
    H[el[0]].append((el[1], el[2]))
    H[el[1]].append((el[0], el[2]))


seen=[False]*(N+1)

distance=[0]*(N+1)
def dfs(n):
    seen[n]=True
    for nxt in H[n]:
        if seen[nxt[0]] == False:
            distance[nxt[0]]=distance[n]+nxt[1]
            dfs(nxt[0])

dfs(1)



for val in distance[1:]:
    if val % 2 == 0:
        print(0)
    else:
        print(1)

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

N = int(input())
uvw = []
for _ in range(N-1):
    uvw.append(tuple(map(int, input().split())))


H=[[] for _ in range(N+1)]
for el in uvw:
    H[el[0]].append((el[1], el[2]))
    H[el[1]].append((el[0], el[2]))


seen=[False]*(N+1)
color=[0]*(N+1)
def dfs(n):
    seen[n]=True
    for nxt in H[n]:
        if seen[nxt[0]] == False:
            if nxt[1] % 2 == 0:
                color[nxt[0]]=color[n]
            else:
                color[nxt[0]]=color[n] ^ 1
            dfs(nxt[0])

dfs(1)



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

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

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

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

color = [-1]*N

def dfs(s,col):
  
  for w,v in edge[s]:
    if color[v]==-1:
      color[v] = col^w
      dfs(v,color[v])
  return

color[0] = 0
dfs(0,0)
ans = color


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

Solution (Python):
class UnionFind:
    def __init__(self,n):
        super().__init__()
        self.par = [-1]*n
        self.rank = [0]*n
        self.tsize = [1]*n
    
    def root(self,x):
        if self.par[x] == -1:
            return x 
        else:
            self.par[x] = self.root(self.par[x])
            return self.par[x]

    def unite(self, x, y):
        x_r = self.root(x)
        y_r = self.root(y)
        
        if self.rank[x_r]>self.rank[y_r]:
            self.par[y_r] = x_r

        elif self.rank[x_r]<self.rank[y_r]:
            self.par[x_r] = y_r

        elif x_r != y_r:
            self.par[y_r] = x_r
            self.rank[x_r] += 1

        if x_r != y_r:
            size = self.tsize[x_r]+self.tsize[y_r]
            self.tsize[x_r] = size
            self.tsize[y_r] = size

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

    def size(self,x):
        return self.tsize[self.root(x)]

def main():

    n= int(input())
    uf = UnionFind(2*(n+1))
    
    for _ in range(n-1):
      x,y,w = tuple([int(t)for t in input().split()])
      if w%2==0:
        uf.unite(2*x,2*y)
        uf.unite(2*x+1,2*y+1)
      else:
        uf.unite(2*x+1,2*y)
        uf.unite(2*x,2*y+1)

    w = uf.root(2)

    for i in range(1,n+1):
      if w == uf.root(2*i):
        print(1)
      else:
        print(0)

if __name__ == "__main__":
    main()

Solution (Python):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(100000)

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

C = [-1] * N


def dfs(pos, color):
    C[pos] = color
    for e in G[pos]:
        if C[e[0]] != -1:
            continue
        
        if e[1] & 1:
            c = 1 - color
            dfs(e[0], c)
        
        else:
            c = color
            dfs(e[0], c)


dfs(0, 0)
for c in C:
    print(c)

Solution (Python):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(100000)

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

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


def dfs(pos, color):
    C[pos] = color
    for e in G[pos]:
        if C[e[0]] != -1:
            continue
        
        if e[1] & 1:
            c = 1 - color
            dfs(e[0], c)
        
        else:
            c = color
            dfs(e[0], c)


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

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

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

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


def dfs(pos, color):
    C[pos] = color
    for e in G[pos]:
        if C[e[0]] != -1:
            continue
        
        if e[1] & 1:
            c = 1 - color
            dfs(e[0], c)
        
        else:
            c = color
            dfs(e[0], c)


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

Solution (Python):

def Graph(ab):
    G=[[] for i in range(n)]
    
    for a,b,c in ab:
        G[a-1].append((b,c%2))
        G[b-1].append((a,c%2))
        
    return G 
from collections import deque
def dfs(G,v,p):
    q=deque()
    q.append((v,p,0))
    ans=[0]*n
    while q:
        V,P,S=q.pop()
        if S==0:
            
            
            for new_v,dis in G[V-1]:
                if new_v==P:continue
                ans[new_v-1]=(ans[V-1]+dis)%2
                q.append((new_v,V,0))
    return ans
n=int(input())
uvw=[list(map(int,input().split())) for i in range(n-1)]
G=Graph(uvw)

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

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

def dfs(s):
    stack = [(s, -1, 1)]
    while(len(stack)):
        v, p, c = stack[-1]
        stack.pop()
        color[v] = c
        for e in graph[v]:
            if e[0] == p: continue
            stack.append((e[0], v, abs(c - e[1] % 2)))


n = int(input())
color = [-1] * n
graph = [[] for _ in range(n)]

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

dfs(0)
for c in color: print(c)

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

def dfs(s):
    stack = [(s, -1, 1)]
    while(len(stack)):
        v, p, c = stack[-1]
        stack.pop()
        color[v] = c
        for e in graph[v]:
            if e[0] == p: continue
            stack.append((e[0], v, abs(c - e[1] % 2)))


n = int(input())
color = [-1] * n
graph = [[] for _ in range(n)]

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

dfs(0)
for c in color: print(c)

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

def dfs(v, p, c):
    color[v] = c
    for e in graph[v]:
        if e[0] == p: continue
        if e[1] % 2: dfs(e[0], v, 1-c)
        else: dfs(e[0], v, c)


n = int(input())
color = [-1] * n
graph = [[] for _ in range(n)]

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

dfs(0, -1, 1)
for c in color: print(c)

Solution (Python):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(100000)

def dfs(v, p, c):
    color[v] = c
    for e in graph[v]:
        if e[0] == p: continue
        if e[1] % 2: dfs(e[0], v, 1-c)
        else: dfs(e[0], v, c)


n = int(input())
color = [-1 for _ in range(n)]
graph = [[] for _ in range(n)]

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

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

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 5)

def dfs(v, p, c):
    color[v] = c
    for e in graph[v]:
        if e[0] == p: continue
        if e[1] % 2: dfs(e[0], v, 1-c)
        else: dfs(e[0], v, c)


n = int(input())
color = [-1 for _ in range(n)]
graph = [[] for _ in range(n)]

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

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

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

color = []
graph = []

def dfs(v, p, c):
    color[v] = c
    for e in graph[v]:
        if e[0] == p: continue
        if e[1] % 2: dfs(e[0], v, 1-c)
        else: dfs(e[0], v, c)


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

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

if __name__ == '__main__':
    main()

Solution (Python):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(100000)

def dfs(v, p, c):
    color[v] = c
    for e in graph[v]:
        if e[0] == p: continue
        if e[1] % 2: dfs(e[0], v, 1-c)
        else: dfs(e[0], v, c)


n = int(input())
color = [-1 for _ in range(n)]
graph = [[] for _ in range(n)]

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

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

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

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

color = [-1]*N
color[0] = 0
stack = [0]

while stack:
    u = stack.pop()
    for v,w in A[u]:
        if color[v] != -1:
            continue
        color[v] = color[u]^(w&1)
        stack.append(v)

for c in color:
    print(c)

Solution (Python):
N=int(input())
import sys
sys.setrecursionlimit(10**6)

colors=[0]*(N)
L=[[] for _ in range(N)]
for i in range(N-1):
  
  u,v,w=map(int, input().split())
  L[u-1].append((v-1,w,i))
  L[v-1].append((u-1,w,i))
  
def dfs(start_node, pre_node,is_even, ):
  for next_node,l,i in L[start_node]:
    if next_node==pre_node:
      continue
    if is_even:
      if l%2==0:
        colors[next_node]=0
        is_even_next=True
      else:
        colors[next_node]=1
        is_even_next=False
    else:
      if l%2==0:
        colors[next_node]=1
        is_even_next=False
      else:
        colors[next_node]=0
        is_even_next=True
    dfs(next_node, start_node, is_even_next)
    
dfs(0,-1,True)
for color in colors:
  print(color)

Solution (Python):
import math,itertools,fractions,heapq,collections,bisect,sys,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

visited=[False]*(10**5)
ans=[-1]*(10**5)

def f(n,edges,s):
  all_visited=True
  for i in range(n):
    if visited[i]==False:
      all_visited=False
      break
  if all_visited:
    return

  for x,c in edges[s]:
    if visited[x]:
      continue
    if ans[s]==0:
      if c%2==1:
        ans[x]=1
      else:
        ans[x]=0
    else:
      if c%2==1:
        ans[x]=0
      else:
        ans[x]=1
    visited[x]=True
    f(n,edges,x)

def main():
  n=I()

  edges=[[] for _ in range(n)]
  for _ in range(n-1):
    a,b,c=LI()
    a-=1
    b-=1
    edges[a].append([b,c])
    edges[b].append([a,c])

  ans[0]=0
  visited[0]=True

  f(n,edges,0)

  for x in ans[:n]:
    print(x)

main()

Solution (Python):
import sys
from collections import deque

rl = sys.stdin.readline


def solve():
    N = int(rl())
    graph = [[] for _ in range(N)]
    for _ in range(N - 1):
        u, v, w = map(int, rl().split())
        u -= 1
        v -= 1
        graph[u].append([v, w])
        graph[v].append([u, w])
    
    ans = [-1] * N
    stack = deque([[0, 0]])
    while stack:
        node, dist = stack.pop()
        for child, weight in graph[node]:
            if ans[child] != -1:
                continue
            nd = dist + weight
            if nd % 2 == 0:
                ans[child] = 0
            else:
                ans[child] = 1
            stack.append([child, nd])
    
    print('\n'.join(map(str, ans)))


if __name__ == '__main__':
    solve()

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

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

A=[0]*n
def dfs(s,p=-1):
    for g in G[s]:
        if g[0]!=p:
            A[g[0]]=A[s]+g[1]
            dfs(g[0],s)

dfs(0)
for a in A:
    if a%2==0:
        print(0)
    else:
        print(1)

Solution (Python):
from collections import deque


def main():

    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][v] = w
        G[v][u] = w

    dist = [-1] * N
    q = deque([0])
    dist[0] = 0

    while q:
        v = q.popleft()
        for n in G[v].keys():
            if dist[n] == -1:
                q.appendleft(n)
                dist[n] = dist[v] + G[v][n]

    print("\n".join([str(x % 2) for x in dist]))


if __name__ == '__main__':
    main()

Solution (Python):
import sys

N=int(input())
d=[-1 for _ in range(N)] 
d[0]=0 
tree=[[] for _ in range(N)] 

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

def dfs(u,D): 
    sys.setrecursionlimit(10**6) 
    for v,w in tree[u]: 
        if d[v]==-1: 
            d[v]=(D+w) 
            dfs(v,D+w) 
            

dfs(0,0) 
for i in d:
    print(i%2)

Solution (Python):
import sys

def dfs(u,D):
    sys.setrecursionlimit(10**6)
    for v,w in tree[u]:
        if d[v]==-1:
            d[v]=(D+w)%2
            dfs(v,D+w)

N=int(input())
d=[-1 for _ in range(N)]
d[0]=0
tree=[[] for _ in range(N)]

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

dfs(0,0)
for i in d:
    print(i%2)

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

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

dist = [-1]*(N+1)
dist[1] = 0
q = [1]
while q:
    p = q.pop()
    for n, w in link[p]:
        if dist[n] == -1:
            dist[n] = dist[p] + w
            q.append(n)

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

Solution (Python):
import sys 
sys.setrecursionlimit(100000000)
n = int(input())
graph = [[] for _ in range(n)]
color = [-1]*n
dist = [-1]*n
dist[0] = 0
visited = [0]*n
for _ in range(n-1):
  u, v, w = map(int, input().split())
  u -= 1
  v -= 1 
  graph[u] += [[v, w]]
  graph[v] += [[u, w]]
  
def dfs(u, d):
  for v, w in graph[u]:
    if dist[v] == -1:
      dist[v] = (w + d) % 2
      dfs(v, d+w)
      
dfs(0, 0)
for i in dist:
  print(i)

Solution (Python):
import sys 
sys.setrecursionlimit(100000000)
n = int(input())
graph = [[] for _ in range(n)]
color = [-1]*n
visited = [0]*n
for _ in range(n-1):
  u, v, w = map(int, input().split())
  u -= 1
  v -= 1 
  graph[u] += [[v, w]]
  graph[v] += [[u, w]]
def dfs(u, c):
  color[u] = c 
  for v, w in graph[u]:
    if color[v] != -1:
      continue
    if color[v] == -1 and w % 2 == 0:
      dfs(v, c)
    if color[v] == -1 and w % 2 != 0:
      dfs(v, abs(1-c))
  return 

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

Solution (Python):


import sys

def main():
    sys.setrecursionlimit(10 ** 6)
    n = int(input())
    adjs = [[] for i in range(n)]
    for i in range(n - 1):
        u, v, w = map(int, input().split())
        adjs[u - 1].append((v - 1, w))
        adjs[v - 1].append((u - 1, w))
    colors = [None for i in range(n)]
    colors[0] = 0
    dfs(0, adjs, -1, colors)
    for i in range(n):
        print(colors[i])

def dfs(i, adjs, p, colors):
    for v, w in adjs[i]:
        if v == p:
            continue
        colors[v] = (colors[i] + w) % 2
        dfs(v, adjs, i, colors)

if __name__ == "__main__":
    main()

Solution (Python):


import sys

def main():
    sys.setrecursionlimit(10 ** 6)
    n = int(input())
    adjs = [[] for i in range(n)]
    for i in range(n - 1):
        u, v, w = map(int, input().split())
        adjs[u - 1].append((v - 1, w))
        adjs[v - 1].append((u - 1, w))
    colors = [None for i in range(n)]
    visited = [False for i in range(n)]
    dfs(0, 0, adjs, visited, colors)
    for i in range(n):
        print(colors[i])

def dfs(i, color, adjs, visited, colors):
    visited[i] = True
    colors[i] = color
    for v, w in adjs[i]:
        if visited[v]:
            continue
        dfs(v, (color + w) % 2, adjs, visited, colors)

if __name__ == "__main__":
    main()

Solution (Python):
from collections import deque

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

queue = deque([0])
while queue:
    now = queue.popleft()
    for u, w in g[now]:
        if ans[u] != -1:
            continue
        ans[u] = ans[now] + w
        queue.append(u)
for a in ans:
    if a % 2 == 0:
        print(1)
    else:
        print(0)

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

N = int(input())

def dfs(v, u, w):
    if w % 2 == 0:
        iro[v] = 0
    else:
        iro[v] = 1
    for i in ki[v]:
        if i[1] == u: continue
        dfs(i[1], v, w + i[0])
    return

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

iro = [0] * N
dfs(0, 0, 0)
for i in iro:
    print(i)

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

for _ in range(N - 1):
    fr, to, d = map(int, input().split())
    fr -= 1
    to -= 1
    edges[fr].append((to, d))
    edges[to].append((fr, d))

minDist = [10**18] * N
st = [(0, 0)]
while st:
    now, dist = st.pop()

    if minDist[now] < dist:
        continue
    minDist[now] = dist

    for to, d in edges[now]:
        if minDist[to] > dist + d:
            st.append((to, dist + d))

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

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

color = [-1 for _ in range(N)]
stack = [u]
color[u] = 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] = (color[u] + 1) % 2

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