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 collections import defaultdict
import queue


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

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

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

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


N = int(input())
g = Graph()
q = queue.Queue()
ans = [-1] * N
ans[0] = 0  # 最初の色はどちらでも良いので 0 とする
q.put(0)

for i in range(N-1):
    src, dst, weight = map(int, input().split())
    src -= 1
    dst -= 1
    g.add_edge(src, dst, weight % 2)
    g.add_edge(dst, src, weight % 2)

while not q.empty():
    v = q.get()
    for i in range(len(g.graph[v])):
        u, w = g.graph[v][i]

        # 来てたならスキップ
        if ans[u] != -1:
            continue

        ans[u] = (ans[v] + w) % 2  # w is 0 or 1
        q.put(u)

for a in ans:
    if a < 0:
        a = 0
    print(a)

Submission status: Accepted

Solution code:
import sys
from collections import deque


def bfs(s):
    color_list[s] = 0
    flag_list[s] = 1
    q.append(s)
    while len(q) > 0:
        u = q.popleft()
        for v, w in m_list[u]:
            if flag_list[v] == 0:
                flag_list[v] = 1
                if w%2 == 0:
                    color_list[v] = color_list[u]
                else:
                    color_list[v] = (color_list[u]+1)%2
                q.append(v)
        flag_list[u] = 2


if __name__ == "__main__":
    input = sys.stdin.readline
    n = int(input())
    m_list = [[]*n for _ in range(n)]
    color_list = [0]*n
    flag_list = [0]*n
    q = deque([])
    for _ in range(n-1):
        u, v, w = map(int, input().split())
        m_list[u-1].append([v-1, w])
        m_list[v-1].append([u-1, w])
    bfs(0)
    for color in color_list:
        print(color)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
ri = lambda: int(input())
#rl = lambda: [int(x) if x.isdecimal() else x for x in input().split()]
#rl = lambda: list(input().split()))
rl = lambda: map(int,input().split())
rr = lambda N: [list(l) for l in zip(*[rl() for _ in range(N)])]
YN = lambda b: print('YES') if b else print('NO')
yn = lambda b: print('Yes') if b else print('No')
OE = lambda x: print('Odd') if x%2 else print('Even')
INF = 10**18
MOD = 10**9+7

N = ri()
coler = [0]*N
ME = [None]*N
MO = [None]*N
UVW=[]
for i in range(N-1):
    u,v,w = rl()
    u -= 1
    v -= 1
    if w%2 == 1:
        if MO[u] == None:
            MO[u] = [v]
        else:
            MO[u].append(v)
        if MO[v] == None:
            MO[v] = [u]
        else:
            MO[v].append(u)
    else:
        if ME[u] == None:
            ME[u] = [v]
        else:
            ME[u].append(v)
        if ME[v] == None:
            ME[v] = [u]
        else:
            ME[v].append(u)

from collections import deque
q = deque([0])
visited = [False]*N
while len(q)>0:
    n = q.popleft()
    if visited[n] == True:
        continue
    else:
        visited[n] = True
    v = coler[n]
    e = ME[n]
    if not e is None:
        q.extend(e)
        for en in e:
            coler[en] = v
    o = MO[n]
    if not o is None:
        v += 1
        q.extend(o)
        for on in o:
            coler[on] = v

for c in coler:
    print(c%2)

Submission status: Accepted

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

rel = {x:{} for x in range(1, N + 1)}
for u, v, w in UVW:
	rel[u][v] = w
	rel[v][u] = w

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

#print(rel)

route = [x for x in range(N, 0, -1)]
while route:
	#print(route)
	current = route.pop()
	for k, v in rel[current].items():
		if -1 == visited[k]:
			route += [k]
		if not v % 2:
			visited[k] = visited[current]
		else:
			visited[k] = (visited[current] + 1) % 2
	#print(visited)

for node in visited[1:]:
	print(node)

Submission status: Accepted

Solution code:
# 根をテキトーに選んで各頂点へのパスにおけるパリティを求める
# （なぜ根からで良いのかはパリティと木の性質によるもの）
# 答えはそのままパリティを出力する

from queue import Queue

# 隣接リスト、隣接コストを作る
n = int(input())

to = [[] for _ in range(n)]
cost = [[] for _ in range(n)]

