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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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)]
    # append=uvw.append
    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
        # print(color)
        stack = tmp
    print(*color, sep="\n")


if __name__ == '__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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())
        # print(u,v,w)
        G[u-1].append((v-1, w))
        G[v-1].append((u-1, w))
    # print(G)

    dist, pred = dijkstra_heap(G, 0)
    # print(dist)

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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)]
            # 直近の親からの重み。root なら 0
            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}
            # 直近の親からの重み。root なら 0
            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

        # 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 = 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')

Submission status: Accepted

Solution code:
import queue


def even_relation(N: int, edges: list)->list:
    color = [-1] * N
    color[0] = 0

    g = [[] for _ in range(N)]
    for u, v, w in edges:
        g[u-1].append((v-1, w))
        g[v-1].append((u-1, w))

    q = queue.Queue()
    q.put((0, -1))

    while not q.empty():
        u, par = q.get()

        for v, w in g[u]:
            if v == par:
                continue

            if w % 2 == 0:
                color[v] = color[u]
            else:
                color[v] = 1-color[u]

            q.put((v, u))

    return color


if __name__ == "__main__":
    N = int(input())
    edges = [tuple(int(s) for s in input().split()) for _ in range(N-1)]

    for ans in even_relation(N, edges):
        print(ans)

Submission status: Accepted

Solution code:
import sys
from collections import deque


fin = sys.stdin.readline
N = int(fin())
adj = [[] for _ in range(N)]
w = {}
for _ in range(N - 1):
    u, v, w_ = [int(elem) for elem in fin().split()]
    u -= 1
    v -= 1
    w[u, v] = w_
    w[v, u] = w_
    adj[u].append(v)
    adj[v].append(u)

que = deque()
que.append([0, 0])
color_of_node = [-1] * N

while que:
    node, dist = que.popleft()
    if dist % 2 == 0:
        color_of_node[node] = 0
    else:
        color_of_node[node] = 1
    for neighbor in adj[node]:
        if color_of_node[neighbor] == -1:
            que.append([neighbor, dist + w[node, neighbor]])

print(*color_of_node, sep="\n")

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
from collections import deque
n=int(input())
Edges=[[] for _ in range(n)]
for _ in range(n-1):
    u,v,w=map(int,input().split())
    u-=1; v-=1
    w%=2
    Edges[u].append((v,w))
    Edges[v].append((u,w))
Dist=[0]*n
Visited=[False]*n
q=deque()
q.append((0,0))
while q:
    fr,dist=q.popleft()
    for to,d in Edges[fr]:
        if not Visited[to]:
            q.append((to,dist+d))
            Dist[to]=dist+d
            Visited[to]=True
for i in range(n):
    print(Dist[i]%2)

Submission status: Accepted

Solution code:
from collections import defaultdict
import sys,heapq,bisect,math,itertools,string,queue,datetime
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inpl(): return list(map(int, input().split()))
def inpl_str(): return list(input().split())

N = int(input())

lines = defaultdict(set)
for i in range(N-1):
    u,v,w = inpl()
    u,v = u-1,v-1
    lines[u].add((v,w))
    lines[v].add((u,w))

ans = [0]*N

def dfs(s,c):
    global ans
    for t,d in list(lines[s]):
        if ans[t] == 0:
            if d%2 == 0:
                ans[t] = c
                dfs(t,c)
            else:
                ans[t] = -c
                dfs(t,-c)


dfs(0,1)
for a in ans:
    if a == -1:
        print(0)
    else:
        print(1)

Submission status: Accepted

Solution code:
import sys
# input = sys.stdin.readline
inf = 10 ** 18

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

table = [[] for _ in range(N)]
for i, (ui, vi, wi) in enumerate(uvw):
    table[ui - 1].append((vi, wi))
    table[vi - 1].append((ui, wi))
    
import heapq

d = [inf] * N
d[0] = 0
prev = [None] * N

q = []
heapq.heappush(q, (0, 1))

while len(q) > 0:
    du, u = heapq.heappop(q)
    for v, wv in table[u - 1]:
        alt = d[u - 1] + wv
        if d[v - 1] > alt:
            d[v - 1] = alt
            prev[v - 1] = u
            heapq.heappush(q, (alt, v))

# print("#", d)
for di in d:
    print(di % 2)

Submission status: Accepted

Solution code:
from sys import stdin, stdout, setrecursionlimit as lim

lim(100003)

n = input()
inp = stdin.readlines()

g = [[] for i in xrange(n + 1)]

for line in inp:
    u, v, w = map(int, line.strip().split())
    g[u].append([v, w])
    g[v].append([u, w])

out = [0] * (n + 1)
vis = [0] * (n + 1)

