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 stdin
input = stdin.buffer.readline

def main():
    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%2))
        edges[v-1].append((u-1, w%2))

    ans = [-1] * n
    ans[0] = 0
    todo = [0]
    while len(todo) > 0:
        parent = todo.pop(-1)
        color = ans[parent]

        for child, w in edges[parent]:
            if ans[child] == -1:
                if w == 0:
                    ans[child] = color
                else:
                    ans[child] = 1 - color
                todo.append(child)

    for i in ans:
        print(i)

main()

Submission status: Accepted

Solution code:
n = int(input())

g = [[] for _ in range(n)]

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

from collections import deque

que = deque()
seen = [0] + [-1]*(n-1)
que.append(0)
while que:
    s = que.popleft()
    for v,w in g[s]:
        if seen[v] != -1:continue
        seen[v] = seen[s]^(w%2)
        que.append(v)
for i in seen:
    print(i)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(500*500)
n = int(input())
l = [list(map(int,input().split())) for _ in range(n-1)]
g = [[] for _ in range(n)]

for i in l:
    v = i[0]-1
    y = i[1]-1
    w = i[2]
    g[v].append([y,w])
    g[y].append([v,w])

seen = [0] + [-1] * (n-1)

def dfs(s):
    for k in g[s]:
        v,w = k[0],k[1]
        if seen[v]!=-1:continue
        seen[v] = seen[s]^(w%2)
        dfs(v)
        
dfs(0)

for i in seen:
    print(i)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
#D - Even Relation
import sys 
from heapq import heappush, heappop
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
N = int(readline())

edges = [[] for _ in range(N+1)]
INF = 10**31
dist = [INF]*(N+1) #最短距離用
prev=[None]*(N+1) #最短経路用
for _ in range(N-1):
  x,y,t = map(int, readline().split())
  edges[x].append((y,t))
  edges[y].append((x,t))
  
q = [(0,1)]
dist[1] = 0 #最短経路用
while q:
  cost, v = heappop(q)
  if dist[v] < cost:
    continue
  for vert,_cost in edges[v]:
    newcost = cost+_cost
    if newcost < dist[vert]:
      prev[vert] = v
      dist[vert] = newcost #最短経路用
      heappush(q,(newcost,vert))

for i in range(1,N+1):
    if dist[i] % 2 == 0:
        print(0)
    else:
        print(1)

Submission status: Accepted

Solution code:
n=int(input())
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)

ans=[None for i in range(n)]
ans[0]=0
s=[0]
while s:
  ns=[]
  for i in s:
    for j in e[i][0]:
      if ans[j]!=None:
        continue
      ns.append(j)
      ans[j]=ans[i]
    for j in e[i][1]:
      if ans[j]!=None:
        continue
      ns.append(j)
      ans[j]=1-ans[i]
  s=ns
print("\n".join(map(str,ans)))

Submission status: Accepted

Solution code:
n = int(input())
explored = set()
next = [[]for _ in range(n)]

from collections import deque
for i in range(n-1):
    u, v, w= map(int, input().split())
    next[u-1].append((v-1, w%2))
    next[v-1].append((u-1, w%2))
ans = [-1] * n
exploring = deque()
next_que = deque([0])
ans[0]=0
explored.add(0)
while next_que:
    i = next_que.popleft()
    exploring.extend(next[i])
    while exploring:
        a, b = exploring.popleft()
        ans[a] = (ans[i]+b)%2
        if a not in explored:
            next_que.append(a)
        explored.add(a)

print(*ans, end='\n')

Submission status: Accepted

Solution code:
n = int(input())
explored = set()
next = [[]for _ in range(n)]

from collections import deque
ls = []
for i in range(n-1):
    u, v, w= map(int, input().split())
    ls.append((u-1, v-1, w%2))
    next[u-1].append((v-1, w%2))
    next[v-1].append((u-1, w%2))

ans = [-1] * n

exploring = deque()
next_que = deque([0])
ans[0]=0
explored.add(0)
while next_que:
    i = next_que.popleft()
    exploring.extend(next[i])
    while exploring:
        a, b = exploring.popleft()
        ans[a] = (ans[i]+b)%2
        list = next[a]
        if a not in explored:
            next_que.append(a)
        explored.add(a)


print(*ans, end='\n')

Submission status: Accepted

Solution code:
n = int(input())
explored = set()
next = [[]for _ in range(n)]

