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:
#!/usr/bin/env python3
import sys

def solve(N: int, u: "List[int]", v: "List[int]", w: "List[int]"):
    stack = [u[0]-1]
    answer = [-1]*N
    tree = [{} for _ in range(N)]
    for i in range(N-1):
        is_even = (w[i] % 2 == 0)
        tree[u[i]-1][v[i]-1] = is_even
        tree[v[i]-1][u[i]-1] = is_even
    answer[u[0]-1]=0
    #1なら訪問済み
    while stack:
        p = stack.pop()
        neighbors = tree[p]
        for n in neighbors:
            if answer[n]<0:
                answer[n] = answer[p] if neighbors[n] else 1-answer[p]
                stack.append(n)

    for a in answer:
        print(a)
    return


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

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n = int(input())
uvw = [tuple(map(int,input().split())) for i in range(n-1)]
to_dist = [[] for i in range(n)]
for u,v,w in uvw:
    u,v = u-1,v-1
    to_dist[u].append((v,w))
    to_dist[v].append((u,w))

visited = [0]* n
visited[0] = 1
ans = [0]*n
start_vertexes = [0]
 
while start_vertexes:
    start_vertex = start_vertexes.pop()
    for to, dist in to_dist[start_vertex]:
        if visited[to]: continue
        ans[to] = (ans[start_vertex]+dist)%2
        visited[to] = 1
        start_vertexes.append(to)
print(*ans, sep='\n')

Submission status: Accepted

Solution code:
n = int(input())
bw = [0] * (n + 1)
uvw = [[] for _ in range (n+1)]

for i in range(0,n-1):
  tmp = list(map(int, input().split()))
  uvw[tmp[0]].append((tmp[1], tmp[2]))
  uvw[tmp[1]].append((tmp[0], tmp[2]))

#print(uvw)

nxt = [1]
bw[1] = 1

while len(nxt) != 0:
  cur = nxt.pop()
  while len(uvw[cur]) > 0:
    tmp = uvw[cur].pop()
    if tmp[1] % 2 == 0:
      jdg = 1
    else:
      jdg = -1

    if bw[tmp[0]] == 0:
#      print ('ADD NXT=' + str(tmp[0]) + ' JUDGE=' + str(jdg))
      bw[tmp[0]] = bw[cur] * jdg
      nxt.append(tmp[0])

for i in range(1,n+1):
  if bw[i] == -1:
    print('0')
  else:
    print('1')

Submission status: Accepted

Solution code:
N = int(input())

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

d = [-1] * N
d[0] = 0
q = [0]
while q:
    p = q.pop()
    for n, w in link[p]:
        if d[n] == -1:
            d[n] = d[p] + w
            q.append(n)

for i in d:
    print(i % 2)

Submission status: Accepted

Solution code:
import sys
import collections


def solve():
    input = sys.stdin.readline
    mod = 10 ** 9 + 7
    n = int(input().rstrip('\n'))
    tmd = collections.defaultdict(list)
    tmdc = collections.defaultdict(int)
    for i in range(n-1):
        tma, tmb, tmc = list(map(int, input().rstrip('\n').split()))
        tmd[tma-1] += [tmb-1]
        tmd[tmb-1] += [tma-1]
        tmdc[tma-1, tmb-1] = tmc
        tmdc[tmb-1, tma-1] = tmc

    ql = [[0, 0]]
    ql = collections.deque(ql)
    fq = collections.defaultdict(list)
    while True:
        if len(ql) != 0:
            cost, tmp = ql.popleft()
            for tmv in tmd[tmp]:
                if tmv not in fq:
                    ql.append([cost + tmdc[tmp, tmv], tmv])
                    fq[tmv] = (cost + tmdc[tmp, tmv]) % 2
        else:
            break
    for i in range(n):
        print(fq[i])


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
import sys
def input():
    return sys.stdin.readline()[:-1]
