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:
from sys import stdin
import math
import fractions
from collections import deque

WHITE = 0
BLACK = 1

N = int(stdin.readline().rstrip())
data = [list(map(int, stdin.readline().rstrip().split())) for _ in range(N-1)]

# 木の繋がりと長さ
connect = [[] for _ in range(N+1)]
for u, v, w in data:
    connect[u].append([v,w])
    connect[v].append([u,w])

# 根から頂点までの距離
# 根は適当な頂点を選べば良いので、u_0とする
dist = [None] * (N+1)
dist[data[0][0]] = 0

que = deque([])
que.append(data[0][0])
is_visited = [False] * (N+1)

# BFSで根からの距離を求めていく
while len(que) != 0:
    u = que.popleft()

    if is_visited[u] == True:
        continue

    is_visited[u] = True

    for v, w in connect[u]:
        que.append(v)
        if dist[v] == None:
            dist[v] = dist[u] + w

# distが偶数の頂点には白で、奇数の頂点には黒で塗ることとする
for i in range(1, N+1):
    if dist[i] % 2 == 0:
        print(WHITE)
    else:
        print(BLACK)

Submission status: Accepted

Solution code:
N = int(input())
U, V, W = [], [], []
T = [[] for _ in range(N)]
# tree
class Tree(object):
    def __init__(self, us, vs, ws):
        self.con_table = [[] for _ in range(len(us) + 1)]
        self.weights = dict()
        for (u, v, w) in zip(us, vs, ws):
            self.con_table[u-1].append(v-1)
            self.con_table[v-1].append(u-1)
            self.weights[(u-1, v-1)] = w
        self.init_search()

    def init_search(self):
        self.visited = [False for _ in range(len(self.con_table))]

dists = [None for _ in range(N)]

from collections import deque

def dfs(tree, s):
    tree.init_search()
    dists[s] = 0
    while not all(tree.visited):
        search = deque()
        tree.visited[s] = True
        search.append(s)
        while len(search) > 0:
            v = search.pop()
            for u in tree.con_table[v]:
                if not tree.visited[u]:
                    dists[u] = dists[v] + tree.weights[(min(u, v), max(u, v))]
                    tree.visited[u] = True
                    search.append(u)

for _ in range(N-1):
    u, v, w = map(int, input().split())
    U.append(u)
    V.append(v)
    W.append(w)

tree = Tree(U, V, W)

dfs(tree, 0)

print('\n'.join(('0' if d % 2 == 0 else '1') for d in dists))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**8)
N = int(input())
num_edges = N-1
edges = [list(map(int, input().split())) for i in range(num_edges)]

adj = [[] for i in range(N+1)]
for ed in edges:
    adj[ed[0]] += [[ed[1], ed[2]]]
    adj[ed[1]] += [[ed[0], ed[2]]]
col_list = [-1 for i in range(N+1)]
def recfun(v, col):
    col_list[v] = col #色を更新
    for ed in adj[v]: #隣接する頂点をみる
        if col_list[ed[0]] == -1: #更新していない場合
            if ed[1] % 2 == 0:
                recfun(ed[0], col) #偶数なら同じ色でその先をみる
            else:
                recfun(ed[0], 1-col) #奇数なら違う色でその先をみる
recfun(1, 0)
for col in col_list[1:]:
    print(col)

Submission status: Accepted

Solution code:
import numpy as np


def read():
    N = int(input().strip())  # N <= 10**5
    edges = dict()
    for i in range(N-1):
        # u[i] < v[i] は保証されている
        u, v, w = list(map(int, input().strip().split()))
        if u - 1 in edges.keys():
            edges[u - 1].update({v - 1: w % 2})
        else:
            edges.update({u - 1: {v - 1: w % 2}})
        if v - 1 in edges.keys():
            edges[v - 1].update({u - 1: w % 2})
        else:
            edges.update({v - 1: {u - 1: w % 2}})
    return N, edges


