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

Solution code:
N = int(input())

used = [False]*N
verts = [[[], None] for i in range(N)] # to color

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

q = [(0, 0)] # 0, distance
verts[0][1] = 1 # black
used[0] = True
while q != []:
    v, c = q.pop(0)
    vert = verts[v]
    for w,d in vert[0]:
        if not used[w]:
            used[w] = True
            if (c+d) % 2 == 0:
                verts[w][1] = 1
            else:
                verts[w][1] = 0
            q.append((w, c+d))
for i in range(N):
    print(verts[i][1])

Submission status: Accepted

Solution code:
from collections import deque


def solve(N, UVWs):
    vertexes = {}

    for u, v, w in UVWs:
        vertexes.setdefault(u, []).append((v, w % 2))
        vertexes.setdefault(v, []).append((u, w % 2))

    colors = [-1 for _ in range(N + 1)]
    colors[1] = 0
    que = deque()
    que.append((1, colors[1]))
    while que:
        u, c = que.popleft()
        for v, w in vertexes[u]:
            if colors[v] == -1:
                colors[v] = (c + w) % 2
                que.append((v, colors[v]))
    return "\n".join(str(c) for c in colors[1:])


if __name__ == "__main__":
    N = int(input())
    UVWs = [tuple(map(int, input().split(" "))) for _ in range(N - 1)]
    print(solve(N, UVWs))

Submission status: Accepted

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

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
        
n = int(input()) #n:頂点数　w:辺の数

# d = [[float("inf") for i in range(n)] for i in range(n)] 
d = []
#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
    d.append(list(map(int,input().split())))
# for i in range(n):
#     d[i][i] = 0 #自身のところに行くコストは０
# print(warshall_floyd(d))

dist = BFS(0,d,n)
# print(dist)
for elm in dist:
    if elm % 2 == 0:
        print(0)
    else:
        print(1)

Submission status: Accepted

Solution code:
from collections import defaultdict


class Solution:
    def main(self):
        N = int(input())
        self.hashmap = defaultdict(set)
        for i in range(N-1):
            u, v, w = map(int, input().split())
            self.hashmap[u-1].add((v-1, w))
            self.hashmap[v-1].add((u-1, w))
        # print(self.hashmap)
        self.colors = [None] * N
        for i in range(N):
            stack = [(i, 0)]
            while stack:
                idx, color = stack.pop()
                if self.colors[idx] == None:
                    self.colors[idx] = color
                    for node, weight in self.hashmap[idx]:
                        if weight % 2 == 0:
                            stack.append((node, color))
                        else:
                            stack.append((node, 1 ^ color))
        for i in range(N):
            print(self.colors[i])

    def dfs(self, i, color):
        if self.colors[i] is None:
            self.colors[i] = color
            for node, weight in self.hashmap[i]:
                if weight % 2 == 0:
                    self.dfs(node, color)
                else:
                    self.dfs(node, 1 ^ color)


if __name__ == '__main__':
    Solution().main()

Submission status: Accepted

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

res = [-1]*n
res[0] = 0
q = [0]
while len(q)>0:
    u = q.pop(0)
    if len(edge[u])==0:
        continue

    for v,w in edge[u]:
        if res[v]!=-1:
            continue
        if w%2==0:
            res[v] = res[u]
        else:
            res[v] = (res[u]+1)%2
        q.append(v)

for r in res:
    print(r)

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc126_d
import collections


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

connected = collections.defaultdict(list)
for (a, b, _) in triples:
    connected[a].append(b)
    connected[b].append(a)

dist = dict()
for (u, v, d) in triples:
    dist[u, v] = d
    dist[v, u] = d

ini, _, _ = triples[0]
stack = [ini]
color = dict()
color[ini] = False

while stack:
    state = stack.pop()
    for new_state in connected[state]:
        if new_state not in color:
            d = dist[state, new_state]
            color[new_state] = color[state] if d % 2 == 0 else (not color[state])
            stack.append(new_state)


for i in sorted(color):
    print(int(color[i]))

Submission status: Accepted

