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:
n=int(input())
cost = [[] for _ in range(n)]
for _ in range(n-1):
    a, b, c = (int(x) for x in input().split())
    cost[a-1].append([b-1, c])
    cost[b-1].append([a-1, c])

dp = [0]*n

move = [0]
check = [-1]*n
check[0] = 0

while len(move):
    v = move.pop(0)
    for i, j in cost[v]:
        if check[i] == -1:
            dp[i] = dp[v] + j
            check[i] = 1
            move.append(i)
for i in dp:
    print(i%2)

Submission status: Accepted

Solution code:
import heapq as h

N=int(input())
u=[0 for i in range(0,N-1)]
v=[0 for i in range(0,N-1)]
w=[0 for i in range(0,N-1)]
for i in range(0,N-1):
    u[i],v[i],w[i]=map(int,input().split())
w=[w[i]%2 for i in range(0,N-1)]
hen=[[] for i in range(0,N+1)]
for i in range(0,N-1):
    hen[u[i]].append([v[i],w[i]])
    hen[v[i]].append([u[i],w[i]])
ans=[[0,0] for i in range(0,N+1)]
ans[1]=[0,1]
q=[]
q.append(1)
h.heapify(q)
sub=[]
h.heapify(sub)
while q!=[]:
    while q!=[]:
        x=h.heappop(q)
        if ans[x][0]==0:
            for p in hen[x]:
                s=p[0]
                t=p[1]
                if ans[s][1]==0:
                    if p[1]==0:
                        ans[s][0]=0
                    else:
                        ans[s][0]=1
                    h.heappush(sub,s)
                    ans[s][1]=1
        else:
            for p in  hen[x]:
                s=p[0]
                t=p[1]
                if ans[s][1]==0:
                    if p[1]==0:
                        ans[s][0]=1
                    else:
                        ans[s][0]=0
                    h.heappush(sub,s)
                    ans[s][1]=1
        if q==[]:
            q=sub
            sub=[]
            h.heapify(sub)
            break
ans[0]=100
ans.remove(100)
for i in range(0,N):
    print(ans[i][0])

Submission status: Accepted

Solution code:
from collections import defaultdict
from queue import deque
N = int(input())
colors = [None]*N
edges = defaultdict(list)
for i in range(N-1):
    u,v,w = map(int,input().split())
    edges[u-1].append((v-1, w))
    edges[v-1].append((u-1, w))
colors[0] = 0
q = deque([0])
while q:
    u = q.popleft()
    for v,w in edges[u]:
        if colors[v] != None:
            continue
        if edges[v] != []:
            q.append(v)
        if w % 2 == 0:
            colors[v] = colors[u]
        else:
            colors[v] = 1 ^ colors[u]
for c in colors:
    print(c)

Submission status: Accepted

Solution code:
import sys
def input():
    return sys.stdin.readline()[:-1]
sys.setrecursionlimit(200000)
N=int(input())
s=[[]for i in range(N)]
c=[None]*N
for i in range(N-1):
    u,v,w=map(int,input().split())
    s[v-1].append((u,w%2))
    s[u-1].append((v,w%2))
def mu(n,l,co):
    for i in l:
        if c[i[0]-1]==None:
            if co==i[1]%2:
                c[i[0]-1]=0
                mu(i,s[i[0]-1],0)
            else:
                c[i[0]-1]=1
                mu(i,s[i[0]-1],1)
mu(1,s[0],0)
print(*c,sep="\n")

Submission status: Accepted

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


# from collections import deque 
q = []
q.append([0,0])
used[0] = 0
# print(M)
while q:
    # print(q)
    e,c = q.pop()
    for i,d in M[e]:
        if used[i]==-1:
            C = (c+d)%2
            used[i] = C
            q.append([i,C])  
for i in used[:-1]:
    print(i)

Submission status: Accepted

Solution code:
N = int(input())
# dic = [[-1]*(N+1) for _ in range(N+1)]
M = [[] for _ in range(N+1)]
used = [-1]*(N+1) 
for i in range(N-1):
    u,v,w = map(int,input().split())
    M[u-1].append([v-1,w])
    M[v-1].append([u-1,w])


