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: Time Limit Exceeded

Solution code:
N = int(input())

class Edge:

    def __init__(self,base,to,weight):
        self.base = base
        self.to = to
        self.weight = weight
        self.is_used = False




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

colors = [100] * N


def dfs(current_node,current_color):
    colors[current_node - 1] = current_color

    same_type_edges = list(filter(lambda e: e.base == current_node and e.weight % 2 ==0 and not e.is_used,edges))
    diff_type_edges = list(filter(lambda e: e.base == current_node and e.weight % 2 !=0 and not e.is_used,edges))
    for e in same_type_edges:
        e.is_used = True
        dfs(e.to,current_color)
    for e in diff_type_edges:
        e.is_used = True
        dfs(e.to, 1- current_color)


dfs(1,0)

for i in range(0,N):
    print(colors[i])

Submission status: Time Limit Exceeded

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

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


# 探索
for key, value in tree_dict.items():
    if len(value) == 1:
        break
# print(key)
paint_dict = dict()

q = [key]
paint_dict[key] = 0

idx = 0
while len(q) < N:
    k = q[idx]
    #print("k", k, paint_dict[k])
    for to, w in tree_dict[k]:
        if to not in q[:idx]:
            if (w + paint_dict[k]) % 2 == 0:
                paint_dict[to] = 0
            else:
                paint_dict[to] = 1
            #print(paint_dict[to], to, w)
            q.append(to)
    idx += 1
for i in range(N):
    print(paint_dict[i+1])

Submission status: Time Limit Exceeded

Solution code:
import collections

n=int(input())
ans=[0]*(n+1)
s=set()
u,v,w=map(int,input().split())
s.add(u)
s.add(v)
if w%2==0:
  ans[u]=1
  ans[v]=1
elif w%2==1:
  ans[u]=1
  ans[v]=0
q=collections.deque()
cnt=1
cnt2=1
while 1:
  if cnt==n-1:
    break
  else:
    if cnt2<n-1:
      u,v,w=map(int,input().split())
    else:
      tmp=q.popleft()
      u,v,w=tmp[0],tmp[1],tmp[2]
    cnt2+=1
    if u in s:
      s.add(v)
      cnt+=1
      if w%2==0:
        ans[v]=ans[u]
      else:
        ans[v]=abs(ans[u]-1)
    elif v in s:
      s.add(u)
      cnt+=1
      if w%2==0:
        ans[u]=ans[v]
      else:
        ans[u]=abs(ans[v]-1)
    else:
      q.append([u,v,w])
for i in range(1,n+1):
  print(ans[i])

Submission status: Time Limit Exceeded

Solution code:
N = int(input())

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

def dfs() :
	paint = [-1] * (N + 1)
	
	queue = [1]
	paint[1] = 1

	while queue :
		current = queue.pop(0)

		for u, v, w in uvw :
			if v == current :
				u, v = v, u

			if u == current and paint[v] == -1 :
				queue.append(v)
				paint[v] = (paint[u] + w) % 2

	return paint[1:]

for i in dfs() :
	print(i)

Submission status: Time Limit Exceeded

Solution code:
def sol(inp=input):
    n=int(inp())
    pots=[None for _ in range(n)]
    edges=[list(map(int,inp().split())) for _ in range(n-1)]
    
    fixed=set()
    fixed.add(1)
    pots[0]=0
    for _ in range(n):
        for u,v,w in edges:
            if u not in fixed and v not in fixed:
                continue
            if u in fixed:
                a=u
                b=v
            elif v in fixed:
                a=v
                b=u
            pots[b-1]=pots[a-1]+w
            fixed.add(b)
        if len(fixed)==n:
            break
    return [p%2 for p in pots]
for c in sol():
  print(c)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

n=int(input())
E=[]
W=[]
node_l=np.zeros(n)
node_l[0]=1
for i in range(n-1):
    u,v,w=map(int,input().split())
    #print(u,v,w)
    E.append([u,v])
    W.append(w)
#print(E,W)

