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: Runtime Error

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

    def add_vertex(self, v):
        self.adjacency_dict[v] = []
    
    def add_edge(self, v1, v2, dist):
        self.adjacency_dict[v1].append([v2, dist])
        self.adjacency_dict[v2].append([v1, dist])
    
    def next_edges(self, v):
        return self.adjacency_dict[v]

    def __str__(self):
        return self.adjacency_dict.__str__()
      
N = int(input())
dists = [list(map(int, input().split())) for _ in range(N-1)]

graph = Graph()
for i in range(1, N+1):
    graph.add_vertex(i)
for v1, v2, dist in dists:
    graph.add_edge(v1, v2, dist)
    
def dfs(start, group):
    if visited[start] is not None:
        return
    visited[start] = group
    for v, dist in graph.next_edges(start):
        if dist % 2 == 0:
            dfs(v, group)
        else:
            dfs(v, 1-group)

visited = [None]*(N+1)
dfs(1, 0)

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

Submission status: Runtime Error

Solution code:
import sys

N = int(input())
G = [[] for i in range(N)]
temp = sys.stdin.readlines()
for line in temp:
    u, v, d = map(int, line.split())
    G[u-1].append([v-1, d])
    G[v-1].append([u-1, d])
    
def dfs(v, G, cur=0):
    # 色をメモ
    color[v] = cur
        
    # 隣接するノードの色を調べる
    for next_v in G[v]:
        # 隣接ノードが探索済みなら、色が正しいか確かめる
        if color[next_v[0]] != -1:
            continue
            
        # 隣接ノードが未探索なら、正しい色に更新して再帰的に探索
        if next_v[1] % 2 == 0:
            dfs(next_v[0], G, cur)
        else:
            dfs(next_v[0], G, 1-cur)

color = [-1 for i in range(N)]
dfs(0, G)
for i in range(N):
    print(color[i])

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.buffer.readline
#再帰回数の上限を変更
# sys.setrecursionlimit(10**9)

N = int(input())
# v = [list(map(int, input().split())) for _ in range(N-1)]

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

for i 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))

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

def dfs(x):
    for v, w in edge[x]:
        if color[v] == -1:
            color[v] = (w + color[x])%2
            dfs(v)



dfs(0)
print(*color, sep="\n")

Submission status: Runtime Error

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

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

for i 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))

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

def dfs(x):
    for v, w in edge[x]:
        if color[v] == -1:
            color[v] = (w + color[x])%2
            dfs(v)



dfs(0)
print(*color, sep="\n")

Submission status: Runtime Error

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

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

for i 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))

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

def dfs(x):
    for v, w in edge[x]:
        if color[v] == -1:
            color[v] = (w + color[x])%2
            dfs(v)



dfs(0)
print(color)

Submission status: Runtime Error

Solution code:
n=int(input())
edges=[[] for i in range(n)]
import sys
input=sys.stdin.buffer.readline
sys.setrecursionlimit(10**9)
for i in range(n-1):
    a,s,w=map(int,input().split())
    edges[a-1].append([s-1,w]);edges[s-1].append([a-1,w])
colors=[-1]*n
colors[0]=1
def dfs(now):
    for to,cost in edges[now]:
        if colors[to]==-1:
            colors[to]=(cost+colors[now])%2
            dfs(to)

dfs(0)
print(*colors,sep="\n")

Submission status: Runtime Error

Solution code:
n=int(input())
edges=[[] for i in range(n)]
import sys
input=sys.stdin.buffer.readline
sys.setrecursionlimit(10**7)
for i in range(n-1):
    a,s,w=map(int,input().split())
    edges[a-1].append([s-1,w]);edges[s-1].append([a-1,w])
colors=[-1]*n
colors[0]=1
def dfs(now):
    for to,cost in edges[now]:
        if colors[to]==-1:
            colors[to]=(cost+colors[now])%2
            dfs(to)

dfs(0)
print(*colors,sep="\n")

Submission status: Runtime Error

Solution code:
n=int(input())
edges=[[] for i in range(n)]
import sys