def solve(N, edges):
    c = [-1] * N  # -1: unvisited, 0: white, 1: black
    stack = list()
    c[0] = 0
    stack.append(0)
    while len(stack) > 0:
        s = stack.pop()
        for t in edges[s].keys():
            if c[t] == -1:
                if edges[s][t]:
                    c[t] = 1 - c[s]
                else:
                    c[t] = c[s]
                stack.append(t)
    return c


if __name__ == '__main__':
    inputs = read()
    colors = solve(*inputs)
    for col in colors:
        print("%d" % col)

Submission status: Accepted

Solution code:
import numpy as np


def read():
    N = int(input().strip())  # N <= 10**5
    to = [[] for _ in range(N)]
    cost = [[] for _ in range(N)]
    for i in range(N-1):
        # u[i] < v[i] は保証されている
        u, v, w = list(map(int, input().strip().split()))
        to[u-1].append(v-1)
        to[v-1].append(u-1)
        cost[u-1].append(w % 2)
        cost[v-1].append(w % 2)
    return N, to, cost


def solve(N, to, cost):
    c = [-1] * N  # -1: unvisited, 0: white, 1: black
    q = list()
    c[0] = 0
    q.append(0)
    while len(q) > 0:
        s = q.pop()
        for t, co in zip(to[s], cost[s]):
            if c[t] == -1:
                if co:
                    c[t] = 1 - c[s]
                else:
                    c[t] = c[s]
                q.append(t)
    return c


if __name__ == '__main__':
    inputs = read()
    colors = solve(*inputs)
    for col in colors:
        print("%d" % col)

Submission status: Accepted

Solution code:
n = int(input())
pea = [[] for _ in range(n + 1)]
for _ in range(n - 1):
    u, v, w = map(int, input().split())
    w %= 2
    pea[u].append([v, w])
    pea[v].append([u, w])
ans = [-1] * (n + 1)
ans[1]=1
nodes=[1]
used=set()
used.add(1)
ansi=1
while nodes:
    nn=[]
    for i in nodes:
        ansi=ans[i]
        for u,w in pea[i]:
            if u in used:continue
            ans[u]=(ansi+w)%2
            used.add(u)
            nn+=[u]
    nodes=nn
for x in ans[1:]:
    print(x)

Submission status: Accepted

Solution code:
# from collections import defaultdict
# dd = defaultdict(lambda: 0)

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

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

opened = {0}
g0 = {0}
used = {0}

while len(opened) != 0:
    n = opened.pop()
    for n2 in T[n]:
        if n2 in used:
            continue
        if n in g0:
            if T[n][n2] % 2 == 0:
                g0.add(n2)
        else:
            if T[n][n2] % 2 == 1:
                g0.add(n2)
        opened.add(n2)
        used.add(n2)

for i in range(N):
    print(0 if i in g0 else 1)

Submission status: Accepted

Solution code:
# 入力が10**5とかになったときに100ms程度早い
import sys
read = sys.stdin.readline


def read_ints():
    return list(map(int, read().split()))


def read_a_int():
    return int(read())


def read_matrix(H):
    '''
    H is number of rows
    '''
    return [list(map(int, read().split())) for _ in range(H)]


def read_map(H):
    '''
    H is number of rows
    文字列で与えられた盤面を読み取る用
    '''
    return [read()[:-1] for _ in range(H)]


def read_col(H, n_cols):
    '''
    H is number of rows
    n_cols is number of cols

    A列、B列が与えられるようなとき
    '''
    ret = [[] for _ in range(n_cols)]
    for _ in range(H):
        tmp = list(map(int, read().split()))
        for col in range(n_cols):
            ret[col].append(tmp[col])

    return ret


N = read_a_int()

from collections import defaultdict
node = defaultdict(set)  # キーで指定したノードが隣接するノードを記録しておく。
for _ in range(N-1):
    u, v, w = read_ints()
    if w % 2:
        # wが奇数だったらTrue
        w = True
    else:
        w = False
    node[v-1].add((u-1, w))
    node[u-1].add((v-1, w))