Solution code:
n = int(input())
A = [list(map(int,input().split())) for i in range(n-1)]

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

for i in range(len(A)):
    B[A[i][0]].append([A[i][1],A[i][2]])
    B[A[i][1]].append([A[i][0],A[i][2]])

root = 0
for i in range(len(B)):
    root = max(root, len(B[i]))

ANS = [-1 for i in range(n+1)]
ANS[root]=0
#print(B)
nurulist = [root]
t = 0
while t < len(nurulist):
    k = nurulist[t]
    col = ANS[k]
    for j in range(len(B[k])):
        if ANS[B[k][j][0]] == -1:
            ANS[B[k][j][0]] = (col + B[k][j][1])%2
            nurulist.append(B[k][j][0])
    t += 1


#print(ANS)

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

Submission status: Accepted

Solution code:


N = int(input())

 
# 隣接リスト
l = [[] for i in range(N+1)]

def tuika(l,a,b):
    l[a].append(b)
    l[b].append(a)

kisuu = [[] for i in range(N+1)] 
guusuu = [[] for i in range(N+1)]
for i in range(N-1):
    u,v,w = map(int,input().split())
    if w%2== 0:
        tuika(guusuu, u, v)
    else:
        tuika(kisuu, u, v)


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

stack = [1]
colors[1] = 1
while stack:
    node = stack.pop()
    for next_node in guusuu[node]:
        if colors[next_node]==0:
            stack.append(next_node)
            colors[next_node] = colors[node]
            
    for next_node in kisuu[node]:
        if colors[next_node]==0:
            stack.append(next_node)
            colors[next_node] = - colors[node]
            
            
#         else:
#             if nodes_color[next_node]==nodes_color[node]:
#                 nibu = False
#                 break
#     if not nibu:
#         break

colors_modify = [1 if x ==1 else 0 for x in colors[1:] ]

for c in colors_modify:
    print(c)

Submission status: Accepted

Solution code:
import heapq

def dijkstra(v,s,path):
    inf = float('inf')

    # 距離をinfで初期化
    d = [inf for i in range(v)]
    d[s] = 0

    # sへの距離は0
    q = [[0,s]]
    heapq.heapify(q)

    # 距離が最小の頂点から更新していけば
    # p[1]から行ける
    while q:
        p = heapq.heappop(q)

        # 頂点p[1]までの距離がheapないのp[1]までの距離より小さい場合、continue
        if d[p[1]]<p[0]:
            continue

        # 頂点p[1]から伸びる、全ての辺の距離を確認
        for i in range(len(path[p[1]])):
            # 頂点p[1]から行ける頂点の距離がp[1]までの距離とp[1]からの距離の和より小さい場合 -> 距離を更新し、heapに追加
            if d[path[p[1]][i][1]] > d[p[1]] + path[p[1]][i][0]:
                d[path[p[1]][i][1]] = d[p[1]]+path[p[1]][i][0]
                heapq.heappush(q,[d[path[p[1]][i][1]], path[p[1]][i][1]])
    return d


n = int(input())

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

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

d = dijkstra(n,0,a)

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

Submission status: Accepted

Solution code:
from collections import deque
N=int(input())

mp={}
for _ in range(N-1):
    i,j,w=map(int,input().split())
    if not i in mp:
        mp[i] = []
    if not j in mp:
        mp[j] = []
    mp[i].append((j,w))
    mp[j].append((i,w))


res = [-1 for _ in range(N+1)]
que = deque([])

que.append((1,0))
res[1]=0
while que:
    i, dist = que.popleft()
    for j, dist2 in mp[i]:
        if res[j] == -1:
            bw = (dist + dist2) % 2
            res[j] = bw
            que.append((j,bw))

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

Submission status: Accepted

Solution code:
from collections import deque
from heapq import heappush,heappop
import re

def int_raw():
    return int(input())

def ss_raw():
    return input().split()

def ints_raw():
    return list(map(int, ss_raw()))

INF = 1<<29
N  = int_raw()
tree = [[] for _ in range(N)]
for _ in range(N-1):
    a,b,w = ints_raw()
    a = a-1
    b = b-1
    tree[a].append((b,w))
    tree[b].append((a,w))