# from collections import deque 
q = []
q.append(0)
used[0] = 0
# print(M)
while q:
    # print(q)
    e = q.pop()
    for i,d in M[e]:
        if used[i]==-1:
            C = (used[e]+d)%2
            used[i] = C
            q.append(i)  
for i in used[:-1]:
    print(i)

Submission status: Accepted

Solution code:
from collections import defaultdict
import sys
sys.setrecursionlimit(1000000)

d = defaultdict(list)
cost = defaultdict(int)
N = int(input())

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

visited = [False]*(N+1)
color = [-1]*(N+1)
color[1] = 0

def dfs(x):
    visited[x]=True
    for y in d[x]:
        if visited[y]:continue
        c = cost[(x, y) if x<y else (y, x)]
        color[y] = color[x]^1 if c%2 else color[x]  
        dfs(y)

dfs(1)
print(*color[1:], sep="\n")

Submission status: Accepted

Solution code:
from collections import defaultdict
import sys
sys.setrecursionlimit(1000000)

d = defaultdict(list)
cost = defaultdict(int)
N = int(input())

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

visited = [False]*(N+1)
color = [-1]*(N+1)
color[1] = 0

def dfs(x):
    visited[x]=True
    for y in d[x]:
        if visited[y]:continue
        c = cost[(x, y) if x<y else (y, x)]
        color[y] = color[x]^1 if c%2 else color[x]  
        dfs(y)

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

Submission status: Accepted

Solution code:
from collections import defaultdict
import sys

sys.setrecursionlimit(1000000)

d = defaultdict(list)
cost = defaultdict(int)
N = int(input())

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

visited = [False]*(N+1)
color = [-1]*(N+1)

def dfs(x):
    visited[x]=True
    if color[x]==-1:
        color[x] = 0

    for y in d[x]:
        if visited[y]:
            continue
        
        c = cost[(x, y) if x<y else (y, x)]
        if c%2==0:
            color[y] = 0 if color[x]==0 else 1
        else:
            color[y] = 1 if color[x]==0 else 0
        dfs(y)

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

Submission status: Accepted

Solution code:
from collections import deque

n = int(input())
edges = [{} for i in range(n+1)]

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

colors = [-1]*(n+1)

d = deque()
d.append(1)
colors[1] = 0

while(len(d) > 0):
    now = d.pop()
    for key,val in edges[now].items():
        if(colors[key] == -1):
            colors[key] = (val + colors[now])%2
            d.append(key)

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

Submission status: Accepted

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

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

for tmp in l:
    link[tmp[0]-1].append([tmp[1]-1,tmp[2]])
    link[tmp[1]-1].append([tmp[0]-1,tmp[2]])

from collections import deque
Q = deque()
Q.append(0)

dis = [-1]*n
dis[0]=0

while Q:
    num=Q.popleft()
    for tmp in link[num]:
        if dis[tmp[0]] == -1:
            dis[tmp[0]] = dis[num]+tmp[1]
            Q.append(tmp[0])

for a in dis:
    print(a%2)

Submission status: Accepted

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


class Tree:
    WHITE = 0
    GRAY = 1
    BLACK = 2

    def __init__(self, adj):
        n = len(adj)
        self.adj = adj
        self.colors = [self.WHITE] * n
        self.depths = [-1] * n
        self.depth = 0

    def dfs(self, u):
        if self.colors[u] == self.BLACK:
            return

        self.colors[u] = self.GRAY
        self.depths[u] = self.depth

        for v, w in self.adj[u]:
            if self.colors[v] == self.WHITE:
                self.depth += w
                self.dfs(v)
                self.depth -= w

        self.colors[u] = self.BLACK


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

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

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

    tree = Tree(g)
    tree.dfs(0)
    ans = [x % 2 for x in tree.depths]
    print(*ans, sep="\n")

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:
  i = q.pop(0)
  for n, w in link[i]:
    if d[n] == -1:
      d[n] = d[i] + w
      q.append(n)
 
