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:
read = input
n = int(read())
v = [[] for i in range(n+1)] # 邻接
used = [0 for i in range(n+1)] # 节点 1~n
def add(f,t,w):
    v[f].append((t, w))
for i in range(n-1):
    f,t,w = map(int, read().split())
    add(f,t,w)
    add(t,f,w)
# 从1出发，贪心即可，1画1，理论不会有回环
# def dfs(f, s, fa=-1):
#     if s % 2 == 0: 
#         used[f] = 1
#     for t, w in v[f]:
# #         print('%d->%d->%d'%(fa, f, t,), s, w)
#         if t == fa:continue
#         dfs(t, w + s, f)
from queue import Queue
q = Queue()
#def dfs(f, s, fa=-1):
#    if s % 2 == 0: 
#        used[f] = 1
#    for t, w in v[f]:
##         print('%d->%d->%d'%(fa, f, t,), s, w)
#        if t == fa:continue
#        dfs(t, w + s, f)
#
#
#dfs(1,0)
q.put_nowait((1, 0, -1))
while not q.empty():
    f, s, fa = q.get_nowait()
    if s % 2 == 0: 
        used[f] = 1
    for t, w in v[f]:
#         print('%d->%d->%d'%(fa, f, t,), s, w)
        if t == fa:continue
        q.put_nowait(
            (t, w + s, f)
        )
    
for i in used[1:]:
    print(used[i])

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000)

N = int(input())

edges = [{} for i in range(N)]
colors = [0 for i in range(N)]

def dfs(s, dist):

    for key, val in edges[s].items():
        d = dist + val
        if d % 2 == 0:
            colors[key] = 0 
        else :
            colors[key] = 1
        
        if s in edges[key]:
            del edges[key][s]

        dfs(key, d)

    return

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

dfs(0, 0)

for color in colors:
    print(color)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(100000)
def search(i, visited, ns, ans) :
    #print(i+1)
    visited[i] = True
    for next, weight in ns[i]:
        if visited[next] == False:
            if weight % 2 == 0:
                ans[next] = ans[i]
            else:
                ans[next] = (ans[i]+1) % 2
            search(next, visited, ns, ans)


def dfs(ns, ans):
    visited = [False] * len(ns)
    search(0, visited, ns, ans)

def main():
    n = int(input())
    ns = [[] for _ in range(n)]
    for _ in range(n-1):
        (st,end,weight) = map(int,input().split())
        ns[st-1].append((end - 1,weight))
        ns[end-1].append((st-1,weight))
    ans = [False] * n
    dfs(ns, ans)
    for a in ans:
        if a:
            print(1)
        else:
            print(0)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

n=int(input())
g=[[] for i in range(1+n)]
v=[0]*(1+n)
c=[-1]*(1+n)
flg=False
for i in range(n-1):
    a,b,w=map(int,input().split())
    g[a].append((b,w))
    g[b].append((a,w))
    if w%2==1:
        flg=True

def bfs(x):
    if v[x]!=0:
        return
    q=deque()
    q.append(x)
    v[x]=1
    while len(q)>0:
        cur=q.popleft()

        for nei in g[cur]:
            y=nei[0]
            d=nei[1]
            if v[y]==0:
                q.append(y)
                v[y]=1
                if d%2==1:
                    c[y]=1-c[cur]
                else:
                    c[y]=c[cur]
            #print('cur=',cur,'nei=(y,d)=',nei,'c=',c,q,v)

c[1]=0
bfs(1)

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

Submission status: Accepted

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

from heapq import heappush, heappop

def dijkstra(graph, start):
    A = [None] * (N)
    queue = [(0, start)]
    while queue:
        path_len, v = heappop(queue)
        if A[v] is None: # v is unvisited
            A[v] = path_len
            for w, edge_len in graph[v].items():
                if A[w] is None:
                    heappush(queue, (path_len + edge_len, w))

    # to give same result as original, assign zero distance to unreachable vertices             
    return [0 if x is None else x for x in A]