for _ in range(n-1):
    u, v, w = map(int, input().split())

    # 各頂点の番号を添え字に合わせてデクリメントする
    # 答えに影響なし
    u-=1
    v-=1


    to[u].append(v)
    cost[u].append(w)

    to[v].append(u)
    cost[v].append(w)    


# 任意の点から初めてBFSで頂点をたどりながら、パリティを獲得していく
## BFS（queueに突っ込んでいって、なくなるまで頂点を辿っていく）

q = Queue()

ans = [-1] * n
q.put(0)

while not q.empty():
    u = q.get()
    
    for i in range(len(to[u])):
        v = to[u][i]
        w = cost[u][i]

        if (ans[v] != -1): continue

        ans[v] = (ans[u] + w) % 2
        q.put(v)
        

for a in ans:
    print(a)

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
N = int(input())
edge = [[] for i in range(N)]
color = [-1 for i in range(N)]
for i in range(N-1):
    u,v,w = map(int,input().split())
    u -= 1
    v -= 1
    w %= 2
    edge[u].append((v,w))
    edge[v].append((u,w))
search = [(e, 0) for e in edge[0]]
color[0] = 0
while len(search) > 0:
    e,c = search.pop()
    n,w = e[0],e[1]
    if color[n] >= 0:
        continue
    color[n] = (c + w) % 2
    search += [(e,color[n]) for e in edge[n]]

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

Submission status: Accepted

Solution code:
n=int(input())
l=[]
for i in range(n-1):
    a=[int(j) for j in input().split()]
    l.append(a)

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()
for src, dst, weight in l:
    g.add_edge(src, dst, weight)
    g.add_edge(dst, src, weight)

d = Dijkstra(g, 1)  
for i in range(n):
    if d.shortest_distance(i+1)%2==0:
        print(0)
    else:
        print(1)

Submission status: Accepted

Solution code:
N = int(input())
tree = []
for i in range(0, N):
	tree.append([])
for i in range(0, N-1):
	u, v, w = map(int, input().split())
	tree[u-1].append([v-1, w])
	tree[v-1].append([u-1, w])
oddeven = []
for i in range(0, N):
	oddeven.append(-1)
stack = [[0, 0]]
while stack != []:
	now = stack.pop(-1)
	oddeven[now[0]] = now[1]%2
	for i in range(0, len(tree[now[0]])):
		if oddeven[tree[now[0]][i][0]] == -1:
			stack.append([tree[now[0]][i][0], now[1]+tree[now[0]][i][1]])
for i in range(0, N):
	print(oddeven[i])

Submission status: Accepted

Solution code:
import numpy as np
N=int(input())
G=[[] for n in range(N+1)]
for n in range(N-1):
    [u,v,w]=[int(_) for _ in input().split()]
    G[u].append(v*((-1)**w))
    G[v].append(u*((-1)**w))
D=[-1 for n in range(N+1)]
V=[0,1]
while V!=[0]:
    now=V[1]
    for nex in G[now]:
        if D[abs(nex)]==-1:
            if np.sign(nex)==1:
                D[abs(nex)]=D[now]%2
            else:
                D[abs(nex)]=(D[now]+1)%2
            V.append(abs(nex))
    V.pop(1)
for n in range(1,N+1):
    print(D[n])

Submission status: Accepted

Solution code:

import sys
input = sys.stdin.readline

n = int(input())

connect_list = [ [] for i in range(n) ]
distance_list = [ -1 for i in range(n) ]
color_list = [ "Gray" for i in range(n) ]
distance_list[0] = 0

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

search_list = [0]

t = 0
stop = 0
while t < len(search_list):
	s = search_list[t]
	stop = 0
	for i in connect_list[s]:
		if distance_list[i[0]] == -1:
			distance_list[i[0]] = (distance_list[s] + i[1]) % 2
			search_list.append(i[0])
	t += 1


for i in distance_list:
	print(i)

Submission status: Accepted

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

n = int(input())

connect_list = [ [] for i in range(n) ]
distance_list = [ -1 for i in range(n) ]
color_list = [ "Gray" for i in range(n) ]
distance_list[0] = 0

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

search_list = [0]


while search_list != []:
	s = search_list[0]
	for i in connect_list[s]:
		if distance_list[i[0]] == -1:
			distance_list[i[0]] = (distance_list[s] + i[1]) % 2
			search_list.append(i[0])
	del search_list[0]