# 0番目から探索していく
import numpy as np
ans = np.full(N, -1, dtype='int16')
# -1は未探索、1は黒、0は白、奇数の重みに当たるたびに反転
visited = np.full(N, False, dtype=bool)
from collections import deque
# 幅優先探索で白黒を記録していく
que = deque([(0, 0)])  # (nodeidx, 現在の色)
ans[0] = 0
visited[0] = True
while que:
    n, c = que.popleft()
    ans[n] = c

    for nex in node[n]:
        nex_node, nex_w = nex
        nex_color = c
        if visited[nex_node]:
            continue
        # 重みが奇数なら色を反転して探索に追加
        if nex_w:
            nex_color = 1-nex_color

        que.append((nex_node, nex_color))
        visited[nex_node] = True

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

Submission status: Accepted

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

noded = {}
edad = {}

class Node:
    def __init__(self, index):
        self.index = index
        self.color = -1
        self.eda_list = []

class Eda:
    def __init__(self, index, w, left, right):
        self.index = index
        self.w = w
        self.left = left
        self.right = right

def color_oppo_of(node):
    c = node.color
    for eda in [edad[edai] for edai in node.eda_list]:
        if eda.right == node.index:
            oppo = eda.left
        else:
            oppo = eda.right

        if noded[oppo].color == -1:
            if eda.w % 2 == 0:
                noded[oppo].color = node.color
            else:
                noded[oppo].color = (node.color + 1) % 2
            color_oppo_of(noded[oppo])

def solve():
    n = int(input())
    if n == 1:
        print("0")
    else:
        do(n)


def do(n):
    for i in range(n-1):
        U, V, W = map(int, input().split())
        u = U
        v = V
        w = W

        eda = Eda(i, w, u, v)
        edad[i] = eda

        if u not in noded.keys():
            noded[u] = Node(u)
        noded[u].eda_list.append(i)

        if v not in noded.keys():
            noded[v] = Node(v)
        noded[v].eda_list.append(i)

    noded[1].color = 0
    color_oppo_of(noded[1])

    for i in range(1, n+1):
        print(noded[i].color)
        #print(vars(noded[i]))



solve()

Submission status: Accepted

Solution code:
N=int(input())
from collections import defaultdict
branch=defaultdict(dict)
for i in range(N-1):
    u,v,w=map(int,input().split())
    branch[u-1][v-1]=w
    branch[v-1][u-1]=w
dist=[float('inf')]*N
dist[0]=0
check={0}
while len(check)>0:
    now=check.pop()
    for nex,w in branch[now].items():
        if dist[nex]>dist[now]+w:
            dist[nex]=dist[now]+w
            check|={nex}
color=[d%2 for d in dist]
for i in range(N):
    print(color[i])

Submission status: Accepted

Solution code:
import sys
import Queue

n = int(raw_input())

graph = dict()
color = [-1 for i in range(0, n)]
for i in range(0, n - 1):
    u, v, w = map(int, raw_input().split(" "))
    if (u - 1) in graph:
        graph[u - 1].append((v-1, w))
    else:
        graph[u - 1] = [(v-1, w)]

    if (v - 1) in graph:
        graph[v - 1].append((u - 1, w))
    else:
        graph[v - 1] = [(u - 1, w)]

# for start, value_list in graph.items():
#     for end, weight in value_list:
#         print("%s -> %d (%d)" % (start, end, weight))

queue = Queue.Queue()
sum = 0
next_check = 0

while True:
    if sum >= n:
        break

    for i in range(next_check, n):
        if color[i] < 0:
            queue.put(i)
            color[i] = 0
            sum += 1
            next_check = i
            break

    while True:
        if queue.empty():
            break

        current_node = queue.get()
        if current_node in graph:
            for end, weight in graph[current_node]:
                if color[end] < 0:
                    color[end] = (color[current_node] + weight % 2) % 2
                    queue.put(end)
                    sum += 1

