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:
# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math
import sys

mod = 10**9+7
sys.setrecursionlimit(mod) # 再帰回数上限はでdefault1000

N = int(input())
graph = [set() for i in range(N+1)]

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


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

# v は今見ている頂点，p はｖの親
def dfs(node,p,color): # Depth First Serch
    res[node] = color
    for new_node,w in graph[node]:
        if new_node == p:continue
        if w == 1:dfs(new_node,node,1-color)
        else:dfs(new_node,node,color)
#tree 探索　
# vは頂点，ｐは親
dfs(0,-1,0)

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

Submission status: Accepted

Solution code:
# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math
import sys



mod = 10**9+7
sys.setrecursionlimit(mod)

N = int(input())
graph = [set() for i in range(N+1)]

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


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

# v は今見ている頂点，p はｖの親
def dfs(node,p,color): # Depth First Serch
    res[node] = color
    for new_node,w in graph[node]:
        if new_node == p:
            pass
        else:
            if w == 1:dfs(new_node,node,1-color)
            else:dfs(new_node,node,color)
#tree 探索　
# vは頂点，ｐは親
dfs(0,-1,0)

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

Submission status: Accepted

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


def rec(edges, nodes, cp, cdistance, visited):
    if not visited[cp]:
        visited[cp] = True
        nodes[cp] = (cdistance % 2 == 0)
        if edges[cp]:
            for v, w in edges[cp]:
                rec(edges, nodes, v, cdistance + w, visited)


def main():
    N = int(input())
    nodes = [False] * N
    visited = [False] * N
    edges = [[] for _ in range(N)]

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

    rec(edges, nodes, 0, 0, visited)

    for n in nodes:
        print(0 if n else 1)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
n = int(input())
mark = [[[],[]]for _ in range(n+1)]
color = [0 for _ in range(n+1)]
done = set()
for i in range(n-1):
    a,b,c = map(int,sys.stdin.readline().split())
    if c&1:
        mark[a][1].append(b)
        mark[b][1].append(a)
    else:
        mark[a][0].append(b)
        mark[b][0].append(a)
run = [1]
temp = []
while(len(run))>0:
    next = run.pop(0)
    done.add(next)
    # print('NEXT:',next)
    if color[next]==0:
        for v in mark[next][1]:
            if v not in done:
                color[v]=1
                temp.append(v)
        for v in mark[next][0]:
            if v not in done:
                temp.append(v)
    else:
        for v in mark[next][0]:
            if v not in done:
                color[v] = 1
                temp.append(v)
        for v in mark[next][1]:
            if v not in done:
                temp.append(v)
    if len(run)==0:
        run=run+temp
        temp=[]
    # print('Then',color)
for i in range(1,n+1):
    sys.stdout.write(str(color[i])+'\n')

Submission status: Accepted

Solution code:
n = int(input())
edges = [set() for _ in range(n)]
for i in range(n-1):
    u,v,w = [int(i)-1 for i in input().split()] 
    edges[u].add((v,w+1))
    edges[v].add((u,w+1))
ans = [-1]*n
q = [(0,0,-1)]
while q:
    v,d,p = q.pop()
    if d%2 == 0:
        ans[v] = 0
    else:
        ans[v] = 1
    for u,w in edges[v]:
        if u == p:
            continue
        q.append((u,d+w,v))
for i in range(n):
    print(ans[i])

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(100000)

N = int(input())

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

dist = [-1 for _ in range(N)]
def measure(src):
    """
    srcを根とした木に対し、根から各頂点までの距離を求める
    """
    for v, w in edges[src]:
        if dist[v] == -1:
            dist[v] = dist[src] + w
            measure(v)

dist[0] = 0
measure(0)

for i in range(N):
    if dist[i] % 2:
        print(1)
    else:
        print(0)

Submission status: Accepted

