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:

def main():
    import sys
    from collections import deque
    input = sys.stdin.readline
    N = int(input())
    color = [-1] * N
    color[0] = 0
    uvw = []
    edge = [[]for _ in range(N)]
    # append=uvw.append
    for i in range(N-1):
        ui, vi, wi = map(int, input().split())
        ui -= 1
        vi -= 1
        edge[ui].append((vi, wi))
        edge[vi].append((ui, wi))
    stack = [0]
    for i in range(N):
        tmp = deque()
        while stack:
            i = stack.pop()
            for e, w in edge[i]:
                if color[e] == -1:
                    stack.append(e)
                    if color[i] == 0:
                        if w % 2 == 0:
                            color[e] = 0
                        else:
                            color[e] = 1
                    else:
                        if w % 2 == 0:
                            color[e] = 1
                        else:
                            color[e] = 0
                # ここを追加--------------------------------------
                # 矛盾判定
                else:
                    if (color[i] == color[e]) != (w % 2 == 0):
                        print(-1)
                        exit()
                # ^^^^^^^^--------------------------------------
        # print(color)
        stack = tmp
    print(*color, sep="\n")


if __name__ == '__main__':
    main()

Submission status: Accepted

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


## 木構造edgesを与えた時、あるノードKから各ノードまでの距離を出力する
# 入力: edges=[(a0,b0,c0),(a1,b1,c1),...], N=len(edges)
# 出力: dist, dist[i]はノードiからノードKまでの距離
def BFS(K,edges,N): 
  roots=[ [] for i in range(N)]
  for a,b,c in edges:
    roots[a-1]+=[(b-1,c)]
    roots[b-1]+=[(a-1,c)]
  dist=[-1]*N
  stack=[]
  stack.append(K)
  dist[K]=0
  while stack:
    label=stack.pop(-1)
    for i,c in roots[label]:
      if dist[i]==-1:
        dist[i]=dist[label]+c
        stack+=[i]
  return dist
 

edges=[]
N = int(input())
for i in range(N-1):
  edges += [list(map(int,input().split()))]
distance = BFS(0,edges,N)
for i in range(N):
  print(distance[i] % 2)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**5-10)

n = int(input())
if n==1:
  print(0)
  exit()
from collections import defaultdict
edge = defaultdict(list)
for i in range(n-1):
  u, v, w = list(map(int, input().split()))
  edge[u].append((v, w))
  edge[v].append((u, w))
graph = [-1 for i in range(n+1)]

def dfs(x, c):
  nexts = edge.get(x)
  if nexts is None:
    return
  if graph[x]!=-1:
    return
  else:
    graph[x] = c
  for y, w in nexts:
    if w%2:
      dfs(y, not c)
    else:
      dfs(y, c)

dfs(1, 0)
for i in range(1, n+1):
  print(int(graph[i]))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**5-1)

n = int(input())
if n==1:
  print(0)
  exit()
from collections import defaultdict
edge = defaultdict(list)
for i in range(n-1):
  u, v, w = list(map(int, input().split()))
  edge[u].append((v, w))
  edge[v].append((u, w))
graph = [-1 for i in range(n+1)]

def dfs(x, c):
  nexts = edge.get(x)
  if nexts is None:
    return
  if graph[x]!=-1:
    return
  else:
    graph[x] = c
  for y, w in nexts:
    if w%2:
      dfs(y, not c)
    else:
      dfs(y, c)

dfs(1, 0)
for i in range(1, n+1):
  print(int(graph[i]))

Submission status: Accepted

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

n = int(input())
if n==1:
  print(0)
  exit()
from collections import defaultdict
edge = defaultdict(list)
for i in range(n-1):
  u, v, w = list(map(int, input().split()))
  edge[u].append((v, w))
  edge[v].append((u, w))
graph = [-1 for i in range(n+1)]

def dfs(x, c):
  nexts = edge.get(x)
  if nexts is None:
    return
  if graph[x]!=-1:
    return
  else:
    graph[x] = c
  for y, w in nexts:
    if w%2:
      dfs(y, not c)
    else:
      dfs(y, c)