sys.setrecursionlimit(10**10)
for i in range(n-1):
    a,s,w=map(int,input().split())
    edges[a-1].append([s-1,w]);edges[s-1].append([a-1,w])
colors=[-1]*n
colors[0]=1
def dfs(now):
    for to,cost in edges[now]:
        if colors[to]==-1:
            colors[to]=(cost+colors[now])%2
            dfs(to)

dfs(0)
print(*colors,sep="\n")

Submission status: Runtime Error

Solution code:
n=int(input())
edges=[[] for i in range(n)]
import sys
input=sys.stdin.buffer.readline
sys.setrecursionlimit(10**7)
for i in range(n-1):
    a,s,w=map(int,input().split())
    edges[a-1].append([s-1,w]);edges[s-1].append([a-1,w])
colors=[-1]*n
colors[0]=1
def dfs(now):
    for to,cost in edges[now]:
        if colors[to]==-1:
            colors[to]=(cost+colors[now])%2
            dfs(to)

dfs(0)
print(*colors,sep="\n")

Submission status: Runtime Error

Solution code:
n=int(input())
edges=[[] for i in range(n)]
for i in range(n-1):
    a,s,w=map(int,input().split())
    edges[a-1].append([s-1,w]);edges[s-1].append([a-1,w])
colors=[-1]*n
colors[0]=1
def dfs(now):
    for to,cost in edges[now]:
        if colors[to]==-1:
            colors[to]=(cost+colors[now])%2
            dfs(to)

dfs(0)
print(*colors,sep="\n")

Submission status: Runtime Error

Solution code:
n = int(input())
if n == 1:
    print(1)
else:
    edge=[[] for _ in range(n)]
    for _ in range(n-1):
        u,v,w = map(int,input().split())
        edge[u-1].append((v-1,w%2))
        edge[v-1].append((u-1,w%2))

    color =[-1]*n
    def dfs(node,edge):
        for next_node,w in edge[node]:
            if color[next_node] != -1:
                continue
            if w == 1:
                color[next_node] = color[node]^1
            elif w == 0:
                color[next_node] = color[node]
            dfs(next_node,edge)
        
        
    color[0] = 0
    dfs(0,edge)
    print(*color,sep="\n")

Submission status: Runtime Error

Solution code:
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%2))
    edge[v-1].append((u-1,w%2))

color =[-1]*n
def dfs(node,edge):
    for next_node,w in edge[node]:
        if color[next_node] != -1:
            continue
        if w == 1:
            color[next_node] = color[node]^1
        elif w == 0:
            color[next_node] = color[node]
        dfs(next_node,edge)
        
        
color[0] = 0
dfs(0,edge)
print(*color,sep="\n")

Submission status: Runtime Error

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

color =[-1]*(n+1)
def dfs(node,edge):
    for next_node,w in edge[node]:
        if color[next_node] != -1:
            continue
        if w == 1:
            color[next_node] = color[node]^1
        else:
            color[next_node] = color[node]
        dfs(next_node,edge)
        
        
color[1] = 0
dfs(1,edge)
color = color[1:]
print(*color,sep="\n")

Submission status: Runtime Error

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

color =[-1]*(n+1)
def dfs(node,edge):
    for next_node,w in edge[node]:
        if color[next_node] != -1:
            continue
        if w == 1:
            color[next_node] = color[node]^1
        elif w == 0:
            color[next_node] = color[node]
        dfs(next_node,edge)
        
        
color[1] = 0
dfs(1,edge)
color = color[1:]
print(*color,sep="\n")

Submission status: Runtime Error

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

N=int(readline())
m=map(int,read().split())
UVW=zip(m,m,m)

graph =[[] for i in range(N+1)]
for u,v,w in UVW:
    graph[u].append((v,w))
    graph[v].append((u,w))
color=[0]*(N+1)

def dfs(cur,par,dist):
    color[cur]=dist
    for dst,w in graph[cur]:
        if (dst==par):
            continue
        dfs(dst,cur,dist^(w&1))
dfs(1,-1,0)
print('\n'.join(map(str,color[1:])))

