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
import collections


def solve():
    input = sys.stdin.readline
    mod = 10 ** 9 + 7
    n = int(input().rstrip('\n'))
    tmd = collections.defaultdict(list)
    tmdc = collections.defaultdict(int)
    for i in range(n-1):
        tma, tmb, tmc = list(map(int, input().rstrip('\n').split()))
        tmd[tma-1] += [tmb-1]
        tmd[tmb-1] += [tma-1]
        tmdc[tma-1, tmb-1] = tmc
        tmdc[tmb-1, tma-1] = tmc

    ql = [[0, 0]]
    ql = collections.deque(ql)
    fq = collections.defaultdict(list)
    while True:
        if len(ql) != 0:
            cost, tmp = ql.popleft()
            for tmv in tmd[tmp]:
                if tmv not in fq:
                    ql.append([cost + tmdc[tmp, tmv], tmv])
                    fq[tmv] = (cost + tmdc[tmp, tmv]) % 2
        else:
            break
    for i in range(n):
        print(fq[i])


if __name__ == '__main__':
    solve()

Solution (Python):
import sys
def input():
    return sys.stdin.readline()[:-1]
n=int(input())
uvw=[list(map(int,input().split())) for i in range(n-1)]
class WeightedUnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n+1)]
        self.rank = [0] * (n+1)
        self.weight = [0] * (n+1)


    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            y = self.find(self.par[x])
            self.weight[x] += self.weight[self.par[x]]
            self.par[x] = y
            return y

    def union(self, x, y, w):
        rx = self.find(x)
        ry = self.find(y)
        if self.rank[rx] < self.rank[ry]:
            self.par[rx] = ry
            self.weight[rx] = w - self.weight[x] + self.weight[y]
        else:
            self.par[ry] = rx
            self.weight[ry] = -w - self.weight[y] + self.weight[x]
            if self.rank[rx] == self.rank[ry]:
                self.rank[rx] += 1

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def diff(self, x, y):
        return self.weight[x] - self.weight[y]
uf=WeightedUnionFind(n)
for i in range(n-1):
    uf.union(uvw[i][0],uvw[i][1],uvw[i][2])

for i in range(n):
    if uf.diff(i+1,uf.find(i+1))%2==0:
        print(0)
    else:
        print(1)

Solution (Python):
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**6)
    n = int(input())
    edge = [dict() for _ in range(n)]
    dist = [0]*n
    for _ in range(n-1):
        u, v, w = map(int, input().split())
        edge[u-1].update({v-1: w})
        edge[v-1].update({u-1: w})

    def dfs(i, pre, d):
        dist[i] = d
        for v in edge[i].keys():
            if v == pre:
                continue
            dfs(v, i, d+edge[i][v])

    dfs(0, -1, 0)
    

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


if __name__ == '__main__':
    main()

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

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

e =[[] for _ in range(n)]
color = [-1]*n
dw = {}

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

def dfs(i,c)  :
  color[i] = c
  for ei in e[i]:
    if color[ei] != -1:
      continue
    dfs(ei, c+dw[(i,ei)])

dfs(0,0)   

for c in color:
  print(c%2)

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

l=[-1]*n
s=[(1,0)]
while s:
    a,w=s.pop()
    l[a-1]=w%2
    for b,c in q[a]:
        if l[b-1]==-1:
            s.append((b,w+c))

for i in l:
    print(i)

Solution (Python):
N=int(input())
p=[[]for _ in range(N+1)]
for _ in range(N-1):
  u,v,w=map(int,input().split())
  p[u].append((v,w))
  p[v].append((u,w))
s=[(1,0)]
l=[-1]*N
while s:
  a,w=s.pop()
  l[a-1]=w%2
  for b,c in p[a]:
    if l[b-1]==-1:
      s.append((b,w+c))
for i in l:
	print(i)

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


N = int(input())
G = [[] for _ in range(N)]
for _ 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 = [0]*N