# 無効グラフなので双方向にする
graph = {}
for a,b,c in edges:
    a = a-1
    b = b-1
    if not a in graph:
        graph[a] = {}
    if not b in graph:
        graph[b] = {}
    graph[a][b] = c
    graph[b][a] = c
    
    
shortest = dijkstra(graph, 0)

for s in shortest:
    print(s % 2)

Submission status: Accepted

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

n = int(input())
ans = [-1]*(n+1)
data =[[] for i in range(n+1)]

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

ans[1] = 1
def color(i):
    for v, w in data[i]:
        if ans[v] == -1:
            if w % 2 == 0:
                ans[v] = ans[i]
            else:
                ans[v] = 1 - ans[i]
            color(v)
    return

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(100000000)
from collections import defaultdict
N = int(input())
tree = defaultdict(list)
for i in range(N-1):
    u,v,w = map(int,input().split())
    tree[u].append((v,w))
    tree[v].append((u,w))

ans = {}
reached = [False] * (N+1)

def dfs(u,v,s):
    reached[v] = True
    if s % 2 == 0: ans[v] = 0
    else: ans[v] = 1
    for n in tree[v]:
        if not reached[n[0]]:
            dfs(v,n[0],s+n[1])

ans[1] = 0
reached[1] = True
for v in tree[1]:
    dfs(1,v[0],v[1])

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

Submission status: Accepted

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

d = dict()
for u, v, w in UVW:
    if u-1 not in d:
        d[u-1] = []
    if v-1 not in d:
        d[v-1] = []
    d[u-1] += [(v-1, w)]
    d[v-1] += [(u-1, w)]

visited = [False]*(N)
visited[0] = True
l = [0]*N
q = [0]
while q:
    # print(q, l, visited)
    len_q = len(q)
    for u in q[:]:
        for v, w in d[u]:
            if visited[v] == True:
                continue
            visited[v] = True
            if w%2 == 0:
                l[v] = l[u]
            else:
                l[v] = (l[u]+1)%2
            q.append(v)
    q = q[len_q:]
            # print(q)
    # print(q)

for m in l:
    print(m)

Submission status: Accepted

Solution code:
N = int(input())
V = [[] for _ in range(N+1)]
check = [0]*(N+1)
color = [0]*(N+1)
d = dict()
for _ in range(N-1):
    u, v, w = map(int, input().split())
    V[u].append((v, w))
    V[v].append((u, w))

color[1] = 1
check[1] = 1
queue = []
for u, w in V[1]:
    queue.append((u, w))
    d[u] = color[1]
while queue:
    u, w = queue.pop()
    check[u] = 1
    if w % 2:
        if d[u]:
            color[u] = 0
        else:
            color[u] = 1
    else:
        color[u] = d[u]
    for next_u, next_w in V[u]:
        if check[next_u] == 0:
            queue.append((next_u, next_w))
            d[next_u] = color[u]

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(100002)
n=int(input())
point=[]
answer=[]
already=[]
for i in range(n):
    point.append([])
    answer.append(0)
    already.append(0)
for i in range(n-1):
    u,v,w=map(int,input().split())
    point[u-1].append((v-1,w))
    point[v-1].append((u-1,w))
def dfs(now,c):
    answer[now]=c
    already[now]=1
    for i in point[now]:
        if already[i[0]]==1:
            pass
        else:
            if i[1]%2==0:
                dfs(i[0],c)
            else:
                if c==0:
                    dfs(i[0],1)
                else:
                    dfs(i[0],0)
dfs(0,0)
for i in answer:
    print(i)

Submission status: Accepted

Solution code:
N=int(input())
M=N-1
graph=[[]  for i in range(N+1)]
weight={}
for _ in range(M):
    a,b,c=list(map(int,input().strip().split(' ')))
    graph[a]+=[b]
    graph[b]+=[a]
    weight[(a,b)]=c
    weight[(b,a)]=c
checked={}
paint=[0]*(N+1)
def dfs(root):
    connected=[]
    stack=[]
    stack+=[root]
    parent={}
    parent[root]=-1
    checked[root]=1
    while stack:
        v=stack.pop()
        for node in graph[v]:
            if node!=parent[v] and node not in checked:
                if weight[(node,v)]%2==0:
                    paint[node]=paint[v]
                else:
                    paint[node]=paint[v]^1    
                checked[node]=1
                parent[node]=v
                stack+=[node]
    return stack
