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



Sample input:
3
1 2 2
2 3 1


Sample output:
0
0
1

Submission status: Accepted

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

visited = set([0])
Col = [-1]*N
Col[0] = 1
stack = [0]
while stack:
    vn = stack.pop()
    for vf, wf in Edge[vn]:
        if vf in visited:
            continue
        if wf % 2 == 0:
            c = Col[vn]
        else:
            c = 1 - Col[vn]
        visited.add(vf)
        Col[vf] = c
        stack.append(vf)
for c in Col:
    print(c)

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time
sys.setrecursionlimit(10**7)
inf = 10**20
#########################
N = int(input())
edges = [[] for _ in range(N)]
for _ in range(N-1):
    u,v,w = map(int,input().split())
    w = w%2
    edges[u-1].append((v-1,w));
    edges[v-1].append((u-1,w));
from collections import deque
queue = deque()
ans = [-1 for _ in range(N)]
queue.append(0)
ans[0] = 1
while len(queue) > 0:
    v = queue.popleft()
    for w,d in edges[v]:
        if ans[w] != -1:
            continue
        # print(w,d)
        ans[w] = (ans[v] + d) % 2
        # checked.add(w)
        queue.append(w)
for i in range(N):
    print(ans[i])

Submission status: Accepted

Solution code:
from collections import deque

N=int(input())

node_list = [[] for i in range(N)]

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

Q=deque([0])

color_list[0] = 0

while len(Q)>0:
    v1 = Q.pop()
    current_color=color_list[v1]
    for v2 in node_list[v1]:
        if color_list[v2[0]]==-1:
            if v2[1]==0:
                color_list[v2[0]]=current_color
            else:
                color_list[v2[0]]=1-current_color
            Q.appendleft(v2[0])

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

Submission status: Accepted

Solution code:
N = int(input())
E = [[] for x in range(N)]
D = [0]*N
L = [0]*N
for i in range(N-1):
    u,v,w = map(int,input().split(" "))
    u -= 1
    v -= 1
    E[u].append([v,w])
    E[v].append([u,w])

q = [[-1,0,0]]
while len(q):
    root,to,dis = q.pop()
    L[to] = 1
    if root != -1:
        D[to] = D[root] + dis
    for t,d in E[to]:
        if L[t]:
            continue
        q.append([to,t,d])

for d in D:
    print(d%2)

Submission status: Accepted

Solution code:
import heapq
import sys


class UnionFind:
    """
    sizeによる実装
    """

    def __init__(self, N):
        self.parent = [i for i in range(N)]
        self.size = [1 for _ in range(N)]

    def find(self, x):
        if self.parent[x] == x:
            return x
        else:
            return self.find(self.parent[x])

    def union(self, x, y):
        px = self.find(x)
        py = self.find(y)
        if px == py:
            return
        if self.size[px] < self.size[py]:
            self.parent[px] = py
            self.size[py] += self.size[px]
        else:
            self.parent[py] = px
            self.size[px] += self.size[py]

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

    def connectedNum(self, x):
        return self.size[self.find[x]]


# python template for atcoder1
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

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

dist = [0]*N


Un = UnionFind(N)
Q = [0]
while Q:
    current = Q.pop()
    for nex, wei in adj[current]:
        if Un.same(nex, current):
            continue
        else:
            Un.union(nex, current)
            dist[nex] = dist[current]+wei
            Q.append(nex)

dist = list(map(lambda x: x % 2, dist))
print("\n".join(map(str, dist)))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 5)
n = int(input())
color = [-1] * n
neighbor = [[] for _ in range(n)]
for _ in range(n - 1):
    u, v, w = tuple(map(int, input().split()))
    neighbor[u - 1].append((v-1, w))
    neighbor[v - 1].append((u-1, w))
def col(u, c):
    color[u] = c
    for v, w in neighbor[u]:
        if color[v] < 0:
            col(v, (c + w) % 2)
col(0, 0)
for i in range(n):
    print(color[i])

Submission status: Accepted

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))

from collections import deque

n = getN()
paths = [[] for i in range(n)]
for i in range(n-1):
    a,b,c = getList()
    paths[a-1].append((b-1,c))
    paths[b-1].append((a-1,c))

def findroot(tree):
    for i, v in enumerate(tree):
        if len(v) == 1:
            return i

root = findroot(paths)


def getdist(tree, root):
    d = deque([root])
    dist = [-1 for i in range(len(tree))]
    dist[root] = 0
    while(d):
        #print(d, dist)
        nxt = d.pop()
        tmp = dist[nxt]
        for edge in tree[nxt]:
            v, c = edge
            if dist[v] == -1:
                d.append(v)
                dist[v] = tmp + c

    return dist

distlist = getdist(paths, root)
for i in distlist:
    print(i % 2)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**9)

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

def dfs(vNow):
    useds[vNow] = True
    ans = anss[vNow]
    for v2, wt in adjL[vNow]:
        if useds[v2]: continue
        if wt % 2:  # 長さが奇数ならば、色を反転
            anss[v2] = 1-ans
        else:
            anss[v2] = ans
        dfs(v2)

