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
from collections.abc import Iterable
from math import *
from itertools import *
from collections import *
from functools import *
from operator import *
try:
    from math import gcd
except Exception:
    from fractions import gcd


class DGraph:
    def __init__(self, n, edges):
        self._vertice = [{} for _ in range(n)]
        for e in edges:
            self._vertice[e[0]][e[1]] = e[2] if len(e) == 3 else 1

    def __len__(self):
        return len(self._vertice)

    def edges(self, n=None):
        srcs = range(len(self)) if n is None else [n]
        return sum([[(s, d, c) for d, c in self._vertice[s].items()] for s in srcs], [])

    def transpose(self):
        tedges = [(t, f, c) for f, t, c in self.edges()]
        return DGraph(len(self), tedges)

    def cost(self, src, dst):
        return self._vertice[src].get(dst, float('inf'))

class Graph(DGraph):
    def __init__(self, n, edges):
        nd_edges = edges + [(d, s, c) for s, d, c in edges]
        super().__init__(n, nd_edges)

    def transpose(self):
        return self


def solve(N: int, u: "List[int]", v: "List[int]", w: "List[int]"):
    edges = [(s - 1, d - 1, w) for s, d, w in zip(u, v, w)]
    g = Graph(N, edges)

    visited = [False] * len(g)
    res = [0] * len(g)
    q = deque([(0, 0)])

    while q:
        i, c = q.popleft()
        if visited[i]:
            continue
        visited[i] = True
        res[i] = c

        for s, d, w in g.edges(i):
            if w % 2 == 0:
                q.append((d, c))
            else:
                q.append((d, (c + 1) % 2))

    return res


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))
    result = solve(N, u, v, w)
    if isinstance(result, Iterable) and not isinstance(result, str):
        result = '\n'.join([str(v) for v in result])
    print(result)

if __name__ == '__main__':
    main()

Solution (Python):
import math, string, itertools, fractions, heapq, collections, re, array, bisect, sys, copy, functools, random
from collections import deque, defaultdict, Counter; from heapq import heappush, heappop
from itertools import permutations, combinations, product, accumulate, groupby
from bisect import bisect_left, bisect_right, insort_left, insort_right; sys.setrecursionlimit(10 ** 7)
inf = 10 ** 20; INF = float("INF"); ans = 0; tmp = 0;  tmpli = []; candili = []
eps = 1.0 / 10 ** 10; mod = 10 ** 9 + 7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]; ddn = dd + [(-1, 1), (1, 1), (1, -1), (-1, -1)]; ddn9 = ddn + [(0, 0)]
"""for dx, dy in dd:
        nx = j + dx; ny = i + dy
            if 0 <= nx < w and 0 <= ny < h:"""