for i in d:
  print(i % 2)

Submission status: Accepted

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

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

q = deque([1])
visited = {1}
while len(q) > 0:
    now = q.popleft()
    visited.add(now)
    for v, w in tree[now]:
        if v in visited:
            pass
        else:
            q.append(v)
            if w % 2 == 0:
                color1[v] = color1[now]
                color2[v] = color2[now]
            else:
                color1[v] = int(not color1[now])
                color2[v] = int(not color2[now])

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

Submission status: Accepted

Solution code:
from collections import deque

N = int(input())

u = [None] * (N - 1)
v = [None] * (N - 1)
w = [None] * (N - 1)
for i in range(N - 1):
    uvw = input().split()
    u[i], v[i], w[i] = int(uvw[0]) - 1, int(uvw[1]) - 1, int(uvw[2])

# adjacency List + distance
# AL[i] = [(j, distance between i and j): j is a neighbor of i]
AL = [[] for _ in range(N)]

for i in range(N - 1):
    AL[u[i]].append((v[i], w[i] % 2))
    AL[v[i]].append((u[i], w[i] % 2))

color = [0] + [-1] * (N - 1) # vertex iの頂点の色 0/1
visited = [False] * N      # vertex iに訪問済みならTrue、まだならFalse
que = deque()   # 探索候補キュー
que.append(0) # vertex 0をキューに追加

while(len(que) > 0):
    current = que.popleft()
    visited[current] = True
    for next, dist in AL[current]:
        if not visited[next]:
            que.append(next)
            color[next] = (color[current] + dist) % 2

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

Submission status: Accepted

Solution code:
from collections import deque

N = int(input())

u = [None] * (N - 1)
v = [None] * (N - 1)
w = [None] * (N - 1)
for i in range(N - 1):
    uvw = input().split()
    u[i], v[i], w[i] = int(uvw[0]) - 1, int(uvw[1]) - 1, int(uvw[2])

# adjacency List + distance
# AL[i] = [(j, distance between i and j): j is a neighbor of i]
AL = [[] for _ in range(N)]

for i in range(N - 1):
    AL[u[i]].append((v[i], w[i]))
    AL[v[i]].append((u[i], w[i]))

color = [0] + [-1] * (N - 1) # vertex iの頂点の色 0/1
visited = [False] * N      # vertex iに訪問済みならTrue、まだならFalse
que = deque()   # 探索候補キュー
que.append(0) # vertex 0をキューに追加

while(len(que) > 0):
    current = que.popleft()
    visited[current] = True
    for next, dist in AL[current]:
        if not visited[next]:
            que.append(next)
            if dist % 2 == 0:  # 距離が偶数
                color[next] = color[current]
            else:
                color[next] = 1 - color[current]

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

Submission status: Accepted

Solution code:
# # ABC126D.py, ATC001A.py などを参照
import sys
sys.setrecursionlimit(1000000)
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])


# 各頂点までの距離をdfsで求める
depth = [-1] * N
depth[0] = 0


def dfs(edge, s):
    for v in edge[s]:
        if depth[v[0]] == -1:  # 未訪問なら更新する
            depth[v[0]] = depth[s] + v[1]
            dfs(edge, v[0])


dfs(edge, 0)
for d in depth:
    if d % 2 == 0:
        print(0)
    else:
        print(1)

Submission status: Accepted

Solution code:
from collections import deque
N = int(input())
graph = [[] * N for _ in range(N)]

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

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

while que:
    v = que[0]
    que.popleft()
    for i in range(len(graph[v])):
        nv = graph[v][i][0]
        d = graph[v][i][1]
        if dist[nv] != -1:
            continue
        dist[nv] = dist[v] + d
        que.append(nv)

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)
def main():
    N = int(input())
    V = [[] for _ in range(N)]
    for _ in range(N - 1):
        u, v, w = list(map(int, input().split()))
        V[u - 1].append((v - 1, w))
        V[v - 1].append((u - 1, w))

    R = [0] * N
    def color(n, c, f):
        R[n] = c
        for u, w in V[n]:
            if u == f:
                continue
            color(u, (c + w) & 1, n)
    color(0, 0, 0)
    print("\n".join(str(i) for i in R))

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())
  adj[u-1].append((w, v-1))
  adj[v-1].append((w, u-1))