from collections import deque
ls = []
for i in range(n-1):
    u, v, w= map(int, input().split())
    ls.append((u-1, v-1, w%2))
    next[u-1].append((v-1, w%2))
    next[v-1].append((u-1, w%2))

ans = [-1] * n

exploring = deque()
next_que = deque([0])
ans[0]=0
explored.add(0)
while next_que:
    i = next_que.popleft()
    exploring.extend(next[i])
    while exploring:
        a, b = exploring.popleft()
        ans[a] = (ans[i]+b)%2
        list = next[a]
        if a not in explored:
            next_que.append(a)
        explored.add(a)


for i in ans:
    print(i)

Submission status: Accepted

Solution code:
import sys
from sys import exit
from collections import deque
from copy import deepcopy
from bisect import bisect_left, bisect_right, insort_left, insort_right
from heapq import heapify, heappop, heappush
from itertools import product, permutations, combinations, combinations_with_replacement
from functools import reduce
from math import gcd, sin, cos, tan, asin, acos, atan, degrees, radians

sys.setrecursionlimit(10**6)
INF = 10**20
eps = 1.0e-20
MOD = 10**9+7

def lcm(x,y):
    return x*y//gcd(x,y)
def lgcd(l):
    return reduce(gcd,l)
def llcm(l):
    return reduce(lcm,l)
def powmod(n,i,mod=MOD):
    return pow(n,mod-1+i,mod) if i<0 else pow(n,i,mod)
def div2(x):
    return x.bit_length()
def div10(x):
    return len(str(x))-(x==0)
def intput():
    return int(input())
def mint():
    return map(int,input().split())
def lint():
    return list(map(int,input().split()))
def ilint():
    return int(input()), list(map(int,input().split()))
def judge(x, l=['Yes', 'No']):
    print(l[0] if x else l[1])
def lprint(l, sep='\n'):
    for x in l:
        print(x, end=sep)
def ston(c, c0='a'):
    return ord(c)-ord(c0)
def ntos(x, c0='a'):
    return chr(x+ord(c0))
class counter(dict):
    def __init__(self, *args):
        super().__init__(args)
    def add(self,x,d=1):
        self.setdefault(x,0)
        self[x] += d
    def list(self):
        l = []
        for k in self:
            l.extend([k]*self[k])
        return l