def dfs(v, p, c):
    global ans
    ans[v] = c
    for e in G[v]:
        nv, cost = e
        if nv == p:
            continue
        if (cost % 2) == 0:
            dfs(nv, v, c)
        else:
            dfs(nv, v, (c+1) % 2)


def main():
    dfs(0, -1, 0)
    for c in ans:
        print(c)


if __name__ == '__main__':
    main()

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


N = int(input())
G = [[] for _ in range(N)]
for _ 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 = [0]*N


def dfs(v, p, c):
    global ans
    ans[v] = c
    for e in G[v]:
        nv, cost = e
        if nv == p:
            continue
        if (cost % 2) == 0:
            dfs(nv, v, c)
        else:
            dfs(nv, v, (c+1) % 2)


def main():
    dfs(0, -1, 0)
    for c in ans:
        print(c)


if __name__ == '__main__':
    main()

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


def dijkstra(s, n, edge):
    d = [float("inf")] * n
    d[s] = 0
    q = []
    for e in edge[s]:
        heapq.heappush(q, e)
    while q:
        minedge = heapq.heappop(q)
        v = minedge[1]
        if d[v] < minedge[0]:
            continue
        d[v] = minedge[0]
        for e in edge[v]:
            heapq.heappush(q, [e[0]+d[v], e[1]])
    return d


def main():
    N = int(input())
    E = [[] for _ in range(N)]
    for _ in range(N-1):
        u, v, w = map(int, input().split())
        E[u-1].append([w, v-1])
        E[v-1].append([w, u-1])
    D = dijkstra(0, N, E)
    for d in D:
        print(d % 2)


if __name__ == '__main__':
    main()

Solution (Python):
import sys
import collections


def solve():
    input = sys.stdin.readline
    mod = 10 ** 9 + 7
    tmd = collections.defaultdict(list)
    n = int(input().rstrip('\n'))
    d = collections.defaultdict(int)
    for i in range(n-1):
        tma, tmb, cost = list(map(int, input().rstrip('\n').split()))
        tmd[tma-1] += [tmb-1]
        tmd[tmb-1] += [tma-1]
        d[tma-1, tmb-1] = cost
        d[tmb-1, tma-1] = cost

    ql = [[0, 0]]
    ql = collections.deque(ql)
    fq = collections.defaultdict(int)
    while True:
        if len(ql) != 0:
            cost, tmp = ql.popleft()
            for tmv in tmd[tmp]:
                if tmv not in fq:
                    ql.append([cost + d[tmv, tmp], tmv])
                    fq[tmv] = (cost + d[tmv, tmp]) % 2
        else:
            break
    for i in range(n):
        print(fq[i])


if __name__ == '__main__':
    solve()

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


def main():
    N = int(readline())
    graph = [[] for _ in range(N + 1)]

    for i in readlines():
        u, v, w = map(int, i.split())
        w %= 2
        graph[u].append((v, w))
        graph[v].append((u, w))

    stack = [1]
    parent = [0] * (N + 1)
    color = [0] * (N + 1)

    while stack:
        here = stack.pop()
        for x, w in graph[here]:
            if x == parent[here]:
                continue
            parent[x] = here
            color[x] = color[here] ^ w
            stack.append(x)

    for i in color[1:]:
        print(i)


if __name__ == '__main__':
    main()

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

def main():
    N = int(readline())
    graph = [[] for _ in range(N + 1)]

    for i in readlines():
        u, v, w = map(int, i.split())
        graph[u].append((v, w))
        graph[v].append((u, w))

    stack = [1]
    parent = [0] * (N + 1)
    color = [0] * (N + 1)

    while stack:
        here = stack.pop()
        for x, w in graph[here]:
            if x == parent[here]:
                continue
            parent[x] = here
            color[x] = color[here] ^ (w % 2)
            stack.append(x)

    for i in color[1:]:
        print(i)


if __name__ == '__main__':
    main()

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