paint = [None] * n
paint[0] = 0
stack = [0]
while stack:
  u = stack.pop()
  for w, v in adj[u]:
    if paint[v] is None:
      stack.append(v)
      paint[v] = (paint[u] + w) % 2
for p in paint:
  print(p)

Submission status: Accepted

Solution code:
def main():
    ii = lambda : int(input())
    mi = lambda : map(int,input().split())
    li = lambda : list(map(int,input().split()))
    n = ii()
    v = [[] for _ in range(n)]
    for i in range(n-1):
        u,vv,w = mi()
        v[u-1].append([vv -1,w % 2])
        v[vv-1].append([u -1,w % 2])
    flag = [0] * n
    flag[0] = 1
    ans = [-1] * n
    from collections import deque
    q = deque()
    q.append((0,0))
    ans[0] = 0
    while q:
        ima,ima_col = q.popleft()
        for lis in v[ima]:
            if flag[lis[0]] :continue
            flag[lis[0]] = 1
            if lis[1]:
                ans[lis[0]] = lis[1] - ima_col
                q.append((lis[0],lis[1] - ima_col))
            else:
                ans[lis[0]] = ima_col
                q.append((lis[0],ima_col))
    for i in range(n):
        print(ans[i])
main()

Submission status: Accepted

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

def dfs(v):
    check[v] = True
    for u, w in T[v]:
        if check[u]:
            continue
        dist[u] = dist[v] + w
        dfs(u)

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

dist = [0] * (N + 1)
check = [False] * (N + 1)
dfs(1)

print(*[d % 2 for d in dist[1:]], sep="\n")

Submission status: Accepted

Solution code:
from collections import deque
def main():
  N=int(input())
  G=[[] for i in range(N)]
  ans=[]
  for i in range(N-1):
    u,v,w=map(int,input().split())
    G[u-1].append([v-1,w%2])
    G[v-1].append([u-1,w%2])
  ans=[-1]*N
  finish=[0]*N
  q=deque([0])
  while q:
    now=q.pop()
    for i in G[now]:
      if finish[i[0]]==1:
        continue
      else:
        if i[1]%2==1:
          ans[i[0]]=-1*ans[now]
        else:
          ans[i[0]]=ans[now]
        finish[i[0]]=1
        q.append(i[0])
  for i in ans:
    print(i%2 if i == -1 else 0)#print(*ans)
main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(100000000)
n=int(input())
es=[[]for i in range(n)]
for i in range(n-1):
    u,v,w=map(int,input().split())
    es[u-1].append([v-1,w])
    es[v-1].append([u-1,w])
color = [0 for i in range(n)] # 頂点0とのパスが存在すればFalse, 存在しないならTrue と定義する
def dfs(v,c):
    color[v] = c
    for i in es[v]:
        if color[i[0]]==0:
            # print(v,i[0],c)
            if i[1]%2==1:
                dfs(i[0],-c)
            else:
                dfs(i[0],c)
dfs(0,1)
# print(color)
for i in color:
    if i==-1:
        print(0)
    else:
        print(1)

Submission status: Accepted

Solution code:
from collections import deque,defaultdict
n=int(input())
routes=[tuple(map(int,input().split())) for i in range(n-1)]

edges=defaultdict(list)
for v1,v2,dist in routes:
  edges[v1-1].append([v2-1,dist])
  edges[v2-1].append([v1-1,dist])
#print(edges)

ans=[0]*n
q=deque([0])
while q:
  v=q.popleft()
  #print(v)
  if ans[v]==0:
    color=[1,0]
  else:
    color=[0,1]
  #print(edges)
  for edge in edges[v]:
    v2=edge[0]
    dist=edge[1]
    edges[v2].remove([v,dist])
    q.append(v2)
    if dist%2==1:
      ans[v2]=color[0]
    else:
      ans[v2]=color[1]
      