for i in distance_list:
	print(i)

Submission status: Accepted

Solution code:

import sys
input = sys.stdin.readline

n = int(input())

connect_list = [ [] for i in range(n) ]
distance_list = [ -1 for i in range(n) ]
color_list = [ "Gray" for i in range(n) ]
distance_list[0] = 0

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

search_list = [0]


while search_list != []:
	s = search_list[0]
	for i in connect_list[s]:
		if distance_list[i[0]] == -1:
			distance_list[i[0]] = (distance_list[s] + i[1]) % 2
			search_list.append(i[0])
	del search_list[0]

for i in distance_list:
	print(i)

Submission status: Accepted

Solution code:
n = int(input())

connect_list = [ [] for i in range(n) ]
distance_list = [ -1 for i in range(n) ]
color_list = [ "Gray" for i in range(n) ]
distance_list[0] = 0

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

search_list = [0]


while search_list != []:
	s = search_list[0]
	for i in connect_list[s]:
		if distance_list[i[0]] == -1:
			distance_list[i[0]] = (distance_list[s] + i[1]) % 2
			search_list.append(i[0])
	del search_list[0]

for i in distance_list:
	print(i)

Submission status: Accepted

Solution code:
n = int(input())
lines = [[] for i in range(n)]
for i in range(n-1):
	u,v,w = map(int,input().split())
	u-=1
	v-=1
	lines[u].append([v,w])
	lines[v].append([u,w])
# print(lines)
ans = [0 for i in range(n)]
q = [[0,0,-1]]
while q:
	u,w,v = q.pop(0)
	if w%2 == 0:
		ans[u] = 0
	else:
		ans[u] = 1
	for n,ww in lines[u]:
		if n == v:
			continue
		q.append([n,w+ww,u])
	# print(q)
	# print(ans)
for a in ans:
	print(a)

Submission status: Accepted

Solution code:
from collections import deque

n = int(input())
neighbor = {}
for _ in range(n - 1):
    u, v, w = map(int, input().split())
    if u not in neighbor:
        neighbor[u] = deque()
    if v not in neighbor:
        neighbor[v] = deque()
    neighbor[u].append((v, w))
    neighbor[v].append((u, w))

color = {1: 0}
visited = set([1])
queue = deque([(1, 0)])

while len(queue) > 0:
    v, wsum = queue.pop()
    for u, w in neighbor[v]:
        if u in visited:
            continue
        visited.add(u)
        color[u] = (wsum + w) % 2
        queue.append((u, wsum + w))

for i in range(n):
    print(color[i + 1])

Submission status: Accepted

Solution code:
from collections import deque

N = int(input())

A = {}
COLOR = [1] * N

for _ in range(N - 1):
  u, v, w = map(int, input().strip().split(' '))
  if u not in A: A[u] = {}
  if v not in A: A[v] = {}
  A[u][v] = w
  A[v][u] = w


def test(key, total_w=0):
  if key not in A:
    return

  COLOR[key - 1] = 0 if total_w % 2 == 0 else 1

  v = A.pop(key)
  for k, w in v.items():
    test(k, w + total_w)


queue = deque()
queue.append((1, 0))
current_key = 1

while len(queue) > 0:
  key, w = queue.popleft()
  if key not in A:
    continue

  COLOR[key - 1] = 0 if w % 2 == 0 else 1

  for child in A.pop(key).items():
    if child[0] in A:
      queue.append((child[0], w + child[1]))

for c in COLOR:
  print(c)

Submission status: Accepted

Solution code:
n = int(input())

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

colors = [None for _ in range(n+1)]
colors[1] = 0

edges = [dict() for _ in range(n+1)]

for u, v, w in uvws:
    edges[u][v] = w
    edges[v][u] = w

plan = set((1,))

while len(plan) > 0:
    g = plan.pop()
    for n, w in edges[g].items():
        if colors[n] is None:
            colors[n] = (colors[g] + w) % 2
            plan.add(n)

print("\n".join(map(str, colors[1:])))

Submission status: Accepted

Solution code:
n = int(input())
l = [[]for i in range(n)]
for i in range(n-1):
    u, v, w = map(int, input().split())
    u -= 1
    v -= 1
    l[u].append([v, w])
    l[v].append([u, w])