n=int(input())
uvw=[list(map(int,input().split())) for i in range(n-1)]
class WeightedUnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n+1)]
        self.rank = [0] * (n+1)
        self.weight = [0] * (n+1)


    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            y = self.find(self.par[x])
            self.weight[x] += self.weight[self.par[x]]
            self.par[x] = y
            return y

    def union(self, x, y, w):
        rx = self.find(x)
        ry = self.find(y)
        if self.rank[rx] < self.rank[ry]:
            self.par[rx] = ry
            self.weight[rx] = w - self.weight[x] + self.weight[y]
        else:
            self.par[ry] = rx
            self.weight[ry] = -w - self.weight[y] + self.weight[x]
            if self.rank[rx] == self.rank[ry]:
                self.rank[rx] += 1

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def diff(self, x, y):
        return self.weight[x] - self.weight[y]
uf=WeightedUnionFind(n)
for i in range(n-1):
    uf.union(uvw[i][0],uvw[i][1],uvw[i][2])

for i in range(n):
    if uf.diff(i+1,uf.find(i+1))%2==0:
        print(0)
    else:
        print(1)

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**6)
    n = int(input())
    edge = [dict() for _ in range(n)]
    dist = [0]*n
    for _ in range(n-1):
        u, v, w = map(int, input().split())
        edge[u-1].update({v-1: w})
        edge[v-1].update({u-1: w})

    def dfs(i, pre, d):
        dist[i] = d
        for v in edge[i].keys():
            if v == pre:
                continue
            dfs(v, i, d+edge[i][v])

    dfs(0, -1, 0)
    # print(dist)

    for i in dist:
        if i % 2 == 0:
            print(0)
        else:
            print(1)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

e =[[] for _ in range(n)]
color = [-1]*n
dw = {}

for u,v,w in uvw:
  e[u-1].append(v-1)
  e[v-1].append(u-1)
  dw[(u-1,v-1)] = dw[(v-1,u-1)] = w

def dfs(i,c)  :
  color[i] = c
  for ei in e[i]:
    if color[ei] != -1:
      continue
    dfs(ei, c+dw[(i,ei)])

dfs(0,0)   

for c in color:
  print(c%2)

Submission status: Accepted

Solution code:
n=int(input())
q=[[] for i in range(n+1)]
for i in range(n-1):
    a,b,c=map(int,input().split())
    q[a].append((b,c))
    q[b].append((a,c))

l=[-1]*n
s=[(1,0)]
while s:
    a,w=s.pop()
    l[a-1]=w%2
    for b,c in q[a]:
        if l[b-1]==-1:
            s.append((b,w+c))

for i in l:
    print(i)

Submission status: Accepted

Solution code:
N=int(input())
p=[[]for _ in range(N+1)]
for _ in range(N-1):
  u,v,w=map(int,input().split())
  p[u].append((v,w))
  p[v].append((u,w))
s=[(1,0)]
l=[-1]*N
while s:
  a,w=s.pop()
  l[a-1]=w%2
  for b,c in p[a]:
    if l[b-1]==-1:
      s.append((b,w+c))
for i in l:
	print(i)

Submission status: Accepted

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


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])
ans = [0]*N


def dfs(v, p, c):
    global ans
    ans[v] = c
    for e in G[v]:
        nv, cost = e
        if nv == p:
            continue
        if (cost % 2) == 0:
            dfs(nv, v, c)
        else:
            dfs(nv, v, (c+1) % 2)


def main():
    dfs(0, -1, 0)
    for c in ans:
        print(c)


if __name__ == '__main__':
    main()

Submission status: Accepted

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


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])
ans = [0]*N


def dfs(v, p, c):
    global ans
    ans[v] = c
    for e in G[v]:
        nv, cost = e
        if nv == p:
            continue
        if (cost % 2) == 0:
            dfs(nv, v, c)
        else:
            dfs(nv, v, (c+1) % 2)


def main():
    dfs(0, -1, 0)
    for c in ans:
        print(c)


if __name__ == '__main__':
    main()

Submission status: Accepted

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