print(*ans,sep='\n')

Submission status: Accepted

Solution code:
import sys
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())
    w%=2
    G[u].append((v,w))
    G[v].append((u,w))
ans=[-1]*(n+1)
#dfs?
stack=[1]
ans[1]=1
while stack:
    t=stack.pop()
    color_t=ans[t]
    for w in G[t]:
        ten,kyori=w
        if ans[ten]==-1:
            if kyori==0:
                ans[ten]=color_t
            else:
                ans[ten]=color_t+1
                ans[ten]%=2
            stack.append(ten)
print(*ans[1::], sep='\n')

Submission status: Accepted

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

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

    go = [True for _ in range(N)]
    length = [0 for _ in range(N)]
    go[0] = False
    q = deque([0])
    while q:
        now = q.pop()
        for fol,d in dist[now]:
            if go[fol]:
                length[fol] = length[now]+d
                go[fol] = False
                q.append(fol)

    for i in length:
        print(i%2)
        
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import deque

# BFS

def main():
    BLACK = 1
    WHITE = 0
    EDGE = 0
    WEIGHT = 1
    N = int(input())
    graph = [[] for i in range(N+1)]
    colors = [-1] * (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))

    q = deque()
    q.append(1)
    colors[1] = WHITE
    visited = [False] * (N + 1)
    visited[1] = True

    while len(q) != 0:
        n = q.popleft()

        for v, w in graph[n]:
            if visited[v]:
                continue

            if w % 2 == 0:
                colors[v] = colors[n]
            else:
                # print(~colors[n], colors[n])
                colors[v] = BLACK if colors[n] == WHITE else WHITE

            visited[v] = True
            q.append(v)

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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#根付き木テンプレ(ABC138-D)
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N = int(readline())
ABW = [list(map(int,readline().split())) for i in range(N-1)]

graph = [[] for _ in range(N+1)] #隣接リスト(重み付き)
for a,b,w in ABW:
    graph[a].append((b,w%2)) #重みは偶奇さえわかれば良い
    graph[b].append((a,w%2))

#親のノードに子を入れてくdfs
stack = [1]
parent = [0]*(N+1)
order = []
while stack:
    x = stack.pop()
    order.append(x)
    for i,j in graph[x]: #jは重みなのでとりあえず使わん
        if i == parent[x]:
            continue
        parent[i] = x
        stack.append(i)

#色のリストを作り、order順に入れてく
#この時、親方向に逆流しないように注意。
color = [-1]*(N+1)
color[1] = 0
for x in order: #親
    c = 0 if color[x] == -1 or color[x] == 0 else 1
    for y,w in graph[x]: #子
        if y == parent[x]: #逆流防止弁
            continue
        if w == 0:
            color[y] = c
        else:
            color[y] = 1 - c

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

Submission status: Accepted

Solution code:
import sys

n = int(sys.stdin.readline().rstrip())
graph = [[] for _ in range(n)]
for _ in range(n-1):
    u, v, w = map(int, sys.stdin.readline().split())
    graph[u-1].append((v - 1, w))
    graph[v-1].append((u - 1, w))

def coloring_tree(g, size):
    par = [None] * size
    stack = [(0, 0)]
    color = [None] * size
    color[0] = 0
    while stack:
        u, d = stack.pop()
        color[u] = d & 1
        for v, w in g[u]:
            if par[u] == v:
                continue
            par[v] = u
            stack.append((v, d + w))
    return color

def main():
    return coloring_tree(graph, n)
    
if __name__ == '__main__':
    ans = main()
    print(*ans, sep='\n')

Submission status: Accepted

Solution code:
from math import ceil,log2