Solution code:
def d_even_relation_dfs(N, Nodes):  # DFSによる
    import sys
    sys.setrecursionlimit(10**6)
    graph = [[] for _ in range(N)]
    for u, v, w in Nodes:  # 0-basedとする
        graph[u - 1].append((v - 1, w))
        graph[v - 1].append((u - 1, w))

    def distance_from_root(parent, current, distance, ret=[0] * N):  # 根(頂点0)から各頂点への距離
        def dfs(p, c, d):
            ret[c] = d
            for next_edge, dist in graph[c]:
                if next_edge != p:  # 木を「逆戻り」しない頂点だけ調べる
                    dfs(c, next_edge, d + dist)
        dfs(parent, current, distance)
        return ret
    ans = (1 if d % 2 == 0 else 0 for d in distance_from_root(-1, 0, 0))  # 根の親は-1番とする
    return ' '.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_dfs(N, Nodes))

Submission status: Accepted

Solution code:
def d_even_relation_bfs(N, Nodes):  # BFSによる
    from collections import deque
    graph = [[] for _ in range(N)]
    for u, v, w in Nodes:  # 0-basedとする
        graph[u - 1].append((v - 1, w))
        graph[v - 1].append((u - 1, w))
    distance_from_root = [0] * N  # 根(頂点0)から各頂点への距離

    queue = deque([(-1, 0, 0)])  # 親と現在の頂点番号、根から親までの距離
    while queue:
        parent, current, distance = queue.pop()
        distance_from_root[current] = distance
        for next_edge, dist in graph[current]:
            if parent != next_edge:  # 木を「逆戻り」しない頂点だけ調べる
                queue.appendleft((current, next_edge, distance + dist))
    ans = (1 if d % 2 == 0 else 0 for d in distance_from_root)
    return ' '.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_bfs(N, Nodes))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(pow(10, 6))

n = int(input())
nodes = [[] for _ in range(n)]
visited = [False for _ in range(n)]
dist = [0 for _ in range(n)]

def dfs(i, d):
  dist[i] = d
  for cn, c in nodes[i]:
    if not visited[cn]:
      visited[cn] = True
      dfs(cn, d+c)

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

visited[0] = True
dfs(0, 0)

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

Submission status: Accepted

Solution code:
import math
import sys
sys.setrecursionlimit(100000)
N=int(input())
edges=[[] for i in range(N+1)]
d=[-1 for i in range(N+1)]
for i in range(1,N):
	u,v,w=[int(i) for i in input().split()]
	edges[u].append([v,w])
	edges[v].append([u,w])
def kyori(u):
	for v,w in edges[u]:
		if d[v]==-1:
			d[v]=d[u]+w
			kyori(v)
d[1]=0
kyori(1)
for i in d[1:]:
	if i%2==0:
		print(1)
	else:
		print(0)

Submission status: Accepted

Solution code:
import math
import sys
sys.setrecursionlimit(30000)
N=int(input())
edges=[[] for i in range(N+1)]
d=[-1 for i in range(N+1)]
for i in range(1,N):
	u,v,w=[int(i) for i in input().split()]
	edges[u].append([v,w])
	edges[v].append([u,w])
def kyori(u):
	for v,w in edges[u]:
		if d[v]==-1:
			d[v]=d[u]+w
			kyori(v)
d[1]=0
kyori(1)
for i in d[1:]:
	if i%2==0:
		print(1)
	else:
		print(0)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)
n = int(input())
edge = [[] for i in range(n)]
colors = [0] * n
for i in range(n-1):
    u, v, w = [int(item) for item in input().split()] 
    u -= 1
    v -= 1
    edge[u].append([v, w % 2])
    edge[v].append([u, w % 2])
    
def dfs(frm, n, d):
    for tv, tw in edge[n]:
        if tv == frm:
            continue
        else:
            td = (d + tw) % 2
            if td == 1:
                colors[tv] = 1 
            else:
                colors[tv] = 0 
            dfs(n, tv, td)
    return True

colors[0] = 0
dfs(0, 0, 0)
for item in colors:
    print(item)

Submission status: Accepted

Solution code:

from collections import deque

def solve2():
    N = int(raw_input())
    to = [ [] for i in range(N) ]
    cost= [ [] for i in range(N) ]
    for i in range(N - 1):
        ui,vi,wi = [int(_) for _ in raw_input().split()]
        ui -= 1
        vi -= 1
        to[ui].append(vi)
        cost[ui].append(wi)
        to[vi].append(ui)
        cost[vi].append(wi)
    # BFS
    ret = [-1] * N
    que = deque()
    ret[0] = 0
    que.append(0)
    while len(que) > 0:
        visit = que.popleft()
        for i in range(len(to[visit])):
            u = to[visit][i]
            w = cost[visit][i]
            if ret[u] != -1:
                continue
            ret[u] = (ret[visit] + w) % 2
            que.append(u)
    for i in range(N):
        print ret[i]