def dijkstra(s, n, edge):
    d = [float("inf")] * n
    d[s] = 0
    q = []
    for e in edge[s]:
        heapq.heappush(q, e)
    while q:
        minedge = heapq.heappop(q)
        v = minedge[1]
        if d[v] < minedge[0]:
            continue
        d[v] = minedge[0]
        for e in edge[v]:
            heapq.heappush(q, [e[0]+d[v], e[1]])
    return d


def main():
    N = int(input())
    E = [[] for _ in range(N)]
    for _ in range(N-1):
        u, v, w = map(int, input().split())
        E[u-1].append([w, v-1])
        E[v-1].append([w, u-1])
    D = dijkstra(0, N, E)
    for d in D:
        print(d % 2)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
import collections


def solve():
    input = sys.stdin.readline
    mod = 10 ** 9 + 7
    tmd = collections.defaultdict(list)
    n = int(input().rstrip('\n'))
    d = collections.defaultdict(int)
    for i in range(n-1):
        tma, tmb, cost = list(map(int, input().rstrip('\n').split()))
        tmd[tma-1] += [tmb-1]
        tmd[tmb-1] += [tma-1]
        d[tma-1, tmb-1] = cost
        d[tmb-1, tma-1] = cost

    ql = [[0, 0]]
    ql = collections.deque(ql)
    fq = collections.defaultdict(int)
    while True:
        if len(ql) != 0:
            cost, tmp = ql.popleft()
            for tmv in tmd[tmp]:
                if tmv not in fq:
                    ql.append([cost + d[tmv, tmp], tmv])
                    fq[tmv] = (cost + d[tmv, tmp]) % 2
        else:
            break
    for i in range(n):
        print(fq[i])


if __name__ == '__main__':
    solve()

Submission status: Accepted

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


def main():
    N = int(readline())
    graph = [[] for _ in range(N + 1)]

    for i in readlines():
        u, v, w = map(int, i.split())
        w %= 2
        graph[u].append((v, w))
        graph[v].append((u, w))

    stack = [1]
    parent = [0] * (N + 1)
    color = [0] * (N + 1)

    while stack:
        here = stack.pop()
        for x, w in graph[here]:
            if x == parent[here]:
                continue
            parent[x] = here
            color[x] = color[here] ^ w
            stack.append(x)

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


if __name__ == '__main__':
    main()

Submission status: Accepted

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

def main():
    N = int(readline())
    graph = [[] for _ in range(N + 1)]

    for i in readlines():
        u, v, w = map(int, i.split())
        graph[u].append((v, w))
        graph[v].append((u, w))

    stack = [1]
    parent = [0] * (N + 1)
    color = [0] * (N + 1)

    while stack:
        here = stack.pop()
        for x, w in graph[here]:
            if x == parent[here]:
                continue
            parent[x] = here
            color[x] = color[here] ^ (w % 2)
            stack.append(x)

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


if __name__ == '__main__':
    main()

Submission status: Accepted

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


N = int(readline())
graph = [[] for _ in range(N + 1)]

for i in readlines():
    u, v, w = map(int, i.split())
    graph[u].append((v, w))
    graph[v].append((u, w))

stack = [1]
parent = [0] * (N + 1)
color = [0] * (N + 1)

