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

def getlist():
	return list(map(int, input().split()))

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

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

    def add_edge(self, a, b, w):
        self.graph[a].append([b, w])
        self.graph[b].append([a,w])

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

class BFS(object):
    def __init__(self, graph, N):
        self.g = graph.graph
        self.dist = [0] * (N + 1)
        self.visit = [0] * (N + 1)
        self.Q = queue.Queue()
        #self.visit[1] = 1
        self.Q.put(1)

        while not self.Q.empty():
            v = self.Q.get()
            for i, w in self.g[v]:
            	if self.visit[i] == 0:
            		self.dist[i] = self.dist[v] + w
            		self.Q.put(i)
            		self.visit[i] = 1

    def weight(self):
        return self.dist

N = int(input())
G = Graph()
for i in range(N - 1):
	u, v, w = getlist()
	G.add_edge(u, v, w)
XX = BFS(G, N)
ans = XX.weight()
for i in range(1, N + 1):
	if ans[i] % 2 == 0:
		print(0)
	else:
		print(1)

Submission status: Accepted

Solution code:
from collections import defaultdict
import queue

def getlist():
	return list(map(int, input().split()))

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

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

    def add_edge(self, a, b, w):
        self.graph[a].append([b, w])
        self.graph[b].append([a,w])

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

class BFS(object):
    def __init__(self, graph, N):
        self.g = graph.graph
        self.dist = [0] * (N + 1)
        self.visit = [0] * (N + 1)
        self.Q = queue.Queue()
        self.visit[1] = 1
        self.Q.put(1)

        while not self.Q.empty():
            v = self.Q.get()
            for i, w in self.g[v]:
            	if self.visit[i] == 0:
            		self.dist[i] = self.dist[v] + w
            		self.Q.put(i)
            		self.visit[i] = 1

    def weight(self):
        return self.dist

N = int(input())
G = Graph()
for i in range(N - 1):
	u, v, w = getlist()
	G.add_edge(u, v, w)
XX = BFS(G, N)
ans = XX.weight()
for i in range(1, N + 1):
	if ans[i] % 2 == 0:
		print(0)
	else:
		print(1)

Submission status: Accepted

Solution code:
n = int(input())
peer = [[] for _ in range(n)]
for _ in range(n-1):
  u,v,w = map(int,input().split())
  u -= 1
  v -= 1
  w %= 2
  peer[u].append([v,w])
  peer[v].append([u,w])
now = [0]
clr = [-1 for _ in range(n)]
clr[0] = 0
while now:
  last = now
  now = []
  for x in last:
    for y in peer[x]:
      if clr[y[0]] == -1:
        now.append(y[0])
        clr[y[0]] = clr[x] ^ y[1]
for z in clr:
  print(z)

Submission status: Accepted

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

color = [-1] * n
dist = [0] * n

import queue
def dfs(v):
    color[v] = dist[v] % 2
    q = queue.LifoQueue()
    q.put(v)

    while not q.empty():
        vv = q.get()
        for next_v in g[vv]:
            if color[next_v[0]] == -1 and next_v[1] != 0:
                dist[next_v[0]] = dist[vv] + next_v[1]
                color[next_v[0]] = dist[next_v[0]] % 2
                q.put(next_v[0])

# 0を始点として各点までの距離を求める
dfs(0)

for c in color:
    print(c)

Submission status: Accepted

Solution code:
from collections import deque

N = int(input())
d_list = [[] for _ in range(N+1)]
for _ in range(N-1):
  a, b, c = map(int, input().split())
  d_list[a].append((b, a, c))
  d_list[b].append((a, b, c))
que = deque([])
for v in d_list[1]:
  que.append(v)
ans = [-1] * (N+1)
ans[1] = 0
while len(que) > 0:
  v = que.popleft()
  ans[v[0]] = (ans[v[1]]+v[2])%2
  for n in d_list[v[0]]:
    if ans[n[0]] == -1:
      que.append(n)
for a in ans[1:]:
  print(a)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(500000)

def dfs(v,w,c):
    if w % 2 ==1 :
        c = 1-c
    color[v] = c

    for i in a[v]:
        if color[i[0]] != -1:continue
        dfs(i[0],i[1],c)