if __name__ == '__main__':
    solve2()

Submission status: Accepted

Solution code:
N=int(input())

tree_list = []
for i in range(N):
  tree_list.append([])

for i in range(N-1):
  ui,vi,wi=map(int,input().split())
  tree_list[ui-1].append((vi-1,wi%2))
  tree_list[vi-1].append((ui-1,wi%2))

paint_list = [-1]*N
paint_list[0] = 0
queue = [0]
while(True):
  if len(queue) == 0:
    break  
  
  new_queue = []
  for q in queue:
    for u,w in tree_list[q]:
      if paint_list[u] == -1:
        paint_list[u] = paint_list[q]^w
        new_queue.append(u)
  queue = new_queue  
    
for i in paint_list:
  print(i)

Submission status: Accepted

Solution code:
import os, sys, re, math, queue

N = int(input())

nodes = {}
colors = [-1 for _ in range(N+1)]
for _ in range(N-1):
    s = input().split(' ')
    u,v,w = int(s[0]), int(s[1]), int(s[2])
    if u not in nodes:
        nodes[u] = [(v,w)]
    else:
        nodes[u].append((v,w))

    if v not in nodes:
        nodes[v] = [(u,w)]
    else:
        nodes[v].append((u,w))

q = queue.Queue()
f = list(nodes.keys())[0]
q.put((f,0))

while not q.empty():
    cur = q.get()
    colors[cur[0]] = cur[1]
    next = nodes[cur[0]]
    for n in next:
        if colors[n[0]] == -1:
            if n[1] % 2 == 0:
                q.put((n[0], cur[1]))
            else:
                q.put((n[0], (cur[1]+1) % 2))

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

Submission status: Accepted

Solution code:
import queue

N = int(input())
to_list = [ [] for i in range(N) ]
cost_list = [ [] for i in range(N) ]
ans = [ -1 for i in range(N) ]

for n in range(N - 1):
    a, b, w = map(int, input().split())
    a -= 1
    b -= 1
    to_list[a].append(b)
    to_list[b].append(a)
    cost_list[a].append(w)
    cost_list[b].append(w)

# FIFOキューの作成
q = queue.Queue()
q.put(0)

while(not q.empty()):
    v = q.get()
    for i in range(len(to_list[v])):
        u = to_list[v][i]
        w = cost_list[v][i]
        if ans[u] != -1:
            continue
        ans[u] = (ans[v] + w) % 2
        q.put(u)

for a in ans:
    print(a)

Submission status: Accepted

Solution code:
n=int(input())
uvw=[list(map(int,input().split())) for _ in range(n-1)]
uvw=[[u-1,v-1,w] for u,v,w in uvw]

z=[[] for _ in range(n)]
for u,v,w in uvw:
    z[u].append([u,v,w%2==0])
    z[v].append([v,u,w%2==0])
from collections import deque
que=deque([])
res=[-1 for _ in range(n)]
res[0]=0
for t in z[0]:
    que.append(t)

visited=[False for _ in range(n)]
visited[0]=True

while que:
    u,v,w=que.pop()
    if w:
        if res[u]>=0 and res[v]<0:
            res[v]=res[u]
        elif res[v]>=0 and res[u]<0:
            res[u]=res[v]
    else:
        if res[u]==0:
            res[v]=1
        elif res[u]==1:
            res[v]=0
        elif res[v]==0:
            res[u]=1
        elif res[v]==1:
            res[u]=1
    if visited[v]==False:
        visited[v]=True
        for t in z[v]:
            que.append(t)
for t in res:
    print(t)

Submission status: Accepted

Solution code:
from collections import deque

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

que = deque(tree[1])
dist = [-1]*(n+1)
dist[1] = 0
while len(que) > 0:
    u, v, w = que.popleft()
    dist[v] = dist[u]+w
    for un, vn, wn in tree[v]:
        if dist[vn] > 0:
            pass
        else:
            que.append((un, vn, wn))
            