N = int(readline())
graph = [[] for _ in range(N + 1)]

for i in readlines():
    u, v, w = map(int, i.split())
    graph[u].append((v, w))
    graph[v].append((u, w))

stack = [1]
parent = [0] * (N + 1)
color = [0] * (N + 1)

while stack:
    here = stack.pop()
    for x, w in graph[here]:
        if x == parent[here]:
            continue
        parent[x] = here
        color[x] = color[here] ^ (w % 2)
        stack.append(x)

for i in color[1:]:
    print(i)

Solution (Python):
import sys
input = sys.stdin.readline
def main():
    N=int(input())
    edge = [[]for _ in range(N)]
    for _ in range(N-1):
        u,v,w = map(int,input().split())
        u,v = u-1,v-1
        edge[u].append((v,w))
        edge[v].append((u,w))
    color = [-1]*N
    color[0]=0
    stack = [(0,0)]
    while stack:
        v,col = stack.pop()
        for to,dist in edge[v]:
            if color[to]!=-1:
                continue
            c = (col+dist)%2  
            color[to] = c
            stack.append((to,c))
    print(*color,sep="\n")
            

if __name__ == '__main__':
    main()

Solution (Python):
def main():
    N=int(input())
    edge = [[]for _ in range(N)]
    for _ in range(N-1):
        u,v,w = map(int,input().split())
        u,v = u-1,v-1
        edge[u].append((v,w))
        edge[v].append((u,w))
    color = [-1]*N
    color[0]=0
    stack = [(0,0)]
    while stack:
        v,col = stack.pop()
        for to,dist in edge[v]:
            if color[to]!=-1:
                continue
            c = (col+dist)%2  
            color[to] = c
            stack.append((to,c))
    print(*color,sep="\n")
            

if __name__ == '__main__':
    main()

Solution (Python):
def main():
    import sys
    input = sys.stdin.buffer.readline
    N = int(input())
    G = [[] for _ in range(N+1)]
    st = 0
    st_w = 0
    for i in range(N-1):
        u, v, w = (int(i) for i in input().split())
        G[u].append((v, w))
        G[v].append((u, w))
        if i == 0:
            st = u
            st_w = w
    color = [-1] * (N+1)  
    from collections import deque

    def coloring(v, w):
        """
        breadth-first search
        a simplified version
        """
        que = deque()
        color[v] = 0
        que.append((v, w))
        while que:
            u, w = que.popleft()
            for v, d in G[u]:
                if color[v] != -1:
                    continue
                if d % 2 != 0:
                    n_col = (color[u] + 1) % 2
                else:
                    n_col = color[u]
                color[v] = n_col
                que.append((v, d))

    coloring(st, st_w)
    for c in color[1:]:
        print(c)


if __name__ == '__main__':
    main()

Solution (Python):
from collections import Counter,defaultdict,deque
def main():
    N=int(input())
    edge = [[]for _ in range(N)]
    for i in range(N-1):
        u,v,w = map(int,input().split())
        u,v = u-1,v-1
        edge[u].append((v,w))
        edge[v].append((u,w))
    color = [-1]*N
    color[0]=0
    queue = deque([(0,0)])
    while queue:
        v,col = queue.popleft()
        for to,dist in edge[v]:
            if color[to]!=-1:
                continue
            c = (col+dist)%2  
            color[to] = c
            queue.append((to,c))
    print(*color,sep="\n")
            

if __name__ == '__main__':
    main()

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


def main():
    n = int(input())

    connect = [[] for _ in range(n+1)]
    color = [None]*(n+1)
    color[1] = 0

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

    def dfs(now=1, prev=-1):
        kids = connect[now]
        for kid in kids:
            if kid[0] == prev:
                continue
            if kid[1] == 0:
                color[kid[0]] = (0, 1)[color[now]]
            else:
                color[kid[0]] = (1, 0)[color[now]]
            dfs(kid[0], now)

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


if __name__ == '__main__':
    main()

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

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