Submission status: Runtime Error

Solution code:
n = int(input())
G = [[] for _ in range(n)]
for i in range(n-1):
  uvw = list(map(int, input().split()))
  u = uvw[0]-1
  v = uvw[1]-1
  w = uvw[2]
  G[u].append([v, w])
  G[v].append([u, w])
  
color = [-1]*n
def dfs(G, v, cur = 0):
  if color[v] == -1:
    
    color[v] = cur
    for next_v, w in G[v]:
     
      if color[next_v]==-1:
        if (w % 2 != 0):
          dfs(G, next_v, 1-cur)
        if (w% 2 == 0):
          dfs(G, next_v, cur)
        continue
      


        

for v in range(n):
  if color[v] != -1:
    continue
  else:
    dfs(G, v)


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

Submission status: Runtime Error

Solution code:
n    = int(input())
li   = [list(map(int,input().split())) for i in range(n-1)]
clr  = [0]*n
done = [0]*n
tmp  = 0

print(li)

for i in li:
  if i[0]>i[1]:
    tmp  = i[0]
    i[0] = i[1]
    i[1] = tmp
  i[2] %= 2

li.sort()

for i in li:
  if done[i[0]-1]==0 and done[i[1]-1]==0:
    if i[2]==1:
      i[1] = i[0]^1
    done[i[0]-1] = 1
    done[i[1]-1] = 1
  elif done[i[0]-1]==1 and done[i[1]-1]==0:
    if i[2]==1:
      i[1] = i[0]^1
    done[i[1]-1] = 1
  elif done[i[0]-1]==0 and done[i[1]-1]==1:
    if i[2]==1:
      i[0] = i[1]^1
    done[i[0]-1] = 1
  else:
    continue

for i in clr:
  print(i)

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
N=int(input())
ki=[[] for f in range(N)]
for i in range(N-1):
 u,v,w = map(int,input().split())
 ki[u-1].append([v-1,w%2])
 ki[v-1].append([u-1,w%2])
stack = [[0,0]]
check = [0]*N #チェック済みリスト
ans=[2]*N
ans[0]=0
while stack != [] :
 a=stack.pop()
 ne=a[0]
 if check[ne]==0:
  check[ne]=1
  for i in range(len(ki[ne])):
   if check[ki[ne][i][0]]==0:
    stack.append([ki[ne][i][0],(ki[ne]][i][1]+ans[ne])%2])
    ans[ki[ne][i][0]]=(ki[ne][i][1]+ans[ne])%2
for i in ans:
 print(i)

Submission status: Runtime Error

Solution code:
n = int(input())
graph = {i: [] for i in range(1, n + 1)}
for _ in range(n - 1):
    u, v, ww = map(int, input().split())
    graph[u].append([v,ww])
    graph[v].append([u,ww])
color = [-1] * n

def dfs(x):
    for sub in graph[x]:
        next = sub[0]
        lon = sub[1]
        if color[next - 1] != -1:
            continue
        if lon % 2 == 0:
            color[next - 1] = color[x - 1]
        else:
            if color[x-1] == 1:
                color[next - 1] = 0
            else:
                color[next - 1] = 1
        dfs(next)

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

Submission status: Runtime Error

Solution code:
n = int(input())

G = {}
for i in range(n):
    G.update({i: []})

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])

color = [-1 for i in range(n)]

def dfs(graph, v, c):
    color[v] = c
    
    for next_v in graph[v]:
        dis = next_v[1]
        if color[next_v[0]] != -1:
            continue
        
        if dis == 0:
            n_c = c
        elif dis == 1:
            n_c = 1 - c
        
        dfs(graph, next_v[0], n_c)

dfs(G, 0, 0)
[print(i) for i in color]

Submission status: Runtime Error

Solution code:
from collections import defaultdict
def solve():
    N = int(input())
    G = defaultdict(list)
    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))

    res = [0] * N

    dfs(0,-1,1,G,res)

    print(*res, sep='\n')