while stack:
    here = stack.pop()
    for x, w in graph[here]:
        if x == parent[here]:
            continue
        parent[x] = here
        color[x] = color[here] ^ (w % 2)
        stack.append(x)

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

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
def main():
    N=int(input())
    edge = [[]for _ in range(N)]
    for _ in range(N-1):
        u,v,w = map(int,input().split())
        u,v = u-1,v-1
        edge[u].append((v,w))
        edge[v].append((u,w))
    color = [-1]*N
    color[0]=0
    stack = [(0,0)]
    while stack:
        v,col = stack.pop()
        for to,dist in edge[v]:
            if color[to]!=-1:
                continue
            c = (col+dist)%2  # 色
            color[to] = c
            stack.append((to,c))
    print(*color,sep="\n")
            

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    N=int(input())
    edge = [[]for _ in range(N)]
    for _ in range(N-1):
        u,v,w = map(int,input().split())
        u,v = u-1,v-1
        edge[u].append((v,w))
        edge[v].append((u,w))
    color = [-1]*N
    color[0]=0
    stack = [(0,0)]
    while stack:
        v,col = stack.pop()
        for to,dist in edge[v]:
            if color[to]!=-1:
                continue
            c = (col+dist)%2  # 色
            color[to] = c
            stack.append((to,c))
    print(*color,sep="\n")
            

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.buffer.readline
    N = int(input())
    G = [[] for _ in range(N+1)]
    st = 0
    st_w = 0
    for i in range(N-1):
        u, v, w = (int(i) for i in input().split())
        G[u].append((v, w))
        G[v].append((u, w))
        if i == 0:
            st = u
            st_w = w
    color = [-1] * (N+1)  # 0: white, 1: black, -1: undefined
    from collections import deque

    def coloring(v, w):
        """
        breadth-first search
        a simplified version
        """
        que = deque()
        color[v] = 0
        que.append((v, w))
        while que:
            u, w = que.popleft()
            for v, d in G[u]:
                if color[v] != -1:
                    continue
                if d % 2 != 0:
                    n_col = (color[u] + 1) % 2
                else:
                    n_col = color[u]
                color[v] = n_col
                que.append((v, d))

    coloring(st, st_w)
    for c in color[1:]:
        print(c)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import Counter,defaultdict,deque
def main():
    N=int(input())
    edge = [[]for _ in range(N)]
    for i in range(N-1):
        u,v,w = map(int,input().split())
        u,v = u-1,v-1
        edge[u].append((v,w))
        edge[v].append((u,w))
    color = [-1]*N
    color[0]=0
    queue = deque([(0,0)])
    while queue:
        v,col = queue.popleft()
        for to,dist in edge[v]:
            if color[to]!=-1:
                continue
            c = (col+dist)%2  # 色
            color[to] = c
            queue.append((to,c))
    print(*color,sep="\n")
            

if __name__ == '__main__':
    main()

Submission status: Accepted

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


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

    connect = [[] for _ in range(n+1)]
    color = [None]*(n+1)
    color[1] = 0

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

    def dfs(now=1, prev=-1):
        kids = connect[now]
        for kid in kids:
            if kid[0] == prev:
                continue
            if kid[1] == 0:
                color[kid[0]] = (0, 1)[color[now]]
            else:
                color[kid[0]] = (1, 0)[color[now]]
            dfs(kid[0], now)

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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(100000)

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

def dfs(i, _d):
    dd[i] = _d
    for c in e[i]:
        if dd[c]!=-1: continue
        dfs(c, _d+d[(i,c)])

dfs(0,0)
for _dd in dd:
    print(_dd%2)

Submission status: Accepted

Solution code:
#ダイクストラ法(単一始点最短路)　計算量O(|E|log|V|)
#V:頂点の集合 E:辺の集合
#負の辺が含まれるときはベルマンフォード法
import collections
import heapq

class Dijkstra():
    def __init__(self):
        self.e=collections.defaultdict(list)
    def add(self,u,v,d,directed=False):
        #0-indexedでなくても良いことに注意
        #u=from,v=to,d=cost
        #directed =Trueなら、有向グラフ
        if directed is False:
            self.e[u].append([v,d])
            self.e[v].append([u,d])
        else:
            self.e[u].append([v,d])
    def delete(self,u,v):
        self.e[u]=[_ for _ in self.e[u] if _[0]!=v]
        self.e[v]=[_ for _ in self.e[v] if _[0]!=u]
    def search(self,s):
        #:param s:始点
        #:return: 始点から各点までの最短経路
        d = collections.defaultdict(lambda: float('inf'))
        d[s] = 0
        q = []
        heapq.heappush(q, (0, s))
        v = collections.defaultdict(bool)
        while len(q):
            k, u = heapq.heappop(q)
            if v[u]:
                continue
            v[u] = True

            for uv, ud in self.e[u]:
                if v[uv]:
                    continue
                vd = k + ud
                if d[uv] > vd:
                    d[uv] = vd
                    heapq.heappush(q, (vd, uv))
        return d

