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 defaultdict
import sys
input = sys.stdin.readline
N = int(input())

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



FROM, TO = 0, 1
q = [(TO, FROM)]

paint_dict = defaultdict(int)

paint_dict[TO] = 0

idx = 0
while idx < N:
    
    now_node, prev_node = q[idx]
    for to_node, w in tree_dict[now_node]:
        if to_node != prev_node:
            if (w + paint_dict[now_node]) % 2 == 0:
                paint_dict[to_node] = 0
            else:
                paint_dict[to_node] = 1
            q.append((to_node, now_node))
    idx += 1
for i in range(N):
    print(paint_dict[i+1])

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

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

def dijkstra(start,ad):
    dist = [inf]*len(ad)
    dist[start] = 0
    pq = [(start,0)]
    while pq:
        v = heappop(pq)[0]
        for nv,nw in ad[v]:
            if dist[nv] > dist[v] + nw:
                dist[nv] = dist[v] + nw
                heappush(pq,(nv,dist[nv]))
    return dist

N = int(input())

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

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

dist = dijkstra(0,ad)

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

Solution (Python):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N = INT()
uvw = [LIST() for _ in range(N-1)]

link_dic = defaultdict(list)

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

searched = [0]*N
color = [0]*N
color[0] = 1
def dfs(i):
	
	for node, w in link_dic[i]:
		if searched[node] == 1:
			continue
		else:
			if w % 2 == 0:
				color[node] = color[i]
			else:
				color[node] = color[i] * (-1)
			searched[node] = 1
			dfs(node)

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

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

g = [dict() for _ in range(N+1)]
for i in range(1, N):
    u, v, w = map(int, input().split())
    w = 0 if w % 2 == 0 else 1
    g[u][v] = w
    g[v][u] = w

ret = {1:0}
q = collections.deque()
q.append(1)
while len(q):
    d = q.pop()
    for h in g[d]:
        if ret.get(h, -1) < 0:
            ret[h] = ret[d] ^ g[d][h]
            q.append(h)

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

Solution (Python):
from operator import itemgetter
import sys
sys.setrecursionlimit(1000000)

def dfs(n,team):
    li[n-1] = team
    for i in grp[n-1]:
        if(li[i[0]-1]==-1):
            dfs(i[0],(team+i[1])%2)



N = int(input())
li = [-1]*N
uvw = [[int(x) for x in input().split()]for _ in range(N-1)]
uvw.sort(key=itemgetter(0))
grp = [[]for _ in range(N)]
for i in uvw:
    grp[i[0]-1].append([i[1],i[2]])
    grp[i[1]-1].append([i[0],i[2]])
dfs(1,0)
for i in li:
    print(i)

Solution (Python):
N = int(input())
W = [ [] for _ in range(N) ]
used = [-1] * N

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

used[0] = 0
lst = [ 0 ]
while len(lst) != 0:
    newList = []
    for v in lst:
        for (nx, w) in W[v]:
            if used[nx] == -1:
                if w % 2 == 0:
                    used[nx] = used[v]
                else:
                    used[nx] = (used[v] + 1) % 2
                newList.append(nx)
    lst = newList

for ans in used:
    print(ans)

Solution (Python):
def dfs(s):
    visited[s]=1
    for v in adj[s]:
        if v not in visited:
            if (s,v) in we:
                y[v]=y[s]+we[(s,v)]
            elif (v,s) in we:
                y[v]=y[s]+we[(v,s)]
            dfs(v)
import sys
sys.setrecursionlimit(10**5)
n=int(input())
adj={}
we={}
visited={}
y=[0]*(n+1)
for q in range(n-1):
    a,b,w=map(int,input().split())
    if a not in adj:
        adj[a]=[b]
    else:
        adj[a].append(b)
    if b not in adj:
        adj[b]=[a]
    else:
        adj[b].append(a)
    we[(a,b)]=w
if n>1:
    dfs(1)
for i in range(1,n+1):
    if y[i]%2==0:
        print(0)
    else:
        print(1)

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

data = [[] for _ in range(N+1)]

for i in range(N-1):
    a, b, c = map(int, input().split())

    data[a].append((b,c))
    data[b].append((a,c))


ans = [0] * (N+1)
went = [False] * (N+1)