dfs(1)
for i in range(1,len(paint)):
    print(paint[i])

Submission status: Accepted

Solution code:
#!venv/bin/python

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

from collections import defaultdict 

N = int(input())
K = []
bridge = defaultdict(list)
for n in range(N-1):
    k = [ int(x) for x in input().split() ]
    K.append(k)
    bridge[k[0]].append([k[1], k[2]])
    bridge[k[1]].append([k[0], k[2]])

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

queue = []
queue.append(1)
color[1] = 1


while queue:
    point = queue.pop()
    for b in bridge[point]:
        if not color[b[0]]:
            queue.append(b[0])
            if b[1] % 2 == 0:
                color[b[0]] = color[point]
            else:
                color[b[0]] = color[point] * -1

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

Submission status: Accepted

Solution code:
from collections import defaultdict

N = int(input())

colors = [0] * (N+1)
vertices = defaultdict(bool)
edges = defaultdict(dict)
for i in range(1, N):
    u, v, w = map(int, input().split())
    edges[u][v] = w % 2 == 0
    edges[v][u] = w % 2 == 0
    vertices[u] = False
    vertices[v] = False

queue = []
for v in edges[u].keys():
    queue.append((u, v))
vertices[u] = True

while len(queue) > 0:
    u, v = queue.pop(0)
    if vertices[v]:
        continue
    vertices[v] = True
    if colors[u] == colors[v]:
        if not edges[u][v]:
            colors[v] = 1 - colors[u]
    else:
        if edges[u][v]:
            colors[v] = colors[u]

    for nv in edges[v].keys():
        if not vertices[nv]:
            queue.append((v, nv))

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

Submission status: Accepted

Solution code:
import queue

N = int(input())

u, v, w = [0 for _ in range(N-1)], [0 for _ in range(N-1)], [0 for _ in range(N-1)]

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

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

col = [-1 for _ in range(N)]
col[0] = 0

q = queue.Queue()
q.put((0, 0))
c = 0

while(not q.empty()):
    a = q.get()
    col[a[0]] = a[1]

    for e in adli[a[0]]:
        if col[e[0]] == -1:
            q.put((e[0], (a[1]+e[1])%2))

for ans in col:
    print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict

N = int(input())

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

colorDict = defaultdict(int)
stack = [1]
colorDict[1] = 1
while(stack):
    key = stack.pop() 
    for ew in dd[key]:
        e, w = ew
        if colorDict[e] == 0:
            if colorDict[key] == 1:
                colorDict[e] = 1 if w % 2 == 0 else 2
            else:
                colorDict[e] = 2 if w % 2 == 0 else 1
            stack.append(e)

for k, v in sorted(colorDict.items()):
    print(str(v - 1))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(100000)

N=int(input())
edges = [[] for i in range(N)]
colors = [-1]*N
for i in range(N-1):
    u,v,w=[int(a) for a in input().split()]
    edges[u-1].append((v-1,w))
    edges[v-1].append((u-1,w))
 
diff = lambda n: 1 if n==0 else 0
 
def dfs(prev,curr):
    for node,d in edges[curr]:
        if node==prev:
            continue
        colors[node] = colors[curr] if d%2==0 else diff(colors[curr])
        dfs(curr,node)
 
colors[0]=0
dfs(1000000,0)
for i in range(N):
    print(colors[i])

Submission status: Accepted

Solution code:
import queue
q=queue.Queue()
N=int(input())
searched=set()
info=list()
edges={}
dict={}

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

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

dict[0]=0

q.put(0)

while not q.empty():
    a=q.get()
    if a in searched:
        continue

    tmplist=edges[a]
    for l in tmplist:
        if l[0] not in searched:
            v,w=l
            q.put(v)
            if w%2==0:
                dict[v]=dict[a]
            else:
                dict[v]=(dict[a]+1)%2
    searched.add(a)