def dfs(i, _d):
    dd[i] = _d
    for c in e[i]:
        if dd[c]!=-1: continue
        dfs(c, _d+d[(i,c)])

dfs(0,0)
for _dd in dd:
    print(_dd%2)

Solution (Python):



import collections
import heapq

class Dijkstra():
    def __init__(self):
        self.e=collections.defaultdict(list)
    def add(self,u,v,d,directed=False):
        
        
        
        if directed is False:
            self.e[u].append([v,d])
            self.e[v].append([u,d])
        else:
            self.e[u].append([v,d])
    def delete(self,u,v):
        self.e[u]=[_ for _ in self.e[u] if _[0]!=v]
        self.e[v]=[_ for _ in self.e[v] if _[0]!=u]
    def search(self,s):
        
        
        d = collections.defaultdict(lambda: float('inf'))
        d[s] = 0
        q = []
        heapq.heappush(q, (0, s))
        v = collections.defaultdict(bool)
        while len(q):
            k, u = heapq.heappop(q)
            if v[u]:
                continue
            v[u] = True

            for uv, ud in self.e[u]:
                if v[uv]:
                    continue
                vd = k + ud
                if d[uv] > vd:
                    d[uv] = vd
                    heapq.heappush(q, (vd, uv))
        return d


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

graph1=Dijkstra()
for u,v,w in l:
    if w%2==0:
        graph1.add(u,v,0)
    else:
        graph1.add(u,v,1)

result_a=graph1.search(1) 


for i in range(1,n+1):
    print(result_a[i]%2)

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

N = int(input())
nodes = [[[], -1] for _ in range(N + 1)]

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


def f(i, c):
    if nodes[i][1] >= 0: return
    nodes[i][1] = c
    for n in nodes[i][0]:
        f(n[0], (c + (n[1] % 2)) % 2)


f(0, 0)
for i in range(N):
    print(nodes[i][1])

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


color = [-1] * N
stack = [[0, 0]]
while stack:
    n, w = stack.pop()
    color[n] = w % 2

    for to, to_w in T[n]:
        if color[to] >= 0:
            continue

        stack.append([to, w + to_w])

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

Solution (Python):
from collections import deque
q=deque([1])
n=int(input())
l=[[] for i in range(n+1)]
for i in range(n-1):
  a,b,c=map(int,input().split())
  c=c%2
  l[a].append([b,c])
  l[b].append([a,c])
inf=10**10
d=[inf for i in range(n+1)]
d[1]=0
def dik(s):
  q=deque([s])
  while q:
    a=q.popleft()
    for i in l[a]:
      index=i[0]
      dis=i[1]
      if d[index]>dis+d[a]:
        d[index]=dis+d[a]
        q.append(index)
dik(1)
for i in range(1,n+1):
  if d[i]%2==0:
    print(0)
  else:
    print(1)

Solution (Python):





from collections import deque

N = int(input())

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

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

color = [0] + [-1]*(N-1)
d = deque([0])

while d:
    current_point = d.popleft()
    for current_edge in edge[current_point]:
        if color[current_edge[0]] == -1:
            color[current_edge[0]] = (color[current_point] + current_edge[1]) % 2
            d.append(current_edge[0])

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

Solution (Python):





from collections import deque

N = int(input())

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

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

color = [0] + [-1]*(N-1)
d = deque([0])

while d:
    current_point = d.pop()
    for current_edge in edge[current_point]:
        if color[current_edge[0]] == -1:
            color[current_edge[0]] = (color[current_point] + current_edge[1]) % 2
            d.append(current_edge[0])

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

Solution (Python):





from collections import deque

N = int(input())

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

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

color = [0] + [-1]*(N-1)
d = deque([0])

while d:
    current_point = d.popleft()
    for current_edge in edge[current_point]:
        if color[current_edge[0]] == -1:
            color[current_edge[0]] = (color[current_point] + current_edge[1]) % 2
            d.append(current_edge[0])

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