def wi(): return list(map(int, sys.stdin.readline().split()))
def wip(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def ws(): return sys.stdin.readline().split()
def i(): return int(sys.stdin.readline())
def s(): return input()
def hi(n): return [i() for _ in range(n)]
def hs(n): return [s() for _ in range(n)]
def mi(n): return [wi() for _ in range(n)]
def mip(n): return [wip() for _ in range(n)]
def ms(n): return [ws() for _ in range(n)]

n = i()

x = mi(n - 1)

routedi = {}
for i in range(n + 1):
    routedi[i] = []
for i in range(n - 1):
    routedi[x[i][0]].append([x[i][1], x[i][2]])
    routedi[x[i][1]].append([x[i][0], x[i][2]])

parli = [-1] * (n + 1)
ansli = [-1]*(n + 1)
ansli[1] = 0
po = 1
que = deque()
que.append(1)
while que != deque():
    po = que.popleft()
    for i in routedi[po]:
        if parli[i[0]] == -1:  
            parli[i[0]] = po
            que.append(i[0])
            if i[1] % 2 == 0:
                ansli[i[0]] = ansli[po]
            else:
                if ansli[po] == 1:
                    ansli[i[0]] = 0
                else:
                    ansli[i[0]] = 1

for i in range(1, len(ansli)):
    print(ansli[i])

Solution (Python):
n = int(input())
data = [list(map(int, input().split())) for _ in range(n - 1)]
result = {}
for i in range(n):
    result[i+1] = -1
nexts = {}
for u, v, w in data:
    nexts.setdefault(u, [])
    nexts[u].append((v, w))
    nexts.setdefault(v, [])
    nexts[v].append((u, w))
u0 = data[0][0]
result[u0] = 1
queue = [u0]
while len(queue) > 0:
    u = queue.pop(0)
    for v, w in nexts[u]:
        if result[v] == -1:
            if w % 2 == 0:
                result[v] = result[u]
            elif result[u] == 1:
                result[v] = 0
            else:
                result[v] = 1
            queue.append(v)
for v in result.values():
    print(v)

Solution (Python):
from collections import deque
N = int(input())
INF = 10**12

tree = [[]for __ in range(N)]

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

color = [INF for __ in range(N)]
treedist = [INF for __ in range(N)]


def bfs(s):
    q = deque()
    q.append(s)
    color[s[0]] = 0
    treedist[s[0]] = 0
    while(len(q) != 0):
        u = q.pop()
        for near in tree[u[0]]:
            if treedist[near[0]] != INF:
                continue
            treedist[near[0]] = treedist[u[0]] + near[1]
            if treedist[near[0]] % 2 == 0:
                color[near[0]] = 0
            else:
                color[near[0]] = 1
            q.append(near)



bfs((u, v))


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

Solution (Python):
from sys import setrecursionlimit
setrecursionlimit(10 ** 9)

n = int(input())
U = [[int(i) for i in input().split()] for j in range(n - 1)]

E = [[] for i in range(n + 1)]

for u, v, w in U:
    E[u].append((v, w))
    E[v].append((u, w))

visited = [False] * (n + 1)
color = [0] * (n + 1)

def dfs(v, w):
    if visited[v]:
        return None
    visited[v] = True
    color[v] = 1 if w % 2 == 1 else 0
    for u, weight in E[v]:
        dfs(u, w + weight)

    return None

dfs(1, 0)

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

Solution (Python):
from math import *

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


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

q = [0]
colors[0]=0
while len(q)!=0:
    u = q.pop()
    for v,w in tonaris[u]:
        tonaris[v].remove((u,w))
        colors[v] = colors[u] ^ w
        q.append(v)

for color in colors:
    print(color)

Solution (Python):
from collections import deque

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

ans = [-1] * (N + 1)
q = deque()
q.append((1, 0, None))
while len(q):
    u, d, prev = q.pop()
    ans[u] = d % 2
    for v, w in tree[u]:
        if v != prev:
            q.append((v, d + w, u))

for v in ans[1:]:
    print(v)

Solution (Python):

import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


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


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, UVW):
    g = defaultdict(dict)
    for u, v, w in UVW:
        g[u][v] = w
        g[v][u] = w

    for i in range(1, N+1):
        if len(g[i]) == 1:
            s = i
            break

    C = [-1] * (N+1)
    C[s] = 0
    q = deque()
    q.append(s)
    while q:
        u = q.popleft()
        for v, w in g[u].items():
            if C[v] == -1:
                q.append(v)
                if w % 2 == 0:
                    C[v] = C[u]
                else:
                    C[v] = C[u] ^ 1

    for c in C[1:]:
        print(c)
    return


def main():
    N = read_int()
    UVW = [read_int_n() for _ in range(N-1)]
    slv(N, UVW)


if __name__ == '__main__':
    main()

Solution (Python):







import sys
import math, itertools, operator
from math import *
from math import factorial as fact
from itertools import permutations, combinations
from functools import reduce


from fractions import gcd

inf = float('inf')

def lcm(a, b):
    return a * b // gcd(a,b)

def perm(a, b):
    import scipy.special
    return scipy.special.perm(a, b, exact = True)