def dfs(v,p,c,G,res):
    res[v] = c
    for e in G[v]:
        if e[0] == p:
            continue
        if e[1] % 2 != 0:
            dfs(e[0], v, 1-c,G,res)
        else:
            dfs(e[0],v,c,G,res)
        
if __name__ == '__main__':
    solve()

Submission status: Runtime Error

Solution code:
from collections import defaultdict
def solve():
    N = int(input())
    G = defaultdict(list)
    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))

    res = [0] * N

    dfs(0,-1,1,G,res)

    print(*res, sep='\n')
def dfs(v,p,c,G,res):
    res[v] = c
    for e in G[v]:
        if e[0] == p:
            continue
        if e[1] % 2 == 0:
            dfs(e[0], v, 1-c,G,res)
        else:
            dfs(e[0],v,c,G,res)
        
if __name__ == '__main__':
    solve()

Submission status: Runtime Error

Solution code:
n = int(input())
graph = [[]for i in range(n)]
for i in range(n-1):
    pre = list(map(int,input().split()))
    graph[pre[0]-1].extend([pre[1]-1,pre[2]])
    graph[pre[1]-1].extend([pre[0]-1,pre[2]])
seen = [0 for i in range(n)]
color = [-1 for i in range(n)]

def DFS(x):
    if seen[x] == 1:
        return 0
    else:
        pass
    seen[x] = 1
    for i in range(len((graph[x]))//2):
        if graph[x][2*i+1] % 2 == 0:
            color[graph[x][2*i]] = color[x]
        else:
            color[graph[x][2*i]] = not color[x]

    for i in range(len((graph[x]))//2):
        DFS(graph[x][2*i])

color[0] = True
DFS(0)
for i in range(n):
    print(int(color[i]))

Submission status: Runtime Error

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

nbors = [[] for _ in range(N+1)]
for uvw in UVW:
    u,v,w = uvw[0], uvw[1], uvw[2]
    nbors[u].append((v, w))
    nbors[v].append((u, w))

dist = [-1] * (N+1)
dist[1] = 0
def dfs(now, nxt, w):
    if dist[nxt] >= 0:
        return
    dist[nxt] = dist[now] + w
    for nbor in nbors[nxt]:
        nxt2, w = nbor[0], nbor[1]
        dfs(nxt, nxt2, w)

for nbor in nbors[1]:
    nxt, w = nbor[0], nbor[1]
    dfs(1, nxt, w)

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

Submission status: Runtime Error

Solution code:
import sys
N = int(sys.stdin.readline())
edges = [list(map(int,sys.stdin.readline().split())) for _ in range(N - 1)]
A = [[] for _ in range(N + 1)]
 
for edge in edges:
    A[edge[0]].append([edge[1],edge[2]])
    A[edge[1]].append([edge[0],edge[2]])
 
depth = [-1] * (N + 1)
depth[1] = 0
 
def dfs(A,s):
    for v in A[s]:
        if depth[v[0]] == -1:
            depth[v[0]] = depth[s] + v[1]
            dfs(A,v[0])    
dfs(A,1)
for d in depth[1:]:
    if d % 2 == 0:
        print(0)
    else:
        print(1)

Submission status: Runtime Error

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

    N = int(input())
    edges = [[] for _ in range(N+1)]
    for _ in range(N-1):
        u,v,w = map(int,input().split())
        edges[u].append((v,w))
        edges[v].append((u,w))
    
    colors = [-1]*(N+1)
    que = [(0,1)]
    heapq.heapify(que)
    while que:
        c,n = heapq.heappop(que)
        if colors[n] == -1:
            colors[n] = c
            for nx,w in edges[n]:
                if w%2==0:
                    nxC = c
                else:
                    nxC = (c+1)%2
                heapq.heappush((nxC,nx))

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

main()

Submission status: Runtime Error

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

ans = [0]*n
def dfs(u,p=-1,c=0):
    for v,w in T[u]:
        if v == p: continue
        if w: c = (c+1)%2
        ans[v] = c
        dfs(v,u,c)
dfs(0)

print("\n".join(map(str,ans)))

Submission status: Runtime Error

Solution code:
N = int(input())
edg = [list(map(int,input().split())) for _ in range(N-1)]
vtx = [[] for _ in range(N)]
for e in edg:
    v1,v2,w = e
    vtx[v1-1].append([v2-1,w])
    vtx[v2-1].append([v1-1,w])

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

def dfs(vtx,i=0,p=-1,c=1): # vertex and its parent
    colors[i] = c
    for v,w in vtx[i]:
        if v == p:
            continue
        dfs(vtx,v,i,1-c if w%2 != 0 else c)
dfs(vtx)

for v in colors:
    print(v)

Submission status: Runtime Error

Solution code:
N = int(input())
edg = [list(map(int,input().split())) for _ in range(N-1)]
vtx = [[] for _ in range(N)]
for e in edg:
    v1,v2,w = e
    vtx[v1-1].append([v2-1,w])
    vtx[v2-1].append([v1-1,w])

colors = [1 for _ in range(N)]
def dfs(vtx,i=0,p=-1): # vertex and its parent
    for c,w in vtx[i]:
        if c == p:
            continue
        colors[c] = 1 - colors[i] if w%2 != 0 else colors[i]
        dfs(vtx,c,i)
dfs(vtx)

for v in colors:
    print(v)

Submission status: Runtime Error

Solution code:
n=int(input())
node=[-1 for i in range(n)]
g=[[] for i in range(n)]
def color(par,i,ini):
  if node[i]>-1:
    return
  else:
    if par==-1:
      node[i]=0
    else:
      node[i]=node[par]^ini
  for j in range(len(g[i])):
    color(i,g[i][j][0],g[i][j][1])
  return
for i in range(n-1):
  u,v,w=map(int,input().split())
  u-=1
  v-=1
  w%=2
  g[u].append([v,w])
  g[v].append([u,w])
color(-1,0,0)
for i in range(n):
  if node[i]==-1:
    node[i]=0
  print(node[i])

Submission status: Runtime Error

Solution code:
n=int(input())
node=[-1 for i in range(n)]
g=[[] for i in range(n)]
def color(par,i,ini):
  if node[i]>-1:
    return
  else:
    if par==-1:
      node[i]=0
    else:
      node[i]=abs(node[par]-ini)
  for j in range(len(g[i])):
    color(i,g[i][j][0],g[i][j][1])
  return
for i in range(n-1):
  u,v,w=map(int,input().split())
  u-=1
  v-=1
  w%=2
  g[u].append([v,w])
  g[v].append([u,w])
color(-1,0,0)
for i in range(n):
  if node[i]==-1:
    node[i]=0
  print(node[i])

Submission status: Runtime Error

Solution code:
n=int(input())
node=[-1 for i in range(n)]
g=[[] for i in range(n)]
def color(par,i,ini):
  if node[i]>-1:
    return
  else:
    if par==-1:
      node[i]=0
    else:
      node[i]=abs(node[par]-ini)
  for j in range(len(g[i])):
    color(i,g[i][j][0],g[i][j][1])
  return
for i in range(n-1):
  u,v,w=map(int,input().split())
  u-=1
  v-=1
  w%=2
  g[u].append([v,w])
  g[v].append([u,w])
for i in range(n):
  color(-1,i,0)
for i in range(n):
  print(node[i])

Submission status: Runtime Error

Solution code:
n=int(input())
node=[-1 for i in range(n)]
g=[[]for i in range(n)]
def color(par,i,ini):
  if node[i]>-1:
    return
  else:
    if par==-1:
      node[i]=0
    else:
      node[i]=abs(node[par]-ini)
    for j in range(len(g[i])):
      color(i,g[i][j][0],g[i][j][1])
for i in range(n-1):
  u,v,w=map(int,input().split())
  u-=1
  v-=1
  w%=2
  g[u].append([v,w])
  g[v].append([u,w])

for i in range(n):
  color(-1,i,0)
for i in range(n):
  if node[i]==-1:
    node[i]=0
  print(node[i])

Submission status: Runtime Error

Solution code:
n=int(input())
node=[0 for i in range(n)]
chil=[[] for i in range(n)]
change=[True for i in range(n)]
def renew(i):
  if chil[i]==[]:
    node[i]=abs(node[i]-1)
  else:
    for j in chil[i]:
      if change[j]:
        node[j]=abs(node[j]-1)
        change[j]=False
        renew(j)
  return
for i in range(n-1):
  u,v,w=map(int,input().split())
  u-=1
  v-=1
  t=w%2
  if t:
    if node[u]==node[v]:
      renew(v)
    else:
      pass
  else:
    if node[u]!=node[v]:
      renew(v)
    else:
      pass
  chil[u].append(v)
  chil[v].append(u)
  change=[True for i in range(n)]
for i in node:
  print(i)

Submission status: Runtime Error

Solution code:
def dfs(g: {}, v: int, seen: [], current_color: int):
    seen[v] = current_color
    for (next_v, next_w) in g[v]:
        # next_v が探索済だったらスルー
        if seen[next_v] != -1:
            if current_color == seen[next_v] and next_w % 2 == 1:
                return False
            elif current_color != seen[next_v] and next_w % 2 == 0:
                return False
            continue
        next_color = current_color if next_w % 2 == 0 else 1 - current_color
        # 再帰的に探索
        return dfs(g, next_v, seen, next_color)
    return True


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

    g = {}
    for i in range(n-1):
        u, v, w = map(int, input().split())
        dic_a = g.setdefault(u-1, [])
        dic_a.append((v-1, w))
        dic_b = g.setdefault(v-1, [])
        dic_b.append((u-1, w))
    # -1:not clear, 0:white, 1:black
    seen = [-1] * n

    is_bipartite = True
    for i in range(n):
        if seen[i] != -1:
            continue
        if not dfs(g, i, seen, 0):
            is_bipartite = False
            break

    if is_bipartite:
        for i in range(n):
            print(seen[i])
    else:
        print("is not bipartite")

main()

Submission status: Runtime Error

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

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

print(edges)
# Aというリストに対応する辺とその距離を収納する。
A = [[] for _ in range(N+1)]
for edge in edges:
    A[edge[0]].append([edge[1], edge[2]])
    A[edge[1]].append([edge[0], edge[2]])

# 頂点1からの距離を記録するリスト
depth = [-1] * (N+1)
depth[0] = 0

# sという点から他の点への距離を出す再帰関数
def dfs(A, s):
    for v in A[s]:
        if depth[v[0]] == -1:
            depth[v[0]] == depth[s] + v[1]
            dfs(A, v[0])

# 1からの距離
dfs(A, 1)
for d in depth[1:]:
    if d % 2 == 0:
        print(0)
    else:
        print(1)

Submission status: Runtime Error

Solution code:
import sys
from math import gcd
def input(): return sys.stdin.readline().strip()


def main():
    N = int(input())
    repn = [[] for _ in range(N)]
    for _ in range(N - 1):
        u, v, w = map(int, input().split())
        repn[u - 1].append((v - 1, w))
        repn[v - 1].append((u - 1, w))
    
    """
    Greedyに隣接する頂点ごとに色を塗っていけばよい
    """

    color = [-1] * N
    color[0] = 0
    q = [0]
    while q:
        v = q.pop()
        for u, w in repn[v]:
            if color[u] != -1:
                continue
            if w % 2 == 0:
                color[u] = color[v]
            else:
                color[u] = (1 + color[v]) % 2
            q.append(u)
    for ans in color:
        print(ans)


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
N = int(input())  #頂点数
tree = [[] for _ in range(N)]
dic = {}
for i in range(N-1):
    u, v, w = map(int, input().split())
    if u > v:
        u, v = v, u
    tree[u-1].append(v-1)
    tree[v-1].append(u-1)
    dic[(u-1, v-1)] = w

#black:1, white:0, none:-1
ans = [-1]*N
ans[0] = 0
flag = [False]*N

def dfs(i):
    flag[i] = True
    for j in tree[i]:
        if flag[j]:
            continue
        x = i
        y = j
        if x > y:
            x, y = y, x
        if dic[(x, y)] % 2 == 0:
            ans[j] = ans[i]
        else:
            if ans[i] == 0:
                ans[j] = 1
            else:
                ans[j] = 0
        if not(flag[j]):
            dfs(j)
            

dfs(0)

#print(tree)
#print(dic)
#print(flag)
for answer in ans:
    print(answer)

Submission status: Runtime Error

Solution code:
N = int(input())  #頂点数
tree = [[] for _ in range(N)]
dic = {}
for i in range(N-1):
    u, v, w = map(int, input().split())
    if u > v:
        u, v = v, u
    tree[u-1].append(v-1)
    tree[v-1].append(u-1)
    dic[(u-1, v-1)] = w
ans = [-1]*N
ans[0] = 0
flag = [False]*N
flag[0] = True
#black:1, white:0, none:-1

def dfs(i):
    flag[i] = True
    for j in tree[i]:
        if ans[j] != -1:
            continue
        x = i
        y = j
        if x > y:
            x, y = y, x
        if dic[(x, y)] % 2 == 0:
            if ans[i] == -1:
                ans[i] = 0
            ans[j] = 0
        else:
            if ans[i] == -1:
                ans[i] = 1
            ans[j] = 1
        if not(flag[j]):
            dfs(j)
            

dfs(0)

#print(tree)
#print(dic)
#print(flag)
for answer in ans:
    print(answer)

Submission status: Runtime Error

Solution code:
#include <iostream>
#include<string>
#include<cstring>
#include <cstdio>
#include<utility>
#include<algorithm>
#include<vector>
#include<cmath>
#include<map>
#include<bitset>
#include<queue>
#include<stack>
#include<set>
#include <limits>
#include <climits>
#include <numeric>
#include <cassert>
#include <algorithm>
#include <functional>
using namespace std;
typedef long long ll;
typedef vector<int>VI;
typedef pair<int,int>P;
typedef pair<double,double>P_D;
#define PI 3.1415926535897932384626433832795
#define rep(i, n) for (int i = 0; i < (int)n; i++)
#define reprev(i, n) for (int i = (int)n - 1; i >= 0; i--)
#define ALL(a)  (a).begin(),(a).end()
#define C_MAX(a, b) ((a)>(b)?(a):(b))
#define fi first
#define se second
#define MAX 100100//5
#define MAX_N 200100
#define MAX_B 1001001//6
#define MAX_S 10010010//7
#define SENTINEL 2000000000//9
#define NIL -1
#define MOD 1000000007
#define INF 1 << 29
#define INFTY 1000000000000000000LL
#define MAX_INT INT_MAX
using Graph=vector<vector<P> >;
//ツリー探索dfs
/*
void tree_dfs(const Graph &G,int v,int p){
    for(auto nv:G[v]){
        if(nv==p)continue;
        tree_dfs(G,nv,v);
    }
}
*/
vector<int>color;
void dfs(const Graph &G,int v,int p,int c){
    color[v]=c;
    for(auto e:G[v]){
        if(e.fi==p)continue;
        if(e.se&1)dfs(G,e.fi,v,1-c);
        else dfs(G,e.fi,v,c);
    }
}
int main(){
    int n;cin>>n;
    Graph G(n);
    color.assign(n,0);
    rep(i,n-1){
        int u,v,w;cin>>u>>v>>w;
        u--;v--;
        G[u].push_back(P(v,w));
        G[v].push_back(P(u,w));
    }
    dfs(G,0,-1,1);
    for(auto v:color)cout<<v<<endl;

}

Submission status: Runtime Error

Solution code:
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] += [[v, w]]
  graph[v] += [[u, w]]

color = [-1]*N 
def dfs(v, c):
  color[v] = c
  for next_v, w in graph[v]:
    if color[next_v] == c and w % 2 != 0:
      return 
    if color[next_v] == -1 and w % 2 == 0:
      dfs(next_v, c)# == False:
      #return False
    if color[next_v] == -1 and w % 2 != 0:
      dfs(next_v, abs(1-c)) #== False:
      #return False
  return True

dfs(0, 0)
for c in color:
  print(c)

Submission status: Runtime Error

Solution code:
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] += [[v, w]]
  graph[v] += [[u, w]]