useds = [False] * N
anss = [0] * N
anss[0] = 0
dfs(0)

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

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 9)


class UnionFind:
    def __init__(self, n):
        self.v = [-1 for _ in range(n)]  # 根(負): 連結頂点数 * (-1) / 子(正): 根の頂点番号(0-indexed)

    def find(self, x):  # xを含む木における根の頂点番号を返す
        if self.v[x] < 0:  # (負)は根
            return x
        else:  # 根の頂点番号
            self.v[x] = self.find(self.v[x])  # uniteでは, 旧根に属する頂点の根が旧根のままなので更新
            return self.v[x]

    def unite(self, x, y):  # 違う根に属していたらrankが低くなるように連結
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if -self.v[x] < -self.v[y]:  # size比較, 　(-1) * (連結頂点数 * (-1)), (正)同士の大小比較
            x, y = y, x  # 連結頂点数が少ない方をyにすると, findでの更新回数が減る？
        self.v[x] += self.v[y]  # 連結頂点数の和を取る, 連結頂点数 * (-1)
        self.v[y] = x  # 連結頂点数が少ないy(引数yの根の頂点番号)の根をx(引数xの根の頂点番号)にする

    def root(self, x):
        return self.v[x] < 0  # (負)は根

    def same(self, x, y):
        return self.find(x) == self.find(y)  # 同じ根に属するか

    def size(self, x):
        return -self.v[self.find(x)]  # 連結頂点数を返す


N = int(input())
e = [[] for _ in range(N)]
uf = UnionFind(N)
for _ in range(N - 1):
    u, v, w = map(int, input().split())
    u -= 1
    v -= 1
    # 0-indexedに直した
    e[u].append((v, w))
    e[v].append((u, w))

    uf.same(u, v)

# e[点]:=(隣接頂点,長さ)

root = uf.find(0)
# 根

ans = [None] * N
ans[root] = 0

# print(e)


def rec(vv):
    for nv, w in e[vv]:
        if ans[nv] is not None: continue
        ans[nv] = (ans[vv] + w) % 2
        rec(nv)


rec(root)

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
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))  # type: int
    u = [int()] * (N-1)  # type: "List[int]" 
    v = [int()] * (N-1)  # type: "List[int]" 
    w = [int()] * (N-1)  # type: "List[int]" 
    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()

Submission status: Accepted

Solution code:
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()]#WideIntPoint
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)]#HeightString
def mi(n): return [wi() for _ in range(n)]#MatrixInt
def mip(n): return [wip() for _ in range(n)]
def ms(n): return [ws() for _ in range(n)]

n = i()
#uvw
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])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from collections import deque
N = int(input())
INF = 10**12
# tree = [[INF for _ in range(N)]for __ in range(N)]
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)

# print(tree)

bfs((u, v))
# print(u, v)
# print(treedist)
for i in range(len(color)):
    print(color[i])

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
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()

Submission status: Accepted

Solution code:
#!/usr/bin/env pypy3

#import numpy as np
#import scipy, scipy.special

# Python 3 modules: https://docs.python.org/3/library/

import sys
import math, itertools, operator
from math import *
from math import factorial as fact
from itertools import permutations, combinations
from functools import reduce
# Use scipy for stats: https://docs.scipy.org/doc/scipy/reference/stats.html
# Before Python 3.5
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())
#U = []
#V = []
#W = []
# Vertex i connects to vertex M[i,x][0] and the weight is M[i,x][1]
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)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
#ABC094-D
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)]
        # 直近の親からの重み。root なら 0
        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
 
        # rank が小さい方が下
        if self._ranks[rx] > self._ranks[ry]:
            # x が root
            self._parents[ry] = rx
            self._sizes[rx] += self._sizes[ry]
            # root 間の重みに変換
            self._weights[ry] = w + self._weights[x] - self._weights[y]
        else:
            # y が root
            self._parents[rx] = ry
            self._sizes[ry] += self._sizes[rx]
            # root 間の重みに変換
            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])

Submission status: Accepted

Solution code:
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()
# start, iro
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")

Submission status: Accepted

Solution code:
from collections import deque

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

# Graph
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

# start from 1
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])

Submission status: Accepted

Solution code:
# coding: utf-8

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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) # 0:black, 1:white, c[i]:頂点i

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)

Submission status: Accepted

Solution code:
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

        # startノードからの最短距離
        # startノードは0, それ以外は無限大で初期化
        self.dist = defaultdict(lambda: float('inf'))
        self.dist[start] = 0

        # 最短経路での1つ前のノード
        self.prev = defaultdict(lambda: None)

        # startノードをキューに入れる
        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])

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
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


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    u = [int()] * (N-1)  # type: "List[int]" 
    v = [int()] * (N-1)  # type: "List[int]" 
    w = [int()] * (N-1)  # type: "List[int]" 
    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()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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])

Submission status: Accepted

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