dfs(1, 0)
for i in range(1, n+1):
  print(int(graph[i]))

Submission status: Accepted

Solution code:
N = int(input())

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

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

COLOR_WHITE = 0
COLOR_BLACK = 1
COLOR_NONE = 2

colors = [COLOR_NONE for _ in range(N)]
colors[0] = COLOR_WHITE

stack = [(0, 0)]

while stack:
    root, abs_distance = stack.pop()
    for node, distance in connections[root]:
        if colors[node] == COLOR_NONE:
            new_distance = abs_distance+distance
            colors[node] = COLOR_WHITE if (new_distance) % 2 == 0 else COLOR_BLACK
            stack += [(node, new_distance)]

for c in colors:
    print(c)

Submission status: Accepted

Solution code:
N = int(input())
graph = {}
root = -1
for n in range(N-1):
    u, v, w = map(int, input().split())
    u -= 1
    v -= 1

    if root == -1:
        root = u
    if u not in graph:
        graph[u] = {}
    if v not in graph:
        graph[v] = {}
    graph[u][v] = w
    graph[v][u] = w    

answer = [-1] * N
queue = [[root, 0]]
counter = -1
while counter < N - 1:
    counter += 1
    node = queue[counter][0]
    depth = queue[counter][1]
    answer[node] = depth
    for n in graph[node]:
        if answer[n] == -1:
            queue.append([n, depth + graph[node][n]])

for a in answer:
   print('0' if a % 2 else '1')

Submission status: Accepted

Solution code:
def solve(string):
    n, *uvw = map(int, string.split())
    g = [[] for _ in range(n + 1)]
    for u, v, w in zip(uvw[::3], uvw[1::3], uvw[2::3]):
        g[u].append((v, w))
        g[v].append((u, w))
    s = [(1, 0)]
    w = [-1] * (n + 1)
    while s:
        _s, _w = s.pop()
        w[_s] = _w % 2
        for _t, _w_ in g[_s]:
            if w[_t] == -1:
                s.append((_t, _w + _w_))
    return "\n".join(str(_w) for _w in w[1:])


if __name__ == '__main__':
    n = int(input())
    print(solve('{}\n'.format(n) + '\n'.join([input() for _ in range(n - 1)])))

Submission status: Accepted

Solution code:
def solve(string):
    n, *uvw = map(int, string.split())
    p = [[] for _ in range(n + 1)]
    for u, v, w in zip(uvw[::3], uvw[1::3], uvw[2::3]):
        p[u].append((v, w))
        p[v].append((u, w))
    s = [(1, 0)]
    l = [-1] * (n + 1)
    while s:
        _s, w = s.pop()
        l[_s] = w % 2
        for _t, _w in p[_s]:
            if l[_t] == -1:
                s.append((_t, w + _w))
    return "\n".join(str(_w) for _w in l[1:])


if __name__ == '__main__':
    n = int(input())
    print(solve('{}\n'.format(n) + '\n'.join([input() for _ in range(n - 1)])))

Submission status: Accepted

Solution code:
def solve(string):
    n, *uvw = map(int, string.split())
    p = [[] for _ in range(n + 1)]
    for u, v, w in zip(uvw[::3], uvw[1::3], uvw[2::3]):
        p[u].append((v, w))
        p[v].append((u, w))
    s = [(1, 0)]
    l = [-1] * n
    while s:
        a, w = s.pop()
        l[a - 1] = w % 2
        for b, c in p[a]:
            if l[b - 1] == -1:
                s.append((b, w + c))
    return "\n".join(str(c) for c in l)


if __name__ == '__main__':
    n = int(input())
    print(solve('{}\n'.format(n) + '\n'.join([input() for _ in range(n - 1)])))

Submission status: Accepted

Solution code:
N=int(input());p=[[]for _ in range(N+1)]
for _ in range(N-1):u,v,w=map(int,input().split());p[u].append((v,w));p[v].append((u,w))
s=[(1,0)];l=[-1]*N
while s:
 a,w=s.pop()
 l[a-1]=w%2
 for b,c in p[a]:
  if l[b-1]==-1:s.append((b,w+c))