class comb():
    def __init__(self, n, mod=None):
        self.l = [1]
        self.n = n
        self.mod = mod
    def get(self,k):
        l,n,mod = self.l, self.n, self.mod
        k = n-k if k>n//2 else k
        while len(l)<=k:
            i = len(l)
            l.append(l[i-1]*(n+1-i)//i if mod==None else (l[i-1]*(n+1-i)*powmod(i,-1,mod))%mod)
        return l[k]
def pf(x,mode='counter'):
    C = counter()
    p = 2
    while x>1:
        k = 0
        while x%p==0:
            x //= p
            k += 1
        if k>0:
            C.add(p,k)
        p = p+2-(p==2) if p*p<x else x
    if mode=='counter':
        return C
    S = set([1])
    for k in C:
        T = deepcopy(S)
        for x in T:
            for i in range(1,C[k]+1):
                S.add(x*(k**i))
    if mode=='set':
        return S
    if mode=='list':
        return sorted(list(S))

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

N=intput()
if N==1:
    print(0)
    exit()
color=[-1]*(N+1)
cost=[-1]*(N+1)
node=[list() for _ in range(N+1)]
for _ in range(N-1):
    u,v,w=mint()
    node[u].append([v,w])
    node[v].append([u,w])
color[1]=0
cost[1]=0
q=deque([1])
while q:
    u=q.popleft()
    for v,w in node[u]:
        if color[v]<0:
            cost[v]=cost[u]+w
            color[v]=cost[v]%2
            q.append(v)
lprint(color[1:])

Submission status: Accepted

Solution code:
from collections import deque

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

q = deque()
l[0] = 0
q.append(0)
while (q):
    u = q.pop()
    for v, w in e[u]:
        if l[v] >= 0:
            continue
        if w % 2 == 0:
            l[v] = l[u]
        else:
            l[v] = 1 - l[u]
        q.append(v)

for col in l:
    print(col)

Submission status: Accepted

Solution code:
import sys, math
from collections import defaultdict, deque, Counter
from bisect import bisect_left, bisect_right
from itertools import combinations, permutations, product
from heapq import heappush, heappop
from functools import lru_cache
input = sys.stdin.readline
rs = lambda: input().strip()
ri = lambda: int(input())
rl = lambda: list(map(int, input().split()))
mat = lambda x, y, v: [[v]*y for _ in range(x)]
ten = lambda x, y, z, v: [mat(y, z, v) for _ in range(x)]
mod = 1000000007
sys.setrecursionlimit(1000000)

N = ri()
edges = defaultdict(list)
for i in range(N-1):
	u, v, w = rl()
	u, v = u-1, v-1
	edges[u].append((v,w))
	edges[v].append((u,w))

visited = {}
colors = [None] * N
colors[0] = 0
def dfs(node, prev=-1):
	if node in visited: return
	visited[node] = 1
	color = colors[node]
	for next_node, dist in edges[node]:
		if next_node == prev: continue
		if dist % 2 == 0:
			colors[next_node] = colors[node]
		else:
			colors[next_node] = int(not colors[node])
		dfs(next_node, node)
dfs(0)
for c in colors:
	print(c)

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

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

for _ in range(N-1):
    u, v, w = mapint()
    graph[u-1][v-1] = w%2
    graph[v-1][u-1] = w%2

from collections import deque
stack = deque([0])

colors = [-1]*N
colors[0] = 0
while stack:
    v = stack.pop()
    for nx in graph[v].keys():
        if colors[nx]==-1:
            w = graph[v][nx]
            colors[nx] = (colors[v]+w)%2
            stack.append(nx)

for a in colors:
    print(a)

Submission status: Accepted

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

N = int(readline())
G = [[] for i in range(N)]

for i in range(N - 1):
  u,v,w = map(int,readline().split())
  G[u - 1].append((v - 1, w))
  G[v - 1].append((u - 1, w))
  
color = [-1] * N
stack = []
stack.append([0, -1, 0])
while stack:
  v,parent,cost = stack.pop()
  color[v] = cost
  for child in G[v]:
    if child[0] == parent:
      continue
    stack.append([child[0], v, (cost + child[1]) % 2])

for c in color:
  print(c)

Submission status: Accepted

Solution code:
from collections import deque

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

l = [[] for _ in range(n)]
for u, v, w in uvw:
    u, v = u-1, v-1
    l[u].append((v, w))
    l[v].append((u, w))

ans = [0] * n
parents = [-1] * n
q = deque([0])
while q:
    a = q.pop()
    for i, j in l[a]:
        if i == parents[a]:
            continue
        parents[i] = a
        q.append(i)
        ans[i] = ans[a] if j%2 == 0 else (ans[a]+1) % 2
for i in ans:
    print(i)

Submission status: Accepted

Solution code:
import sys
from collections import deque
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

def dfs(start,n,g):
    visited = [-1]*(n+1)
    visited[start] = 0
    stack = deque([start])
    while stack:
        c_node = stack.pop()
        for neib, dist in g[c_node]:
            if visited[neib] != -1: continue
            visited[neib] = visited[c_node] + dist
            stack.append(neib)
    return visited
    

N = int(input())
g = [ [] for _ in range(N+1)]
visited = [-1] * (N+1)

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

visited = dfs(1,N,g)
for p in visited[1:]:
    print(p%2)

Submission status: Accepted

Solution code:

icase=0
if icase==0:
    n=int(input())
    g=[[] for i in range(n)]
    for i in range(n-1):
        ui,vi,wi=map(int,input().split())
        wi=wi%2
        g[ui-1].append((vi-1,wi))
        g[vi-1].append((ui-1,wi))
elif icase==1:
    vv,e,r=4,5,0
    g = [[] for _ in range(vv)]
    g[0]=[(1,1),(2,4)]
    g[1]=[(2,2),(3,5)]
    g[2]=[(3,1)]
    n=3
    g=[[(1, 0)], [(0, 0), (2, 1)], [(1, 1)]]
elif icase==2:
    n=5
    g=[[(2, 0)], [(4, 0), (2, 0)], [(1, 0), (0, 0), (3, 0)], [(2, 0)], [(1, 0)]]

from heapq import heappop,heappush

q=[]
heappush(q,(0,0)) 

inf=float("INF")
dist=[inf]*(n)
dist[0]=0
while len(q)>0:
    dd,state = heappop(q)
#    print("dd:",dd,"state:",state,"q:",q)
    for v,dv in g[state]:
#        print("v:",v,"dv:",dv,"g[state]:",g[state],"parent[v]:",parent[v])
        if dist[v]>dist[state]+dv:
            dist[v]=dist[state]+dv
            heappush(q,(dist[v],v))
#            print(" state:",state,"v:",v,"dist[v]",dist[v])

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

Submission status: Accepted

Solution code:
N = int(input())
G = [[] for n in range(N+1)]
q = [(1,0)]
ans = N*[-1]

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

while q:
  x,y = q.pop()
  ans[x-1] = y%2 
  for g,d in G[x]:
    q+=[(g,y+d)]*(ans[g-1]<0)

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

Submission status: Accepted

Solution code:
import collections
n=int(input())
d=[2]*n
w=collections.deque()
for i in range(n-1):
    a,b,c=map(int,input().split())
    if i==0:
        d[a-1]=0
        d[b-1]=c%2
    elif d[a-1]!=2:
        d[b-1]=(d[a-1]+c%2)%2
    elif d[b-1]!=2:
        d[a-1]=(d[b-1]+c%2)%2
    else:
        w.append((a,b,c))

while len(w):
    a,b,c=w.pop()
    if d[a-1]!=2:
        d[b-1]=(d[a-1]+c%2)%2
    elif d[b-1]!=2:
        d[a-1]=(d[b-1]+c%2)%2
    else:
        w.appendleft((a,b,c))
for i in d:
    print(i)

Submission status: Accepted

Solution code:
n = int(input())

tree = [[] for _ in range(n+1)]

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

color = [-1] * (n+1)
color[1] = 0
stack = [1]

while stack:
    node = stack.pop()
    for vertex, weight in tree[node]:
        if color[vertex] != -1:
            continue
        color[vertex] = (color[node] + weight) % 2
        stack.append(vertex)

print("\n".join(map(str, color[1:])))

Submission status: Accepted

Solution code:
import sys
from heapq import heappush, heappop

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N, *UVW = map(int, read().split())
    G = [[] for _ in range(N)]
    for u, v, w in zip(*[iter(UVW)] * 3):
        G[u - 1].append((v - 1, w))
        G[v - 1].append((u - 1, w))

    dist = [INF] * N
    dist[0] = 0
    hq = [(0, 0)]

    while hq:
        d, v = heappop(hq)
        if d > dist[v]:
            continue
        for nv, cost in G[v]:
            if dist[nv] > dist[v] + cost:
                dist[nv] = dist[v] + cost
                heappush(hq, (dist[nv], nv))

    ans = [0] * N
    for i in range(N):
        ans[i] = 0 if dist[i] % 2 == 0 else 1

    print(*ans, sep='\n')
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
input=sys.stdin.readline

def search(nodes, searched, labels, v):
  searched[v] = 1
  label = labels[v]
  for l in nodes[v]:
    x, w = l
    if not searched[x]:
      if w %2 == 0:
        labels[x] = label
      else:
        labels[x] = (label + 1) % 2
      search(nodes, searched, labels, x)

def solve(n, nodes):
  searched = [0]*n
  labels = [None]*n
  labels[0] = 0
  search(nodes, searched, labels, 0)
  return labels

def main():
  n = int(input())
  nodes = [[] for _ in range(n)]
  for _ in range(n-1):
    v, u, w = map(int, input().split(' '))
    nodes[v-1].append((u-1,w))
    nodes[u-1].append((v-1,w))
  ans = solve(n, nodes)
  for r in ans:
    print(r)
  

if __name__=='__main__':
  main()

Submission status: Accepted

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


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

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


def dfs(v, color):
    for nv, w in to[v]:
        if color[nv] == -1:
            color[nv] = color[v] ^ (w % 2)
            dfs(nv, color)


def main():
    color = [-1] * N
    color[0] = 0
    dfs(0, color)
    print(*color, sep='\n')


if __name__ == "__main__":
    main()

Submission status: Accepted

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


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

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


def dfs(v, color):
    for nv, w in to[v]:
        if color[nv] == -1:
            if w % 2:
                color[nv] = color[v] ^ 1
            else:
                color[nv] = color[v]
            dfs(nv, color)


def main():
    color = [-1] * N
    color[0] = 0
    dfs(0, color)
    print(*color, sep='\n')


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
#import math
#import itertools
from collections import deque

INT = lambda: int(input())
INTM = lambda: map(int,input().split())
STRM = lambda: map(str,input().split())
STR = lambda: str(input())
LIST = lambda: list(map(int,input().split()))
LISTS = lambda: list(map(str,input().split()))

class Graph():
    def __init__(self, v):
        self.v = v
        self.graph = [[] for _ in range(v)]
        self.INF = 10 ** 9
    
    def addEdge(self, start, end, dist):
        self.graph[start].append((end, dist))
        self.graph[end].append((start, dist))

def do():
    n=INT()
    g=Graph(n)
    for i in range(n-1):
        u,v,d=INTM()
        u-=1
        v-=1
        g.addEdge(u,v,d)

    que=deque()
    check=[True]*n
    dists=[-1]*n
    check[0]=False
    dists[0]=0
    que.append([0,0])
    while que:
        now,dist_f=que.popleft()
        for next,dist in g.graph[now]:
            if check[next]:
                check[next]=False
                temp=dist_f+dist
                dists[next]=temp
                que.append([next,temp])

    for i in dists:
        if i%2==0:
            print(0)
        else:
            print(1)
    
if __name__=='__main__':
    do()

Submission status: Accepted

Solution code:
from collections import deque

n = int(input())

distance = [-1] * n

edge = [dict() for _ in range(n)]

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

D = deque([0])
distance[0] = 0

while D:
    now = D.popleft()
    for i in edge[now]:
        if distance[i] == -1:
            distance[i] = (distance[now] + edge[now][i]) % 2
            D.append(i)

for i in distance:
    print(i)

Submission status: Accepted

Solution code:
from collections import deque

def bfs(s):
    global color
    q = deque()
    q.append(s)
    color[s] = 0
    while q:
        i = q.popleft()
        for g in G[i]:
            if color[g[0]] == -1:
                if g[1] % 2 == 0:
                    color[g[0]] = color[i]
                else:
                    color[g[0]] = 1 - color[i]
                q.append(g[0])
    return

n = int(input())
G = [[] for _ in range(n + 1)]
color = [-1] * (n + 1)
for _ in range(n - 1):
    u, v, w = map(int, input().split())
    G[u].append([v, w])
    G[v].append([u, w])
bfs(1)
for i in range(1, n + 1):
    print(color[i])

Submission status: Accepted

Solution code:
from collections import deque
n = int(input())
trees = [[] for _ in range(n)]

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

color = [0 for _ in range(n)]
visited = set()

next = deque()
next.append(0)
visited.add(0)
color[0] = 1

while len(next):
    i = next.popleft()
    for j, d in trees[i]:
        if j in visited:
           continue
        if d % 2 == 0:
            color[j] = color[i]
        else:
            color[j] = color[i] * -1
        next.append(j)
        visited.add(j)

for i in color:
    if i == -1:
        print(0)
    else:
        print(i)

Submission status: Accepted

Solution code:
import heapq as hq
N = int(input())
L = [set() for _ in range(N)]
for _ in range(N-1):
    u, v, w = list(map(int, input().split()))
    u -= 1
    v -= 1
    L[u].add((w, v))
    L[v].add((w, u))
# print(L)

INF = float('inf')
D = [INF]*N
D[0] = 0
task = []
hq.heapify(task)
for w, v in L[0]:
    hq.heappush(task, (w, v))
while task:
    w, v = hq.heappop(task)
    # print(v,w)
    if D[v] <= w:
        continue
    D[v] = w
    for y, x in L[v]:
        hq.heappush(task, (w+y, x))
# print(D)

for i in range(N):
    print(D[i] % 2)

Submission status: Accepted

Solution code:
from collections import deque

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

q = deque([1])
d = [-1]* (N + 1)
d[1] = 0
while q:
    u = q.popleft()
    for e in conn[u]:
        v, w = e[0], e[1]
        if d[v] == -1:
            d[v] = d[u] + w
            q.append(v)

for v in range(1, N + 1):
    print(d[v] % 2)

Submission status: Accepted

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

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

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

color=[-1]*N
def even(v=0,col=0):
    color[v]=col
    for i in range(len(graph[v])):
        nv,nw=map(int,graph[v][i])
        if color[nv]!=-1: continue
        if nw%2==0:
            even(nv,col)
        else:
            even(nv,1-col)

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

Submission status: Accepted

Solution code:
import collections

n = int(input())
graph = [[] for i in range(n + 1)]
flag = [False for i in range(n + 1)]
for i in range(n - 1):
    u, v, w = map(int, input().split())
    graph[u].append([v, w])
    graph[v].append([u, w])
color = [None for i in range(n + 1)]
color[1] = 0
queue = collections.deque([1])
while queue:
    test = queue.popleft()
    flag[test] = True
    for i in graph[test]:
        if flag[i[0]] == True:
            continue
        queue.append(i[0])
        color[i[0]] = i[1] % 2 ^ color[test]
for i in range(n):
    print(color[i + 1])

Submission status: Accepted

Solution code:
from collections import deque
N=int(input())
visited=[-1]*N
l=[[] for i in range(N)]
for i in range(N-1):
   a,b,c=map(int,input().split())
   a-=1;b-=1
   l[a].append((b,c%2))
   l[b].append((a,c%2))
def ans(node,dis):
   visited[node]=0
   que=deque(l[node])
   while que:
      node,dis=que.popleft()
      visited[node]=dis
      for i,j in l[node]:
         if visited[i]==-1:
            visited[i]=(dis+j)%2
            que.append((i,(dis+j)%2))
ans(0,0)
for i in visited:
   print(i)

Submission status: Accepted

Solution code:
from collections import deque

N = int(input())

graph = [[] for _ in range(N+1)]
cost = [[] for _ in range(N+1)]
ans = [-1] * (N+1)

for query in range(N-1):
    u, v, w = map(int, input().split())
    graph[u].append(v)
    cost[u].append(w % 2)
    graph[v].append(u)
    cost[v].append(w % 2)
#print('input')

que = deque()

ans[1] = 0
que.append(1)

while que:
    now = que.popleft()
    #print(graph[now])
    for index in range(len(graph[now])):
        nextg = graph[now][index]
        nextc = cost[now][index]
        #print(ans[nextg])
        if ans[nextg] != -1:
            #print('continued')
            continue
        que.append(nextg)

        #print(nextc)
        if nextc == 1:
            ans[nextg] = (ans[now] + 1) % 2
        else:
            ans[nextg] = ans[now]
    #print(que)
    #print(ans)

#print(ans)

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

Submission status: Accepted

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

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

color = [0 for _ in range(N)]
visited = [False for _ in range(N)]

def dfs(now):

    for adj in graph[now]:
        v, dist = adj
        if visited[v]:
            continue
        visited[v] = True
        color[v] = color[now] + dist
        dfs(v)

    return


for start in range(N):
    if not visited[start]:
        color[start] = 0
        visited[start] = True
        dfs(start)

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

Submission status: Accepted

Solution code:
from collections import deque

N = int(input())
dist = {}
graph = [[] for i in range(N)]

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


q = deque()
q.append(0)

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

while q:
    now = q.popleft()

    for adj in graph[now]:
        if color[adj] == -1:
            if now < adj:
                color[adj] = color[now] + dist[(now, adj)]
            else:
                color[adj] = color[now] + dist[(adj, now)]

            q.append(adj)


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

Submission status: Accepted

Solution code:
from collections import deque
N = int(input())
#隣接リスト
g = [[] for i in range(N)]
for i in range(N-1):
  u,v,w = map(int,input().split())
  g[u-1].append([v-1,w])
  g[v-1].append([u-1,w])
q = deque()
#通ったかどうか
check = [0] * N
check[0] = 1
q.append(0)
ans = [-1] * N
ans[0] = 0
while len(q) > 0:
  e = q.popleft()
  for i,j in g[e]:
    if check[i] == 1:
      continue
    ans[i] = (ans[e] + j) %2
    check[i] = 1
    q.append(i)
for i in range(N):
  print(ans[i])

Submission status: Accepted

Solution code:
from collections import*
n=int(input())
l=[[]for i in range(n)]
ans=[-1 for i in range(n)]
visit=[False for i in range(n)]
ans[0]=0
for i in range(n-1):
    u,v,w=map(int,input().split())
    l[u-1].append((v-1,w))
    l[v-1].append((u-1,w))
      
q=deque()
q.append((0,0,-1))
while q:
    v,d,p=q.popleft()
    if d%2==0:
        ans[v]=0
    else:
        ans[v]=1
    for u,w in l[v]:
        if u==p:
            continue
        q.append((u,d+w,v))
print('\n'.join(map(str, ans)))

Submission status: Accepted

Solution code:
N=int(input())
G=[[] for _ in [0]*(N+1)]
for _ in [0]*(N-1):
    u,v,w=map(int,input().split())
    G[u].append((v,w))
    G[v].append((u,w))

c=[0]*(N+1)
stack=[1]
c[1]=1
while stack:
    r=stack.pop()
    for nr,nw in G[r]:
        if c[nr]==0:
            stack.append(nr)
            if nw%2:
                c[nr]=-c[r]
            else:
                c[nr]=c[r]
for i in c[1:]:
    print((i+1)//2)

Submission status: Accepted

Solution code:
class Graph():
	def __init__(self):
		self.adjacency_dict = {}
		self.weight = []

	def add_vartex(self, v):
		self.adjacency_dict[v] = []
		self.weight.append([])

	def add_edge(self, v1, v2, w):
		self.adjacency_dict[v1].append(v2)
		self.adjacency_dict[v2].append(v1)
		self.weight[v1].append(w)
		self.weight[v2].append(w)

	def get_vartexes(self):
		return self.adjacency_dict.keys()

	def get_edges(self, v):
		return self.adjacency_dict[v], self.weight[v]

	def printgraph(self):
		return print(self.adjacency_dict)

n = int(input())

res = []
g = Graph()
for i in range(n):
	res.append(-1)
	g.add_vartex(i)

for i in range(n-1):
	u, v, w = map(int, input().strip().split())
	g.add_edge(u - 1, v - 1, w % 2)


q = []
res[0] = 0
q.append(0)
while(len(q) > 0):
	v = q.pop()
	u_l, w_l = g.get_edges(v)
	for u, w in zip(u_l, w_l):
		if res[u] != -1:
			continue
		res[u] = (res[v] + w) % 2
		q.append(u)

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

Submission status: Accepted

Solution code:
from collections import deque

N = int(input())

length = {}
conn = [[] for _ in range(N + 1)]
for i in range(N - 1):
    u, v, w = [int(x) for x in input().split()]
    conn[u].append(v)
    conn[v].append(u)
    length[(u, v)] = w

q = deque([1])
dist = [-1] * (N + 1)
dist[1] = 0
while q:
    u = q.popleft()
    for v in conn[u]:
        if dist[v] == -1:
            if u < v:
                dist[v] = dist[u] + length[(u, v)]
            else:
                dist[v] = dist[u] + length[(v, u)]
            q.append(v)

for i in range(1, N + 1):
    print(dist[i] % 2)

Submission status: Accepted

Solution code:
from sys import stdin
import sys
import math
from functools import reduce
import functools
import itertools
from collections import deque,Counter,defaultdict
from operator import mul
import copy
# ! /usr/bin/env python
# -*- coding: utf-8 -*-
import heapq
sys.setrecursionlimit(10**6)
# INF =  float("inf")
INF = 10**18
import bisect
import statistics
mod = 10**9+7
# mod = 998244353

N = int(input())

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


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

def bfs(u):
    stack = deque([u])
    seen[u] = 1
    ans[u] = 0

    while len(stack) > 0:
        v = stack.popleft()

        for w in al[v]:
            if seen[w[0]] == 0:
                stack.append(w[0])
                if w[1] % 2 == 0:
                    ans[w[0]] = ans[v]
                else:
                    ans[w[0]] = 1 - ans[v]
                seen[w[0]] = 1

bfs(1)

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

Submission status: Accepted

Solution code:
# coding: utf-8
import sys
import copy

sys.setrecursionlimit(10 ** 9)


def dfs(seen, graph, i):
    for v, w in graph[i]: 
        if seen[v-1] != -1:
            continue
        seen[v-1] = abs((w % 2) - seen[i])
        dfs(seen, graph, v-1)
    

def main():
    n = int(input())
    graph = [[] for _ in range(n)]
    for _ in range(n-1):
        ui, vi, wi = map(int, input().split())
        graph[ui-1].append((vi, wi))
        graph[vi-1].append((ui, wi))
    
    seen = [-1 for _ in range(n)]
    seen[0] = 0
    for i in range(n-1):
        dfs(seen, graph, i)
        
    print(*seen, sep='\n')
        
main()

Submission status: Accepted

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

stack = [0]
color = [-1]*N
color[0] = 0
while stack:
    v = stack.pop()
    for child, w in adj[v]:
        if color[child] < 0:
            color[child] = (color[v] + w) % 2
            stack.append(child)

for i in color:
    print(i)