def dfs(u, par, z):
    global out
    
    if z & 1: out[u] = out[par] ^ 1
    else: out[u] = out[par]
    vis[u] = 1
    for v, w in g[u]:
        if vis[v] == 1: continue
        dfs(v, u, w)

dfs(1, 1, 0)

stdout.write("\n".join(map(str, out[1:])))

Submission status: Accepted

Solution code:
import sys
stdin = sys.stdin

sys.setrecursionlimit(10 ** 7)

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x) - 1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

from heapq import heappush, heappop


def dijkstra(graph: list, node: int, start: int) -> list:
    # 未探索のノードは距離INF
    INF = float("inf")
    dist = [INF] * node

    # 始点ノードの距離を0とし、dfsのためのpriority queを作成
    dist[start] = 0
    heap = [(0, start)]

    # 未探索のノードをpriority queueに入れる
    while heap:
        cost, cur_node = heappop(heap)

        for nex_cost, nex_node in graph[cur_node]:
            dist_cand = dist[cur_node] + nex_cost
            if dist_cand < dist[nex_node]:
                dist[nex_node] = dist_cand
                heappush(heap, (dist[nex_node], nex_node))

    return dist

n = ni()
graph = [[] for _ in range(n)]
for _ in range(n-1):
    u,v,w = li()
    u -= 1
    v -= 1
    graph[u].append((w, v))
    graph[v].append((w, u))

dist = dijkstra(graph, n, 0)

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

Submission status: Accepted

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

visited = [0]*N
visited[0] = 1
ans = [0]*N
stack = [0]

while stack:
    v = stack.pop()
    for to,c in es[v]:
        if visited[to]: continue
        ans[to] = (ans[v]+c)%2
        visited[to] = 1
        stack.append(to)
print(*ans, sep='\n')

Submission status: Accepted

Solution code:

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

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

color = [None]*N
color[0] = False
stack = [0]

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

for c in color:
    print(1 if c else 0)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(114514)

N=int(input())

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

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

def walk(i, c):
	if d[i] == -1:
		d[i] = c
		for x,w in path[i]:
			walk(x, c+w)

walk(1, 0)

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

Submission status: Accepted

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

Ans = [-1]*(N+1)
Ans[1] = 0
q = [1]
Closed = [False]*(N+1)
Closed[1] = True
while len(q):
    v = q.pop()
    col = Ans[v]
    for u, w in E[v]:
        if not Closed[u]:
            Closed[u] = True
            q.append(u)
            Ans[u] = col if w%2==0 else 1-col
print(*Ans[1:], sep="\n")

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(200000)

def dfs(idx, color, colors, conn, visited):
    visited[idx] = True
    colors[idx] = color
    for node, w in conn[idx]:
        if visited[node]:
            continue
        if w % 2 == 0:
            colors = dfs(node, color, colors, conn, visited)
        else:
            colors = dfs(node, (color + 1) % 2, colors, conn, visited)
    return colors


def solve(N: int, u: "List[int]", v: "List[int]", w: "List[int]"):
    conn = [[] for _ in range(N)]
    for i in range(N - 1):
        conn[u[i] - 1].append([v[i] - 1, w[i]])
        conn[v[i] - 1].append([u[i] - 1, w[i]])
    colors = [-1] * N
    visited = [False] * N
    colors = dfs(0, 0, colors, conn, visited)
    #for i in range(N - 1):
    #    if w[i] % 2 == 0:
    #        if color[u[i]] >= 0 or color[w[i]] >= 0 :
    #            color[w[i]] = color[u[i]]
    #            color[u[i]] = color[w[i]]
    #    else:
    #        if color[u[i]] >= 0:
    #            color[w[i]] = (color[u[i]] + 1) % 2
    for c in colors:
        print(c)
    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))  # 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:
import sys
input = sys.stdin.readline

N=int(input())

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

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

for x,y,w in EDGE:
    E[x].append([y,w])
    E[y].append([x,w])

from collections import deque
QUE = deque([1])

check=[-1]*(N+1)
check[1]=0

while QUE:
    now=QUE.pop()

    for to,w in E[now]:
        if check[to]!=-1:
            continue
        check[to]=(check[now]+w)%2
        QUE.append(to)

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

Submission status: Accepted

Solution code:
from collections import deque


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

for i in range(n-1):
    tree[info[i][0] - 1].append([info[i][1] - 1, info[i][2]])
    tree[info[i][1] - 1].append([info[i][0] - 1, info[i][2]])
    
q = deque()
q.append(0)
visited = [False]*n
visited[0] = True
color = [0]*n