n = int(input())

a = [[]for i in range(n)]
color = [-1 for _ in range(n)]

for i in range(n-1):
    x,y,z = map(int,input().split())
    a[x-1].append([y-1,z])
    a[y-1].append([x-1,z])
dfs(a[0][0][0],a[0][0][1],0)
print(*color,sep="\n")

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
n=int(input())
uvw=[list(map(int,input().split())) for i in range(n-1)]
graph=[[] for i in range(n+1)]
color=[-1]*(n+1)
for u,v,w in uvw:
    graph[u].append((v,w))
    graph[v].append((u,w))

color[1]=1
ne=[1]
while ne:
    t=ne.pop()
    for v,w in graph[t]:
        if color[v]==-1:
            ne.append(v)
            color[v]=color[t] if w%2==0 else (color[t]+1)%2

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

Submission status: Accepted

Solution code:
from collections  import deque
'''
N = int(input())
graph = [[] for _ in range(N)]
for _ in range(N - 1):
    a , b , w = map(int , input().split())
    a -= 1
    b -= 1
    graph[b].append([a,w])
    graph[a].append([b,w])

#print(len(graph.pop()[0]))
#print(graph.pop())
#print(len(graph.pop()))
def dfs():
    q = deque(graph[0])
    color = [0] * N
    corrent_color = 0
    other_color = 1
    searched = [0]
    while q:
        count = len(q)
        #print(count)
        search = q.popleft()
        #print("search : ",search)
        #print("search[0] : ",search[0])
        #print(len(search))
        for i in range(count):

            if not search[0] in searched:
                searched.append(search[0])
                if search[1] % 2 == 0:
                    color[search[0]] = corrent_color
                else:
                    color[search[0]] = other_color
                #print(len(graph[search[0]]))
                #print(graph[search[0]][0])
                for i in range(len(graph[search[0]])):
                    #print("i : ",i)
                    #print(graph[search[0]][i])
                    q.append(graph[search[0]][i])
                #print(q)
        corrent_color = color[search[0]]
        other_color = 1 - corrent_color
    print(*color , sep = "\n")
dfs()
'''

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

color = [-1] * N
color[0] = 0
q = deque()
q.append(int(0))

#print(cost[0])
#print(graph[0])
while q:
    value = q.popleft()
    #print(value)
    for to , c in zip(graph[value] , cost[value]):
        #print(to , c)
        if color[to] != -1:
            continue
        color[to] = color[value]^c
        q.append(to)
print(*color , sep = "\n")

Submission status: Accepted

Solution code:
import collections

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

cs = [-1 for _ in range(n + 1)]
cs[1] = 0
q = collections.deque([1])
while len(q) > 0:
    x = q.popleft()
    for y, b in es[x]:
        if cs[y] >= 0:
            continue
        cs[y] = cs[x] if b else 1 - cs[x]
        q.append(y)
print(*cs[1:], sep='\n')

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor


INF = float('inf')
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


n = I()
graph = [[] for _ in range(n)]
for a, b, cost in LIR(n-1):
    graph[a-1] += [(b-1, cost)]
    graph[b-1] += [(a-1, cost)]



color = [0] * n
color[0] = 0
dist = [-1] * n
dist[0] = 0
que = deque([0])
while que:
    cur = que.pop()
    for nxt, cost in graph[cur]:
        if dist[nxt] == -1:
            dist[nxt] = dist[cur] + cost
            color[nxt] = dist[nxt] % 2
            que += [nxt]


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

Submission status: Accepted

Solution code:
from collections import Counter,defaultdict
import sys,heapq,bisect,math,itertools,string,queue
sys.setrecursionlimit(10**8)
mod = 10**9+7
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())
def inpln(n): return list(int(sys.stdin.readline()) for i in range(n))

def dfs(x):
    for p in g[x]:
        # print(p[0])
        if color[p[0]] != -1:
            continue
        if p[1] % 2: #odd
            if color[x]: #pre=white
                color[p[0]] = 0
            else:
                color[p[0]] = 1
        else:
            if color[x]: #pre=white
                color[p[0]] = 1
            else:
                color[p[0]] = 0
        dfs(p[0])