color = [-1]*N 
def dfs(v, c):
  color[v] = c
  for next_v, w in graph[v]:
    if color[next_v] == c and w % 2 != 0:
      return False
    if color[next_v] == -1 and w % 2 == 0 and dfs(next_v, c) == False:
      return False
    if color[next_v] == -1 and w % 2 != 0 and dfs(next_v, abs(1-c)) == False:
      return False
  return True

dfs(0, 0)
for c in color:
  print(c)

Submission status: Runtime Error

Solution code:
def dfs(G,v,p):
    for nv,nw in G[v]:
        if(nv==p):
            continue
        if(nw%2==0):
            color[nv]=color[v]
        else:
            color[nv]=int(not color[v])
        dfs(G,nv,v)
N=int(input())
G=[[] for i in range(N)]
color=[-1]*N
for i in range(N-1):
    u,v,w=map(int,input().split())
    u,v=u-1,v-1
    G[u].append((v,w))
    G[v].append((u,w))
color[0]=0
dfs(G,0,-1)
print(*color,sep='\n')

Submission status: Runtime Error

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

color = [None] * N


def dfs(node, parent, col):
    if color[node] is not None:
        return
    color[node] = col
    for k in en[node]:
        if k != parent:
            dfs(k, node, col)
    for k in on[node]:
        if k != parent:
            dfs(k, node, (col + 1) % 2)