def comb(a, b):
    import scipy.special
    return scipy.special.comb(a, b, exact = True)

def dfact(n):
    import scipy.special
    return scipy.special.factorial2(n, exact = True)

def prod(l):
    return reduce(operator.mul, l)

def input_ints(inp = input, sep = ' ', conv = int):
    return map(conv, inp().split(sep = sep))



sys.setrecursionlimit(30000)

N = int(input())




M = [[] for i in range(N)]
for i in range(N-1):
    u, v, w = input_ints()
    u -= 1
    v -= 1
    w &= 1
    M[u].append((v, w))
    M[v].append((u, w))

WHITE = 0
BLACK = 1
UNK = -1
C = [UNK for i in range(N)]

def dfs(n):
    for t in M[n]:
        if C[t[0]] == UNK:
            C[t[0]] = int(not C[n]) if t[1] else C[n]
            dfs(t[0])

C[0] = WHITE
dfs(0)
for c in C:
    print(c)

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

def dijkstra(g,st):
    from heapq import heappush, heappop, heapify
    inf=10**18
    dist=[inf for i in range(len(g))]
    visited=[False for i in range(len(g))]
    dist[st]=0
    que=[]
    heappush(que,(0,st))
    while que:
        c,v=heappop(que)
        if visited[v]:
            continue
        visited[v]=True
        for x in g[v]:
            tmp=x[0]+c
            if tmp<dist[x[1]] and not visited[x[1]]:
                dist[x[1]]=tmp
                heappush(que,(tmp,x[1]))
    return dist

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

Solution (Python):

def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(input())
def S(): return list(input())
class WeightedUnionFind:
    def __init__(self, size):
        """
        :param collections.Iterable nodes:
        """
        self._parents = [i for i in range(size)]
        self._ranks = [0 for _ in range(size)]
        self._sizes = [1 for _ in range(size)]
        
        self._weights = [0 for _ in range(size)]
 
    def unite(self, x, y, w):
        """
        x が属する木と y が属する木を併合
        :param x:
        :param y:
        :param w: x と y の重みの差; (重み y) - (重み x)
        :return:
        """
        rx = self.find(x)
        ry = self.find(y)
        if rx == ry:
            return
 
        
        if self._ranks[rx] > self._ranks[ry]:
            
            self._parents[ry] = rx
            self._sizes[rx] += self._sizes[ry]
            
            self._weights[ry] = w + self._weights[x] - self._weights[y]
        else:
            
            self._parents[rx] = ry
            self._sizes[ry] += self._sizes[rx]
            
            self._weights[rx] = -w + self._weights[y] - self._weights[x]
            if self._ranks[rx] == self._ranks[ry]:
                self._ranks[ry] += 1
 
    def find(self, x):
        """
        x が属する木の root
        :param x:
        :return:
        """
        if self._parents[x] == x:
            return x
        root = self.find(self._parents[x])
        self._weights[x] += self._weights[self._parents[x]]
        self._parents[x] = root
        return root
 
    def size(self, x):
        """
        x が属する木のノード数
        :param x:
        :return:
        """
        return self._sizes[self.find(x)]
 
    def weight(self, x):
        """
        :param x:
        :return:
        """
        
        self.find(x)
        return self._weights[x]
 
    def diff(self, x, y):
        """
        (y の重み) - (x の重み)
        :param x:
        :param y:
        :return:
        """
        if self.find(x) == self.find(y):
            return self._weights[y] - self._weights[x]
        return float('inf')
n=I()
uf=WeightedUnionFind(n)
for i in range(n-1):
    u,v,w=IL()
    uf.unite(u-1,v-1,w)
C=[0]*n
for i in range(1,n):
    if uf.diff(i,0)%2==0:
        C[i]=0
    else:
        C[i]=1
for i in range(n):
    print(C[i])

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

q =deque()

q.append((0,0))