#Saving Shuuk
n=int(input())
uvw=l=[list(map(int, input().split())) for i in range(n-1)]
#print(l)
graph1=Dijkstra()
for u,v,w in l:
    if w%2==0:
        graph1.add(u,v,0)
    else:
        graph1.add(u,v,1)

result_a=graph1.search(1) #{2: 0, 1: 1, 4: 2, 3: 21})
#print(result_a) #{3: 0, 1: 1, 4: 101, 2: 11})

for i in range(1,n+1):
    print(result_a[i]%2)

Submission status: Accepted

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

N = int(input())
nodes = [[[], -1] for _ in range(N + 1)]

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


def f(i, c):
    if nodes[i][1] >= 0: return
    nodes[i][1] = c
    for n in nodes[i][0]:
        f(n[0], (c + (n[1] % 2)) % 2)

# print(nodes)
f(0, 0)
for i in range(N):
    print(nodes[i][1])

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())
    u, v = u - 1, v - 1
    T[u].append([v, w])
    T[v].append([u, w])


color = [-1] * N
stack = [[0, 0]]
while stack:
    n, w = stack.pop()
    color[n] = w % 2

    for to, to_w in T[n]:
        if color[to] >= 0:
            continue

        stack.append([to, w + to_w])

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

Submission status: Accepted

Solution code:
from collections import deque
q=deque([1])
n=int(input())
l=[[] for i in range(n+1)]
for i in range(n-1):
  a,b,c=map(int,input().split())
  c=c%2
  l[a].append([b,c])
  l[b].append([a,c])
inf=10**10
d=[inf for i in range(n+1)]
d[1]=0
def dik(s):
  q=deque([s])
  while q:
    a=q.popleft()
    for i in l[a]:
      index=i[0]
      dis=i[1]
      if d[index]>dis+d[a]:
        d[index]=dis+d[a]
        q.append(index)
dik(1)
for i in range(1,n+1):
  if d[i]%2==0:
    print(0)
  else:
    print(1)

Submission status: Accepted

Solution code:
# D - Even Relation

# 木なのでノードAB間の辺を辿ればそれがAB間の最短経路となる
# 全ての｢辺｣についてループする

from collections import deque

N = int(input())

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

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

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

while d:
    current_point = d.popleft()
    for current_edge in edge[current_point]:
        if color[current_edge[0]] == -1:
            color[current_edge[0]] = (color[current_point] + current_edge[1]) % 2
            d.append(current_edge[0])

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

Submission status: Accepted

Solution code:
# D - Even Relation

# 木なのでノードAB間の辺を辿ればそれがAB間の最短経路となる
# 全ての｢辺｣についてループする

from collections import deque

N = int(input())

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

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

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

while d:
    current_point = d.pop()
    for current_edge in edge[current_point]:
        if color[current_edge[0]] == -1:
            color[current_edge[0]] = (color[current_point] + current_edge[1]) % 2
            d.append(current_edge[0])

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

Submission status: Accepted

Solution code:
import sys
from collections import deque

n = int(input())

color_ls = {i: None for i in range(n)}
dict_map = {i : [] for i in range(n)}
already = set()
for i in range(n - 1):
    u, v, w = [int(i) for i in sys.stdin.readline().split()]
    u -= 1
    v -= 1
    if i == 0:
        root = u
    dict_map[u].append([v, w])
    dict_map[v].append([u, w])
    already.update({u, v})