while q:
    pos = q.pop()
    for i, cost in tree[pos]:
        if not visited[i]:
            visited[i] = True
            if cost % 2 == 0:
                color[i] = color[pos]
            else:
                color[i] = color[pos]^1
            q.append(i)
for i in range(n):
    print(color[i])

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
import heapq
INF = float("inf")


# 無向グラフを仮定する。
class Graph(object):
    def __init__(self, N):
        self.N = N
        self.V = list(range(N))
        self.E = [[] for _ in range(N)]

    def add_edge(self, edge):
        """辺を加える。edgeは(始点, 終点、重み)からなるリスト
        重みがなければ、重み1とする。
        """
        if len(edge) == 2:
            edge.append(1)
        elif len(edge) != 3:
            print("error in add_edge")
            pass

        s, t, w = edge
        self.E[s].append([t, w])
        self.E[t].append([s, w])  # 無向グラフを仮定。逆向きにも辺を張る

        pass


def shortestPath(g: Graph, s: int):
    """ グラフgにおいて、始点sから各頂点への最短路を求める
    引数
    g: グラフ, s: 始点
    返り値
    dist: 始点からの距離が格納されたリスト
    prev: 始点から最短経路で移動する場合、各頂点に至る前の頂点のリスト
    """
    dist = [INF]*g.N
    dist[s] = 0

    prev = [None]*g.N
    Q = []
    heapq.heappush(Q, (dist[s], s))

    while len(Q) > 0:
        _, u = heapq.heappop(Q)
        for v, w in g.E[u]:
            if dist[v] > dist[u] + w:
                dist[v] = dist[u] + w
                prev[v] = u
                heapq.heappush(Q, (dist[v], v))
    return dist, prev


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

    g = Graph(N)
    for _u, _v, _w in zip(u, v, w):
        g.add_edge([_u-1, _v-1, _w])  # インデックスのとり方が違うので調整。

    dist, prev = shortestPath(g, 0)

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

    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))  # 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:
import sys, math, collections, heapq, itertools
F = sys.stdin
def single_input(): return F.readline().strip("\n")
def line_input(): return F.readline().strip("\n").split()

def solve():
    N = int(single_input())
    edge = [[] for i in range(N)]
    for i in range(N-1):
        u, v, w = map(int, line_input())
        edge[u-1].append((v-1, w))
        edge[v-1].append((u-1, w))
    
    col = [-1] * N
    que = collections.deque()
    que.append((0, 0))
    while que:
        nownode, nowdist = que.popleft()
        if col[nownode] == -1:
            col[nownode] = nowdist
            for nextnode, weight in edge[nownode]:
                if col[nextnode] == -1:
                    que.append((nextnode, nowdist + weight))
    for i in range(N):
        print(col[i] % 2)

    return 0
  
if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LS()
    return l
sys.setrecursionlimit(1000000)
mod = 1000000007

#A
def A():
    n,k = LI()
    s = input()
    for i in range(k-1):
        print(s[i],end = "")
    print(s[k-1].lower(),end = "")
    for i in range(k,n):
        print(s[i],end = "")
    print()
    return

#B
def B():
    s = S()
    k = int(s[0])*10+int(s[1])
    l = int(s[2])*10+int(s[3])
    if k == 0:
        if l == 0:
            print("NA")
        elif l < 13:
            print("YYMM")
        else:
            print("NA")
    elif k < 13:
        if l == 0:
            print("MMYY")
        elif l < 13:
            print("AMBIGUOUS")
        else:
            print("MMYY")
    else:
        if l == 0:
            print("NA")
        elif l < 13:
            print("YYMM")
        else:
            print("NA")

#C
def C():
    n,k = LI()
    ans = 0
    for i in range(1,n+1):
        l = k/i
        ans += 1/n*1/(2 << max(0,math.ceil(math.log(l,2))))
    print(ans*2)
    return

#D
def D():
    n = I()
    v = [[] for i in range(n)]
    for i in range(n-1):
        x,y,w = LI()
        x -= 1
        y -= 1
        v[x].append((y,w))
        v[y].append((x,w))
    ans = [0 for i in range(n)]
    bfs_map = [1 for i in range(n)]
    bfs_map[0] = 0
    q = deque()
    q.append(0)
    while q:
        x = q.popleft()
        for y,w in v[x]:
            if bfs_map[y]:
                if w%2:
                    ans[y] = ans[x]^1
                else:
                    ans[y] = ans[x]
                bfs_map[y] = 0
                q.append(y)
    for i in ans:
        print(i)
    return

#E
def E():
    n = I()

    return

#F
def F():
    n = I()

    return

#Solve
if __name__ == "__main__":
    D()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from collections import deque