went[0] = True
went[1] = True
go = [1]

while len(go) > 0:
    before = go.pop()
    for i, c in data[before]:
        if not went[i]:
            went[i] = True
            if c % 2 == 0:
                ans[i] = ans[before]
            else:
                ans[i] = 1 - ans[before]
            go.append(i)

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

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

data = [[] for _ in range(N+1)]

for i in range(N-1):
    a, b, c = map(int, input().split())

    data[a].append((b,c))
    data[b].append((a,c))


ans = [0] * (N+1)
went = [False] * (N+1)

went[0] = True
went[1] = True
go = [1]

while len(go) > 0:
    before = go.pop()
    for i, c in data[before]:
        if not went[i]:
            went[i] = True
            if c % 2 == 0:
                ans[i] = ans[before]
            else:
                ans[i] = 1 - ans[before]
            go.append(i)

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

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

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

visited = [False]*N
from collections import deque

q = deque()
q.append([0, 0])
while q:
    num, kyori = q.pop()
    visited[num] = '1' if kyori%2 == 1 else '0'
    for hen in g[num]:
        if not visited[hen[0]]:
            q.append([hen[0], kyori+hen[1]]) 

print('\n'.join(visited))

Solution (Python):
import sys
sys.setrecursionlimit(1000000)
def solve():
    n = int(input())
    ans = [-1] * (n + 1)
    li = [[] for _ in range(n + 1)]
    for _ in range(n - 1):
        u, v, w = map(int, input().split())
        li[u].append((v, w))
        li[v].append((u, w))
    def f(i, ans, c):
        if li[i] == []:
            return
        for u, w in li[i]:
            if ans[u] == -1:
                if w % 2 == 0:
                    ans[u] = c
                    f(u, ans, c)
                else:
                    ans[u] = c ^ 1
                    f(u, ans, c ^ 1)
    for i in range(1, n):
        if li[i] != [] and ans[i] == -1:
            ans[i] = 0
            f(i, ans, 0)
    print(*ans[1:], sep="\n")
solve()

Solution (Python):
import sys
sys.setrecursionlimit(1000000)
def solve():
    n = int(input())
    ans = [-1] * (n + 1)
    li = [[] for _ in range(n + 1)]
    for _ in range(n - 1):
        u, v, w = map(int, input().split())
        li[u].append((v, w))
        li[v].append((u, w))
    def f(i, ans, c):
        if li[i] == []:
            return
        for u, w in li[i]:
            if ans[u] == -1:
                if w % 2 == 0:
                    ans[u] = c
                    f(u, ans, c)
                else:
                    ans[u] = c ^ 1
                    f(u, ans, c ^ 1)
    for i in range(1, n):
        if li[i] != [] and ans[i] == -1:
            ans[i] = 0
            f(i, ans, 0)
    print(*ans[1:], sep="\n")
solve()

Solution (Python):
from collections import deque
n = int(input())
l = []
ans = [-1 for i in range(n+1)]

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

deq = deque()
deq.appendleft(1)

while len(deq) > 0:
    v = deq.pop()
    for u, w in adj[v]:
        if ans[u] == -1:
            deq.appendleft(u)
        if ans[v] == -1 and ans[u] == -1:
            if w %2 == 0:
                ans[v] = 0
                ans[u] = 0
            else:
                ans[v] = 0
                ans[u] = 1
        elif ans[v] == 0:
            if w % 2 == 0:
                ans[u] = 0
            else:
                ans[u] = 1
        else:
            if w % 2 == 0:
                ans[u] = 1
            else:
                ans[u] = 0
        

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

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

data = [[] for _ in range(N+1)]

for i in range(N-1):
    a, b, c = map(int, input().split())

    data[a].append((b,c))
    data[b].append((a,c))


ans = [0] * (N+1)
went = [False] * (N+1)

went[0] = True
went[1] = True
go = [1]

while len(go) > 0:
    before = go.pop()
    for i, c in data[before]:
        if not went[i]:
            went[i] = True
            if c % 2 == 0:
                ans[i] = ans[before]
            else:
                ans[i] = 1 - ans[before]
            go.append(i)

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