def main():
    N = int(input())
    UVW = [list(map(int,input().split())) for _ in range(N - 1)]
    edge = [[] for _ in range(N + 1)]
    dis = {}
    for u,v,w in UVW:
        edge[u].append(v)
        edge[v].append(u)
        dis[(u,v)] = w
        dis[(v,u)] = w
    cnt = 0
    queue = [1]
    gone = {1:0}
    while cnt < N:
        node = queue[cnt]
        for e in edge[node]:
            if e not in gone:
                if dis[(node,e)]%2 == 1:
                    gone[e] = (gone[node] + 1)%2
                else:
                    gone[e] = gone[node]
                queue.append(e)
        cnt += 1
    for i in range(1,N + 1):
        print(gone[i])
    return
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import deque
n=int(input())
edge=[[] for i in range(n)]
if n==1:
  print(0)
  exit()
col=[-1 for i in range(n)]
for i in range(n-1):
  u,v,w=map(int,input().split())
  u-=1
  v-=1
  edge[u].append((v,w))
  edge[v].append((u,w))
def dfs(edge,col):
  stack=deque([0])
  col[0]=0
  while stack:
    x=stack.pop()
    for i,j in edge[x]:
      newx=i
      if col[i]==-1:
        col[newx]=(col[x]+j)%2
        stack.append(newx)
  return col
for i in range(n):
  print(dfs(edge,col)[i])

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(200000)

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

def dfs(v, p=-1, c=0):
    for i in range(len(to[v])):
        u, w=to[v][i]
        if p==u:
            continue
        color[u]=(c+w)%2
        dfs(u, v, color[u])

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(200000)

def dfs(v, p=-1, c=0):
  for i in range(len(to[v])):
    u, w=to[v][i]
    if u==p:
      continue
    color[u]=(c+w)%2
    dfs(u, v, color[u])
    
N=int(input())
uvw=[list(map(int, input().split())) for _ in range(N-1)]
to=[[] for _ in range(N)]
color=[0 for _ in range(N)]
for i in range(N-1):
  u, v, w=uvw[i]
  u-=1
  v-=1
  to[u].append([v, w%2])
  to[v].append([u, w%2])

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
from collections import defaultdict
n = int(input())
e = defaultdict(lambda: [])

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

col = [-1]*n
q = [0]
col[0] = 0
while len(q)>0:
    v = q.pop()
    for u,w in e[v]:
        if col[u]<0:
            if w%2==1:
                col[u] = (col[v]+1)%2
            else:
                col[u] = col[v]
            q.append(u)

print(*col)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(500*500)

def search(tree, now, pre, t, ans):
  nex_li = tree[now]
  for nex, w in nex_li:
    if pre == nex:
      continue
    t1 = t+w
    if t1%2 == 0:
      ans[nex] = 0
    else:
      ans[nex] = 1
    ans = search(tree, nex, now, t1, ans)
  return ans

def run():
  N = int(input())
  tree = {}
  for n in range(N-1):
    u, v, w = map(int, input().split())
    tree.setdefault(u, []).append((v, w%2))
    tree.setdefault(v, []).append((u, w%2))
  ans = [0]*(N+1)
  ans = search(tree, 1, -1, 0, ans)
  for a in ans[1:]:
    print(a)
  
  
if __name__ == '__main__':
    run()

Submission status: Accepted

Solution code:
from collections import deque

n = int(input())
ans = [0] * n
visited = [False] * n
G = [[] for _ in range(n)]

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

q = deque([])
q.append(0)
visited[0] = True

def dfs():
    while q:
        p = q.popleft()
        for u, w in G[p]:
            if visited[u]: continue
            else:
                ans[u] = (ans[p] + w) % 2
                visited[u] = True
                q.append(u)

dfs()

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

Submission status: Accepted

Solution code:
from collections import deque
 
n = int(input())
ans = [0] * n
visited = [False] * n
G = [[] for _ in range(n)]
 
for i in range(n-1):
    u, v, w = map(int, input().split())
    u -= 1
    v -= 1
    G[u].append([v, w])
    G[v].append([u, w])
 
q = deque([])
q.append(0)
visited[0] = True
 
def dfs():
    while q:
        p = q.pop()
        for u, w in G[p]:
            if visited[u]: continue
            else:
                ans[u] = (ans[p] + w) % 2
                visited[u] = True
                q.append(u)
 
dfs()
 