for d in dist[1:]:
    print(0 if d%2 == 0 else 1)

Submission status: Accepted

Solution code:
class POTENTIAL_UNION_FIND(object):
    def __init__(self, n):
        self.parent = [-1 for i in range(n)]#非負なら親ノード，負ならグループの要素数
        self.diff_p = [0 for i in range(n)]#親ノードを基準としたポテンシャル
 
    def root(self, x): #root(x): xの根ノードを返す
        if self.parent[x] < 0:
            return x
        else:
            rx = self.root(self.parent[x]) #xをxの根rxに直接つなぎたい
            self.diff_p[x] += self.diff_p[self.parent[x]] #そのために，diff(rx,x)を計算
            self.parent[x] = rx #xをrxに直接つなげる
            return rx
 
    def size(self,x): #size(x): xのいるグループの要素数を返す
        return -self.parent[self.root(x)]

    def merge(self, x, y, dxy): #ポテンシャル差の条件p(y)-p(x)=dxyでxとyのグループをまとめる
        rx = self.root(x) #rxを新たにxと名づける
        ry = self.root(y) #ryを新たにyと名づける
        dxy += self.diff_p[x] - self.diff_p[y] #dxyをdiff(rx,ry)で置き換え
        x,y=rx,ry
        if x == y:
            return False
        if self.parent[x] > self.parent[y]: #xの要素数がyの要素数より「小さい」とき入れ替える
            x,y,dxy=y,x,-dxy
        self.parent[x] += self.parent[y] #xの要素数を更新
        self.parent[y] = x #yをxにつなぐ
        self.diff_p[y] = dxy #yの相対ポテンシャルを更新
        return True
 
    def issame(self, x, y): #issame(x,y): xとyが同じグループにあるならTrue
        return self.root(x) == self.root(y)
        
    def diff(self,x,y): #diff(x,y): xを基準としたyのポテンシャルを返す 
        if self.root(x) == self.root(y): #この時点でxの親はroot(x)
            return self.diff_p[y] - self.diff_p[x]
        else:
            return None

n=int(input())
u=POTENTIAL_UNION_FIND(n)
for i in range(n-1):
    a,b,c=map(int,input().split())
    u.merge(a-1,b-1,c)
for i in range(n):
    print(u.diff(0,i)%2)

Submission status: Accepted

Solution code:
from heapq import heappush, heappop

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

# 頂点1からの距離が偶数である頂点は白、奇数である頂点は黒で塗る
G = [{} for _ in range(N + 1)]
for x, y, c in zip(u, v, w):
    G[x][y] = c
    G[y][x] = c
INF = 10**18


def dijkstra(G, s):
    dp = [INF for _ in range(len(G))]
    q = []
    heappush(q, (0, s))
    while q:
        c, i = heappop(q)
        if dp[i] == INF:
            dp[i] = c
            for j, w in G[i].items():
                heappush(q, (c + w, j))
    return dp


dp = dijkstra(G, 1)
ans = '\n'.join(
    str(dp[i] % 2)
    for i in range(1, N + 1)
)

# 出力
print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(200000)

n = int(input())
edge = [[] for _ 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))
dp = [-1] * n

def dist(x, prev, d):
    dp[x] = d
    for i, j in edge[x]:
        if i == prev:
            continue
        if dp[i] != -1:
            continue
        dist(i, x, d + j)
    return

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

Submission status: Accepted

Solution code:
N = int(input())
us = []
vs = []
ws = []

for i in range(N-1):
    u,v,w = map(int, input().strip().split(" "))
    us.append(u)
    vs.append(v)
    ws.append(w)

class Node:
    def __init__(self, i):
        self.id = i
        self.friends = []
        self.color = -1
nodes = [Node(i) for i in range(N+1)]
nodes[0] = None
for u,v,w in zip(us, vs, ws):
    nodes[u].friends.append((v,w))
    nodes[v].friends.append((u,w))

nodes[1].color = 0

stack = [(1,-1)]
while len(stack):
    node_id, parent_id = stack.pop()
    node = nodes[node_id]
    node_color = node.color
    children = [(f,w) for f,w in node.friends if f != parent_id]
    for child_id, w in children:
        child_node = nodes[child_id]
        child_node.color = (node_color + w) % 2
        stack.append((child_id, node_id))