def bfs(node,node_l,l,w_l):
    i=0
    for edge in l:
        if edge[0]==node:
            if node_l[edge[1]-1]==0:
                if W[i]%2==0:
                    node_l[edge[1]-1]=node_l[node-1]
                    bfs(edge[1],node_l,l,w_l)
                else:
                    node_l[edge[1]-1]=node_l[node-1]*-1
                    bfs(edge[1],node_l,l,w_l)
        elif edge[1]==node:
            if node_l[edge[0]-1]==0:
                if W[i]%2==0:
                    node_l[edge[0]-1]=node_l[node-1]
                    bfs(edge[0],node_l,l,w_l)
                else:
                    node_l[edge[0]-1]=node_l[node-1]*-1
                    bfs(edge[0],node_l,l,w_l)
        i+=1
    return


bfs(1,node_l,E,W)
for i in range(n):
    if node_l[i]==1:
        print('1',end='\n')
    else:
        print('0',end='\n')

Submission status: Time Limit Exceeded

Solution code:
import sys

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

#  0: 白
#  1: 黒
# -1: 未確定
wb = [-1] * n

# とりあえず一箇所を白に固定する
wb[0] = 0

# 残りの未確定頂点数
progress = n - 1

while True:
    for i in range(n - 1):
        u, v, w = uvw[i]
        u -= 1
        v -= 1
        if wb[u] == -1 and wb[v] == -1:
            # 両方未確定なので何も出来ない
            continue
        if wb[u] != -1 and wb[v] != -1:
            # 両方確定なので何もしない
            continue
        if wb[u] in (0, 1):
            # 頂点v_iのみが未確定
            if w % 2 == 0:
                # 偶数なら頂点v_iはu_iと同じ
                wb[v] = wb[u]
            else:
                # 奇数なら逆
                wb[v] = 1 - wb[u]
        else:
            # 頂点u_iのみが未確定
            if w % 2 == 0:
                wb[u] = wb[v]
            else:
                wb[u] = 1 - wb[v]
        progress -= 1
        if progress == 0:
            # 完了
            print(*wb, sep='\n')
            sys.exit(0)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())

uvws = [list(map(int, input().split())) for _ in range(n-1)]
uvws.sort(key=lambda x: x[0])

zeros = {1}
ones = set()

while len(zeros) + len(ones) < n:
    for uvw in uvws:
        u, v, w = uvw
        if u not in zeros and u not in ones and v in zeros:
            if w % 2:
                ones.add(u)
            else:
                zeros.add(u)
        if u not in zeros and u not in ones and v in ones:
            if w % 2:
                zeros.add(u)
            else:
                ones.add(u)

        if v not in zeros and v not in ones and u in zeros:
            if w % 2:
                ones.add(v)
            else:
                zeros.add(v)
        if v not in zeros and v not in ones and u in ones:
            if w % 2:
                zeros.add(v)
            else:
                ones.add(v)

for i in range(1, n+1):
    print(1 if i in ones else 0)

Submission status: Time Limit Exceeded

Solution code:
#!venv/bin/python

#N = [ int(x) for x in input().split() ]
#S = input()

N = int(input())
K = []
for n in range(N-1):
    K.append([ int(x) for x in input().split() ])

color = [ None for i in range(N)]
color[0] = 1
solved = 1

next_k = K
while solved < N:
    K = next_k
    next_k = []
    for k in K:
        f = k[0] - 1
        t = k[1] - 1
        l = k[2]
        if color[f]:
            if l % 2 == 0:
                color[t] = color[f]
            else:
                color[t] = color[f] * -1
        elif color[t]:
            if l % 2 == 0:
                color[f] = color[t]
            else:
                color[f] = color[t] * -1
        else:
            next_k.append(k)
            continue
        solved += 1

ans = []
for c in color:
    if c == 1:
        ans.append("1")
    else:
        ans.append("0")
print("\n".join(ans))

Submission status: Time Limit Exceeded

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

UVW.sort(key = lambda x: x[0])
color = [2 for _ in range(N)]

while len(UVW) > 0:
  uvw = UVW.pop(0)
  if len(UVW) == N - 2:
    if uvw[2] % 2 == 0:
      color[uvw[0] - 1] = 0
      color[uvw[1] - 1] = 0
    else:
      color[uvw[0] - 1] = 0
      color[uvw[1] - 1] = 1
  if uvw[2] % 2 == 0:
    if color[uvw[0] - 1] != 2:
      color[uvw[1] - 1] = color[uvw[0] - 1]
    elif color[uvw[1] - 1] != 2:
      color[uvw[0] - 1] = color[uvw[1] - 1]
    else:
      UVW.append(uvw)
  else:
    if color[uvw[0] - 1] != 2:
      color[uvw[1] - 1] = color[uvw[0] - 1] ^ 1
    elif color[uvw[1] - 1] != 2:
      color[uvw[0] - 1] = color[uvw[1] - 1] ^ 1
    else:
      UVW.append(uvw)