di=sorted(dict.items(), key=lambda x:x[0])

for d in di:
    print(d[1])

Submission status: Accepted

Solution code:
from collections import deque

N=input()

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

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

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

q=deque()
q.append(1)

while q:
	x=q.popleft()
	for to,kyori in nl[x]:
		if Visit[to] is None:
			if kyori%2==0:
				Visit[to]=Visit[x]
			else:
				Visit[to]=(Visit[x]+1)%2
			q.append(to)
			

for i in Visit[1:]:
	print i

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 5 + 1)

def dfs(i, V, E):
    for k in E[i].keys():
        if V[k] >= 0:
            continue
        if E[i][k] % 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][vi] = wi
    else:
        E[ui] = {vi: wi}
    if vi in E.keys():
        E[vi][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: Accepted

Solution code:
import heapq

N = int(input())
graph = {i:[] for i in range(1, N+1)}
route = [10**20 for i in range(N+1)]
visited = [False for i in range(N+1)]

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

for key, value in graph.items():
    if len(value):
        start = key
        route[start] = 0
        visited[start] = True
        q = []
        for v, w in value:
            route[v] = min(route[v], w)
            heapq.heappush(q, (w, v))
        break

while len(q):
    w, v = heapq.heappop(q)
    if not visited[v]:
        visited[v] = True
        for u, c in graph[v]:
            if route[u] > route[v] + c:
                route[u] = route[v] + c
                heapq.heappush(q, (c, u))

for n in route[1:]:
    if n % 2:
        print('1')
    else:
        print('0')

Submission status: Accepted

Solution code:
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 [i%2 for i in dist]
N = int(input())
edges = []
for n in range(N-1):
    a,b,c = map(int, input().split())
    edges.append([a,b,c])
ans = BFS(0,edges,N)
for a in ans:
    print (a)

Submission status: Accepted

Solution code:
if __name__ == '__main__':
    import sys
    input = sys.stdin.readline

    n = int(input())

    parent = {x:[] for x in range(1,n+1)}

    ans = [None]*n

    ans[0] = 1

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

    base = [1]


    while True:
        pop_num = base.pop()
        for i in parent[pop_num]:
            abs_i = abs(i)
            ans[abs_i-1] = ans[pop_num-1]*(i/abs_i)
            parent[abs_i].remove(pop_num*(i/abs_i))
            base.append(abs_i)
        if len(base) == 0:
            break

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10000000)
n=int(input())
s=[[]for i in range(n+1)]
g=[0]*(n+1)
h=[True]*(n+1)
for i in range(n-1):
    a,b,c=map(int,input().split())
    s[a].append([b,c])
    s[b].append([a,c])
def dfs(x):
    h[x]=False
    for i in s[x]:
        if h[i[0]]:
            g[i[0]]=g[x]+i[1]
            dfs(i[0])
dfs(1)
for i in range(1,n+1):
    if g[i]%2==0:
        print(0)
    else:
        print(1)

Submission status: Accepted

Solution code:
from collections import defaultdict, deque
n = int(input())
data = [list(map(int, input().split())) for _ in range(n-1)]
tree = defaultdict(list)
for u, v, w in data:
    if w % 2 == 0:
        tree[u].append((v, "ok"))
        tree[v].append((u, "ok"))
    else:
        tree[u].append((v, "ng"))
        tree[v].append((u, "ng"))
# print(tree.items())
queue = deque()
queue.append(1)
visited = set()
ans = [None for _ in range(n)]
ans[0] = 1
while len(queue):
    now = queue.popleft()
    opps = tree[now]
    # print(now, opps)
    for opp in opps:
        if opp[0] not in visited:
            queue.append(opp[0])
            # print(ans[now-1])
            if opp[1] == "ok":
                ans[opp[0]-1] = ans[now-1]
            else:
                ans[opp[0]-1] = -ans[now-1]
        visited.add(opp[0])
for value in ans:
    if value == 1:
        print(1)
    else:
        print(0)

Submission status: Accepted