for i in range(n):
    print(ans[i])

Submission status: Accepted

Solution code:
from collections import deque

n = int(input())
ans = [0] * n
visited = [False] * n
G = [[] for _ in range(n)]

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

q = deque([])
q.append(0)
visited[0] = True

def dfs():
    while q:
        p = q.pop()
        for u, w in G[p]:
            if visited[u]: continue
            else:
                ans[u] = (ans[p] + w) % 2
                visited[u] = True
                q.append(u)

dfs()

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10000000)
INF = 1<<32


def solve(N: int, u: "List[int]", v: "List[int]", w: "List[int]"):
    colors = [-1] *(N+1)
    g = [[] for i in range(N+1)]
    for i in range(N-1):
        g[u[i]].append([v[i], w[i]])
        g[v[i]].append([u[i], w[i]])

    # print(g)

    from collections import deque
    d = deque()
    colors[1] = 0
    d.append(1)
    while len(d) > 0:
        # print("d:"+d)
        n = d.popleft()
        for V, W in g[n]:
            if colors[V] != -1:
                continue
            d.append(V)
            if W%2 == 0:
                colors[V] = colors[n]
            else:
                colors[V] = int(not colors[n])
    
    for i in range(1, N+1):
        print(colors[i])
            

    return



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:
import numpy as np


def calDistance_dfs(aList, d, node):
    stack = [node]
    d[node] = 0
    while len(stack) != 0:
        current = stack.pop()
        for v in aList[current]:
            if d[v[0]] == -1:
                stack.append(v[0])
                d[v[0]] = d[current]+v[1]


n = int(input())
adjacencyList = [[] for i in range(n)]
d = [-1] * n

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


d[0] = 0
calDistance_dfs(adjacencyList, d, 0)
for i in d:
    print(i % 2)

Submission status: Accepted

Solution code:
n = int(input())

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

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

visited = [0] * n
visited[0] = 1
ans = [0] * n
stack = [0]

while stack:
    v = stack.pop()
    for next, distance in edge[v]:
        if visited[next]: continue
        ans[next] = (ans[v] + distance) % 2
        visited[next] = 1
        stack.append(next)

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

Submission status: Accepted

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

n = int(input())
edges = [[] for _ in range(n+1)]
colors = [None] * (n+1)

for i in range(n-1):
    u, v, w = [int(x) for x in input().split()]
    if w & 1 == 0:
        edges[u].append((v, 0))
        edges[v].append((u, 0))
    else:
        edges[u].append((v, 1))
        edges[v].append((u, 1))

colors[1] = 0


def color(node, c):
    colors[node] = c
    for i, j in edges[node]:
        if colors[i] is None:
            new_color = (c + j)%2
            color(i, new_color)

color(1,1)

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

Submission status: Accepted

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

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

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

def journey(u, p, bit):
    ans[u] = bit
    for v, w in tree[u]:
        if v == p: continue
        if w % 2 == 0: journey(v, u, bit)
        else: journey(v, u, 1-bit)
    
journey(0, -1, 0)
[print(x) for x in ans]

Submission status: Accepted

Solution code:
import sys
N = int(input())
V = {}
if N == 1:
  print(0)
  exit(0)

# change limit for deep tree (recursion)
sys.setrecursionlimit(N)

# Vertice
for i in range(N-1):
  u,v,w = list(map(int, input().split()))
  u,v = u-1, v-1 #1-index -> 0-index
  if u not in V:
    V[u] = [[v,w]]
  else:
    V[u].append([v,w])
  if v not in V:
    V[v] = [[u,w]]
  else:
    V[v].append([u,w])
     
#print(V)
ANS = [-1] * N
visited = [False] * N

def dfs(pos):
  visited[pos] = True
  for x,w in V[pos]:
    if visited[x]:
      continue
    if w % 2 == 0:
      ANS[x] = ANS[pos]
    else:
      ANS[x] = 1 - ANS[pos]
    #print(pos,x,ANS)
    dfs(x)
  return

ANS[0] = 0
dfs(0)

for a in ANS:
  print(a)