for n in nodes[1:]:
    print(n.color)

Submission status: Accepted

Solution code:
n = int(input())
li = [[] for _ in range(n+1)]
q = [(1,0)]
ans = [-1]*n

while n>1:
  s,g,c = map(int,input().split())
  li[s] += [(g,c)]
  li[g] += [(s,c)]
  n -= 1
#print(li)

while q:
  s,c = q.pop()
  ans[s-1] = c%2 
  for g, d in li[s]:
    q += [(g, c+d)] * (ans[g-1]<0)
print(*ans)

Submission status: Accepted

Solution code:
N = int(input())
lis = [[] for _ in range(N + 1)]
for _ in range(N - 1):
    u, v, w = map(int, input().split())
    lis[u] += [v * [-1, 1][w % 2]]
    lis[v] += [u * [-1, 1][w % 2]]
colors = [-1 for _ in range(N + 1)]

q = [1]
colors[1] = 0
while q:
    start = abs(q.pop(0))
    nodes = lis[start]
    for node in nodes:
        if colors[abs(node)] < 0:
            if node < 0:
                colors[abs(node)] = colors[start]
            else:
                colors[abs(node)] = int(colors[start] == 0)
            q.append(abs(node))

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

Submission status: Accepted

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

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


bw = [-1 for i in range(n + 1)]
bw[1] = 0

def dfs(frm):
	for ne in edges[frm]:
		if bw[ne[0]] >= 0:
			continue
		else:
			bw[ne[0]] = abs(bw[frm] - ne[1])
			dfs(ne[0])

dfs(1)
for i in range(1, n + 1):
	print(bw[i])

Submission status: Accepted

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

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

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

for e in edges:
	new_edges[e[0]].append([e[1], e[2]]) 
	new_edges[e[1]].append([e[0], e[2]]) 

def dfs(frm, now):
	for ne in new_edges[now]:
		if ne[0] == frm:
			continue
		else:
			if ne[1] % 2 == 0:
				bw[ne[0]] = bw[now]
			else:
				bw[ne[0]] = abs(1 - bw[now])
			dfs(now, ne[0])

dfs(0, 1)

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from queue import Queue as queue
import numpy as np
n = int(input())
e = [[] for i in range(n + 1)]
for i in range(n - 1):
    u, v, w = map(int, input().split())
    e[u].append([v, w])
    e[v].append([u, w])

q = queue()
donelist = [0 for i in range(n + 1)]

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

for i in e[1]:
    q.put([i, False])
    donelist[1] = 1

while not q.empty():
    nx = q.get()
    donelist[nx[0][0]] = 1
    if not nx[0][1] % 2:
        ans[nx[0][0]] = nx[1]
    else:
        ans[nx[0][0]] = not nx[1]
    for i in e[nx[0][0]]:
        if donelist[i[0]]:
            continue
        q.put([i, ans[nx[0][0]]])

del ans[0]

for i in ans:
    if i:
        print(0)
    else:
        print(1)

Submission status: Accepted

Solution code:
n=int(input());e=[[]for _ in[0]*-~n];q=[(1,0)];f=[-1]*n
while n>1:v,w,c=map(int,input().split());e[v]+=(w,c),;e[w]+=(v,c),;n-=1
while q:
 v,c=q.pop();f[v-1]=c%2
 for w,d in e[v]:
  if f[w-1]<0:q+=(w,c+d),
print(*f)

Submission status: Accepted

Solution code:
import collections
n=int(input())
way=[[] for i in range(n)]
for i in range(n-1):
  u,v,w=list(map(int,input().split()))
  u-=1
  v-=1
  way[u].append((v,w))
  way[v].append((u,w))
visited=[False]*n
ans=[0]*n

q=collections.deque()
q.append(0)
while len(q)>0:
  c=q.popleft()
  visited[c]=True
  for next in way[c]:
    if not visited[next[0]]:
      ans[next[0]]=(ans[c]+next[1])%2
      q.append(next[0])
for i in ans:
  print(i)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)