for c in color:
  print(c)

Submission status: Time Limit Exceeded

Solution code:
###############################################################################

from sys import stdout
from bisect import bisect_left as binl
from copy import copy, deepcopy
from collections import defaultdict


mod = 1


def intin():
    input_tuple = input().split()
    if len(input_tuple) <= 1:
        return int(input_tuple[0])
    return tuple(map(int, input_tuple))


def intina():
    return [int(i) for i in input().split()]


def intinl(count):
    return [intin() for _ in range(count)]


def modadd(x, y):
    global mod
    return (x + y) % mod


def modmlt(x, y):
    global mod
    return (x * y) % mod


def lcm(x, y):
    while y != 0:
        z = x % y
        x = y
        y = z
    return x


def combination(x, y):
    assert(x >= y)

    if y > x // 2:
        y = x - y

    ret = 1

    for i in range(0, y):
        j = x - i
        i = i + 1

        ret = ret * j
        ret = ret // i

    return ret


def get_divisors(x):
    retlist = []
    for i in range(1, int(x**0.5) + 3):
        if x % i == 0:
            retlist.append(i)
            retlist.append(x // i)
    return retlist


def get_factors(x):
    retlist = []
    for i in range(2, int(x**0.5) + 3):
        while x % i == 0:
            retlist.append(i)
            x = x // i
    retlist.append(x)
    return retlist


def make_linklist(xylist):
    linklist = {}
    for a, b in xylist:
        linklist.setdefault(a, [])
        linklist.setdefault(b, [])
        linklist[a].append(b)
        linklist[b].append(a)
    return linklist


def calc_longest_distance(linklist, v=1):
    distance_list = {}
    distance_count = 0
    distance = 0
    vlist_previous = []
    vlist = [v]
    nodecount = len(linklist)

    while distance_count < nodecount:
        vlist_next = []
        for v in vlist:
            distance_list[v] = distance
            distance_count += 1
            vlist_next.extend(linklist[v])
        distance += 1
        vlist_to_del = vlist_previous
        vlist_previous = vlist
        vlist = list(set(vlist_next) - set(vlist_to_del))

    max_distance = -1
    max_v = None
    for v, distance in distance_list.items():
        if distance > max_distance:
            max_distance = distance
            max_v = v

    return (max_distance, max_v)


def calc_tree_diameter(linklist, v=1):
    _, u = calc_longest_distance(linklist, v)
    distance, _ = calc_longest_distance(linklist, u)
    return distance


class UnionFind:

    def __init__(self, n):
        self.parent = [i for i in range(n)]

    def root(self, i):
        if (self.parent[i] == i):
            return i
        self.parent[i] = self.root(self.parent[i])
        return self.parent[i]

    def unite(self, i, j):
        rooti = self.root(i)
        rootj = self.root(j)
        if rooti == rootj:
            return
        if i < j:
            self.parent[rootj] = rooti
        else:
            self.parent[rooti] = rootj

    def same(self, i, j):
        return self.root(i) == self.root(j)


###############################################################################


def make_wlinklist(xyzlist):
    linklist = {}
    for a, b, c in xyzlist:
        linklist.setdefault(a, [])
        linklist.setdefault(b, [])
        linklist[a].append((b, c))
        linklist[b].append((a, c))
    return linklist


def main():
    n = intin()
    if n == 1:
        print(0)
        return
    uvwlist = intinl(n - 1)

    linklist = make_wlinklist(uvwlist)
    anslist = {1: 0}
    anscount = 1
    search = [(1, 0)]

    while anscount < n:
        search_next = []
        for u, color in search:

            #print('%s %s' % (u, linklist[u]))

            for v, w in linklist[u]:
                if w & 1:
                    ans = 0 if color else 1
                else:
                    ans = 1 if color else 0
                if v not in anslist:
                    anslist[v] = ans
                    anscount += 1
                search_next.append((v, ans))
        search = search_next

        #print('== anscount=%d %s' % (anscount, anslist))


    #print(anslist)

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


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def dfs(i, V, E):
    for k in range(1, len(V)):
        if V[k] >= 0:
            continue
        for e in E[i]:
            if e[0] == k:
                if e[1] % 2:
                    V[k] = 1 - V[i]
                else:
                    V[k] = V[i]
                V = dfs(k, V, E)
    return V

n = int(input())
E = {}
for i in range(n - 1):
    ui, vi, wi = map(int, input().split())
    if ui in E.keys():
        E[ui].append([vi, wi])
    else:
        E[ui] = [[vi, wi]]
    if vi in E.keys():
        E[vi].append([ui, wi])
    else:
        E[vi] = [[ui, wi]]
V = [-1 for _ in range(n + 1)]
V[1] = 0
V = dfs(1, V, E)
for vi in V[1:]:
    print(vi)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter


def solve(string):
    n, *uvw = map(int, string.split())
    count = Counter(uvw[::3] + uvw[1::3])
    uvw = list(zip(uvw[::3], uvw[1::3], uvw[2::3]))
    whites = set([count.most_common(1)[0][0]])
    blacks = set([])
    while len(uvw) > 0:
        tmp = []
        for i in range(len(uvw)):
            t = uvw.pop()
            if t[0] in whites:
                if t[2] % 2 == 0:
                    whites.add(t[1])
                else:
                    blacks.add(t[1])
            elif t[1] in whites:
                if t[2] % 2 == 0:
                    whites.add(t[0])
                else:
                    blacks.add(t[0])
            elif t[0] in blacks:
                if t[2] % 2 == 0:
                    blacks.add(t[1])
                else:
                    whites.add(t[1])
            elif t[1] in blacks:
                if t[2] % 2 == 0:
                    blacks.add(t[0])
                else:
                    whites.add(t[0])
            else:
                tmp.append(t)
        uvw = tmp
    ans = ["0"] * n
    for i in range(n):
        if i + 1 in blacks:
            ans[i] = "1"

    return "\n".join(ans)


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

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
U = [[int(a) for a in input().split()] for _ in range(n-1)]

arr = [-1] * n
u, v, w = U[0]
arr[u-1] = 0
arr[v-1] = (arr[u-1] + w) % 2
done = set([u, v])

while not len(done) == n:
    for u, v, w in U:
        if u in done and v in done:
            continue
        if u in done:
            arr[v-1] = (arr[u-1] + w) % 2
            done.add(v)
        if v in done:
            arr[u-1] = (arr[v-1] + w) % 2
            done.add(u)

for i in arr:
    print(i)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
uvw = [list(map(int, input().split())) for _ in range(n - 1)]
ans = [-1] * (n + 1)
ans[1] = True
while uvw:
    nuvw = []
    for u, v, w in uvw:
        if ans[u] != -1:
            if w % 2:
                ans[v] = not ans[u]
            else:
                ans[v] = ans[u]
        elif ans[v] != -1:
            if w % 2:
                ans[u] = not ans[v]
            else:
                ans[u] = ans[v]
        else:
            nuvw.append([u, v, w])
    uvw = nuvw
for x in ans[1:]:
    print(x * 1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
N = int(input())
edge = [[] for _ in range(N)]
W = [[3 for i in range(N)] for i in range(N)]
Color = [1 for i in range(N)]

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


d = [[-1] * N]

d[0][0] = 0
q = deque([0])
while len(q) > 0:
    u = q.popleft()
    for v in edge[u]:
        if d[0][v] > -1:
            continue
        d[0][v] = d[0][u] + 1
        if W[u][v] == 0:
            Color[v] = Color[u]
        if W[u][v] == 1:
            Color[v] = (Color[u] + 1) % 2
        q.append(v)

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

Submission status: Time Limit Exceeded

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

UVW.sort(key = lambda x: x[0])
color = [2 for _ in range(N)]

while len(UVW) > 0:
  uvw = UVW.pop()
  if len(UVW) == N - 2:
    if uvw[2] % 2 == 0:
      color[uvw[0] - 1] = 0
      color[uvw[1] - 1] = 0
    else:
      color[uvw[0] - 1] = 0
      color[uvw[1] - 1] = 1
  if uvw[2] % 2 == 0:
    if color[uvw[0] - 1] != 2:
      color[uvw[1] - 1] = color[uvw[0] - 1]
    elif color[uvw[1] - 1] != 2:
      color[uvw[0] - 1] = color[uvw[1] - 1]
    else:
      UVW.append(uvw)
  else:
    if color[uvw[0] - 1] != 2:
      color[uvw[1] - 1] = color[uvw[0] - 1] ^ 1
    elif color[uvw[1] - 1] != 2:
      color[uvw[0] - 1] = color[uvw[1] - 1] ^ 1
    else:
      UVW.append(uvw)

for c in color:
  print(c)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
N = int(input())
edge = [[] for _ in range(N)]
W = [[3 for i in range(N)] for i in range(N)]
Color = [1 for i in range(N)]
for _ in range(N - 1):
    a, b, w = map(int, input().split())
    w = w % 2
    edge[a - 1].append(b - 1)
    edge[b - 1].append(a - 1)
    W[a-1][b-1] = w % 2
    W[b-1][a-1] = w % 2


d = [[-1] * N]

d[0][0] = 0
q = deque([0])
while len(q) > 0:
    u = q.popleft()
    for v in edge[u]:
        if d[0][v] > -1:
            continue
        d[0][v] = d[0][u] + 1
        if W[u][v] == 0:
            Color[v] = Color[u]
        if W[u][v] == 1:
            Color[v] = Color[u] * (-1)
        q.append(v)

for i in range(N):
    Color[i] = max(Color[i],0)
print(*Color, sep = "\n")

Submission status: Time Limit Exceeded

Solution code:
n = int(input())

g = [[0 for _ in range(n)] for _ in range(n)]
ans = [-1 for _ in range(n)]

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


ans[0] = 0 # white

def dfs(now):
    for i in range(n):
        if i == now or ans[i] != -1 or g[i][now] == 0:
            continue
        elif g[i][now] % 2 == 0:
            ans[i] = ans[now]
            dfs(i)
        else:
            ans[i] = ans[now] ^ 1
            dfs(i)


dfs(0)

for a in ans:
    print(a)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())

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

Li = [0] * 2 + [2] * (n-1)

while 2 in Li:
    for uvw in uvws:
        u, v, w = uvw
        if Li[u] != 2 and Li[v] == 2:
            if w % 2 == 0:
                Li[v] = Li[u]
            else:
                Li[v] = 1 - Li[u]
        elif Li[v] != 2 and Li[u] == 2:
            if w % 2 == 0:
                Li[u] = Li[v]
            else:
                Li[u] = 1 - Li[v]

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

Submission status: Time Limit Exceeded

Solution code:
n = int(input())

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

Li = [0] * 2 + [2] * (n-1)

while 2 in Li:
    for uvw in uvws:
        u, v, w = uvw
        if Li[u] != 2:
            if w % 2 == 0:
                Li[v] = Li[u]
            else:
                Li[v] = 1 - Li[u]
        elif Li[v] != 2:
            if w % 2 == 0:
                Li[u] = Li[v]
            else:
                Li[u] = 1 - Li[v]

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

Submission status: Time Limit Exceeded

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

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

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

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
ans = dfs(0, 0)

for _, c in sorted(ans, key=lambda x: x[0]):
  if c % 2 == 0:
    print(0)
  else:
    print(1)

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
# Your code here!

def warshall_floyd(d):
    #d[i][j]: iからjへの最短距離
    for k in range(n):
        for i in range(n):
            for j in range(n):
                d[i][j] = min(d[i][j],d[i][k] + d[k][j])
    return d

##############################
n = int(input()) #n:頂点数　w:辺の数

d = [[float("inf") for i in range(n)] for i in range(n)] 
#d[u][v] : 辺uvのコスト(存在しないときはinf)
for i in range(n-1):
    x,y,z = map(int,input().split())
    x -= 1
    y -= 1
    d[x][y] = z
    d[y][x] = z
for i in range(n):
    d[i][i] = 0 #自身のところに行くコストは０
# print(warshall_floyd(d))

dist = warshall_floyd(d)

for elm in dist[0]:
    if elm % 2 == 0:
        print(0)
    else:
        print(1)

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.readline
N = int(input())
uvw = [list(map(int, input().split())) for _ in range(N - 1)]
g = [[] for _ in range(N)]
for a, b, w in uvw:
    g[a-1].append((b-1, w))
    g[b - 1].append((a - 1, w))

children = [[] for _ in range(N)]
colors = [None]*N
q = [(0, None, 0)]  # nodeid, parent, color
while len(q) > 0:
    v, p, c = q.pop()
    colors[v] = c
    for u, w in g[v]:
        if u != p:
            c_ = (c+(w%2))%2
            q.append((u, v, c_))
            children[v].append(u)
for c in colors:
    print(c)

Submission status: Accepted

Solution code:
from collections import deque

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

colors = [-1 for _ in range(N)]
stack = deque()
stack.append(0)
colors[0] = 0

while stack:
    n = stack.popleft()
    for _next, w in graph[n]:
        if colors[_next] != -1:
            continue
        colors[_next] = (colors[n] + w) % 2
        stack.append(_next)

for c in colors:
    print(c)

Submission status: Accepted

Solution code:
from collections import deque

N = int(input())
ki = [[] for _ in range(N)]
for _ in range(N-1):
    u, v, w = map(int, input().split())
    ki[u-1].append([v-1, w])
    ki[v-1].append([u-1, w])
f = [False]*N
f[0] = True
c = [0]*N

q = deque([0])
while q:
    now = q.popleft()
    for nxt, w in ki[now]:
        if f[nxt]:
            continue
        if w&1:
            c[nxt] = c[now]^1
        else:
            c[nxt] = c[now]
        q.append(nxt)
        f[nxt] = True


for a in c:
    print(a)

Submission status: Accepted

Solution code:
import sys
# sys.setrecursionlimit(100000)


def input():
    return sys.stdin.readline().strip()


def input_int():
    return int(input())


def input_int_list():
    return [int(i) for i in input().split()]


def main():
    from collections import defaultdict, deque
    n = input_int()
    G = defaultdict(dict)
    color = [None] * (n + 1)
    for _ in range(n - 1):
        u, v, w = input_int_list()
        G[u][v] = w
        G[v][u] = w

    # ノード1 を起点にBFSをする
    color[1] = 0
    dq = deque()
    dq.append((1, 0))  # node,cost
    while dq:
        u, cur = dq.popleft()
        for v, cost in G[u].items():
            if color[v] is None:
                if (cur + cost) % 2 == 0:
                    color[v] = 0
                else:
                    color[v] = 1
                dq.append((v, cur + cost))
    for c in color[1:]:
        print(c)

    return


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n=int(input())
col=[-1]*n
e=[[[],[]]for i in range(n)]
for i in range(n-1):
    u,v,w=map(int,input().split())
    u-=1
    v-=1
    w%=2
    e[u][w].append(v)
    e[v][w].append(u)
col[0]=1
from collections import deque
dq=deque([])
#pop/append/(append,pop)_left/in/len/count/[]/index/rotate()(右へnずらす)
dq.append(0)
while dq:
    a=dq.pop()
    b=col[a]
    for i in range(2):
        for ne in e[a][i]:
            if col[ne]==-1:
                col[ne]=b^i
                dq.appendleft(ne)
print(*col,sep='\n')

Submission status: Accepted

Solution code:
# coding: utf-8
import sys

# from operator import itemgetter
sysread = sys.stdin.buffer.readline
read = sys.stdin.buffer.read
printout = sys.stdout.write
sprint = sys.stdout.flush
#from heapq import heappop, heappush
#from collections import defaultdict
sys.setrecursionlimit(10 ** 7)
#import math
# from itertools import product, accumulate, combinations, product
#import bisect
# import numpy as np
# from copy import deepcopy
from collections import deque
# from decimal import Decimal
# from numba import jit

INF = 1 << 50
EPS = 1e-8
mod = 998244353


def intread():
    return int(sysread())
def mapline(t=int):
    return map(t, sysread().split())
def mapread(t=int):
    return map(t, read().split())

def dfs(c, num, to, cols):
    for n, nw in to[c]:
        if cols[n] == -1:
            y = (num + nw) % 2
            cols[n] = (num + nw) % 2
            dfs(n, y, to, cols)

def run():
    N = intread()
    to = [[] for _ in range(N+1)]
    for _ in range(N-1):
        u, v, w = mapline()
        to[u].append((v, w))
        to[v].append((u, w))
    cols = [-1] * (N+1)
    cols[1] = 0
    dfs(1, 0, to, cols)

    for x in cols[1:]:
        print(x)

if __name__ == "__main__":
    run()

Submission status: Accepted

Solution code:
def abc126d():
    n = int(input())
    e = [list() for _ in range(n)]
    for _ in range(n-1):
        u, v, w = map(int, input().split())
        e[u - 1].append([v - 1, w])
        e[v - 1].append([u - 1, w])
    ans = [-1] * n
    ans[0] = 0
    q = e[0].copy()
    while len(q) > 0:
        v, w = q.pop()
        #print(v, w)
        if ans[v] != -1: continue
        elif w % 2 == 0: ans[v] = 0
        else: ans[v] = 1
        for v1, w1 in e[v]:
            if ans[v1] != -1: continue
            q.append([v1, w+w1])
    for i in ans:
        print(i)
abc126d()

Submission status: Accepted

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

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

def dfs(graph, queue, color):
    is_bigraph = True
    while queue:
        current = queue.pop()
        current_color = color[current]

        for _next, dist in graph[current]:
            if color[_next] != - 1:
                if color[_next] != (color[current] + dist) % 2:
                    is_bigraph = False
            else:
                color[_next] = (color[current] + dist) % 2
                queue.append(_next)

    return is_bigraph

queue = [1]
color = [-1] + [-1] * n
color[1] = 0
if not dfs(graph, queue, color):
    print('Something wrong')
    sys.exit(1)

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

Submission status: Accepted

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

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

q = deque()
q.append((0, 0))
color = {}
while q:
    node, dist = q.popleft()
    if node in color:
        continue
    if dist % 2 == 0:
        color[node] = 0
    else:
        color[node] = 1
    for n_node, n_dist in edges[node]:
        q.append((n_node, dist+n_dist))

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(500*500)
n = int(input())
a = [[] for _ in range(n)]; b = [-1]*n; b[0] = 0
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])
def dfs(A, k):
    for i in A[k]:
        if b[i[0]] == -1:
            b[i[0]] = b[k]+i[1]
            dfs(A, i[0])