Solution (Python):
import sys
sys.setrecursionlimit(1000000)
def solve():
    n = int(input())
    ans = [-1] * (n + 1)
    li = [[] for _ in range(n + 1)]
    for _ in range(n - 1):
        u, v, w = map(int, input().split())
        li[u].append((v, w))
        li[v].append((u, w))
    def f(i, ans, c):
        if li[i] == []:
            return
        for u, w in li[i]:
            if ans[u] == -1:
                if w % 2 == 0:
                    ans[u] = c
                    f(u, ans, c)
                else:
                    ans[u] = c ^ 1
                    f(u, ans, c ^ 1)
    for i in range(1, n):
        if li[i] != [] and ans[i] == -1:
            ans[i] = 0
            f(i, ans, 0)
    print(*ans[1:], sep="\n")
solve()

Solution (Python):
import sys
sys.setrecursionlimit(1000000)
def solve():
    n = int(input())
    ans = [-1] * (n + 1)
    li = [[] for _ in range(n + 1)]
    for _ in range(n - 1):
        u, v, w = map(int, input().split())
        li[u].append((v, w))
        li[v].append((u, w))
    def f(i, ans, c):
        if li[i] == []:
            return
        for u, w in li[i]:
            if ans[u] == -1:
                if w % 2 == 0:
                    ans[u] = c
                    f(u, ans, c)
                else:
                    ans[u] = c ^ 1
                    f(u, ans, c ^ 1)
    for i in range(1, n):
        if li[i] != [] and ans[i] == -1:
            ans[i] = 0
            f(i, ans, 0)
    print(*ans[1:], sep="\n")
solve()

Solution (Python):

from heapq import heappop, heappush
def solve(): 
    N = int(input())
    edges = [[] for _ in range(N+1)]
    for _ in range(N-1):
        u, v, w = map(int, input().split())
        edges[u].append((v, w&1))
        edges[v].append((u, w&1))

    D = [-1]*(N+1)
    hq = [(0,1)]
    checked = set()
    while hq:
        c, u = heappop(hq)
        checked.add(u)
        D[u] = c
        for v, w in edges[u]:
            if not v in checked:
                heappush(hq, (c^w, v))

    res = '\n'.join(map(str, D[1:]))
    return str(res)

if __name__ == '__main__':
    print(solve())

Solution (Python):

from heapq import heappop, heappush
def solve(): 
    N = int(input())
    edges = [[] for _ in range(N+1)]
    for _ in range(N-1):
        u, v, w = map(int, input().split())
        edges[u].append((v, w&1))
        edges[v].append((u, w&1))

    D = [-1]*(N+1)
    hq = [(0,1)]
    checked = set()
    while hq:
        c, u = heappop(hq)
        checked.add(u)
        D[u] = c
        for v, w in edges[u]:
            if not v in checked:
                heappush(hq, (c^w, v))

    res = '\n'.join(map(str, D[1:]))
    return str(res)

if __name__ == '__main__':
    print(solve())

Solution (Python):

from heapq import heappop, heappush
def solve(): 
    N = int(input())
    edges = [[] for _ in range(N+1)]
    for _ in range(N-1):
        u, v, w = map(int, input().split())
        edges[u].append((v, w&1))
        edges[v].append((u, w&1))

    D = [-1]*(N+1)
    hq = [(0,1)]
    checked = set()
    while hq:
        c, u = heappop(hq)
        checked.add(u)
        D[u] = c
        for v, w in edges[u]:
            if not v in checked:
                heappush(hq, (c^w, v))

    res = '\n'.join(map(str, D[1:]))
    return str(res)

if __name__ == '__main__':
    print(solve())

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



def main():
    n = int(input())
    g = [dict() for _ in range(n)]
    for _ in range(n-1):
        u, v, w = list(map(int, input().split()))
        g[u-1][v-1] = w
        g[v-1][u-1] = w
    dist = [-1 for _ in range(n)]
    dist[0] = 0
    q = [0]
    while len(q) > 0:
        f = q.pop()
        for t in g[f]:
            if dist[t] != -1:
                continue
            dist[t] = dist[f] + g[f][t]
            q.append(t)
    for i in range(n):
        if dist[i] % 2 == 0:
            print(0)
        else:
            print(1)


if __name__ == '__main__':
    main()

Solution (Python):


import sys
sys.setrecursionlimit(1000000)