n = int(input())
edge = [[] for i in range(n)]
colors = [0] * n
for i in range(n-1):
    u, v, w = [int(item) for item in input().split()] 
    u -= 1
    v -= 1
    edge[u].append([v, w%2])
    edge[v].append([u, w%2])

def dfs(frm, n, d):
    for tv, tw in edge[n]:
        if tv == frm:
            continue
        else:
            td = (d + tw) % 2
            if td == 1:
                colors[tv] = 1 
            else:
                colors[tv] = 0 
            dfs(n, tv, td)
    return True

colors[0] = 0
dfs(0, 0, 0)
for item in colors:
    print(item)

Submission status: Accepted

Solution code:
from collections import deque

N = int(input())

colors = [-1] * N
trees = [{} for _ in range(N)]
for _ in range(N-1):
    u, v, w = list(map(int, input().split()))
    trees[u-1][v-1] = (w % 2 == 0)
    trees[v-1][u-1] = (w % 2 == 0)

targets = deque([0])
colors[0] = 0
while len(targets) > 0:
    target = targets.popleft()
    next_targets = trees[target]
    for next_target, is_even in next_targets.items():
        if colors[next_target] != -1:
            continue
        if is_even:
            colors[next_target] = colors[target]
        else:
            colors[next_target] = 1 - colors[target]
        targets.append(next_target)

for c in colors:
    print(c)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(100000)

# input data
n=int(input())
u=[]
v=[]
w=[]
for i in range(0,n-1):
	ui,vi,wi = map(int, input().split())
	u.append(ui)
	v.append(vi)
	w.append(wi%2)


# solve
ans=[]
for i in range(0,n+1):
	ans.append(-1)

_neighbors=[]
for i in range(0,n+1):
	_neighbors.append([])

for i in range(0,n-1):
	_neighbors[u[i]].append([v[i], w[i]])
	_neighbors[v[i]].append([u[i], w[i]])

# paint v with c=0,1 and its neighbors
def bfs(u,c):
	if ans[u] != -1:
		return

	ans[u] = c

	for vw in _neighbors[u]:
		if vw[1] == 0:
			bfs(vw[0],c)
		else:
			bfs(vw[0],1-c)

bfs(1,0)

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

Submission status: Accepted

Solution code:
# /usr/bin/python
# -*- coding: utf-8 -*-
from collections import deque,defaultdict


N = int(input())

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

visiting = set([0])
colors[0] = 0
while len(visiting) > 0:
  p = visiting.pop()
  for q in tree[p]:
    if colors[q] < 0:
      colors[q] = (tree[p][q]+colors[p]) % 2
      visiting.add(q)

for c in colors:
  print(c)

Submission status: Accepted

Solution code:
# /usr/bin/python
# -*- coding: utf-8 -*-
from collections import deque,defaultdict


N = int(input())

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

visiting = deque([0])
colors[0] = 0
while len(visiting) > 0:
  p = visiting.popleft()
  for q in tree[p]:
    if colors[q] < 0:
      colors[q] = (tree[p][q]+colors[p]) % 2
      visiting.append(q)

for c in colors:
  print(c)

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 sum < n:

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

    while not queue.empty():
        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

N = int(input())

colors = [-1 for _ in range(N)]
tree = [{} for _ in range(N)]
for _ in range(N - 1):
  u, v, w = map(int, input().split())
  is_even = (w % 2 == 0)
  tree[u-1][v-1] = is_even
  tree[v-1][u-1] = is_even

visiting = deque([0])
colors[0] = 0
while len(visiting) > 0:
  n = visiting.popleft()
  neighbors = tree[n]
  for m in neighbors:
    if colors[m] < 0:
      colors[m] = colors[n] if neighbors[m] else 1 - colors[n]
      visiting.append(m)

for color in colors:
  print(color)

Submission status: Accepted

Solution code:
from collections import deque

N = int(input())
es = [[] for _ in range(N)]
# 0-indexed

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

visited = [-1] * N
visited[0] = 0

dq = deque()
dq.append(0)
while dq:
    v = dq.popleft()
    for nv, cost in es[v]:
        if visited[nv] != -1: continue
        visited[nv] = (visited[v] + cost) % 2
        dq.append(nv)
print(*visited, sep='\n')