c = [-1] * (n-1)
color = [0] + c
x = [0]
while x:
    current = x.pop(0)
    for y, d in l[current]:
        if color[y] > -1:
            continue
        color[y] = (color[current] + d)%2
        x.append(y)
for col in color:
    print(col)

Submission status: Accepted

Solution code:
n = int(input())

info = [[] for _ in range(0,n+1)]

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

#print(info)

frt = [1]
dis = [0] * (n+1)

while frt != []:
    x = frt.pop()
    for j in range(0,len(info[x])):
        dis[info[x][j][0]] = dis[x] + info[x][j][1]
        info[info[x][j][0]].remove([x,info[x][j][1]])
        frt.append(info[x][j][0])

for k in range(1,n+1):

    if dis[k] % 2 ==0:
        print(0)
    else:
        print(1)

Submission status: Accepted

Solution code:
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=int(input())
uf=WeightedUnionFind(n)
for i in range(n-1):
    u,v,w=map(int, input().split())
    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())
uvw=list(list(map(int,input().split())) for _ in range(N-1))

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

colors=[-1]*N
colors[0]=0
queue=deque([1])

while len(queue)>0:
    x=queue.popleft()
    if all(colors[i]!=-1 for i in range(N)):
        break
    for j in graph_list[x-1]:
        if colors[j[0]-1]==-1:
            queue.append(j[0])
            colors[j[0]-1]=(2+colors[x-1]+j[1])%2
for p in colors:
    print(p)

Submission status: Accepted

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

def DFS(v, p ,c):
    res[v] = c
    for next in tree[v]:
        if next[0] == p:
            continue
        if next[1] % 2:
            DFS(next[0], v, 1-c)
        else:
            DFS(next[0], v, c)


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

    u, v, w = map(int, input().split())
    tree[u-1].append([v-1, w])
    tree[v-1].append([u-1, w])

DFS(0, -1, 1)

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

Submission status: Accepted

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

D = [-1 for k in range(N)]
D[G[0][0][0]] = 0
Q = [G[0][0]]

while len(Q) > 0:
    now = Q.pop()
    ima = now[0]
    for tsugi in G[ima]:
        if D[tsugi[0]] == -1:
            D[tsugi[0]] = tsugi[1] + D[ima]
            Q.append(tsugi)