color_ls[root] = 0
cur = root
already.clear()
que = deque()
while True:
    candidate = dict_map[cur]
    for cand, w in candidate:
        if cand in already:
            continue
        already.add(cand)
        que.append(cand)
        if w % 2 == 0:
            color_ls[cand] = 0 if color_ls[cur] == 0 else 1
        else:
            color_ls[cand] = 1 if color_ls[cur] == 0 else 0
    if len(que) == 0 or len(already) == n:
        break
    cur = que.popleft()

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(4100000)
input = sys.stdin.readline
def main():
    def Dfs(G, v, cur=0):
        color[v] = cur % 2
        for next_v in G[v]:
            if color[next_v[0]] != -1:
                continue
            Dfs(G, next_v[0], cur+next_v[1])


    n = int(input())
    e = [[0, 0, 0]] + [list(map(int, input().split())) for i in range(n-1)]
    g = [[] for i in range(n+1)]

    for i in range(1, n):
        g[e[i][0]].append([e[i][1], e[i][2]])
        g[e[i][1]].append([e[i][0], e[i][2]])

    color = [-1 for i in range(n+1)]
    for v in range(1, n+1):
        if color[v] != -1:
            continue
        Dfs(g, v)

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

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque
def bfs(n,e,fordfs):
    #点の数、スタートの点、有向グラフ
    W = [-1]*n
    W[e] = 0
    que = deque()
    que.append(e)
    len = [0]*n
    color = [0]*n
    while que:
        now = que.popleft()
        nowv = W[now]
        nowlen = len[now]
        nowcolor = color[now]
        for ne in fordfs[now]:
            if nowv == W[ne]:
                return -1
            elif W[ne] == -1:
                W[ne] = (nowv+1) % 2
                len[ne] = nowlen+1
                if nowcolor==0:
                    color[ne] = 1
                que.append(ne)
    return color[:n//2]
#############################################################
import sys
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
mod = 10**9 + 7
inf = float('inf')
ans = []

N = I()
uvw = [LI() for _ in range(N-1)]
g = [[] for i in range(2*N)]

for i in range(N-1):
    x = uvw[i][0] - 1
    y = uvw[i][1] - 1
    if uvw[i][2]%2==1:
        g[x].append(y)
        g[y].append(x)
    else:
        g[x].append(N+x)
        g[N+x].append(y)
        g[y].append(N+y)
        g[N+y].append(x)

ans = bfs(2*N,0,g)

for i in ans:
    print(i)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(4100000)

def Dfs(G, v, cur=0):
    color[v] = cur % 2
    for next_v in G[v]:
        if color[next_v[0]] != -1:
            continue
        Dfs(G, next_v[0], cur+next_v[1])


n = int(input())
e = [[0, 0, 0]] + [list(map(int, input().split())) for i in range(n-1)]
g = [[] for i in range(n+1)]

for i in range(1, n):
    g[e[i][0]].append([e[i][1], e[i][2]])
    g[e[i][1]].append([e[i][0], e[i][2]])

color = [-1 for i in range(n+1)]
for v in range(1, n+1):
    if color[v] != -1:
        continue
    Dfs(g, v)

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

Submission status: Accepted

Solution code:
def resolve():
    N = int(input())
    import collections
    n_dict = collections.defaultdict(list)
    for i in range(N-1):
        u,v,w = map(int,input().split())
        n_dict[u-1].append((v-1,w))
        n_dict[v-1].append((u-1,w))

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

    d = collections.deque()
    for i in range(N):
        if color[i] == -1:
            d.append((i,1))
        while d:
            j,c = d.pop()
            color[j] = c
            for n,w in n_dict[j]:
                if color[n] == -1:
                    d.append((n,c^1)) if w % 2 != 0 else d.append((n,c))
                else:
                    continue
        print(color[i])
resolve()

Submission status: Accepted

Solution code:
from collections import deque

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

q = deque()
q.append([0, 0])
visited = [0]*(N)
while q:
    temp = q.pop()
    for L in edge[temp[0]]:
        if visited[L[0]] == 0:
            d[L[0]] = L[1] + temp[1]
            q.append([L[0], d[L[0]]])
            visited[L[0]] = 1
            
for i in range(N):
    print(d[i]%2)

Submission status: Accepted

Solution code:
N=int(input())
to = [[] for _ in range(N)]
for _ in range(N-1):
    u, v, w = [int(x) for x in input().split()]
    u -= 1
    v -= 1
    to[u].append([v, w])
    to[v].append([u, w])
ans = [-1] * N
ans[0] = 0
q = [0]
while(len(q) != 0):
    v = q.pop()
    for u, w in to[v]:
        if (ans[u] != -1): continue
        ans[u] = (ans[v]+w) % 2
        q.append(u)
for v in ans:
    print(v)

Submission status: Accepted

Solution code:
import sys
n=int(input())
if n==1:
    print(0)
    sys.exit()
lst=[list(map(int,input().split())) for _ in range(n-1)]
data=[[] for i in range(n+1)]
for i in range(n-1):
    u,v,w=lst[i]
    data[u].append(i)
    data[v].append(i)
flag=[-1]*(n+1)
u,v,w=lst[0]
flag[u]=0
flag[v]=(flag[u]+w)%2
que=[data[u],data[v]]
while que:
    h=que.pop()
    for k in h:
        u,v,w=lst[k]
        if flag[u]!=-1 and flag[v]!=-1:
            continue
        else:
            if flag[u]!=-1:
                flag[v]=(flag[u]+w)%2
                que.append(data[v])
            else:
                flag[u]=(flag[v]+w)%2
                que.append(data[u])
for i in range(1,n+1):
    print(flag[i])

Submission status: Accepted

Solution code:
#%%
import numpy as np
n = int(input())
u, v, w = [0] * (n-1), [0] * (n-1), [0] * (n-1)

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

#print(app)

que = [1]
ans = [2] * (n+1)
check = [0] * (n+1)

while len(que) > 0:
    tmp = que.pop(0)
    tmp_color = ans[tmp]
    tmp_list = app[tmp]
    check[tmp] = 1
    for i in range(2):
        for j in range(len(tmp_list[i])):
            if tmp_color == 0:
                if i == 0:
                    ans[tmp_list[i][j]] = 1
                else:
                    ans[tmp_list[i][j]] = 0
            else:
                if i == 0:
                    ans[tmp_list[i][j]] = 0
                else:
                    ans[tmp_list[i][j]] = 1
            if check[tmp_list[i][j]] == 0:
                que.append(tmp_list[i][j])

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

Submission status: Accepted

Solution code:
from collections import deque

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

for _ in range(N - 1):
    fr, to, c = map(int, input().split())
    fr -= 1
    to -= 1
    edges[fr].append((to, c))
    edges[to].append((fr, c))

depth = [-1] * N
st = deque([(0, -1, 0)])  # now, parent, dep

while st:
    now, parent, d = st.pop()

    depth[now] = d

    for to, c in edges[now]:
        if to == parent:
            continue
        st.append((to, now, d + c))

ans = [d % 2 for d in depth]
print(*ans, sep='\n')

Submission status: Accepted

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

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

inf = float("inf")
E = [[] for _ in range(N+1)]
for i in range(N-1):
	if w[i] % 2 == 0:
		E[u[i]].append(v[i])
		E[v[i]].append(u[i])
	else:
		E[u[i]].append(v[i] * (-1))
		E[v[i]].append(u[i] * (-1))

flg = [inf for _ in range(N+1)]
flg[0] = 0

def dfs(q):
	cp = q.pop()
	next = E[cp]

	for np in next:
		if flg[abs(np)] == inf:
			if np > 0:
				flg[abs(np)] = flg[cp]
			else:
				flg[abs(np)] = flg[cp] * (-1)
			q.append(abs(np))

	if len(q) == 0:
		return

	dfs(q)

flg[1] = 1
dfs([1])

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

Submission status: Accepted

Solution code:
import sys
from collections import deque
input=sys.stdin.readline

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

D=[-1 for _ in range(n+1)]
D[1]=0
L=deque()
L.append(1)

while L:
    p=L.popleft()
    for i in G[p]:
        if D[i[0]]==-1:
            D[i[0]]=D[p]+i[1]
            L.append(i[0])

for m in range(1,n+1):
    print(D[m]%2)

Submission status: Accepted

Solution code:
import collections
N = int(input())
Map = [[] for j in range(N+1)]

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

q = collections.deque()
q.append(1)
ans = [-1 for i in range(N+1)]
ans[1] = 0
while(q):
    v = q.popleft()
    for e,w in Map[v]:
        if ans[e] == -1:
            ans[e] = ans[v]+w
            q.append(e)
for i in range(1,N+1):
    print(ans[i]%2)