ans = [-1]*n
while q:
    now, color = q.popleft()
    if ans[now] != -1:
        continue
    ans[now] = color
    for to_, w in edge[now]:
        if ans[to_] == -1:
            if w%2==0:
                q.append((to_, color))
            else:
                q.append((to_, (color+1)%2))
print(*ans, sep="\n")

Solution (Python):
from collections import deque

N = int(input())
G = dict()


for i in range(1, N + 1):
    G[i] = dict()

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


res = [2]*(N+1)
res[1] = 0
queue = deque([1])

while len(queue) > 0:
    u = queue.popleft()
    for v in G[u].keys():
        if res[v] == 2:
            if G[u][v] % 2 == 1:
                res[v] = 1 - res[u]
            else:
                res[v] = res[u]
            queue.append(v)

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

Solution (Python):


import sys
import math

import array
import bisect
import collections
from collections import Counter, defaultdict
import fractions
import heapq
import re

sys.setrecursionlimit(1000000)


def array2d(dim1, dim2, init=None):
    return [[init for _ in range(dim2)] for _ in range(dim1)]

def argsort(l, reverse=False):
    return sorted(range(len(l)), key=lambda i: l[i], reverse=reverse)

def argmin(l):
    return l.index(min(l))

def YESNO(ans, yes="YES", no="NO"):
    print([no, yes][ans])

II = lambda: int(input())
MI = lambda: map(int, input().split())
MIL = lambda: list(MI())
MIS = lambda: input().split()


def bfs(nm, N):
    color = [None] * N
    visited = [False] * N
    q = collections.deque()

    def _bfs(node, before):
        if visited[node]: return
        visited[node] = True
        if before is None:
            color[node] = 0
        else:
            if nm[node][before] % 2 == 0:
                color[node] = color[before]
            else:
                color[node] = 0 if color[before] == 1 else 1
        for k in nm[node].keys():
            q.append((k, node))
        while(q):
            n, b = q.pop()
            _bfs(n, b)

    _bfs(0, None)
    return color


def main():
    N = II()
    nm = {i: {} for i in range(N)}
    for i in range(N-1):
        u, v, w = MI()
        nm[u-1][v-1] = nm[v-1][u-1] = w
    for c in bfs(nm, N):
        print(c)


if __name__ == "__main__":
    main()

Solution (Python):
import sys
from collections import defaultdict as dd
sys.setrecursionlimit(100000)
N = int(input())
edge = dd(lambda: dd(int))
for _ in range(N-1):
  a, b, w = map(int, input().split())
  edge[a-1][b-1] = w
  edge[b-1][a-1] = w

ans = [None] * N
def dfs(n, dist):
  ans[n] = dist % 2
  for t in edge[n]:
    if ans[t] is not None:
      continue
    dfs(t, dist + edge[n][t])
dfs(0, 0)
for a in ans:
  print(a)

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

_adjacent_dict={}

for u,v,w in UVW:
  _adjacent_dict.setdefault(u, set()).add((v,w))
  _adjacent_dict.setdefault(v, set()).add((u,w))
  
c = [None]*(N+1) 

stack = [1]
c[1] = 0

while stack:
  u = stack.pop()
  for v,w in _adjacent_dict[u]:
    if c[v] is None:
      c[v] = c[u]^(w%2)
      stack.append(v)

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

Solution (Python):
from collections import defaultdict
from heapq import heappop, heappush


class Graph(object):
    """
    隣接リストによる有向グラフ
    """

    def __init__(self):
        self.graph = defaultdict(list)

    def __len__(self):
        return len(self.graph)

    def add_edge(self, src, dst, weight=1):
        self.graph[src].append((dst, weight))

    def get_nodes(self):
        return self.graph.keys()