n = inp()
g = [[] for i in range(n)]
#0:黒 1:白 -1:未訪問
color = [-1] * n

for i in range(n-1):
    u,v,w = inpl()
    g[u-1].append([v-1,w])
    g[v-1].append([u-1,w])
# print(g)
color[0] = 0
dfs(0)
for i in range(1,n):
    if color[i] != -1:
        continue
    dfs(i)
for i in range(n):
    print(color[i])

Submission status: Accepted

Solution code:
from collections import deque
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)
    to[v].append(u)
    cost[u].append(w%2)
    cost[v].append(w%2)

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

q=deque()
q.append(0)
while q:
    v=q.popleft()

    for t,c in zip(to[v], cost[v]):
        if color[t]!=-1:
            continue
        color[t]=color[v]^c
        q.append(t)

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

Submission status: Accepted

Solution code:
# ABC126D - Even Relation
def dfs(r: int) -> None:
    stack = [r]
    while stack:
        v = stack.pop()
        for u, w in T[v]:
            if D[u] == -1:
                D[u] = (D[v] + w) % 2
                stack += [u]


def main():
    global T, D
    N, *A = map(int, open(0).read().split())
    T = [[] for _ in range(N + 1)]
    for i in range(0, (N - 1) * 3, 3):
        v, u, w = A[i : i + 3]
        T[v] += [(u, w)]
        T[u] += [(v, w)]
    D = [-1] * (N + 1)  # D[i] := parity of distance from vertex 1 (root)
    D[1] = 0
    dfs(1)
    print(*D[1:], sep="\n")


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# ABC126D - Even Relation
def dfs(r: int) -> None:
    stack = [r]
    while stack:
        v = stack.pop()
        for u, w in T[v]:
            if D[u] == -1:
                D[u] = (D[v] + w) % 2
                stack.append(u)


def main():
    # same parity of distance from root <-> same group
    global T, D
    N, *A = map(int, open(0).read().split())
    T = [[] for _ in range(N + 1)]
    for i in range(0, (N - 1) * 3, 3):
        v, u, w = A[i : i + 3]
        T[v].append((u, w))
        T[u].append((v, w))
    D = [-1] * (N + 1)  # D[i] := parity of distance from vertex 1 (root)
    D[1] = 0
    dfs(1)
    print(*D[1:], sep="\n")


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# ABC126D - Even Relation
def main():
    # same parity of distance from root <-> same group
    global T, D
    N, *A = map(int, open(0).read().split())
    T = [[] for _ in range(N + 1)]
    for i in range(0, (N - 1) * 3, 3):
        v, u, w = A[i : i + 3]
        T[v] += [(u, w)]
        T[u] += [(v, w)]
    D = [-1] * (N + 1)  # D[i] := parity of distance from vertex 1 (root)
    D[1] = 0
    stack = [1]  # dfs starting from root
    while stack:
        v = stack.pop()
        for u, w in T[v]:
            if D[u] == -1:
                D[u] = (D[v] + w) % 2
                stack.append(u)
    print(*D[1:], sep="\n")


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# ABC126D - Even Relation
def dfs(r: int) -> None:
    stack = [r]
    while stack:
        v = stack.pop()
        for u, w in T[v]:
            if D[u] == -1:
                D[u] = (D[v] + w) % 2
                stack += [u]


def main():
    global T, D
    N, *A = map(int, open(0).read().split())
    T = [[] for _ in range(N + 1)]
    for i in range(0, (N - 1) * 3, 3):
        v, u, w = A[i : i + 3]
        T[v] += [(u, w)]
        T[u] += [(v, w)]
    D = [-1] * (N + 1)  # D[i] := parity of distance from vertex 1 (root)
    D[1] = 0
    dfs(1)
    print(*D[1:], sep="\n")


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# ABC126D - Even Relation
def dfs(r: int) -> None:
    stack = [r]
    while stack:
        v = stack.pop()
        for u, w in T[v]:
            if D[u] == -1:
                D[u] = (D[v] + w) % 2
                stack.append(u)