for node in range(0, n):
    print(color[node])

Submission status: Accepted

Solution code:
from collections import deque
import math
from functools import reduce

def s(generator, splitter, mapper):
    return [ mapper(s) for s in generator().split(splitter) ]

# スペース区切りの入力を読み込んで数値リストにして返します。
def get_nums_l():
    return [ int(s) for s in input().split(" ")]

# 改行区切りの入力をn行読み込んで数値リストにして返します。
def get_nums_n(n):
    return [ int(input()) for _ in range(n)]

n = int(input())
ans = [-1] * n
ans[0] = 0

edges = [ [] for _ in range(n)]
for i in range(n-1):
    u,v,w = get_nums_l()
    edges[u-1].append([v-1,w%2==0])
    edges[v-1].append([u-1,w%2==0])

def aaa(x):
    # xを含むエッジ

    # breakpoint()

    for edge in edges[x]:
        to = edge[0] # edgeのうちxじゃないほう
        if ans[to] != -1:
            continue
        same = edge[1]
        ans[to] = ans[x] ^ (not same)

        queue.append(to)

queue = deque()
queue.append(0)
while queue:
    aaa(queue.popleft())
for annn in ans:
    print(annn)

Submission status: Accepted

Solution code:
N = int(input())
to = [[] for _ in range(N)]
cost = [[] for _ in range(N)]

for _ in range(N - 1):
  a, b, w = map(int, input().split())
  a -= 1
  b -= 1
  to[a].append(b)
  to[b].append(a)
  cost[a].append(w)
  cost[b].append(w)

ans = [-1 for _ in range(N)]
queue = []
queue.append(0)
while len(queue) > 0:
  v = queue.pop(0)
  for i in range(len(to[v])):
    u = to[v][i]
    w = cost[v][i]
    if ans[u] != -1:
      continue
    ans[u] = (ans[v] + w) % 2
    queue.append(u)

for a in ans:
  print(a)

Submission status: Accepted

Solution code:
def d_even_relation(N, Nodes):
    from collections import deque
    graph = [{} for _ in range(N)]
    for u, v, w in Nodes:
        graph[u - 1][v - 1] = w
        graph[v - 1][u - 1] = w

    distance_from_root = [0] * N  # 頂点1を根としたときの、各頂点への距離
    queue = deque([(-1, 0, 0)])  # 親の頂点番号、子の頂点番号、根から親までの距離
    while queue:
        parent, child, distance = queue.pop()
        if parent != -1:  # 今調べている頂点が根でない
            distance += (graph[parent][child] % 2)  # 偶奇だけわかればいい
            distance_from_root[child] = distance
        for k in graph[child].keys():
            if parent != k:  # 木を「逆戻り」しない頂点だけ調べる
                queue.appendleft((child, k, distance))
    ans = (1 if d % 2 == 0 else 0 for d in distance_from_root)
    return '\n'.join(map(str, ans))

N = int(input())
Nodes = [[int(i) for i in input().split()] for j in range(N - 1)]
print(d_even_relation(N, Nodes))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

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

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

for u, v, w in edge:
    u -= 1; v -= 1
    ad[u].append((v,w))
    ad[v].append((u,w))

ans = [0]*N

def dfs(v=0,pv=-1,d=0):
    if d % 2 == 0:
        ans[v] = 1
    for nv,w in ad[v]:
        if nv != pv:
            dfs(nv,v,d+w)

dfs()

for a in ans:
    print(a)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(100000)
nnn = int(input())

a = [-2 for i in range(nnn)]
a[0] = 0

def m():
	return map(int,input().split())


def oon(x,n,nn,k):
	global a
	for i in range(len(x[n])):
		if x[n][i][0] != nn and a[nn] != -2:
			p = (k + x[n][i][1]) % 2
			if p == 0:
				a[x[n][i][0]] = 0
			else:
				a[x[n][i][0]] = 1
			oon(x,x[n][i][0],n,p)