# UnionFindしたのは無意味だった
# どこから探索を始めても問題ない

Submission status: Accepted

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

#print(connect_list)
d = [0]+[-1 for i in range(N-1)]
stack = []
stack.append(0)
while len(stack) != 0:
    #print("Stack=",stack)
    s = stack.pop()
    #print("s=",s)
    for x,w in connect_list[s]:
        #print("x=",x,"W=",w)
        if d[x] == -1:
            d[x] = d[s] + w
            stack.append(x)
        #print("d=",d)
for i in range(N):
    print(d[i]%2)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
n = int(input())
g = [[] for _ in range(n)]
for i in range(n - 1):
    u, v, w = map(int, input().split())
    g[u - 1].append((v - 1, w % 2))
    g[v - 1].append((u - 1, w % 2))

# print(g)

ans = [-1 for _ in range(n)]
q = list()

# g[0] の処理
ans[0] = 0
q.append(0)

while(len(q) != 0):
    v = q[0]
    q.pop(0)
    for u, w in g[v]:
        # print(v, u, w)
        if ans[u] != -1:
            continue
        ans[u] = (ans[v] + w) % 2
        q.append(u)
    # print(v, q)

for a in ans:
    print(a)

Submission status: Accepted

Solution code:
n=int(input());e=[[]for _ in[0]*-~n];q=[(1,0)];f=[-1]*n
while n>1:v,w,c=map(int,input().split());e[v]+=(w,c),;e[w]+=(v,c),;n-=1
while q:
 v,c=q.pop();f[v-1]=c%2
 for w,d in e[v]:q+=[(w,c+d)]*(f[w-1]<0)
print(*f)

Submission status: Accepted

Solution code:
from collections import deque
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))

st = deque()
push, pop = st.appendleft, st.pop
push(0)
dist = [0]*N
cnt = [0]*N
cnt[0] = 1

while st:
    u = pop()
    for v,w in G[u]:
        if cnt[v] == 1:
            continue
        dist[v] = dist[u] + w
        push(v)
        cnt[v] = 1

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Mon May 20 23:18:56 2019

@author: Yamazaki Kenichi
"""

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

import sys
sys.setrecursionlimit(10**6)

class UnionFind(object):

    def __init__(self, size):
        self.table = [-1 for _ in range(size)]

    def find(self, x):
        if self.table[x] < 0:
            return x
        else:
            self.table[x] = self.find(self.table[x])
            return self.table[x]

    def union(self, x, y):
        s1 = self.find(x)
        s2 = self.find(y)
        if s1 != s2:
            if self.table[s1] <= self.table[s2]:
                self.table[s1] += self.table[s2]
                self.table[s2] = s1
            else:
                self.table[s2] += self.table[s1]
                self.table[s1] = s2
            return True
        else:
            return False

uf = UnionFind(N*2 + 1)

for c in uvw:
    if c[2] % 2 == 0:
        uf.union(c[0],c[1])
        uf.union(c[0]+N, c[1]+N)
    else:
        uf.union(c[0]+N, c[1])
        uf.union(c[0], c[1]+N)
for i in range(N*2+1):
    uf.find(i)
tmp1,tmp2 = 0, 0
for i in range(1,N+1):
    if uf.table[i] == tmp1 or i == tmp1:
        print(1)
    elif uf.table[i] == tmp2 or i == tmp2:
        print(0)
    elif tmp1 == 0:
        tmp1 = max(uf.table[i],i)
        print(1)
    else:
        tmp2 = max(uf.table[i],i)
        print(0)
#    print(i,tmp1,tmp2)

Submission status: Accepted

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

d = [0]+[-1 for i in range(N-1)]
stack = []
stack.append(0)
while len(stack) != 0:
    s = stack.pop()
    for x,w in connect_list[s]:
        if d[x] == -1:
            d[x] = d[s] + w
            stack.append(x)

for i in range(N):
    print(d[i]%2)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000)

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
def dfs(num, kyori): # 始点からの距離
    if not visited[num]:
        visited[num] = '1' if kyori%2 == 1 else '0'
        for hen in g[num]:
            dfs(hen[0], kyori+hen[1])
    return visited
 
print('\n'.join(dfs(0,0)))