def main():
    colors = [-1]*N
    colors[0]=1
    qu = deque()
    qu.append((0,0,-1))
    while len(qu)!=0:
        cur = qu.popleft()
        if cur[0]%2 == 0:
            colors[cur[1]]=0
        else:
            colors[cur[1]]=1
        for e in tree[cur[1]]:
            if e[0] ==cur[2]:
                continue
            qu.append([cur[0]+e[1],e[0],cur[1]])
    for c in colors:
        print (c)      
            
main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000)

N=int(input())

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

for i in range(N-1):
    u,v,w=map(int,input().split())
    n[u].append([v,w])
    n[v].append([u,w])
L=[-1 for i in range(N+1)]
L[1]=0
def dfs(x):
    for i in n[x]:
        if L[i[0]]==-1:
            L[i[0]]=L[x]+i[1]
            dfs(i[0])
dfs(1)
#print(n)
#print(L)
for i in range(1,N+1):
    if L[i]%2==0:
        print(0)
    else:
        print(1)

Submission status: Accepted

Solution code:
n = int(input())
ls = [[] for i in range(n)]
for i in range(n-1):
    u,v,w = map(int,input().split())
    ls[u-1].append([v-1,w])
    ls[v-1].append([u-1,w])
#行ってないとこはtrue
check_edge = [True for i in range(n)]
stack = []
stack.append(0)
check_edge[0] = False
ans = [0]*n
while stack:
    v = stack.pop()
    for j in ls[v]:
        u,w = j[0],j[1]
        if not check_edge[u]:continue
        if w % 2 == 0:
            ans[u] = ans[v]
        else:
            ans[u] = not ans[v]
        check_edge[u] = False
        stack.append(u)
for i in range(n):
    if ans[i] == True:
        print(1)
    else:
        print(0)

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc126/tasks/abc126_d
import itertools
from collections import Counter
from collections import defaultdict
import bisect

def main():
    N = int(input())

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

    que = [1]
    ans[1] = 0  # 1 を白にする

    while que:
        cursor = que.pop(0)
        for next, weight in vec[cursor]:
            if ans[next] == -1:
                if weight % 2 == 0:
                    ans[next] = ans[cursor]
                else:
                    ans[next] = 1 if ans[cursor] == 0 else 0
                que.append(next)
    for i in ans[1:]:
        print(i)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(100000000)

N = int(input())

v_to = [[] for i in range(N + 1)]
v_color = [-1 for i in range(N + 1)]

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

def unko(i, par):
  for to, w in v_to[i]:
    if to == par:
      continue
    if w % 2 == 1:
      v_color[to] = 1 - v_color[i]
    else:
      v_color[to] = v_color[i]
    unko(to, i)


v_color[1] = 0
unko(1, 1)

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()
from collections import defaultdict

def main():
    N = II()
    edges = [[] for _ in range(N)]
    for _ in range(N-1):
        u, v, w = LI()
        u, v = u - 1, v - 1
        w = w % 2
        edges[u].append([v, w])
        edges[v].append([u, w])
    ans = [-1] * N
    ans[0] = 0
    def solve(k):
        for e, w in edges[k]:
            if ans[e] == -1:
                ans[e] = ans[k] if w == 0 else 1 - ans[k]
                solve(e)
    solve(0)
    for a in ans:
        print(a)
    return

main()

Submission status: Accepted