n = int(input())
link = [[] for _ in range(n)]
for i in range(n-1):
    ut, vt, wi = list(map(int, input().split()))
    ui = ut - 1
    vi = vt - 1
    link[ui].append((vi, wi))
    link[vi].append((ui, wi))
color = [-1] * n

def dfs(index, c):
    color[index] = c
    for nxt, w in link[index]:
        if color[nxt] == -1:
            dfs(nxt, ((w % 2) + c) % 2)

def main():
    dfs(0, 0)
    for c in color:
        print(c)


if __name__ == '__main__':
    main()

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

n = int(input())
link = [[] for _ in range(n)]
for i in range(n-1):
    ut, vt, wi = list(map(int, input().split()))
    ui = ut - 1
    vi = vt - 1
    link[ui].append((vi, wi))
    link[vi].append((ui, wi))
color = [-1] * n

def dfs(index, c):
    color[index] = c
    for nxt, w in link[index]:
        if color[nxt] == -1:
            dfs(nxt, ((w % 2) + c) % 2)

def main():
    dfs(0, 0)
    for c in color:
        print(c)


if __name__ == '__main__':
    main()

Solution (Python):



def main():
    n = int(input())
    g = [dict() for _ in range(n)]
    for _ in range(n-1):
        u, v, w = list(map(int, input().split()))
        g[u-1][v-1] = w
        g[v-1][u-1] = w
    dist = [-1 for _ in range(n)]
    dist[0] = 0
    q = [0]
    while len(q) > 0:
        f = q.pop()
        for t in g[f]:
            if dist[t] != -1:
                continue
            dist[t] = dist[f] + g[f][t]
            q.append(t)
    for i in range(n):
        if dist[i] % 2 == 0:
            print(0)
        else:
            print(1)


if __name__ == '__main__':
    main()

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

n = int(input())
link = [[] for _ in range(n)]
for i in range(n-1):
    ut, vt, wi = list(map(int, input().split()))
    ui = ut - 1
    vi = vt - 1
    link[ui].append((vi, wi))
    link[vi].append((ui, wi))
color = [-1] * n

def dfs(index, c):
    color[index] = c
    for nxt, w in link[index]:
        if color[nxt] == -1:
            dfs(nxt, ((w % 2) + c) % 2)

def main():
    dfs(0, 0)
    for c in color:
        print(c)


if __name__ == '__main__':
    main()

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(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):
def dfs(s):
    visited[s]=1
    for v in adj[s]:
        if v not in visited:
            if (s,v) in we:
                y[v]=y[s]+we[(s,v)]
            elif (v,s) in we:
                y[v]=y[s]+we[(v,s)]
            dfs(v)
import sys
sys.setrecursionlimit(10**5)
n=int(input())
adj={}
we={}
visited={}
y=[0]*(n+1)
for q in range(n-1):
    a,b,w=map(int,input().split())
    if a not in adj:
        adj[a]=[b]
    else:
        adj[a].append(b)
    if b not in adj:
        adj[b]=[a]
    else:
        adj[b].append(a)
    we[(a,b)]=w
if n>1:
    dfs(1)
for i in range(1,n+1):
    if y[i]%2==0:
        print(0)
    else:
        print(1)

Solution (Python):
import collections

n=int(input())
ans=[0]*(n+1)
tree=[[] for _ in range(n+1)]
for i in range(n-1):
  u,v,w=map(int,input().split())
  tree[u].append([v,w])
  tree[v].append([u,w])
q=collections.deque([1])
check=[False]*(n+1)
check[1]=True
tmp=tree[1][0]
if tmp[1]%2==0:
  ans[1]=1
  ans[tmp[0]]=1
else:
  ans[1]=1
  ans[tmp[0]]=0
while 1:
  if len(q)==0:
    break
  tmp=q.popleft()
  for i in range(len(tree[tmp])):
    v,w=tree[tmp][i][0],tree[tmp][i][1]
    if check[v]:
      continue
    else:
      check[v]=True
      if w%2==0:
        ans[v]=ans[tmp]
      else:
        ans[v]=abs(1-ans[tmp])
      q.append(v)
for i in range(1,n+1):
  print(ans[i])

Solution (Python):

import sys

sys.setrecursionlimit(100000+10)