for i in l:print(i)

Submission status: Accepted

Solution code:
n = int(input())

to_cost = [[] for i in range(n + 1)]
for _ in range(n-1):
    u, v, w = map(int, input().split())
    to_cost[u].append([v, w % 2])
    to_cost[v].append([u, w % 2])
ans = [-1] * (n + 1)
stack = [(1,1)]
while stack:
    a, w = stack.pop()
    ans[a] = w
    for to, cost in to_cost[a]:
        if ans[to] < 0:
            stack.append((to, w ^ cost))

for a in ans[1:]:
    print(a)

Submission status: Accepted

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

ans = [-1] * N
P = [set() for _ in range(N)]
for l in L:
    u, v, w = l
    P[u - 1].add(((v - 1), w))
    P[v - 1].add(((u - 1), w))

ans[0] = 0
F = [0] * (N + 1)
it = 0
po = 1
already = {0}
for _ in range(N + 1):
    if it > po:
        break
    u = F[it]
    it += 1
    for (v, w) in P[u]:
        if v in already:
            continue
        ans[v] = ans[u] if w % 2 == 0 else 1 - ans[u]
        F[po] = v
        already.add(v)
        po += 1

res = ""
for a in ans:
    res += "{}\n".format(a)
print(res)

Submission status: Accepted

Solution code:
from queue import Queue

N = int(input())
X = [list(map(int, input().split())) for _ in range(N-1)]
X = list(map(lambda x: (x[0]-1, x[1]-1, x[2]), X))
# [u番目の頂点, v番目の頂点, 距離w]
# インデックスは0,...,N-1

# 頂点iの隣接情報を保持
node = [[] for i in range(N)]
for x in X:
    u, v, w = x
    node[u].append((v, w))
    node[v].append((u, w))

# 頂点iの色, 未彩色は-1
color = [-1] * N

# 幅優先探索で全頂点の色を決定
# 頂点0の色を0とする
q = Queue()
color[0] = 0
q.put((0, color[0]))
while not q.empty():
    q0 = q.get()

    n = q0[0]
    c = q0[1]
    neighbors = node[n]
    for p in neighbors:
        if color[p[0]] == -1:
            color[p[0]] = (c + p[1]) % 2
            q.put((p[0], color[p[0]]))

for c in color:
    print(c)

Submission status: Accepted

Solution code:
N = int(input())
adj = [[] for _ in range(N)]
 
for i in range(N-1):
    u,v,w = map(int,input().split())
    u,v = u-1, v-1
    w %= 2
    adj[u].append((v,w))
    adj[v].append((u,w))
 
color = [None]*N
color[0] = False
stack = [0]
 
while stack:
    u = stack.pop()
    for v,w in adj[u]:
        if color[v] is None:
            color[v] = (w%2) ^ color[u]
            stack += [v]
 
for c in color:
    print(1 if c else 0)

Submission status: Accepted

Solution code:
def sub():
    N = int(input())
    edges = []
    for _ in range(N-1):
        ed = [int(e) for e in input().split(" ")]
        edges.append(ed)
    
    d_neighbor = {i: [] for i in range(1, N+1)} 
    d_weight = {}
    for ed in edges:
        h, t, w = ed
        d_neighbor[h].append(t)
        d_neighbor[t].append(h)
        d_weight[(h,t)] = w
    
    d_color = {i: None for i in range(1, N+1)}
    for i in range(1, N+1):
        if d_color[i] is not None:
            continue
        
        s_visit = set()
        position = i
        # s_visit.add(position)
        stack = [position]
        d_color[position] = False
        while len(stack) > 0:
            position = stack.pop()
            s_visit.add(position)
            nn = d_neighbor[position]
            nn_uv = [n for n in nn if n not in s_visit]
            cTmp = d_color[position]
            for n in nn_uv:
                t = (position, n)
                if position > n:
                    t = (n, position)
                w = d_weight[t]
                if w % 2 == 0:
                    d_color[n] = cTmp
                else:
                    d_color[n] = not cTmp
            stack.extend(nn_uv)
    
    for i in range(1, N+1):
        print(int(d_color[i]))