N=int(input())
table=[[] for i in range(N)]
for i in range(N-1):
    u,v,w=map(int,input().split())
    u,v=u-1,v-1
    table[u].append((v,w))
    table[v].append((u,w))
visit=[-1]*N
H=deque()
H.append(0)
visit[0]=0
while H:
    x=H.popleft()
    for y,w in table[x]:
        if visit[y]==-1:
            visit[y]=(visit[x]+w)%2
            H.append(y)
for i in range(N):
    print(visit[i])

Submission status: Accepted

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

N = input()
W = [[] for _ in range(N)]
E = [[] for _ in range(N)]
for i in range(N-1):
  u, v, w = map(int, raw_input().split())
  E[u-1] += [v-1]
  W[u-1] += [w]
  E[v-1] += [u-1]
  W[v-1] += [w]

ans = [0]*N
def f(v, p, c):
  ans[v] = c
  for e, w, in zip(E[v], W[v]):
    if e!=p:
      f(e, v, c if w%2==0 else 1-c)
f(0, -1, 0)

for a in ans:
  print a

Submission status: Accepted

Solution code:
import sys
range = xrange
input = sys.stdin.readline

n = int(input())

coupl = [[] for _ in range(n)]
weight = [[] for _ in range(n)]
for _ in range(n-1):
    a,b,w = [int(x) for x in input().split()]
    coupl[a-1].append(b-1)
    weight[a-1].append(w)

    coupl[b-1].append(a-1)
    weight[b-1].append(w)


depth = [0]*n
found = [False]*n

stack = [0]
found[0] = True
while stack:
    node = stack.pop()
    for nei,w in zip(coupl[node],weight[node]):
        if not found[nei]:
            found[nei] = True
            depth[nei] = depth[node] + w
            stack.append(nei)

print '\n'.join(str(x%2) for x in depth)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)
def input():
	return sys.stdin.readline()[:-1]

n = int(input())
colors = [2 for _ in range(n)]
adj = [[] for _ in range(n)]

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

def dfs(v):
	for c, d in adj[v]:
		if colors[c] < 2:
			continue
		if d == 0:
			colors[c] = colors[v]
			dfs(c)
		else:
			colors[c] = abs(1 - colors[v])
			dfs(c)
	return 

colors[0] = 0
dfs(0)
print(*colors, sep="\n")

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 6)
N = int(input())
G = [[] for i in range(N)]
C = [-1] * N
for i in range(N - 1):
    u, v, w = map(int, input().split())
    u, v = u - 1, v - 1
    G[u].append((v, w))
    G[v].append((u, w))


def dfs(u, p, d):
    if C[u] != -1:
        return
    if d % 2 == 0:
        C[u] = 0
    else:
        C[u] = 1

    for w, c in G[u]:
        if w == p:
            continue
        dfs(w, u, d + c)


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

Submission status: Accepted

Solution code:
from collections import deque
import sys
readline = sys.stdin.readline

N = int(readline())
G = [[] for i in range(N)]
for i in range(N-1):
    a, b, c = map(int, readline().split())
    G[a-1].append((b-1, c))
    G[b-1].append((a-1, c))

used = [0]*N
que = deque([0])
used[0] = 1
ans = [0]*N
while que:
    v = que.popleft()
    l = ans[v]
    for w, c in G[v]:
        if used[w]:
            continue
        if c % 2:
            ans[w] = l^1
        else:
            ans[w] = l
        que.append(w)
        used[w] = 1
print(*ans, sep='\n')

Submission status: Accepted

Solution code:
N=int(input())
G=[dict() for i in range(N)]
for i in range(N-1):
    u,v,w=map(int,input().split())
    G[u-1][v-1]=w
    G[v-1][u-1]=w
color=[-1 for i in range(N)]
dist=[-1 for i in range(N)]
dist[0]=0
q=[0]
while(len(q)>0):
    r=q.pop()
    for p in G[r]:
        if dist[p]!=-1:
            continue
        dist[p]=dist[r]+G[r][p]
        q.append(p)
for i in range(N):
    color[i]=dist[i]%2
for ans in color:
    print(ans)

Submission status: Accepted

Solution code:
from sys import setrecursionlimit
setrecursionlimit(10**8)
N=int(input())
Graph=[[] for i in range(N)]
for i in range(N-1):
  u,v,w=map(int,input().split())
  w%=2
  Graph[u-1].append((v-1,w))
  Graph[v-1].append((u-1,w))
  
root=0
color=[-1]*N
color[0]=0
def dfs(x):
  for i,w in Graph[x]:
    if color[i]==-1:
      color[i]=(color[x]+w)%2
      dfs(i)
dfs(0)
for i in range(N):
  print(color[i])