class Dijkstra(object):
    """
    ダイクストラ法（二分ヒープ）による最短経路探索
    計算量: O((E+V)logV)
    """

    def __init__(self, graph, start):
        self.g = graph.graph

        
        
        self.dist = defaultdict(lambda: float('inf'))
        self.dist[start] = 0

        
        self.prev = defaultdict(lambda: None)

        
        self.Q = []
        heappush(self.Q, (self.dist[start], start))

        while self.Q:
            
            dist_u, u = heappop(self.Q)
            if self.dist[u] < dist_u:
                continue
            for v, weight in self.g[u]:
                alt = dist_u + weight
                if self.dist[v] > alt:
                    self.dist[v] = alt
                    self.prev[v] = u
                    heappush(self.Q, (alt, v))

    def shortest_distance(self, goal):
        """
        startノードからgoalノードまでの最短距離
        """
        return self.dist[goal]

    def shortest_path(self, goal):
        """
        startノードからgoalノードまでの最短経路
        """
        path = []
        node = goal
        while node is not None:
            path.append(node)
            node = self.prev[node]
        return path[::-1]


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

d = Dijkstra(g, 0)

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

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

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

Solution (Python):

import sys
sys.setrecursionlimit(1000000)

def solve(N: int, u: "List[int]", v: "List[int]", w: "List[int]"):
    col = [-1 for _ in range(N+1)]
    G = [[] for _ in range(N+1)]
    for i in range(N-1):
        G[u[i]].append((v[i], w[i]))
        G[v[i]].append((u[i], w[i]))

    def dfs(p, c, cnt):
        if cnt == N:
            return
        for np, dis in G[p]:
            if col[np] == -1:
                cnt += 1
                if dis%2 == 0:
                    col[np] = c
                    dfs(np, c, cnt)
                else:
                    nc = 1 - c
                    col[np] = nc
                    dfs(np, nc, cnt)

    col[1] = 0
    dfs(1, 0, 0)
    for elem in col[1:]:
        print(elem)


    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):
def dfs(graph, start):
    stack = [(start, 0)]
    visited = set()
    li = [0] * N
    while stack:
        d = stack.pop()
        li[d[0] - 1] = d[1] % 2
        for node, w in graph[d[0]]:
            if node not in visited:
                visited.add(node)
                stack.append((node, d[1] + w))
    return li


N = int(input())
g = {i: []for i in range(1, N + 1)}
for i in range(N - 1):
    u, v, w = map(int, input().split())
    w %= 2
    g[u].append((v, w))
    g[v].append((u, w))
for c in dfs(g, 1):
    print(c)

Solution (Python):
from collections import defaultdict, deque
N = int( input())
d = defaultdict( int)
E = [ [] for _ in range(N)]
for _ in range(N-1):
    u, v, w = map( int, input().split())
    u = u-1
    v = v-1
    E[u].append(v)
    E[v].append(u)
    d[(u,v)] = w%2
    d[(v,u)] = w%2
V = [-1]*N
V[0] = 0
q = deque([0])
while q:
    v = q.popleft()
    l = V[v]
    for t in E[v]:
        if V[t] == -1:
            V[t] = (l+d[(v,t)])%2
            q.append(t)
for i in range(N):
    print(V[i])

Solution (Python):
N=int(input())
uvw= [list(map(int,input().split())) for _ in [0]*(N-1)]
connect=[[] for _ in [0]*N]
for u,v,w in uvw:
    connect[u-1].append((v-1,w))
    connect[v-1].append((u-1,w))
MAX=10**16
dist = [MAX]*N
dist[0]=0
q = [0]
while q:
    i = q.pop()
    for j,w in connect[i]:
        if dist[j] == MAX:
            dist[j] = dist[i]+w
            q.append(j)
for o in dist:
    print(o%2)

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

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

D = [-1] * N
def calc(i, c):
    D[i] = c
    for j, w in X[i]:
        if D[j] < 0:
            calc(j, D[i]^w)

calc(0, 0)
for d in D:
    print(d)

Solution (Python):
import sys
sys.setrecursionlimit(2*10**5)

N = int(input())
u, v, w = (
    zip(*(map(int, input().split()) for _ in range(N - 1))) if (N - 1) else
    ((), (), ())
)