b = [[] for i in range(nnn)]

for i in range(nnn-1):
	z,x,c = m();
	b[z-1].append([x-1,c])
	b[x-1].append([z-1,c])

oon(b,0,0,0)

for i in range(nnn):
	print(a[i])

Submission status: Accepted

Solution code:
from collections import deque


class Node:
    def __init__(self, id, w):
        self.id = id
        self.w = w


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

nodes = {1: Node(1, 0)}
q = deque([nodes[1]])
while len(q) > 0:
    node = q.pop()
    for v, w in pairs[node.id]:
        if v not in nodes:
            nodes[v] = Node(v, node.w + w)
            q.append(nodes[v])

for i in range(1, N + 1):
    print(nodes[i].w % 2)

Submission status: Accepted

Solution code:
from sys import setrecursionlimit, getrecursionlimit
setrecursionlimit(getrecursionlimit()*10000)
from collections import defaultdict
g = defaultdict(list)
visited = defaultdict(bool)
N = int(input())
ans = [0] * N

def dfs(v, d=0):
    if visited[v]:
        return
    visited[v] = True
    if d % 2:
        ans[v-1] = 1
    for c,w in g[v]:
        dfs(c, d+w)

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

dfs(1)

for a in ans:
    print(a)

Submission status: Accepted

Solution code:
import sys
from collections import deque

def solve(tree, u, v):

    colors = {}
    colors[u] = 0
    stack = deque([u])
    while stack:
        u = stack.pop()
        for v in tree[u]:
            if v in colors:
                continue

            stack.append(v)
            if tree[u][v] % 2 == 0:
                colors[v] = colors[u]
            else:
                colors[v] = 0 if colors[u] == 1 else 1

    sorted(colors)
    for c in colors:
        print colors[c]

if __name__ == '__main__':

    tree = {}
    n = sys.stdin.readline().strip()
    for _ in xrange(int(n)-1):
        u, v ,w = map(int, sys.stdin.readline().strip().split(" "))
        if u not in tree:
            tree[u] = {}
        if v not in tree:
            tree[v] = {}
        tree[u][v] = w
        tree[v][u] = w

    solve(tree, u, v)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(100000)
n = int(input())
# n = 10000
d = [set() for i in range(n)]
cost = {}
for i in range(n-1):
    u,v,w = map(int,input().split())
    # u,v,w = i,i+1,i
    d[u-1].add(v-1)
    d[v-1].add(u-1)
    cost[(u-1,v-1)] = w%2
    cost[(v-1,u-1)] = w%2

visited = [False for i in range(n)]
colors = [0 for i in range(n)]

stack = []
def dfs(v,c):
    visited[v] = True
    colors[v] = c%2
    for i in d[v]:
        if not visited[i]:
            dfs(i,c+cost[(v,i)])

dfs(0,0)

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

Submission status: Accepted

Solution code:
N = int(input())
W = [ [] for _ in range(N) ]
dist = [-1] * N
dist[0] = 0

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

lst = [ ( 0 ,0, -1)]
idx = 0
while len(lst) > idx:
    cur, d, prev = lst[idx]
    idx += 1
    for v, w in W[cur]:
        if v == prev:
            continue
        dist[v] = d + w
        lst.append( (v, dist[v], cur))

for ans in dist:
    print(ans % 2)

Submission status: Accepted

Solution code:
from collections import defaultdict
import sys
input = sys.stdin.readline
N = int(input())

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


# 任意の1点を選んで周辺を判定していく
FROM, TO = 0, 1
q = [(TO, FROM)]

paint_dict = defaultdict(int)
# 明示的な代入
paint_dict[TO] = 0

idx = 0
while idx < N:
    # 現在のノード(now)から隣接ノード(to)の白黒を定め，そのノードを探索のqに回す
    now_node, prev_node = q[idx]
    for to_node, w in tree_dict[now_node]:
        if to_node != prev_node:
            if (w + paint_dict[now_node]) % 2 == 0:
                paint_dict[to_node] = 0
            else:
                paint_dict[to_node] = 1
            q.append((to_node, now_node))
    idx += 1