sub()

Submission status: Accepted

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

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

color = [-1] * N


def dfs(x, y):
    for i, w in G[x]:
        if color[i] == -1:
            color[i] = (y+w) % 2
            dfs(i, y+w)


dfs(0, 0)
for i in color:
    print(i)

Submission status: Accepted

Solution code:
class UNION_FIND(object):
    def __init__(self,n):
        self.parent=[-1 for i in range(n)]
        
    def root(self,x):
        if self.parent[x]<0:
            return x
        else:
            self.parent[x]=self.root(self.parent[x])
            return self.parent[x]
 
    def size(self,x):
        return -self.parent[self.root(x)]
    def union(self,x,y):
        x=self.root(x)
        y=self.root(y)
        if x==y:
            return False
        if self.size(x)<self.size(y):
            x,y=y,x
        self.parent[x]+=self.parent[y]  #Aのサイズを更新する
        self.parent[y]=x   #Bの親をAに変更する
        return True

n=int(input())
u=UNION_FIND(2*n)
for i in range(n-1):
    a,b,c=map(int,input().split())
    if c%2==0:
        u.union(a-1,b-1)
        u.union(a-1+n,b-1+n)
    else:
        u.union(a-1+n,b-1)
        u.union(a-1,b-1+n)
#print(u.parent)
for i in range(n):
    if u.root(i)<n:
        print(1)
    else:
        print(0)

Submission status: Accepted

Solution code:
import sys
from collections import deque
sys.setrecursionlimit(200000)
 
readline = sys.stdin.readline
 
N = int(readline())
 
nodes = [deque() for i in range(N)]
node_colors = [-1 for i in range(N)]
 
for i in range(N - 1):
    u,v,w = map(int, readline().split())
    u, v = u - 1, v - 1
    nodes[u].append([v, w])
    nodes[v].append([u, w])
 
 
node_colors[0] = 0
 
def process(u, parent, w): 
    p_color = node_colors[parent]
    node_colors[u] = p_color if w % 2 == 0 else 1 - p_color
    
    for v, w in nodes[u]:
        if v == parent:
            continue
        process(v, u, w)
 
for v, w in nodes[0]:
    process(v, 0, w)
 
for c in node_colors:
    print(c)

Submission status: Accepted

Solution code:
N=int(input());p=[[]for _ in range(N+1)]
for _ in range(N-1):u,v,w=map(int,input().split());p[u].append((v,w));p[v].append((u,w))
s=[(1,0)];l=[-1]*N
while s:
 a,w=s.pop()
 l[a-1]=w%2
 for b,c in p[a]:
  if l[b-1]==-1:s.append((b,w+c))
for i in l:print(i)

Submission status: Accepted

Solution code:
N=int(input())
p=[[]for _ in range(N+1)]
for _ in range(N-1):
 u,v,w=map(int,input().split())
 p[u].append((v,w))
 p[v].append((u,w))
s=[(1,0)]
l=[-1]*N
while s:
 a,w=s.pop()
 l[a-1]=w%2
 for b,c in p[a]:
  if l[b-1]==-1:
   s.append((b,w+c))
for i in l:
 print(i)

Submission status: Accepted

Solution code:
N=int(input())
p=[[]for _ in range(N+1)]
for _ in range(N-1):
  u,v,w=map(int,input().split())
  p[u].append((v,w))
  p[v].append((u,w))
s=[(1,0)]
l=[-1]*N
while s:
  a,w=s.pop()
  l[a-1]=w%2
  for b,c in p[a]:
    if l[b-1]==-1:
      s.append((b,w+c))
for i in l:
	print(i)

Submission status: Accepted

Solution code:
from collections import defaultdict
import sys