G = [{} for _ in range(N + 1)]
for x, y, c in zip(u, v, w):
    G[x][y] = c
    G[y][x] = c

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


def f(i):
    for j in G[i]:
        if dp[j] == -1:
            if G[i][j] % 2 == 0:
                dp[j] = dp[i]
            else:
                dp[j] = 1 - dp[i]
            f(j)


f(1)
ans = '\n'.join(
    str(dp[i])
    for i in range(1, N + 1)
)
print(ans)

Solution (Python):
def main():
    import sys
    from collections import deque
    input = sys.stdin.readline
    N = int(input())
    color = [-1] * N
    color[0] = 0
    uvw = []
    edge = [[]for _ in range(N)]
    
    for i in range(N-1):
        ui, vi, wi = map(int, input().split())
        ui -= 1
        vi -= 1
        edge[ui].append((vi, wi))
        edge[vi].append((ui, wi))
    stack = [0]
    for i in range(N):
        tmp = deque()
        while stack:
            i = stack.pop()
            for e, w in edge[i]:
                if color[e] == -1:
                    stack.append(e)
                    if color[i] == 0:
                        if w % 2 == 0:
                            color[e] = 0
                        else:
                            color[e] = 1
                    else:
                        if w % 2 == 0:
                            color[e] = 1
                        else:
                            color[e] = 0
        
        stack = tmp
    print(*color, sep="\n")


if __name__ == '__main__':
    main()

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

n = int(input())

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

p = -1
cnt = -1
for i in range(n):
    if len(edge[i]) > cnt:
        p = i
        cnt = len(edge[i])

res = [-1]*n
res[p] = 0

tank = deque([p])
while len(tank):
    new = deque.pop(tank)
    for e in edge[new]:

        if res[e[0]] == -1:
            if  e[1] %2 == 0:
                if res[new] == 1:
                    res[e[0]] =1
                else:
                    res[e[0]] = 0                
            else:
                if res[new] == 1:
                    res[e[0]] =0
                else:
                    res[e[0]] = 1
            tank.append(e[0])
for e in res:
    print(e)

Solution (Python):
def dijkstra_heap(graph: list, s: int, V: int=None):
    """
    :param graph: - adjacency list [(v, w), ...]:
    :param s: start
    :param V: number of vertices
    :return: dist, pred
    """
    import heapq

    pq = []
    INF = float("inf")

    if V is None:
        V = len(graph)

    dist = [INF] * V
    pred = [-1] * V

    dist[s] = 0

    heapq.heappush(pq, (0, s))

    while pq:
        d, u = heapq.heappop(pq)
        if d > dist[u]:
            continue

        for v, w in graph[u]:
            new_dist = dist[u] + w
            if new_dist < dist[v]:
                heapq.heappush(pq, (new_dist, v))
                dist[v] = new_dist
                pred[v] = u
    return dist, pred


def main():
    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))
    

    dist, pred = dijkstra_heap(G, 0)
    

    ans = [0] * N
    for u, d in enumerate(dist):
        ans[u] = 0 if d%2==0 else 1

    for c in ans:
        print(c)


if __name__ == '__main__':
    main()

Solution (Python):
n=int(input())
d={i:[] for i in range(n)}
c=[-1]*n
for i in range(n-1):
    u,v,w=map(int,input().split())
    d[u-1].append([v-1,w])
    d[v-1].append([u-1,w])
c[0]=0
q=[[0,0]]
while(q):
    p,w=q.pop(0)
    l=d[p]
    for x in l:
        p_=x[0]
        w_=x[1]
        if c[p_]>=0:
            continue
        else:
            w_+=w
            q.append([p_,w_])
            if w_%2==0:
                c[p_]=0
            else:
                c[p_]=1
for i in range(n):
    print(c[i])

Solution (Python):
N = int(input())
edge = []
nlist = [[] for i in range(N)]
for i in range(N-1):
    u, v, w = map(int,input().split())
    u, v = u-1, v-1
    edge.append([u,v,w])