for d in D:
    if d%2 == 0:
        print(0)
    else:
        print(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:
    print(0 if di % 2 else 1)

Submission status: Accepted

Solution code:
n = int(input())
tree = [[] for i in range(n+1)]

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

#print(tree)
stack=[1]
visitted={}
ans=[0]*n

while stack:
    cur = stack.pop()
    pre=ans[cur-1]
    visitted.setdefault(cur,1)
    #visitted.append(cur)
    for v, w in tree[cur]:
        if v in visitted:
            continue
        if w % 2 == 1:
            ans[v-1]=(pre+1)%2
        else:
            ans[v-1]=pre
        stack.append(v)

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

Submission status: Accepted

Solution code:
"""
解説と提出 #5739708をもとに作成
"""

import sys
sys.setrecursionlimit(10 ** 6)


def solve():
    N = int(input())
    result = [-1] * N
    uvw_map = [[] for _ in range(N)]
    '''枝毎の距離相関図を作る'''
    for i in range(N - 1):
        u, v, w = map(int, input().split())
        u -= 1
        v -= 1
        uvw_map[u].append([v, w])
        uvw_map[v].append([u, w])
    # 木の頂点を求める
    # -> 任意の場所で良い. 1 とする.
    # 頂点から順に塗っていく
    result[0] = False
    result = paint(uvw_map, 0, result)
    for i in result:
        print(int(i))


def paint(uvw_map, num, result):
    # num に紐づくノードの一覧を取得する
    num_map = uvw_map[num]
    # num との距離に応じて色を決定する
    nums = []
    for v, w in num_map:
        if result[v] != -1:
            continue
        result[v] = result[num] if w % 2 == 0 else not(result[num])
        # # 色分けを行ったものについてのみ記録しておく(num')
        nums.append(v)
    # num' すべてに対して同様の操作を行う
    for n in nums:
        result = paint(uvw_map, n, result)
    return result


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
from collections import deque

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

dist = [-1 for i in range(n)]
stack = deque([0])
while( len(stack) != 0 ):
    current = stack.popleft()
    current_dist = dist[current]

    for neibor_n, neibor_w in neibors[current]:
        if dist[neibor_n] == -1:
            stack.append( neibor_n )
            dist[neibor_n] = (neibor_w + current_dist) % 2  

for item in dist:
    print(item)

Submission status: Accepted

Solution code:
n=int(input())
L=[[] for i in range(n)]
for i in range(n-1):
    u,v,w=map(int, input().split())
    u-=1
    v-=1
    L[u].append([v,w])
    L[v].append([u,w])
ans=[-1]*n
ans[0]=0
from collections import deque
stack=deque([])
stack.append(0)
while stack:
    v=stack.popleft()
    for u, w in L[v]:
        if ans[u]!=-1:
            continue
        ans[u]=(ans[v]+w)%2
        stack.appendleft(u)
for a in ans:
    print(a)

Submission status: Accepted

Solution code:
n=int(input())
L=[[] for i in range(n)]
for i in range(n-1):
    u,v,w=map(int, input().split())
    u-=1
    v-=1
    L[u].append([v,w])
    L[v].append([u,w])
ans=[-1]*n
ans[0]=0
from collections import deque
que=deque([])
que.append(0)
while que:
    v=que.popleft()
    for u, w in L[v]:
        if ans[u]!=-1:
            continue
        ans[u]=(ans[v]+w)%2
        que.append(u)
for a in ans:
    print(a)

Submission status: Accepted

Solution code:
n=int(input())
L=[[] for i in range(n)]
for i in range(n-1):
    u,v,w=map(int, input().split())
    u-=1
    v-=1
    L[u].append([v,w])
    L[v].append([u,w])
ans=[-1]*n
ans[0]=0
que=[0]
import queue
que=queue.Queue()
que.put(0)
while not que.empty():
    v=que.get()
    for u, w in L[v]:
        if ans[u]!=-1:
            continue
        ans[u]=(ans[v]+w)%2
        que.put(u)
for a in ans:
    print(a)

Submission status: Accepted

Solution code:
n=int(input())
L=[[] for i in range(n)]
for i in range(n-1):
    u,v,w=map(int, input().split())
    u-=1
    v-=1
    L[u].append([v,w])
    L[v].append([u,w])
ans=[-1]*n
ans[0]=0
stack=[0]
while stack:
    v=stack.pop()
    for u, w in L[v]:
        if ans[u]!=-1:
            continue
        ans[u]=(ans[v]+w)%2
        stack.insert(0,u)
for a in ans:
    print(a)

Submission status: Accepted

Solution code:
n=int(input())
L=[[] for i in range(n)]
for i in range(n-1):
    u,v,w=map(int, input().split())
    u-=1
    v-=1
    L[u].append([v,w])
    L[v].append([u,w])
ans=[-1]*n
ans[0]=0
que=[0]
while que:
    v=que.pop()
    for u, w in L[v]:
        if ans[u]!=-1:
            continue
        ans[u]=(ans[v]+w)%2
        que.append(u)
for a in ans:
    print(a)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(1000000)

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

V = [0] * N
D = [0] * N
C = [0] * N


def dfs(n, c):
    if V[n] == 1:
        return
    C[n] = c
    V[n] = 1
    for w in M[n]:
        if w[1] % 2 == 0:
            dfs(w[0], c)
        else:
            dfs(w[0], (c + 1) % 2)

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

Submission status: Accepted

Solution code:
import queue

n = int(input())
links = [set() for _ in [0] * n]
for i in range(n-1):
    u, v, w = map(int, input().split())
    u -= 1
    v -= 1
    links[u].add((v, w))
    links[v].add((u, w))
ans = [-1] * n
q = queue.Queue()
q.put((0, 0, -1))
while not q.empty():
    v, d, p = q.get()
    if d % 2 == 0:
        ans[v] = 0
    else:
        ans[v] = 1
    for u, w in links[v]:
        if u == p:
            continue
        q.put((u, d + w, v))
for i in ans:
    print(i)

Submission status: Accepted

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

def dfs(v, p, c):
    res[v] = c
    for next in link[v]:
        if next[0] == p:
            continue
        if next[1] % 2:
            dfs(next[0], v, 1-c)
        else:
            dfs(next[0], v, c)


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

dfs(0, -1, 1)

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

Submission status: Accepted

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

def dfs(v, p, c):
    #vを根にしてまずそれをcに塗るっていう意味なはず、、、そう考えると、、
    res[v] = c
    for next in link[v]:
        if next[0] == p:
            continue
        # next[1]%2==1　というのは根からの距離が奇数になるという意味　だから　1-cにしてdfsすればいいはず！！
        if next[1] % 2:
            dfs(next[0], v, 1-c)
        # 同じように考えれば こっちは根からの距離が偶数になるという意味　だからcでdfsかな
        else:
            dfs(next[0], v, c)


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

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

Submission status: Accepted

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

def dfs(v, p, c):
    res[v] = c
    for next in link[v]:
        if next[0] == p:
            continue
        if next[1] % 2:
            dfs(next[0], v, 1-c)
        else:
            dfs(next[0], v, c)


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

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

Submission status: Accepted

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

def dfs(v, p, c):
    res[v] = c
    for next in link[v]:
        if next[0] == p:
            continue
        if next[1] % 2:
            dfs(next[0], v, 1-c)
        else:
            dfs(next[0], v, c)


N = int(input())
link = [[]  for _ in range(N)]
res = [0] * N
for i in range(N-1):
    u, v, w = map(int, input().split())
    link[u-1].append([v-1, w])
    link[v-1].append([u-1, w])
    
dfs(0, -1, 1)
#print(link)
for i in range(N):
    print(res[i])

Submission status: Accepted

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


def func(v, c):
    for next_v, w in graph[v]:
        if color[next_v] == -1:
            color[next_v] = (c + w) & 1
            func(next_v, c + w) 

n = int(input())
graph = [[] for _ in range(n)]
color = [-1] * n

for _ in range(n-1):
    u, v, w = map(int, sys.stdin.readline().split())
    graph[u-1].append((v-1, w))
    graph[v-1].append((u-1, w))


color[0] = 0
func(0, 0)

for i in color:
    print(i)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(20000000)


def dfs(node, distance):
    for next_node, edge_size in G[node]:
        if ans[next_node] == -1:
            ans[next_node] = ((distance+edge_size) % 2)
            dfs(next_node, distance+edge_size)


N = int(input())

G = [[] for i 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])