def tree_path_dict():
    def walk(i, c):
        if d[i] == -1:
            d[i] = c
            for node, dist in edge[i].items():
                walk(node, c + dist)

    sys.setrecursionlimit(100000)
    n = int(input())
    edge = defaultdict(lambda: defaultdict(lambda: float("inf")))
    for _ in range(n - 1):
        u, v, w = map(int, input().split())
        edge[u][v] = w
        edge[v][u] = w
    d = [-1] * (n + 1)
    walk(1, 0)
    for item in d[1:]:
        print(item % 2)

tree_path_dict()

Submission status: Accepted

Solution code:
import sys
def tree_path():
    # 辺と長さが与えられる
    # 頂点1からの各点の距離を計算する
    # 距離が偶数か奇数かで色分け
    def walk(i, c):
        if d[i] == -1:
            d[i] = c
            for node, dist in path[i]:
                walk(node, c + dist)

    sys.setrecursionlimit(100000)
    n = int(input())
    path = [[] for _ in range(n + 1)]
    for _ in range(n - 1):
        u, v, w = map(int, input().split())
        # 無向グラフ
        path[u].append([v, w])
        path[v].append([u, w])
    # d[0]は使わない
    d = [-1] * (n + 1)
    walk(1, 0)
    for item in d[1:]:
        print(item % 2)


tree_path()

Submission status: Accepted

Solution code:
from collections import defaultdict
import sys

def tree_path_dict():
    sys.setrecursionlimit(100000)
    n = int(input())
    edge = defaultdict(lambda: defaultdict(lambda: float("inf")))

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

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

    def walk(i, c):
        if d[i] == -1:
            d[i] = c
            for node, dist in edge[i].items():
                walk(node, c + dist)

    walk(1, 0)
    for i in d[1:]:
        print(i % 2)

        
tree_path_dict()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(100000)

def tree_path():
    # 辺と長さが与えられる
    # 頂点1からの各点の距離を計算する
    # 距離が偶数か奇数かで色分け
    sys.setrecursionlimit(100000)
    n = int(input())
    path = [[] for _ in range(n + 1)]
    for _ in range(n - 1):
        u, v, w = map(int, input().split())
        # 無向グラフ
        path[u].append((v, w))
        path[v].append((u, w))
    # d[0]は使わない
    d = [-1] * (n + 1)

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

    walk(1, 0)
    for i in d[1:]:
        print(i % 2)

        
tree_path()

Submission status: Accepted

Solution code:
N = int(input())
        
G = [[] for i in range(N)]
for _ in range(N - 1):
    a, b, c = map(int, input().split())
    G[a - 1].append([b - 1, c])
    G[b - 1].append([a - 1, c])
    
color = [-1] * N
color[0] = 0
Q = [0]

while len(Q) != 0:
    cur = Q.pop()
    for to, dist in G[cur]:
        if color[to] == -1:
            color[to] = (color[cur] + dist) % 2
            Q.append(to)
            
for i in range(N):
    print(color[i])

Submission status: Accepted

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

kyori = [-1 for k in range(N)]
kyori[T[0][0][0]] = 0
que = [T[0][0][0]]

while len(que) > 0:
    now = que.pop()
    for tsugi in T[now]:
        if kyori[tsugi[0]] == -1:
            kyori[tsugi[0]] = kyori[now] + tsugi[1]
            que.append(tsugi[0])

for a in kyori:
    print(a%2)

Submission status: Accepted

Solution code:
'''input
3
1 2 2
2 3 1
'''
import sys
sys.setrecursionlimit(100100)
N = int(input())

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

for i in range(N-1):
	a, b, w = [int(x) for x in input().split()]
	a -= 1
	b -= 1
	edges[a].append((b, w))
	edges[b].append((a, w))


color = [None]*N

color[0] = 0

def dfs(curr, prev):
	for i in edges[curr]:
		if i[0] == prev: continue

		if i[1] % 2 == 0: color[i[0]] = color[curr]
		else: color[i[0]] = 1 - color[curr]

		dfs(i[0], curr)

dfs(0, -1)

for i in color:
	print(i)

Submission status: Accepted

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

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