def main():
    global T, D
    N, *A = map(int, open(0).read().split())
    T = [[] for _ in range(N + 1)]
    for i in range(0, (N - 1) * 3, 3):
        v, u, w = A[i : i + 3]
        T[v] += [(u, w)]
        T[u] += [(v, w)]
    D = [-1] * (N + 1)  # D[i] := parity of distance from vertex 1 (root)
    D[1] = 0
    dfs(1)
    print(*D[1:], sep="\n")


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# ABC126D - Even Relation
import sys

sys.setrecursionlimit(10 ** 9)


def dfs(v: int, p: int) -> None:
    for u, w in T[v]:
        if u != p:
            D[u] = (D[v] + w) % 2
            dfs(u, v)


def main():
    global T, D
    N, *A = map(int, open(0).read().split())
    T = [[] for _ in range(N + 1)]
    for i in range(0, (N - 1) * 3, 3):
        v, u, w = A[i : i + 3]
        T[v] += [(u, w)]
        T[u] += [(v, w)]
    D = [0] * (N + 1)  # D[i] := distance from vertex 1 (root)
    dfs(1, -1)
    print(*D[1:], sep="\n")


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# ABC126D - Even Relation
import sys

sys.setrecursionlimit(10 ** 9)


def dfs(v: int, p: int) -> None:
    for u, w in T[v]:
        if u != p:
            D[u] = D[v] + w
            dfs(u, v)


def main():
    global T, D
    N, *A = map(int, open(0).read().split())
    T = [[] for _ in range(N + 1)]
    for i in range(0, (N - 1) * 3, 3):
        v, u, w = A[i : i + 3]
        T[v] += [(u, w)]
        T[u] += [(v, w)]
    D = [0] * (N + 1)  # D[i] := distance from vertex 1 (root)
    dfs(1, -1)
    ans = [i % 2 for i in D[1:]]  # same parity of distance -> same group
    print(*ans, sep="\n")


if __name__ == "__main__":
    main()

Submission status: Accepted

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


def solve(N: int, u: "List[int]", v: "List[int]", w: "List[int]"):
    res = [0 for i in range(N)]
    G = [[] for i in range(N)]
    for i, j, k in zip(u, v, w):
        # print(i, j, k)
        i -= 1
        j -= 1
        # print(i, j, k)
        G[i].append((j, k))
        G[j].append((i, k))
    # print(G)

    # v を c に塗る。 p は v の親。
    def dfs(v, p, c):
        res[v] = c
        for e in G[v]:
            if e[0] == p:
                continue
            if e[1] & 1:
                dfs(e[0], v, 1 - c)
            else:
                dfs(e[0], v, c)

    dfs(0, -1, 1)

    for x in res:
        print(x)

    return


# Generated by 1.1.5 https://github.com/kyuridenamida/atcoder-tools
# (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    u = [int()] * (N - 1)  # type: "List[int]"
    v = [int()] * (N - 1)  # type: "List[int]"
    w = [int()] * (N - 1)  # type: "List[int]"
    for i in range(N - 1):
        u[i] = int(next(tokens))
        v[i] = int(next(tokens))
        w[i] = int(next(tokens))
    solve(N, u, v, w)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10 ** 7)
 
def solve(N: int, u: "List[int]", v: "List[int]", w: "List[int]"):
    res = [0 for i in range(N)]
    G = [[] for i in range(N)]
    for i, j, k in zip(u, v, w):
        # print(i, j, k)
        i -= 1
        j -= 1
        # print(i, j, k)
        G[i].append((j, k))
        G[j].append((i, k))
 
    # v を c に塗る。 p は v の親。
    def dfs(v, p, c):
        res[v] = c
        for e in G[v]:
            if e[0] == p:
                continue
            if e[1] & 1:
                dfs(e[0], v, 1 - c)
            else:
                dfs(e[0], v, c)
 
    dfs(0, -1, 1)
 
    for x in res:
        print(x)
 
    return
 
 
# Generated by 1.1.5 https://github.com/kyuridenamida/atcoder-tools
# (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    u = [int()] * (N - 1)  # type: "List[int]"
    v = [int()] * (N - 1)  # type: "List[int]"
    w = [int()] * (N - 1)  # type: "List[int]"
    for i in range(N - 1):
        u[i] = int(next(tokens))
        v[i] = int(next(tokens))
        w[i] = int(next(tokens))
    solve(N, u, v, w)
 
 
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque


def main():
    # 幅優先探索
    def bfs():
        q = deque([0])
        while q:
            u = q.popleft()
            # 接続頂点を精査
            for v, w in g[u]:
                # まだチェックしていない頂点をチェック
                if color[v] == -1:
                    q.append(v)
                    # 偶数なら同じ色で塗る
                    if w == 0:
                        color[v] = color[u]
                    else:
                        color[v] = color[u] ^ 1

    n = int(input())
    g = [[] for _ in range(n)]
    # 塗りつぶし結果
    color = [-1] * n
    # スタートは黒で塗っておく
    color[0] = 1
    for _ in range(n - 1):
        u, v, w = map(int, input().split())
        u -= 1
        v -= 1
        w %= 2
        g[u].append((v, w))
        g[v].append((u, w))
    bfs()
    print(*color)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import deque


def main():
    def bfs(start):
        q = deque([start])
        while q:
            u = q.popleft()
            for v, w in g[u]:
                if color[v] == -1:
                    q.append(v)
                    if w == 0:
                        color[v] = color[u]
                    else:
                        color[v] = color[u] ^ 1

    n = int(input())
    g = [[] for _ in range(n)]
    color = [-1] * n
    color[0] = 1
    for _ in range(n - 1):
        u, v, w = map(int, input().split())
        u -= 1
        v -= 1
        w %= 2
        g[u].append((v, w))
        g[v].append((u, w))
    bfs(0)
    print(*color)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n = int(input())

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

from collections import deque
q = deque()
q.append(0)    
seen = [-1]*n
seen[0] = 0  #Node0 White    

while q:
    node = q.pop()
    for pair,length in graph[node]:
        if seen[pair]==-1:
            q.append(pair)
            if length%2 == 0:
                if seen[node] == 0:
                    seen[pair] = 0
                if seen[node] == 1:
                    seen[pair] = 1
            else:
                if seen[node] == 0:
                    seen[pair] = 1
                if seen[node] == 1:
                    seen[pair] = 0                         
for i in range(n):
    print(seen[i])

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)
def dfs(p,v,c):
    ans[v]=c
    for i in E[v]:
        if i[0]==p:
            continue
        if i[1]%2==1:
            dfs(v,i[0],1-c)
        else:
            dfs(v,i[0],c)
N= int(input())
ans = [100]*(N+1)
memo = {i:False for i in range(1,N+1)}
E = {i: []for i in range(1,N+1)}
for i in range(N-1):
    u,v,w = list(map(int,input().split()))
    E[v].append((u,w))
    E[u].append([v,w])
dfs(-1,1,1)
for i in range(1,N+1):
    print(ans[i])

Submission status: Accepted

Solution code:
N=int(input())

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

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


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

ne=[1]

while ne!=[]:
	t=ne.pop()
	for s,w in graph[t]:
		if color[s]==-1:
			ne.append(s)
			color[s]=color[t] if w%2==0 else (color[t]+1)%2

print(*color[1:],sep='\n')

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
import collections

def breadth_first_search(graph, root): 
    visited, queue = set([root]), collections.deque([root])
    color = [0] * len(graph)
    # root is always 0
    while queue: 
        vertex = queue.popleft()
        for neighbour in graph[vertex]: 
            if neighbour[0] not in visited: 
                visited.add(neighbour[0]) 
                queue.append(neighbour[0])
                color[neighbour[0]] = (color[vertex] + neighbour[1] % 2) % 2
    return color 

def solve(N: int, u: "List[int]", v: "List[int]", w: "List[int]"):
    graph = [[] for i in range(N)]
    for i in range(len(u)):
        graph[u[i]-1] += [[v[i]-1, w[i]]]
        graph[v[i]-1] += [[u[i]-1, w[i]]]
    color = breadth_first_search(graph, 0)
    print("\n".join(list(map(str, color))))
    return