def add_edge(u, v, distance ):
	G[u].append([v, distance])
	G[v].append([u, distance])

def dfs(vertex, distance_from_start):
	global colors

	colors[vertex] = distance_from_start % 2

	for info in G[vertex]:
		v = info[0]
		if colors[v] >= 0: 
			
			pass
		else:
			dfs(v, distance_from_start + info[1])

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

G = [[] for _ in range(n)] 
for edge in edges:
	add_edge(edge[0]-1, edge[1]-1, edge[2])

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

dfs(0, 0)

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

Solution (Python):
from collections import deque

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

visited = [False]*N
q = deque([0])
dist = [0]*N
while q:
    cur = q.popleft()
    if visited[cur]:
        continue
    visited[cur] = True
    for nex, w in adj[cur]:
        if (not visited[nex]):
            q.append(nex)
            dist[nex] = dist[cur] + w

for d in dist:
    print(d%2)

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

edge = [[] for i in range(n)]
d = [-1] * n

for i in range(n-1):
    x,y,cost = map(int,input().split())
    
    
    x -=1
    y -=1
    cost %=2
    edge[x].append((cost,y))
    edge[y].append((cost,x))
q = deque()
q.append(0)
d[0] =0
while q:
    t = q.popleft()
    for s in edge[t]:
        if d[s[1]] == -1:
            d[s[1]] = d[t] + s[0]
            q.append(s[1])
for i in d:
    print(i%2)

Solution (Python):
class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n+1)]
        self.rank = [0] * (n+1)

    
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            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 self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
    def height(self, x):
        return self.rank[x]

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


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())
edges=[]
for i in range(N-1):
  edges+=[list(map(int,input().split()))]

distance = BFS(0, edges, N)


ans = []
for i in range(N):
    if distance[i] % 2 == 0:
        ans.append(0)
    else:
        ans.append(1)

for c in ans:
    print(c)

Solution (Python):



N = int(input())

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

for i in range(N-1):
    u, v, w = map(int, input().rstrip().split(' '))
    u = u - 1
    v = v - 1
    
    edges[u].append([v, w])
    edges[v].append([u, w])
    
from collections import deque

temp = deque([[0, 0]])

color = [-1] * N
while len(temp) > 0:
    a, b = temp.popleft()
    color[a] = b
    
    
    for edge in edges[a]:
        if edge[1] % 2 == 1 and color[edge[0]] == -1:
            temp.append([edge[0], 1 - b])
        elif color[edge[0]] == -1:
            temp.append([edge[0], b])

for c in color:
    print(c)

Solution (Python):
from collections import deque
N = int(input())
ans = [True]*(N+1)
already = [False] * (N+1)

td = {i:[] for i in range(1,N+1)}
for i in range(N-1):
	ut,vt,wt = map(int,input().split(' '))
	td[ut].append((vt,wt%2))
	td[vt].append((ut,wt%2))

q = deque([1])
while(q):
	i = q.popleft()
	already[i] = True
	for v,w in td[i]:
		if not already[v]:
			q.append(v)
			
			if w:
				ans[v] = not ans[i]
			else:
				ans[v] = ans[i]



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

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

N = int(input())
        
G = [[] for i in range(N)]
for _ in range(N - 1):
    a, b, c = map(int, input().split())
    G[a - 1].append([b - 1, c])
    G[b - 1].append([a - 1, c])
    
color = [0] * N

def dfs(v, c):
    if color[v] == 0:
        color[v] = c
    for i in range(len(G[v])):
        if color[G[v][i][0]] == 0:
            if G[v][i][1] % 2 == 0:
                dfs(G[v][i][0], color[v])
            else:
                dfs(G[v][i][0] , -color[v])
                
for i in range(N):
    dfs(i, 1)
    
    
for i in range(N):
    if color[i] == 1:
        print(0)
    else:
        print(1)

Solution (Python):
import array
import collections
import heapq

AdjacentVertex = collections.namedtuple("AdjacentVertex", "vertex cost")
INF = 2**31 - 1
NO_VERTEX = -1

ans = [0 for i in range(10**5)]