def dfs(x):
    for y in t[x]:
        del t[y][x]
        ans[y] = ans[x] if t[x][y] % 2 == 0 else 1-ans[x]
        if len(t[y]) > 0:
            dfs(y)

ans[0] = 0
dfs(0)
for i in range(n):
    print(ans[i])

Submission status: Accepted

Solution code:
N = int(input())
graph = [[] for _ in range(N)]
for _ in range(N - 1):
    u, v, w = map(int, input().split())
    u -= 1
    v -= 1
    graph[u].append((v, w))
    graph[v].append((u, w))
qu = [0]
colors = [0 for _ in range(N)]
visited = set()
while len(qu) != 0:
    cur = qu.pop()
    visited.add(cur)
    for nxt, weight in graph[cur]:
        if nxt not in visited:
            colors[nxt] = (colors[cur] + weight)%2
            qu.append(nxt)
for v in colors:print(v)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**5)
N=int(input())
uvw=[list(map(int,input().split())) for i in range(N-1)]
link=[[] for i in range(N+1)]
for u,v,w in uvw:
    link[u].append((v,w))
    link[v].append((u,w))
mark=[0]*(N+1)
color=[0]*(N+1)
def dfs(n,c):
    mark[n]=1
    color[n]=c
    for i,w in link[n]:
        if mark[i]==1:
            continue
        if w%2==0:
            dfs(i,c)
        else:
            dfs(i,1-c)
dfs(uvw[0][0],0)
for i in range(1,N+1):
    print(color[i])

Submission status: Accepted

Solution code:
# coding: utf-8
class PotUnionFind:
    def __init__(self, size):
        self.parent = [-1 for i in range(size)]#非負なら親ノード，負ならグループの要素数
        self.diff_p = [0 for i in range(size)]#親ノードを基準としたポテンシャル

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

    def size(self,x): #size(x): xのいるグループの要素数を返す
        return -self.parent[self.root(x)]

n = int(input())

T=PotUnionFind(n)
for _ in [0]*(n-1):
    u,v,w = [int(i) for i in input().split()]
    T.merge(u-1,v-1,w)

for i in range(n):
    print(T.diff(0,i)%2)

Submission status: Accepted

Solution code:
# coding: utf-8
class PotUnionFind:
    def __init__(self, size):
        self.parent = [-1 for i in range(size)]#非負なら親ノード，負ならグループの要素数
        self.diff_p = [0 for i in range(size)]#親ノードを基準としたポテンシャル

    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 weight(self, x):
        self.root(x)
        return self.diff_p[x]

    def merge(self, x, y, dxy): #ポテンシャル差の条件p(y)-p(x)=dxyでxとyのグループをまとめる
        dxy += self.weight(x) - self.weight(y) #dxyをdiff(rx,ry)で置き換え
        x = self.root(x) #rxを新たにxと名づける
        y = self.root(y) #ryを新たにyと名づける
        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

    def size(self,x): #size(x): xのいるグループの要素数を返す
        return -self.parent[self.root(x)]

n = int(input())

T=PotUnionFind(n)
for _ in [0]*(n-1):
    u,v,w = [int(i) for i in input().split()]
    T.merge(u-1,v-1,w)

for i in range(n):
    print(T.diff(0,i)%2)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
# IMPORT ###############################################################################################################
import sys                                                      # システム
sys.setrecursionlimit(10**6)                                    # 再帰処理の上限変更
from collections import deque, Counter                          # キュー・個数カウント
from itertools   import accumulate, permutations, combinations  # 累積和・順列・組み合わせ
from operator    import itemgetter                              # ソート補助
from bisect      import bisect_left, bisect_right, bisect       # 二分探索
from heapq       import heappop, heappush                       # プライオリティキュー
from fractions   import gcd                                     # 最大公約数
from math        import ceil, floor, sqrt, cos, sin, tan, pi    # 数学処理
from copy        import deepcopy                                # オブジェクトコピー
import numpy         as np                                      # 数値計算