Solution code:
from collections import deque
def sol():
    n=int(input())
    d=[-1]*n
    l=deque([])
    for i in range(n-1):
        u,v,w=map(int,input().split())
        u,v=min(u,v),max(u,v)
        l.append((u-1,v-1,w))
    f=0
    while len(l):
        x=l.popleft()
        if f:
            if x[2]%2 and d[x[0]]==0:
                d[x[1]]=1
            elif x[2]%2 and d[x[0]]==1:
                d[x[1]]=0
            elif x[2]%2==0 and d[x[0]]==1:
                d[x[1]]=1
            elif x[2]%2==0 and d[x[0]]==0:
                d[x[1]]=0
            elif x[2]%2 and d[x[1]]==0:
                d[x[0]]=1
            elif x[2]%2 and d[x[1]]==1:
                d[x[0]]=0
            elif x[2]%2==0 and d[x[1]]==1:
                d[x[0]]=1
            elif x[2]%2==0 and d[x[1]]==0:
                d[x[0]]=0
            else:
                l.append(x)
        else:
            f=1
            if x[2]%2:
                d[x[0]]=0
                d[x[1]]=1
            else:
                d[x[0]]=0
                d[x[1]]=0
    for i in d:
        print(i)

if __name__=="__main__":
    sol()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N=INT()
nodes=[[] for i in range(N)]
for i in range(N-1):
    u,v,w=MAP()
    nodes[u-1].append((v-1, w))
    nodes[v-1].append((u-1, w))

ans=[-1]*N
def rec(cur, color):
    if ans[cur]!=-1:
        return
    ans[cur]=color
    for node in nodes[cur]:
        nxt,w=node
        if w%2==0:
            rec(nxt, color)
        else:
            rec(nxt, 1-color)
    return

rec(0, 0)

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

Submission status: Accepted

Solution code:
N = int(input())

E = [[] for _ in range(N)]
Color = [None] * N

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


for i in range(N):
	if Color[i] is not None:
		continue
	stack = [(i, 0)]
	
	while stack:
		u, color = stack.pop()
		Color[u] = color
		for v, w in E[u]:
			if Color[v] is not None:
				continue
			stack.append((v, color if w == 0 else 1 - color))

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

Submission status: Accepted

Solution code:

def main():
    buf = input()
    N = int(buf)
    edge = dict()
    for i in range(N):
        edge[i] = [] # zero index
    for i in range(N-1):
        buf = input()
        buflist = list(buf.split())
        u = int(buflist[0])-1 # zero index
        v = int(buflist[1])-1 # zero index
        w = int(buflist[2])
        edge[u].append((w, v))
        edge[v].append((w, u))
    vertex_color = []
    for i in range(N):
        vertex_color.append(None)
    stack = [(0, 0)] # distance, vertex_id
    while stack:
        current = stack.pop()
        if current[0] % 2 == 0:
            vertex_color[current[1]] = 1
        else:
            vertex_color[current[1]] = 0
        for e in edge[current[1]]:
            if vertex_color[e[1]] == None:
                stack.append((current[0]+e[0], e[1]))
    for x in vertex_color:
        print(x)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n = int(input())
links = {u: {} for u in range(1, n + 1)}
for i in range(n - 1):
	x, y, z = map(int, input().split())
	links[x][y] = z
	links[y][x] = z
vis = [0] * (n + 1)
col = [0] * (n + 1)

now = 0
q = [(1, 0)]
while now < len(q):
	u = q[now][0]
	c = q[now][1]
	now += 1
	vis[u] = 1
	col[u] = c
	for v, l in links[u].items():
		if vis[v] == 0:
			if l & 1:
				q.append((v, c ^ 1))
			else:
				q.append((v, c))

for u in range(1, n + 1):
	print(col[u])

Submission status: Accepted

Solution code:
from sys import stdin
input = stdin.readline
n=int(input())
b=[]
for i in range(n-1):b.append(list(map(int,input().split())))
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
a=BFS(0,b,n)
for i in a:print(0 if i%2==0 else 1)

Submission status: Accepted

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

N = int(input())

edge = [[] for _ in range(N+1)]


for _ in range(N-1):
  v1,v2,w = [int(x) for x in input().split()]
  if w&1:
    edge[v1].append((v2,-1))
    edge[v2].append((v1,-1))
  else:
    edge[v1].append((v2,1))
    edge[v2].append((v1,1))

color = [None] * (N+1)

def set_color(v,c):
  color[v] = c
  for x,sgn in edge[v]:
    if color[x] is None:
      set_color(x,sgn*c)
      
set_color(1,1)