def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    u = [int()] * (N - 1)  # type: "List[int]"
    v = [int()] * (N - 1)  # type: "List[int]"
    w = [int()] * (N - 1)  # type: "List[int]"
    for i in range(N - 1):
        u[i] = int(next(tokens))
        v[i] = int(next(tokens))
        w[i] = int(next(tokens))
    solve(N, u, v, w)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N = int(input())
G = [dict() for n in range(N)] ## 各頂点間の距離を一旦格納する

for n in range(N-1):
  u,v,w = map(int,input().split())
  G[u-1][v-1] = w
  G[v-1][u-1] = w
  
colors = [-1 for n in range(N)]
dists = [-1 for n in range(N)]
dists[0] = 0

"""考え方
現在、各頂点間の距離を求めた。
ここから「根」から各頂点への距離を求める。(dists)
そして、その値に基づいて適当に色を決める。(colors)
"""

q = [0]

while len(q) > 0:
  ## 計算済みの最大の頂点の値を取得
  ## 全ての頂点の距離を計算している場合は、whileが終了する
  r = q.pop()
  
  for node in G[r]:
    if dists[node] != -1: ## 距離を計算している頂点に関しては処理をスキップ
      continue
    
    dists[node] = dists[r] + G[r][node] # 根-対象の頂点間の距離を格納
    
    ## 次回は計算ずみの頂点の最大点から処理を進める。
    ## Gには値の順に登録されている
    q.append(node) 


## 偶奇だけを見ればいいので、色は下記で求まる。
## また、必ず答えが１つ存在する、ということが前提なのでこのようなシンプルな形で求めてしまって問題無い
for n in range(N):
  colors[n] = dists[n] % 2

for color in colors:
  print(color)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(100000)

N=int(input())
tree_dict={i:0 for i in range(N)}
tree_map=[[] for i in range(N)]
start=set([i for i in range(N)])

edge=[]

#数字の若いほうから見ていくとする
for i in range(N-1):
    u,v,w = map(int, input().split())
    tree_map[u-1].append([v-1,w])
    tree_map[v-1].append([u-1,w])

def fill(index, now_color, dist):
    for v,w in tree_map[index]:
        
        if tree_dict[v] == 0:
            if w%2==0:
                tree_dict[v] = now_color
                fill(v, tree_dict[v], w)
            else:
                tree_dict[v] = -1*now_color
                fill(v, tree_dict[v],w)


now_color=1
tree_dict[0]=now_color
fill(0,now_color, 0)

for i in tree_dict.values():
    if i==-1:
        print(0)
    else:
        print(1)

Submission status: Accepted

Solution code:
#21:30
n = int(input())
peer = [[] for _ in range(n)]
for _ in range(n-1):
  a,b,x = map(int,input().split())
  a -= 1
  b -= 1
  peer[a].append([b,x])
  peer[b].append([a,x])
ans = [-1 for _ in range(n)]
now = [0]
while now != []:
  last = now
  now = []
  for x in last:
    for yz in peer[x]:
      y = yz[0]
      z = yz[1]
      if ans[y] == -1:
        ans[y] = (ans[x] + z) % 2
        now.append(y)
  #print(now)
for i in range(n):
  print(ans[i])

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)
n=int(input())
a=[[] for i in range(n)]
for i in range(n-1):
    u,v,w=map(int,input().split())
    a[u-1].append((v-1,w))
    a[v-1].append((u-1,w))
b=[None for i in range(n)]
def k(v,dis):
    b[v]=dis
    for next_v,w in a[v]:
        if b[next_v]!=None:
            continue
        if w%2==0:
            k(next_v,dis)
        else:
            k(next_v,1-dis)
k(0,0)
for i in range(n):
    print(b[i])

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(20000000)

N = int(input())
Tree = [[] for i in range(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])

ans = [-1]*N

def dfs(node, dist):
    for next_node, size in Tree[node]:
        if ans[next_node] == -1:
            ans[next_node] = ((dist+size)%2)
            dfs(next_node, dist+size)
dfs(0, 0)
print(*ans, sep='\n')

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(200000)

N = int(input())

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

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