# MAIN #################################################################################################################
def main():
    # Init #############################################################################################################
    im = InputManager()
    # Input ############################################################################################################
    n = im.inputSingle()
    nodes = [Node(i) for i in range(n)]
    for i in range(n-1):
        u, v, w = im.inputMultiple()
        nodes[u-1].addConnection(nodes[v-1], w)
        nodes[v-1].addConnection(nodes[u-1], w)
    # Logic ############################################################################################################
    weights = [-1 for i in range(n)]
    Node.calcWeights(nodes[0], 0, weights)
    # Output ###########################################################################################################
    for weight in weights:
        if weight % 2 == 0:
            print(0)
        else:
            print(1)
    # Return ###########################################################################################################
    return

class Node(object):
    def __init__(self, index):
        self._index = index
        self._connections = []
    
    @property
    def connections(self):
        return self._connections
    
    def addConnection(self, node, weight):
        self._connections.append({"node": node, "weight": weight})
    
    def __eq__(self, other):
        return self._index == other._index
    
    @staticmethod
    def calcWeights(node, weight, weights):
        weights[node._index] = weight
        if - 1 not in weights:
            return
        for connection in node.connections:
            if weights[connection["node"]._index] == -1:
                Node.calcWeights(connection["node"], weight+connection["weight"], weights)

# INPUT MANAGER ########################################################################################################
class InputManager(object):
    def __init__(self):
        pass

    @staticmethod
    def inputSingle(dtype=int):
        return dtype(input())
    
    @staticmethod
    def inputMultiple(dtype=int, aslist=False):
        if aslist:
            return list(map(dtype, input().split()))
        else:
            return map(dtype, input().split())

    @staticmethod
    def input2D(h, dtype=int):
        return [list(map(dtype, input().split())) for i in range(h)]

# CALL MAIN ############################################################################################################
main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3.4
# -*- coding: utf-8 -*-

# abc126_d

from collections import namedtuple
import sys

sys.setrecursionlimit(10**5)

DistFrom = namedtuple('DistFrom', ['f', 'dist'])

def main():
    # Input
    n, = [int(s) for s in input().split()]
    fs = [[int(s) for s in input().split()] for _ in range(n-1)]
    # Get ans
    gs = [None] * n
    for i in range(n):
        gs[i] = list()
    for x, y, d in fs:
        x -= 1
        y -= 1
        d = d%2
        gs[x].append(DistFrom(y, d))
        gs[y].append(DistFrom(x, d))
    distlist = [None] * n
    def dfs(cur, dist):
        if distlist[cur] != None:
            return
        distlist[cur] = dist
        for i, d in gs[cur]:
            dfs(i, dist^d)
    dfs(0, 0)
    # Output
    for d in distlist:
        print(d)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N = int(input())
uvw = [[int(x) for x in input().split()] for _ in range(N-1)]

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

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

for u,v,w in uvw:
    path[u-1].append([v-1,w%2])
    path[v-1].append([u-1,w%2])
    
Q = [0]     
while Q:
    v = Q.pop(-1)
    for p,d in path[v]:
        if ans[p] == -1:
            ans[p] = (ans[v]+d)%2
            Q.append(p)
            
for a in ans:
    print(a)

Submission status: Accepted

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

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

costs = [-1 for _ in range(n)]

def dfs(cur, dist):
    if costs[cur] != -1:
        return
    costs[cur] = dist
    for v, d in p[cur]:
        dfs(v, dist^d)
dfs(0, 0)

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

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:
    #print(que)
    u = que.popleft()

    is_visited[u] = True

    for v, w in connect[u]:
        if not is_visited[v]:
            que.append(v)
            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:
import sys

sys.setrecursionlimit(10**5)

n = int(input())

p = [[] for i in range(n)]

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

c = [-1 for i in range(n)]

def dfs(num, zo):
    if c[num] != -1:
        return
    else:
        c[num] = zo
    for v, w in p[num]:
        if w % 2 == 0:
            dfs(v, zo)
        else:
            dfs(v, not zo)
dfs(0, 0)

for i in range(n):
    print(1 if c[i] else 0)