for u, v, w in edge:
    nlist[u].append([v,w])
    nlist[v].append([u,w])
visit = [False]*N
ans = [0]*N

def dfs(v):
    S = []
    visit[v] = True
    S.append([v,0])
    while S:
        v = S.pop()
        if v[1] % 2 == 0:
            ans[v[0]] = 0
        else:
            ans[v[0]] = 1
        for index, w in nlist[v[0]]:
            if not visit[index]:
                visit[index] = True
                S.append([index,v[1]+w])
                
dfs(0)
for a in ans:
    print(a)

Solution (Python):
from collections import deque


def main():
    N = int(input())
    adj = [{} for _ in range(N)]
    ans = [float("inf")] * N
    for i in range(N-1):
        u, v, w = map(int, input().split())
        adj[u-1][v-1] = w
        adj[v-1][u-1] = w
    q = deque([(0, 0)])
    while len(q):
        cur, dist = q.popleft()
        ans[cur] = dist % 2
        for nxt in adj[cur]:
            if ans[nxt] == float("inf"):
                q.append((nxt, dist + adj[cur][nxt]))
    for i in range(N):
        print(ans[i])


if __name__ == "__main__":
    main()

Solution (Python):
from collections import Counter, deque
from fractions import gcd
from functools import lru_cache
from functools import reduce
import functools
import heapq
import itertools
import math
import numpy as np
import re
import sys

sys.setrecursionlimit(10000)
INF = float('inf')


class WeightedUnionFind:
    def __init__(self, size=None, nodes=None):
        """
        size か nodes どっちか指定。
        nodes は set、size は list を使う。
        set の最悪計算量は O(N) なので size 指定のほうが若干速い
        :param int size:
        :param collections.Iterable nodes:
        """
        assert size is not None or nodes is not None
        if size is not None:
            self._parents = [i for i in range(size)]
            self._ranks = [0 for _ in range(size)]
            self._sizes = [1 for _ in range(size)]
            
            self._weights = [0 for _ in range(size)]
        else:
            self._parents = {k: k for k in nodes}
            self._ranks = {k: 0 for k in nodes}
            self._sizes = {k: 1 for k in nodes}
            
            self._weights = {k: 0 for k in nodes}

    def unite(self, x, y, w):
        """
        x が属する木と y が属する木を併合
        :param x:
        :param y:
        :param w: x と y の重みの差; (重み y) - (重み x)
        :return:
        """
        rx = self.find(x)
        ry = self.find(y)
        if rx == ry:
            return

        
        if self._ranks[rx] > self._ranks[ry]:
            
            self._parents[ry] = rx
            self._sizes[rx] += self._sizes[ry]
            
            self._weights[ry] = w + self._weights[x] - self._weights[y]
        else:
            
            self._parents[rx] = ry
            self._sizes[ry] += self._sizes[rx]
            
            self._weights[rx] = -w + self._weights[y] - self._weights[x]
            if self._ranks[rx] == self._ranks[ry]:
                self._ranks[ry] += 1

    def find(self, x):
        """
        x が属する木の root
        :param x:
        :return:
        """
        if self._parents[x] == x:
            return x
        root = self.find(self._parents[x])
        self._weights[x] += self._weights[self._parents[x]]
        self._parents[x] = root
        return root

    def size(self, x):
        """
        x が属する木のノード数
        :param x:
        :return:
        """
        return self._sizes[self.find(x)]

    def weight(self, x):
        """
        :param x:
        :return:
        """
        
        self.find(x)
        return self._weights[x]

    def diff(self, x, y):
        """
        (y の重み) - (x の重み)
        :param x:
        :param y:
        :return:
        """
        if self.find(x) == self.find(y):
            return self._weights[y] - self._weights[x]
        return float('inf')


N = int(input())
U, V, W = zip(*[list(map(int, input().split())) for _ in range(N - 1)])

uf = WeightedUnionFind(size=N + 1)
for u, v, w in zip(U, V, W):
    uf.unite(u, v, w)

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