Solution (Python):





from collections import deque

N = int(input())

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

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

color = [0] + [-1]*(N-1)
d = deque([0])

while d:
    current_point = d.pop()
    for current_edge in edge[current_point]:
        if color[current_edge[0]] == -1:
            color[current_edge[0]] = (color[current_point] + current_edge[1]) % 2
            d.append(current_edge[0])

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

Solution (Python):
import sys
from collections import deque

n = int(input())

color_ls = {i: None for i in range(n)}
dict_map = {i : [] for i in range(n)}
already = set()
for i in range(n - 1):
    u, v, w = [int(i) for i in sys.stdin.readline().split()]
    u -= 1
    v -= 1
    if i == 0:
        root = u
    dict_map[u].append([v, w])
    dict_map[v].append([u, w])
    already.update({u, v})
color_ls[root] = 0
cur = root
already.clear()
que = deque()
while True:
    candidate = dict_map[cur]
    for cand, w in candidate:
        if cand in already:
            continue
        already.add(cand)
        que.append(cand)
        if w % 2 == 0:
            color_ls[cand] = 0 if color_ls[cur] == 0 else 1
        else:
            color_ls[cand] = 1 if color_ls[cur] == 0 else 0
    if len(que) == 0 or len(already) == n:
        break
    cur = que.popleft()

for i in range(n):
    print(color_ls[i])

Solution (Python):
import sys
sys.setrecursionlimit(4100000)
input = sys.stdin.readline
def main():
    def Dfs(G, v, cur=0):
        color[v] = cur % 2
        for next_v in G[v]:
            if color[next_v[0]] != -1:
                continue
            Dfs(G, next_v[0], cur+next_v[1])


    n = int(input())
    e = [[0, 0, 0]] + [list(map(int, input().split())) for i in range(n-1)]
    g = [[] for i in range(n+1)]

    for i in range(1, n):
        g[e[i][0]].append([e[i][1], e[i][2]])
        g[e[i][1]].append([e[i][0], e[i][2]])

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

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

if __name__ == '__main__':
    main()