dfs(0, -1, 0)
print(*color, sep="\n")

Submission status: Runtime Error

Solution code:
N=int(input())
E=[]
for i in range(N-1):
  u,v,w=map(int,input().split())
  E.append([u,v,w%2])
par=[0]*(N+1)
dist=[0]*(N+1)
for u,v,w in E:
  if par[u]==0 and par[v]==0:
    par[u]=-1
    par[v]=u
    dist[v]^=w
  elif par[u]==-1:
    par[v]=u
    dist[v]^=w
  elif par[v]==-1:
    par[u]=v
    dist[u]^=w
  elif par[u]==0:
    par[u]=v
    dist[u]^=dist[par[u]]^w
  elif par[v]==0:
    par[v]=u
    dist[v]^=dist[par[v]]^w
for i in range(1,N+1):
  print(dist[i])
    else:
      f[UVW[i][1]]=1-f[UVW[i][0]]
for i in range(1,N+1):
  if f[i]==-1:
    print(0)
  else:
    print(f[i])

Submission status: Runtime Error

Solution code:
 D - Even Relation

from collections import deque

n = int(input())

# adjacency list
alist = [[] for _ in range(n)]

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

#print(alist)

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

q = deque()
q.append(0)

while len(q)>0:
    node = q.popleft()
    for i, j in alist[node]:
        if dlist[i]<0:
            q.append(i)
            dlist[i] = j
        else:
            continue

'''
def dfs(node, par, dist):
    dlist[node] = dist%2
    for i, j in alist[node]:
        if i==par:
            continue
        else:
            dfs(i, node, dist+j)
dfs(0,0,0)
'''

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

Submission status: Runtime Error

Solution code:
# D - Even Relation

import sys
sys.setrecursionlimit = 10**9

n = int(input())

# adjacency list
alist = [[] for _ in range(n)]

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

#print(alist)

dlist = [-1] * n

def dfs(node, par, dist):
    dlist[node] = dist%2
    for i, j in alist[node]:
        if i==par:
            continue
        else:
            dfs(i, node, dist+j)

dfs(0,0,0)

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

Submission status: Runtime Error

Solution code:
# D - Even Relation

import sys
sys.setrecursionlimit = 10**6

n = int(input())

# adjacency list
alist = [[] for _ in range(n)]

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

#print(alist)

dlist = [-1] * n

def dfs(node, par, dist):
    dlist[node] = dist%2
    for i, j in alist[node]:
        if i==par:
            continue
        else:
            dfs(i, node, dist+j)

dfs(0,0,0)

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