ans = [-1]*N
dfs(0, 0)
print(*ans, sep='\n')

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(20000000)
#input = sys.stdin.readline
n = int(input())
g = [[] for i in range(n)]
for i in range(n-1):
    u,v,w = map(int,input().split())
    u-=1;v-=1
    g[u].append([v,w])
    g[v].append([u,w])
ans = [-1]*n
def dfs(x,y):
    for i,j in g[x]:
        if ans[i] == -1:
            ans[i] = (y+j)%2
            dfs(i,y+j)
dfs(0,0)
for i in ans:
    print(i)

Submission status: Accepted

Solution code:
N=int(input())
uvw=[list(map(int,input().split())) for _ in range(N-1)]
q=[[] for _ in range(N)]
max=10**15
dist=[0]+[max for i in range(N-1)]
for i in range(N-1):
    q[uvw[i][0]-1].append((uvw[i][1]-1,uvw[i][2]))
    q[uvw[i][1]-1].append((uvw[i][0]-1,uvw[i][2]))
now=0
now_d=0

while(True):
    if q[q[now][-1][0]]==[]:
        q[now].pop()
        if q[now]==[]:
            break
    if dist[q[now][-1][0]]!=max:
        if len(q[now])!=1:
            q[now]=[q[now][-1]]+q[now][:-1]
    posi=q[now][-1]
    if dist[posi[0]]==max:
        dist[posi[0]]=now_d+posi[1]
    now_d=dist[posi[0]]
    q[now].pop()
    now=posi[0]
    posi=q[posi[0]][0]
for i in range(N):
    if dist[i]%2==0:
        print(0)
    else:
        print(1)

Submission status: Accepted

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

def cur(current,e,dist,color):
    for it in e[current]:
        if color[it]!=-1: continue
        color[it]=(color[current]+dist[(it,current)])%2
        cur(it,e,dist,color)

N=int(input())
e=[[] for i in range(N+1)]
dist={}
for i in range(N-1):
    u,v,w=map(int,input().split())
    e[u].append(v)
    e[v].append(u)
    dist[(u,v)],dist[(v,u)]=w,w
memo=[-1]*N




color=[-1]*(N+1)
color[1]=0
cur(1,e,dist,color)

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