dfs(a, 0)
for i in b:
    print(0) if i%2 == 0 else print(1)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1<<30)

N = int(input())
def dfs(x):
    for y in Tree[x]:
        if Parent[x] != y:
            Parent[y] = x
            distance[y] += Web[min(x,y),max(x,y)]+distance[x]
            dfs(y)
Tree = [[] for i in range(N+1)]
Parent = [0]*(N+1)
Web = dict()
for i in range(N-1):
    a,b,w = map(int,input().split())
    Tree[a].append(b)
    Tree[b].append(a)
    Web[(min(a,b),max(a,b))] = w
distance = [0]*(N+1)
dfs(1)
for i in distance[1:]:
    if i%2 == 0:
        print(1)
    else:
        print(0)

Submission status: Accepted

Solution code:
from collections import deque
N=int(input())
G=[[] for _ in range(N)]
for i in range(N-1):
	u, v, w = map(int, input().split())
	u,v=u-1,v-1
	G[u].append([v,w])
	G[v].append([u,w])
#print(G) #[[[1, 2]], [[0, 2], [2, 1]], [[1, 1]]]
color=[-1]*N
que=deque([0])
color[0]=0

while que:#dfs
	p=que.popleft()#直近で追加したグラフの頂点を取得
	for q, W in G[p]:#結合しているグラフの頂点を参照
		if color[q]==-1:#塗られていないなら
			color[q]=(color[p]+W)%2
			que.append(q)
print(*color, sep="\n")

Submission status: Accepted

Solution code:
from collections import deque

N = int(input())


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

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

ans = [-1] * N
q = deque()

ans[0] = 0
q.append(0)

while q:
    new = q.popleft()
    for node, weight in vlist[new]:
        if ans[node] != -1:
            continue
        ans[node] = (ans[new] + weight) % 2
        q.append(node)
    
for i in ans:
    print(i)