Solution code:
N = int(input())
import sys
graph = [dict() for _ in range(N)]

for i in range(N-1):
    u, v, w = map(int, sys.stdin.readline().split())
    graph[u-1][v-1] = w
    graph[v-1][u-1] = w

color = [-1] * N

import sys
sys.setrecursionlimit(10 ** 9)

def dfs(i, col):
    color[i] = col
    for k, v in graph[i].items():
        if color[k] == -1:
            if v % 2 == 0:
                dfs(k, col)
            else:
                dfs(k, 1-col)

dfs(0, 1)

# 1 -> 0
# 2 -> 1

for c in color:
    print(c)

Submission status: Accepted

Solution code:
import queue
from queue import Queue

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

#色
c = [-1]*(n+1)
c[1] = 0

q = Queue()
q.put(1)

while not q.empty():
  x = q.get()
  for y in g[x]:
    if c[y] == -1:
      q.put(y)
      c[y] = c[x]
  for y in k[x]:
    if c[y] == -1:
      q.put(y)
      c[y] = (c[x]+1)%2
    
for i in range(1,n+1):
  print(c[i])

Submission status: Accepted

Solution code:
n=int(input())
s=[None for i in range(n)]
l=[[] for i in range(n)]
for i in range(n-1):
  x,y,w=map(int,input().split())
  x-=1
  y-=1
  l[x]+=[[y,w%2]]
  l[y]+=[[x,w%2]]

s[0]=0
p=[0]
while p:
  q=p.pop()
  for t,w in l[q]:
    if s[t] == None:
      if w==1:
        s[t]=(s[q]+1)%2
      else:
        s[t]=s[q]
      p+=[t]
for i in s:
  print(i)

Submission status: Accepted

Solution code:
import collections
N = int(input())
UVW = [[int(_) for _ in input().split()] for _ in range(N - 1)]
cd = collections.defaultdict
G = cd(lambda: cd(int))
for u, v, w in UVW:
    G[u][v] = G[v][u] = w
ans = [-1] * (N + 1)
ans[1] = 0
stack = [1]
while stack:
    f = stack.pop()
    for t in G[f].keys():
        if ans[t] == -1:
            stack += [t]
            if G[f][t] % 2:
                ans[t] = 1 - ans[f]
            else:
                ans[t] = ans[f]
print(*ans[1:], sep='\n')

Submission status: Accepted

Solution code:
from collections import defaultdict

N = int(input())

D = defaultdict(list) 
S = {} #STEPD
for i in range(1,N+1):S[i] = -1
R = defaultdict(int) #ROOT
for i in range(N-1):
    u,v,w = map(int,input().split())
    D[u].append(v)
    D[v].append(u)
    R["{}-{}".format(u,v)] = w
    R["{}-{}".format(v,u)] = w
    
T = [(1,0)]
S[1] = 0
while T:
    n,w = T.pop()
    for d in D[n]:
        wr = R["{}-{}".format(n,d)]
        if S[d]>=0:continue
        else: S[d] = (w+wr)%2
        T.append((d,(w+wr)%2))
        
for k in range(1,N+1):
    print(S[k] if S[k]>=0 else 0)

Submission status: Accepted

Solution code:
N = int(input())

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

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

import sys
sys.setrecursionlimit(10000000)
def f(i, color):
    for t, w in data[i]:
        if ans[t] is not None:
            continue
        ans[t] = color^w
        f(t, color^w)

f(0, 0)

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

Submission status: Accepted

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

def readInts():
  return [int(s) for s in input().split(" ")]

def main():
  N = readInts()[0]
  links = {}
  for i in range(N-1):
    u, v, w = readInts()
    if not u in links:
      links[u] = {}
    if not v in links:
      links[v] = {}
    links[u][v] = w
    links[v][u] = w

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

  nodes = [(1, False)]
  while len(nodes) > 0:
    v, color = nodes.pop()
    colors[v - 1] = '1' if color else '0'

    for u, w in links[v].items():
      if colors[u - 1]: continue
      if w % 2 == 0:
        nodes.append((u, color))
      else:
        nodes.append((u, not(color)))
  for n in range(N):
    print(colors[n])