for x in color[1:]:
  print((x+1)//2)

Submission status: Accepted

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

n = int(input())

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

memo = [-1] * n

def dfs(v, memo, color):
    memo[v] = color
    for (nv, dist) in graph[v]:
        if memo[nv] != -1:
            continue
        if dist == 0:
            dfs(nv, memo, color)
        else:
            dfs(nv, memo, (color + 1)%2)

dfs(0, memo, 0)

for i in memo:
    print(i)

Submission status: Accepted

Solution code:
N=int(input())
S=[]
ans=[-1 for x in range(N+1)]
con=[[] for x in range(N+1)]
for i in range(N-1):
    u,v,w=[int(x) for x in input().split()]
    con[u].append([v,w])
    con[v].append([u,w])
K=[]
ans[1]=0
focus=[[1,0]]
M=1
while(M<N):
    newfocus=[]
    for f in focus:
        s=f[0]
        c=f[1]
        for A in con[s]:
            d,w=A
            if ans[d]==-1:
                nc =c
                if w%2:
                    nc=not(c)
                ans[d]=nc
                newfocus.append([d,nc])
                M+=1
        focus=newfocus[:]
for i in range(1,N+1):
    print(int(ans[i]))

Submission status: Accepted

Solution code:
n=int(input())
l=[list(map(int,input().split())) for i in range(n-1)]
r=[[] for i in range(n+1)]
ans=[-1 for i in range(n+1)]
for i in l:
  u,v,w=i
  r[u].append((v,w))
  r[v].append((u,w))
q=[1]
ans[1]=0
while(len(q)>0):
  t=q.pop()
  for i in r[t]:
    V,W=i
    if(ans[V]!=-1):
      continue
    q.append(V)
    c=ans[t]
    if(W%2==0):
      ans[V]=c
    else:
      ans[V]=c^1
for i in ans[1:]:
  print(i)

Submission status: Accepted

Solution code:
N = int(input())
T = [[] for i in range(N)]
for i 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])
D = [-1] * N
D[0] = 0
Q = [0]
while Q:
  q = Q.pop()
  for adj, w in T[q]:
    if D[adj] < 0:
      D[adj] = D[q] + w
      Q.append(adj)
for d in D:
  print(d % 2)

Submission status: Accepted

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

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

arrival = [-1 for i in range(n+1)]
q = [1]
r = []
while not(len(q) == 0 and len(r) == 0): 
    while len(q) != 0:
        arrival[q[0]] = 0
        for i in range(len(graph[q[0]])):
            if arrival[graph[q[0]][i][0]] == -1 and graph[q[0]][i][1] % 2 == 0:
                arrival[graph[q[0]][i][0]] = 0
                q.append(graph[q[0]][i][0])
            elif arrival[graph[q[0]][i][0]] == -1 and graph[q[0]][i][1] % 2 == 1:
                r.append(graph[q[0]][i][0])
        q.pop(0)

    while len(r) != 0:
        arrival[r[0]] = 1
        for i in range(len(graph[r[0]])):
            if arrival[graph[r[0]][i][0]] == -1 and graph[r[0]][i][1] % 2 == 0:
                arrival[graph[r[0]][i][0]] = 1
                r.append(graph[r[0]][i][0])
            elif arrival[graph[r[0]][i][0]] == -1 and graph[r[0]][i][1] % 2 == 1:
                q.append(graph[r[0]][i][0])
        r.pop(0)


for i in range(1,n+1):
    if arrival[i] != 0:
        print("1")
    else:
        print("0")

Submission status: Accepted

Solution code:
from collections import deque, defaultdict


def read_input():
    n = int(input())
    edges = []

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

    return n, edges


# グラフのノード間の距離の偶奇に応じてノードをグループ分けする
def search_graph(nodes, edges):
    edge_table = {n:[] for n in nodes}

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

    # 探索開始
    q = deque()
    # (node, これまでの距離), 初期ノードは(1, 0)とする
    q.appendleft((nodes[0], 0))

    even = []
    odd = []
    searched = defaultdict(int)

    while len(q) > 0:
        cnode, cdist = q.pop()
        searched[cnode] = 1

        if cdist % 2:
            odd.append(cnode)
        else:
            even.append(cnode)

        next_nodes = edge_table[cnode]
        for nn in next_nodes:
            if searched[nn[0]] == 0:
                q.appendleft((nn[0], cdist + nn[1]))

    return set(even), set(odd)