for i in range(N):
    print(paint_dict[i+1])

Submission status: Accepted

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

from heapq import heappush, heappop
inf = float('inf')
# (始点,隣接リスト)
def dijkstra(start,ad):
    dist = [inf]*len(ad)
    dist[start] = 0
    pq = [(start,0)]
    while pq:
        v = heappop(pq)[0]
        for nv,nw in ad[v]:
            if dist[nv] > dist[v] + nw:
                dist[nv] = dist[v] + nw
                heappush(pq,(nv,dist[nv]))
    return dist

N = int(input())

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

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

dist = dijkstra(0,ad)

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

Submission status: Accepted

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

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

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

link_dic = defaultdict(list)

for u, v, w in uvw:
	link_dic[u-1].append((v-1, w))
	link_dic[v-1].append((u-1, w))
# print(link_dic)
searched = [0]*N
color = [0]*N
color[0] = 1
def dfs(i):
	# print(i)
	for node, w in link_dic[i]:
		if searched[node] == 1:
			continue
		else:
			if w % 2 == 0:
				color[node] = color[i]
			else:
				color[node] = color[i] * (-1)
			searched[node] = 1
			dfs(node)

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

Submission status: Accepted

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

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

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

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

Submission status: Accepted

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

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



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

Submission status: Accepted

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

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

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

for ans in used:
    print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N = int(input())

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

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

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


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

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

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

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

Submission status: Accepted

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

visited = [False]*N
from collections import deque

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

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

Submission status: Accepted

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

Submission status: Accepted

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

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

deq = deque()
deq.appendleft(1)

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

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

Submission status: Accepted

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

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

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

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000)
 
nVertices = int(input())
edges = [[] for _ in range(nVertices + 1)]
length = {}
for _ in range(nVertices - 1):
    u, v, l = map(int, input().split())
    edges[u].append(v)
    edges[v].append(u)
    if u > v:
        u, v = v, u
    length[(u, v)] = l
color = [None] * (nVertices + 1)
color[1] = 0
 
def dfs(par, v):
    for child in edges[v]:
        if child != par:
            key = (min(v, child), max(v, child))
            if length[key] & 1 == 0:
                color[child] = color[v]
            else:
                color[child] = color[v] ^ 1
            dfs(v, child)
 
dfs(0, 1)
print('\n'.join(map(str, color[1:])))

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# coding: utf-8

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


if __name__ == '__main__':
    main()

Submission status: Accepted

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

import sys
sys.setrecursionlimit(1000000)

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

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

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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import collections

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

Submission status: Accepted

Solution code:
# 木の深さ優先探索
import sys

sys.setrecursionlimit(100000+10)


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

def dfs(vertex, distance_from_start):
	global colors

	colors[vertex] = distance_from_start % 2

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

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

G = [[] for _ in range(n)] #グラフの隣接リスト表現
for edge in edges:
	add_edge(edge[0]-1, edge[1]-1, edge[2])

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

dfs(0, 0)

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

Submission status: Accepted

Solution code:
from collections import deque

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

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

Submission status: Accepted

Solution code:
n = int(input())
from collections import deque
#隣接リストedge
edge = [[] for i in range(n)]
d = [-1] * n
#入力
for i in range(n-1):
    x,y,cost = map(int,input().split())
    #edge[x].append([cost,y])
    #edge[y].append([cost,x])
    x -=1
    y -=1
    cost %=2
    edge[x].append((cost,y))
    edge[y].append((cost,x))
q = deque()
q.append(0)
d[0] =0
while q:
    t = q.popleft()
    for s in edge[t]:
        if d[s[1]] == -1:
            d[s[1]] = d[t] + s[0]
            q.append(s[1])
for i in d:
    print(i%2)