if __name__ == "__main__":
  main()

Submission status: Accepted

Solution code:
from collections import deque
N = int(input())
X = [list(map(int, input().split())) for _ in range(N - 1)]
class UnionFind:
    def __init__(self, n=1):
        self.par = [i for i in range(n)]
    def find(self, x):
        if self.par[x] == x:
            return x
        self.par[x] = self.find(self.par[x])
        return self.par[x]
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x != y:
            self.par[y] = x
    def is_same(self, x, y):
        return self.find(x) == self.find(y)
uf = UnionFind(N)
next_ = [[] for _ in range(N)]
for u, v, w in X:
    next_[u - 1].append((v - 1, w))
    next_[v - 1].append((u - 1, w))
    uf.union(u - 1, v - 1)
now = min(set(uf.par))
result = ["" for _ in range(N)]
result[now] = "0"
ver = deque([now])
while len(ver) > 0:
    now = ver.pop()
    color = result[now]
    for n, w in next_[now]:
        if result[n] != "":
            continue
        if w % 2 == 0:
            result[n] = color
        else:
            result[n] = "1" if color == "0" else "0"
        ver.append(n)
print("\n".join(result))

Submission status: Accepted

Solution code:
from itertools import*
from math import*
from collections import*
from heapq import*
from bisect import bisect_left,bisect_right
from copy import deepcopy
inf = 10**18
mod = 10**9+7
from functools import reduce
import sys
sys.setrecursionlimit(10**7)

n = int(input())
G = defaultdict(set)
color = [0]*(n)
for i in range(n-1):
    a, b, c = map(int, input().split())
    G[a-1].add((b-1, c))
    G[b-1].add((a-1, c))
def dijkstra(v):
    d = [inf] * n
    d[v] = 0
    hq =[(0,v)]

    while hq:
        u = heappop(hq)[1]
        for (v,c) in G[u]:
            if d[v] > d[u] + c:
                d[v] = d[u] +c
                heappush(hq,(d[u]+c,v))
    return d
d = dijkstra(0)
for i in range(n):
    if d[i] % 2==0:
        color[i]=0
    else:
        color[i]=1
for i in range(n):
    print(color[i])

Submission status: Accepted

Solution code:
from collections import defaultdict, deque

def bfs(s):
    queue = deque([s])
    cv = [0] * n
    cv[s] = 1
    while queue:
        u = queue.popleft()
        for nxt, w in adj[u]:
            if not cv[nxt]:
                if w % 2 == 1:
                    color[nxt] = color[u] ^ 1
                else:
                    color[nxt] = color[u]
                queue.append(nxt)
                cv[nxt] = 1

n = int(input())
adj = defaultdict(list)
for _ in range(n - 1):
    u, v, w = [int(item) for item in input().split()]
    u -= 1
    v -= 1
    adj[u] += [(v, w)]
    adj[v] += [(u, w)]

color = [0] * n
bfs(0)

for x in color:
    print(x)

Submission status: Accepted

Solution code:
from bisect import bisect_left, bisect_right
from collections import Counter, defaultdict, deque, OrderedDict
from copy import deepcopy
from fractions import gcd
from functools import lru_cache, reduce
from math import ceil, floor
from sys import setrecursionlimit

import heapq as hq
import itertools as its
import operator as op


# globals
inf = float('inf')
N = 0


def set_inputs():
    global N
    return


def main():
    setrecursionlimit(100000)
    set_inputs()
    # ----------MAIN----------
    n = get_int()
    u, v, w = get_data(n - 1, [int, int, int])
    d = defaultdict(list)
    for ui, vi, wi in zip(u, v, w):
        d[ui].append((vi, wi))
        d[vi].append((ui, wi))
    color = [-1] * n
    q = deque()
    color[1-1] = 0
    q.append(1)
    while len(q) > 0:
        ui = q.popleft()
        for vi, wi in d[ui]:
            if color[vi-1] >= 0:
                continue
            color[vi-1] = (color[ui-1] + wi) % 2
            q.append(vi)
    for c in color:
        print(c)
    return