def submit():
    n, edges = read_input()
    nodes = [i for i in range(1, n + 1)]
    even, odd = search_graph(nodes, edges)

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



if __name__ == '__main__':
    submit()

Submission status: Accepted

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

R = {}

for u, v, w in uvw:
  U = u - 1
  V = v - 1
  if U not in R:
    R[U] = [[U, V, w]]
  else:
    R[U].append([U, V, w])
  if V not in R:
    R[V] = [[V, U, w]]
  else:
    R[V].append([V, U, w])

S = [0]
L = [-1] * N
L[0] = 0
while S != []:
  t = []
  for j in S:
    for i in R[j]: 
      if L[i[1]] == -1:
        if i[2] % 2 == 0:
          L[i[1]] = L[i[0]]
        else:
          L[i[1]] = 1 - L[i[0]]
        t.append(i[1])
  S = t

for i in L:
  print(i)

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict, deque

def main():
    input = sys.stdin.readline
    N = int(input())
    d = defaultdict(list)
    for _ in range(N-1):
        u, v, w = map(int, input().split())
        d[u-1].append((v-1, w))
        d[v-1].append((u-1, w))

    dist = [0] * N
    q = deque()
    q.append((0, 0))
    visited = set()

    while len(q) > 0:
        q_ = deque()
        while len(q) > 0:
            node1, cost1 = q.popleft()

            dist[node1] = cost1
            visited.add(node1)

            for node2, cost2 in d[node1]:
                if node2 in visited:
                    continue

                q_.append((node2, cost1 + cost2))

        q = q_

    for d in dist:
        print(d % 2)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import defaultdict

n = int(input())
edges = {}
connected_nodes = defaultdict(list)

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

#print(edges)
#print(connected_nodes)

color = {}
color[1] = 0

visiting = [1]

while edges:
  node = visiting.pop()
  #print('visiting node {0} with edges {1}, colors {2} '.format(node, edges, color))
  #es = list(map(lambda nn: (node, nn) if node < nn else (nn, node) ,connected_nodes[node]))
  for nn in connected_nodes[node]:
    edge = (node, nn) if node < nn else (nn, node)
    if edge in edges:
      w = edges[edge]
      del edges[edge]
      visiting.append(nn)
      if w % 2 == 0:
        color[nn] = color[node]
      else:
        color[nn] = 1 - color[node]

for node in sorted(color.keys()):
  print(color[node])
#def dfs(root, edges, connected_nodes, color):

Submission status: Accepted

Solution code:
n=int(input())
path=[[] for i in range(n)]
for i in range(n-1):
    a,b,c=map(int, input().split())
    path[a-1].append([b-1,c%2])
    path[b-1].append([a-1,c%2])
ans=[-1]*n
ans[0]=0
q=[0]
while q:
    nq=[]
    for k in q:
        for i,j in path[k]:
            if ans[i]==-1:
                ans[i]=(ans[k]+j)%2
                nq.append(i)
    q=nq[:]
for i in ans:print(str(i))

Submission status: Accepted

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

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


visited = [False] * N
visited[0] = True


def dfs(n):
    visited = [False] * N
    stack = [[n, 0]]
    longest = [-1, -1]

    while stack:
        node, weight = stack.pop()
        if visited[node]:
            continue
        visited[node] = True
        if longest[1] < weight:
            longest = [node, weight]

        for n, w in T[node]:
            if not visited[n]:
                stack.append([n, w + weight])

    return longest


start, xw = dfs(0)


color = [None] * N


def dfs(n):
    for to, weight in T[n]:
        if color[to] is None:
            if weight % 2 == 0:
                color[to] = color[n]
                dfs(to)
            else:
                color[to] = color[n] ^ 1
                dfs(to)


color[start] = 0
dfs(start)
print(*color, sep='\n')