def dfs(v, p, c):
    ans[v - 1] = c
    for next_v, distance in neighbors[v]:
        if next_v == p:
            continue
        next_c = c if distance % 2 == 0 else 1 - c
        dfs(next_v, v, next_c)


dfs(1, -1, 0)
for e in ans:
    print(e)

Submission status: Accepted

Solution code:
n = int(input())
graph = [[] for i in range(n)]

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

colors = [-1] * n
colors[0] = 0
Me_Parent = [[0, -1]]
while Me_Parent:
    m, p = Me_Parent.pop()
    Child = graph[m]
    for c, w in Child:
        if c != p:
            colors[c] = (colors[m] + w) % 2
            Me_Parent.append([c, m])
            
for i in range(n):
    print(colors[i])

Submission status: Accepted

Solution code:
import math
import functools
import itertools
import numpy as np
import sys
MAX_INT = int(10e10)
MIN_INT = -MAX_INT
mod = 1000000007
sys.setrecursionlimit(1000000)
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

def tami(node,cost):
  if visited[node] == True:
    return
  else:
    visited[node] = True
    if cost%2 == 0:
      ans[node-1] = 0
    else:
      ans[node-1] = 1
    for x,c in root[node]:
      tami(x, cost+c)

N = I()
uvw = [IL() for i in range(N-1)]

root = [[] for _ in range(N+1)]
visited = [False]*(N+1)
ans = [0]*N

for u,v,w in uvw:
  root[u].append([v, w])
  root[v].append([u, w])

tami(1, 0)
for i in ans:
  print(i)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)
# 上記の文がないとREになる。


def k(v, distance):  # distanceは0or1
    flag[v] = distance  # 最初は0

    for next_v, w in graph[v]:
        if flag[next_v] == 1 or flag[next_v] == 0:  # 到達済み（親）であればcontinue
            continue
        if (w % 2) == 0:  # そのノードへの距離が偶数であればそのまま（最初は0なので）
            k(next_v, distance)
        else:
            k(next_v, 1-distance)


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

for i in range(N-1):
    u, v, w = map(int, input().split())
    graph[u-1].append((v-1, w))
    graph[v-1].append((u-1, w))
# これによって木が定義できた
# print(graph)

flag = [None for _ in range(N)]  # まだどの頂点も探索していない

k(0, 0)  # 親を強制的に決めてよい, この場合は0のノードを親にしている
for i in range(N):
    print(int(flag[i]))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)
# 上記の文がないとREになる。
N = int(input())
graph = [[] for _ in range(N)]

for i in range(N-1):
    u, v, w = map(int, input().split())
    graph[u-1].append((v-1, w))
    graph[v-1].append((u-1, w))
# これによって木が定義できた
# print(graph)

flag = [None for _ in range(N)]  # まだどの頂点も探索していない


def k(v, distance):  # distanceは0or1
    flag[v] = distance  # 最初は0

    for next_v, w in graph[v]:
        if flag[next_v] == 1 or flag[next_v] == 0:  # 到達済み（親）であればcontinue
            continue
        if (w % 2) == 0:  # そのノードへの距離が偶数であればそのまま（最初は0なので）
            k(next_v, distance)
        else:
            k(next_v, 1-distance)


k(0, 0)  # 親を強制的に決めてよい, この場合は0のノードを親にしている
for i in range(N):
    print(int(flag[i]))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)
N = int(input())
graph = [[] for _ in range(N)]

for i in range(N-1):
    u, v, w = map(int, input().split())
    graph[u-1].append((v-1, w))
    graph[v-1].append((u-1, w))
# これによって木が定義できた
# print(graph)

flag = [None for _ in range(N)]  # まだどの頂点も探索していない


def k(v, distance):  # distanceは0or1
    flag[v] = distance  # 最初は0

    for next_v, w in graph[v]:
        if flag[next_v] == 1 or flag[next_v] == 0:  # 到達済み（親）であればcontinue
            continue
        if (w % 2) == 0:  # そのノードへの距離が偶数であればそのまま（最初は0なので）
            k(next_v, distance)
        else:
            k(next_v, 1-distance)


k(0, 0)  # 親を強制的に決めてよい, この場合は0のノードを親にしている
for i in range(N):
    print(int(flag[i]))