def get_int():
    return int(input())


def get_float():
    return float(input())


def get_str():
    return input().strip()


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


def get_lf():
    return [float(f) for f in input().split()]


def get_lc():
    return list(input().strip())


def get_data(n, types, sep=None):
    if len(types) == 1:
        return [types[0](input().strip()) for _ in range(n)]
    return list(zip(*(
        [t(x) for t, x in zip(types, input().strip().split(sep=sep))]
        for _ in range(n)
    )))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N = int(input())
edge = [[] for i in range(N)]
for i in range(N-1):
  u,v,w = map(int, input().split())
  edge[u-1] += [[u-1,v-1, w%2]]
  edge[v-1] += [[v-1,u-1, w%2]]
  
group = [0]+ [-1]* (N-1)
cnt = N-1#未訪問数
path = edge[0]
while path:
  uv = path.pop()
  if group[uv[1]] == -1:#未訪問
    group[uv[1]] = (group[uv[0]] + uv[2])%2
    for e in edge[uv[1]]:
      path.append(e)

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

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())
    u, v = u-1, v-1
    graph[u].append([v, w])
    graph[v].append([u, w])
d = [0 for i in range(N)]
visited = [False for i in range(N)]
def bfs(v):
    Q = []
    visited[v] = True
    Q.append(v)
    while len(Q) > 0:
        v = Q.pop(0)
        for u, w in graph[v]:
            if not visited[u]:
                visited[u] = True
                d[u] = d[v] + w
                Q.append(u)
bfs(0)
for i in range(N):
    if d[i] % 2 == 0:
        print('1')
    else:
        print('0')

Submission status: Accepted

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

color = [-1] * N
color[0] = 0
nextlist = [0]
while nextlist:
    tmp = []
    for proc in nextlist:
        for n in nlist[proc]:
            if color[n[0]] != -1:
                continue
            color[n[0]] = (color[proc] + n[1]) % 2
            tmp.append(n[0])
    nextlist = tmp

for c in color:
    print(c)

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-
import collections


class Node(object):

  def __init__(self):
    self.edges = []
    self.color = None


def main():
  nodes = [Node() for _ in range(int(input()))]

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

    nodes[u - 1].edges.append((nodes[v - 1], w))
    nodes[v - 1].edges.append((nodes[u - 1], w))

  queue = collections.deque()

  nodes[0].color = 0
  queue.append(nodes[0])

  while len(queue) != 0:
    node = queue.pop()

    for e, w in node.edges:
      if e.color is not None:
        continue

      if w % 2 == 0:
        e.color = node.color
      else:
        e.color = 1 - node.color

      queue.append(e)

  for node in nodes:
    print(node.color)


if __name__ == '__main__':
  main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
D - Even Relation
https://atcoder.jp/contests/abc126/tasks/abc126_d

"""
import sys

from heapq import heappush, heappop


def dijkstra(adj, s):
    N = len(adj)
    WHITE, GRAY, BLACK = 0, 1, 2
    color = [WHITE] * N
    d = [float('inf')] * N
    d[s] = 0
    pq = []
    heappush(pq, (0, s))
    while pq:
        cost, u = heappop(pq)
        color[u] = BLACK
        if d[u] < cost:
            continue
        for v, cost in adj[u]:
            if color[v] == BLACK:
                continue
            if d[v] > d[u] + cost:
                d[v] = d[u] + cost
                heappush(pq, (d[v], v))
                color[v] = GRAY
    return d


def solve(N, path):
    adj = [[] for _ in range(N+1)]
    for f, t, w in path:
        adj[f].append([t, w])
        adj[t].append(([f, w]))
    dist = dijkstra(adj, 1)
    ans = []
    for d in dist[1:]:
        if d%2 == 0:
            ans.append(0)
        else:
            ans.append(1)
    return ans


def main(args):
    N = int(input())
    path = [[int(i) for i in input().split()] for _ in range(N-1)]
    ans = solve(N, path)
    print(*ans, sep='\n')


if __name__ == '__main__':
    main(sys.argv[1:])