Solution (Python):
from collections import deque
def bfs(n,e,fordfs):
    
    W = [-1]*n
    W[e] = 0
    que = deque()
    que.append(e)
    len = [0]*n
    color = [0]*n
    while que:
        now = que.popleft()
        nowv = W[now]
        nowlen = len[now]
        nowcolor = color[now]
        for ne in fordfs[now]:
            if nowv == W[ne]:
                return -1
            elif W[ne] == -1:
                W[ne] = (nowv+1) % 2
                len[ne] = nowlen+1
                if nowcolor==0:
                    color[ne] = 1
                que.append(ne)
    return color[:n//2]

import sys
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
mod = 10**9 + 7
inf = float('inf')
ans = []

N = I()
uvw = [LI() for _ in range(N-1)]
g = [[] for i in range(2*N)]

for i in range(N-1):
    x = uvw[i][0] - 1
    y = uvw[i][1] - 1
    if uvw[i][2]%2==1:
        g[x].append(y)
        g[y].append(x)
    else:
        g[x].append(N+x)
        g[N+x].append(y)
        g[y].append(N+y)
        g[N+y].append(x)

ans = bfs(2*N,0,g)

for i in ans:
    print(i)

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

def Dfs(G, v, cur=0):
    color[v] = cur % 2
    for next_v in G[v]:
        if color[next_v[0]] != -1:
            continue
        Dfs(G, next_v[0], cur+next_v[1])


n = int(input())
e = [[0, 0, 0]] + [list(map(int, input().split())) for i in range(n-1)]
g = [[] for i in range(n+1)]

for i in range(1, n):
    g[e[i][0]].append([e[i][1], e[i][2]])
    g[e[i][1]].append([e[i][0], e[i][2]])

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

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

Solution (Python):
def resolve():
    N = int(input())
    import collections
    n_dict = collections.defaultdict(list)
    for i in range(N-1):
        u,v,w = map(int,input().split())
        n_dict[u-1].append((v-1,w))
        n_dict[v-1].append((u-1,w))

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

    d = collections.deque()
    for i in range(N):
        if color[i] == -1:
            d.append((i,1))
        while d:
            j,c = d.pop()
            color[j] = c
            for n,w in n_dict[j]:
                if color[n] == -1:
                    d.append((n,c^1)) if w % 2 != 0 else d.append((n,c))
                else:
                    continue
        print(color[i])
resolve()

Solution (Python):
from collections import deque

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

q = deque()
q.append([0, 0])
visited = [0]*(N)
while q:
    temp = q.pop()
    for L in edge[temp[0]]:
        if visited[L[0]] == 0:
            d[L[0]] = L[1] + temp[1]
            q.append([L[0], d[L[0]]])
            visited[L[0]] = 1
            
for i in range(N):
    print(d[i]%2)

Solution (Python):
N=int(input())
to = [[] for _ in range(N)]
for _ in range(N-1):
    u, v, w = [int(x) for x in input().split()]
    u -= 1
    v -= 1
    to[u].append([v, w])
    to[v].append([u, w])
ans = [-1] * N
ans[0] = 0
q = [0]
while(len(q) != 0):
    v = q.pop()
    for u, w in to[v]:
        if (ans[u] != -1): continue
        ans[u] = (ans[v]+w) % 2
        q.append(u)
for v in ans:
    print(v)

Solution (Python):
import sys
n=int(input())
if n==1:
    print(0)
    sys.exit()
lst=[list(map(int,input().split())) for _ in range(n-1)]
data=[[] for i in range(n+1)]
for i in range(n-1):
    u,v,w=lst[i]
    data[u].append(i)
    data[v].append(i)
flag=[-1]*(n+1)
u,v,w=lst[0]
flag[u]=0
flag[v]=(flag[u]+w)%2
que=[data[u],data[v]]
while que:
    h=que.pop()
    for k in h:
        u,v,w=lst[k]
        if flag[u]!=-1 and flag[v]!=-1:
            continue
        else:
            if flag[u]!=-1:
                flag[v]=(flag[u]+w)%2
                que.append(data[v])
            else:
                flag[u]=(flag[v]+w)%2
                que.append(data[u])
for i in range(1,n+1):
    print(flag[i])

Solution (Python):

import numpy as np
n = int(input())
u, v, w = [0] * (n-1), [0] * (n-1), [0] * (n-1)

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



que = [1]
ans = [2] * (n+1)
check = [0] * (n+1)

while len(que) > 0:
    tmp = que.pop(0)
    tmp_color = ans[tmp]
    tmp_list = app[tmp]
    check[tmp] = 1
    for i in range(2):
        for j in range(len(tmp_list[i])):
            if tmp_color == 0:
                if i == 0:
                    ans[tmp_list[i][j]] = 1
                else:
                    ans[tmp_list[i][j]] = 0
            else:
                if i == 0:
                    ans[tmp_list[i][j]] = 0
                else:
                    ans[tmp_list[i][j]] = 1
            if check[tmp_list[i][j]] == 0:
                que.append(tmp_list[i][j])

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

Solution (Python):
from collections import deque

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

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

depth = [-1] * N
st = deque([(0, -1, 0)])  

while st:
    now, parent, d = st.pop()

    depth[now] = d

    for to, c in edges[now]:
        if to == parent:
            continue
        st.append((to, now, d + c))

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

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

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

inf = float("inf")
E = [[] for _ in range(N+1)]
for i in range(N-1):
	if w[i] % 2 == 0:
		E[u[i]].append(v[i])
		E[v[i]].append(u[i])
	else:
		E[u[i]].append(v[i] * (-1))
		E[v[i]].append(u[i] * (-1))

flg = [inf for _ in range(N+1)]
flg[0] = 0

def dfs(q):
	cp = q.pop()
	next = E[cp]

	for np in next:
		if flg[abs(np)] == inf:
			if np > 0:
				flg[abs(np)] = flg[cp]
			else:
				flg[abs(np)] = flg[cp] * (-1)
			q.append(abs(np))

	if len(q) == 0:
		return

	dfs(q)

flg[1] = 1
dfs([1])

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

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

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

D=[-1 for _ in range(n+1)]
D[1]=0
L=deque()
L.append(1)

while L:
    p=L.popleft()
    for i in G[p]:
        if D[i[0]]==-1:
            D[i[0]]=D[p]+i[1]
            L.append(i[0])

for m in range(1,n+1):
    print(D[m]%2)

Solution (Python):
import collections
N = int(input())
Map = [[] for j in range(N+1)]

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

q = collections.deque()
q.append(1)
ans = [-1 for i in range(N+1)]
ans[1] = 0
while(q):
    v = q.popleft()
    for e,w in Map[v]:
        if ans[e] == -1:
            ans[e] = ans[v]+w
            q.append(e)
for i in range(1,N+1):
    print(ans[i]%2)

Solution (Python):
from collections import deque

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

d = [-1] * n
d[0] = 0

q = deque()
q.append(0)

while q:
    v = q.popleft()
    for u, w in g[v]:
        if d[u] != -1:
            continue
        d[u] = (d[v] + w) % 2
        q.append(u)

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

Solution (Python):
from collections import deque
n = int(input())

ed = [[] for _ in range(n)]

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

c = [0]*n
done = [0]*n
Q = deque()

Q.append(0)
while Q:
    u = Q.popleft()
    for e in ed[u]:
        if not done[e[0]]:
            c[e[0]] = (e[1]&1) ^ c[u]
            Q.append(e[0])
            done[e[0]] = 1

for i in range(n):
    print(c[i])

Solution (Python):
n = int(input())
links = [ set() for _ in range(n) ]
ans = [ -1 for _ in range(n) ]
for _ in range(n-1):
    u, v, w = map(int, input().split())
    u -= 1
    v -= 1
    links[u].add( (v,w) )
    links[v].add( (u,w) )

que = [ (0, 0, -1) ]
while que:
    v, d, p = que.pop()
    if d%2 == 0:
        ans[v] = 0
    else:
        ans[v] = 1
    for u,w in links[v]:
        if u==p:
            continue
        que.append( (u, d+w, v) )

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

Solution (Python):


import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N = INT()
nodes = tuple([] for i in range(N))
for i in range(N-1):
    a, b, c = MAP()
    a -= 1
    b -= 1
    nodes[a].append((b, c))
    nodes[b].append((a, c))

ans = [0] * N
def rec(u, prev, prevc):
    
    if prev == -1:
        ans[u] = 0
    elif prevc % 2 == 0:
        ans[u] = ans[prev]
    else:
        ans[u] = 1 - ans[prev]
    for v, c in nodes[u]:
        if v != prev:
            rec(v, u, c)
rec(0, -1, 0)

[print(a) for a in ans]

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

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

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

for i in d:
    print(i % 2)

Solution (Python):
import sys
input = sys.stdin.readline
from collections import deque
def solve():
  n = int(input())
  treenode = [[] for _ in range(n)]
  treecolor = [-2]*n
  for i in range(n-1):
    u,v,w = (int(i) for i in input().split())
    u -= 1
    v -= 1
    treenode[u].append((v,w%2))
    treenode[v].append((u,w%2))
  query = deque([(0,0,0)])
  while query:
    a,b,c = query.popleft()
    if b%2 == 0:
      treecolor[a] = c
      nextc = c
    else:
      treecolor[a] = 1^c
      nextc = 1^c
    for nextnode,weight in treenode[a]:
      if treecolor[nextnode] != -2:
        continue
      else:
        query.append((nextnode,weight,nextc))  
        treecolor[nextnode] = -1
  for i in treecolor:
    print(i)
solve()