def compute_mst_prim(max_v, adj_list):
    
    pred = collections.defaultdict(lambda: NO_VERTEX)
    
    key = collections.defaultdict(lambda: INF)
    key[0] = 0
    
    pq = [(key[v], v) for v in range(max_v)]
    heapq.heapify(pq)
    
    in_pq = array.array("B", (True for _ in range(max_v)))
    while pq:
        _, u = heapq.heappop(pq)
        in_pq[u] = False
        for v, v_cost in adj_list[u]:
            if in_pq[v]:
                weight = v_cost
                if weight < key[v]:
                    pred[v] = u
                    key[v] = weight
                    ans[v] = ans[pred[v]] + key[v]
                    heapq.heappush(pq, (weight, v))
                    in_pq[v] = True
    return (pred, key)


def main():
    max_v = int(input())
    max_e = max_v - 1
    adjacency_list = collections.defaultdict(set)
    for _ in range(max_e):
        s, t, w = map(int, input().split())
        s -= 1
        t -= 1
        adjacency_list[s].add(AdjacentVertex(t, w))
        adjacency_list[t].add(AdjacentVertex(s, w))
    (_, key) = compute_mst_prim(max_v, adjacency_list)
    for i in range(max_v):
        print(ans[i] % 2)


if __name__ == '__main__':
    main()

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
input = sys.stdin.readline
sys.setrecursionlimit(1000000)

n = int(input())
ans = [-1]*n
tree = [[] for i in range(n)]

def dfs(x,y):
  ans[x] = y
  for node in tree[x]:
    if ans[node[0]] == -1:
      if node[1] % 2 == 0:
        dfs(node[0],y)
      else:
        if y:
          dfs(node[0],0)
        else:
          dfs(node[0],1)

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

dfs(0,0)
for a in ans:
  print(a)

Solution (Python):
n = int(input())
route = {}

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

r = [-1] * n
q = [1]
r[0] = 0
while len(q) > 0:
    u = q.pop()
    vws = route[u]
    for (v, w) in vws:
        if r[v-1] != -1:
            continue
        r[v-1] = (w & 1) ^ r[u-1]
        q.append(v)

for i in r:
    print(i)

Solution (Python):
from collections import deque

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

adj = [[] for _ in range(N+1)]
for b in branch:
  adj[b[0]].append([b[1],b[2]])
  adj[b[1]].append([b[0],b[2]])

ans = [-1] * (N+1)
deq = deque()
deq.appendleft(1)
while len(deq) > 0:
  v = deq.pop()
  for u, w in adj[v]:
    if ans[u] == -1:
      deq.appendleft(u)
    if ans[v] == -1 and ans[u] == -1:
      if w % 2 == 0:
        ans[v] = 0
        ans[u] = 0
      else:
        ans[v] = 0
        ans[u] = 1
    elif ans[v] == 0:
      if w % 2 == 0:
        ans[u] = 0
      else:
        ans[u] = 1
    else:
      if w % 2 == 0:
        ans[u] = 1
      else:
        ans[u] = 0
if N == 1:
  print(0)
else:
  for i in range(1,N+1):
    print(ans[i])

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

mpA = dict()
mpB = dict()
for n in range(N-1):
    u, v, w = list(map(int, input().split()))
    if u in mpA:
        mpA[u].append((v, w))
    else:
        mpA[u] = [(v, w)]
    if v in mpB:
        mpB[v].append((u, w))
    else:
        mpB[v] = [(u, w)]

Z = [-1] * (N+1)

A = 0
Z[1] = A

nxt = [(1, A)]
while(len(nxt) > 0):
    nxt2 = []
    for x in nxt:
        xx, xA = x[0], x[1]
        if xx in mpA:
            vA = mpA[xx]
            for wa in vA:
                v, w = wa[0], wa[1]
                if Z[v] == -1:
                    if w % 2 == 0:
                        Z[v] = xA
                        nxt2.append((v, Z[v]))
                    else:
                        Z[v] = 1 - xA
                        nxt2.append((v, Z[v]))
        if xx in mpB:
            vB = mpB[xx]
            for wb in vB:
                u, w = wb[0], wb[1]
                if Z[u] == -1:
                    if w % 2 == 0:
                        Z[u] = xA
                        nxt2.append((u, Z[u]))
                    else:
                        Z[u] = 1 - xA
                        nxt2.append((u, Z[u]))
    nxt = nxt2

for n in range(1, N+1):
    print(Z[n])