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:
import sys
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def II(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def SI(): return input()
YN = lambda b: print('YES') if b else print('NO')
yn = lambda b: print('Yes') if b else print('No')

import numpy as np

N = II()
u_li = []
v_li = []
w_li = []
for i in range(N-1):
    u, v, w = LI()
    u_li.append(u)
    v_li.append(v)
    w_li.append(w)


# 辺のリストを作成。
max_node = max(max(u_li), max(v_li))
edges = np.zeros((max_node+1, max_node+1))
for i in range(N-1):
    u, v = (u_li[i], v_li[i]) if u_li[i] < v_li[i] else (v_li[i], u_li[i])
    edges[u,v] = w_li[i]

# 連結リストを作成
neighbor = [[] for i in range(max_node+1)]
for i in range(N-1):
    neighbor[u_li[i]].append(v_li[i])
    neighbor[v_li[i]].append(u_li[i])

# 深さ優先探索をしつつ色を塗っていく。
from collections import deque
def depth_first(neighbor, start):
    visited, stack = [], deque()
    stack.append(start)
    result = [None, 0] + [None]*(N-1)
    while len(stack) > 0:
        next_node = stack.pop()
        if next_node in visited: continue
        visited.append(next_node)
        for nei in neighbor[next_node]:
            if result[nei] is not None: continue
            u, v = (nei, next_node) if nei < next_node else (next_node, nei)
            if edges[u,v]%2 == 0:
                result[nei] = result[next_node]
            else:
                result[nei] = (result[next_node]+1)%2
            stack.append(nei)
    return result

colors = depth_first(neighbor, 1)

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

Submission status: Runtime Error

Solution code:
import sys
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def II(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def SI(): return input()
YN = lambda b: print('YES') if b else print('NO')
yn = lambda b: print('Yes') if b else print('No')

import numpy as np

N = II()
u_li = []
v_li = []
w_li = []
for i in range(N-1):
    u, v, w = LI()
    u_li.append(u)
    v_li.append(v)
    w_li.append(w)


# 辺のリストを作成。
max_node = max(max(u_li), max(v_li))
edges = np.zeros((max_node+1, max_node+1))
for i in range(N-1):
    u, v = (u_li[i], v_li[i]) if u_li[i] < v_li[i] else (v_li[i], u_li[i])
    edges[u,v] = w_li[i]

# 連結リストを作成
neighbor = [[] for i in range(max_node+1)]
for i in range(N-1):
    neighbor[u_li[i]].append(v_li[i])
    neighbor[v_li[i]].append(u_li[i])
print(neighbor)

# 深さ優先探索をしつつ色を塗っていく。
from collections import deque
def depth_first(neighbor, start):
    visited, stack = [], deque()
    stack.append(start)
    result = [None, 0] + [None]*(N-1)
    while len(stack) > 0:
        next_node = stack.pop()
        if next_node in visited: continue
        visited.append(next_node)
        for nei in neighbor[next_node]:
            if result[nei] is not None: continue
            u, v = (nei, next_node) if nei < next_node else (next_node, nei)
            if edges[u,v]%2 == 0:
                result[nei] = result[next_node]
            else:
                result[nei] = (result[next_node]+1)%2
            stack.append(nei)
    return result

colors = depth_first(neighbor, 1)

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

Submission status: Runtime Error

Solution code:
def func(num,pr):
  global l,ans

  if len(l[num])!=0:
    for z in l[num]:
      if z[0]==pr:
        continue

      if pr==-1:
        ans[z[0]]=z[1]
      else:
        ans[z[0]]=ans[pr]+z[1]
      func(z[0],num)

N=int(input())
l=[ [] for z in range(N)]
ans=[0]*N


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

func(0,-1)

for z in ans:
  if z%2==0:
    print(1)
  else:
    print(0)

Submission status: Runtime Error

Solution code:
from collections import defaultdict
N =int( input())
col_nodes = defaultdict(set)
node_col = {}
col = 1
for _ in range(N - 1):
    u, v, w = map(int, input().split())
    u_col, v_col = node_col.get(u, 0), node_col.get(v, 0)
    if (0 in [u_col, v_col]) and (u_col or v_col):
        if u_col == 0:
            node_col[u] = v_col * [1, -1][w % 2]
            col_nodes[v_col] = col_nodes[v_col] | {u}
        else:
            node_col[v] = u_col * [1, -1][w % 2]
            col_nodes[u_col] = col_nodes[u_col] | {v}
        continue
    col_ = col * [1, -1][w % 2]
    node_col[u] = col
    node_col[v] = col_
    if u_col and v_col:
        col_nodes[col] = col_nodes[col] | col_nodes.pop(u_col)
        col_nodes[col_] = col_nodes[col_] | col_nodes.pop(v_col)
        continue
    col_nodes[col] =  col_nodes[col] | {u}
    col_nodes[col_] = col_nodes[col_] | {v}
    col += 1
        
for n in range(1, N + 1):
    print([0, 1][node_col[n] > 0])

Submission status: Runtime Error

Solution code:
n = int(input())
A = [0]*n
for i in range(n):
  u,v,w = map(int, input().split())
  if w % 2 == 0:
    A[u-1] = 1
    A[v-1] = 1
    
for a in A:
  print(a)

Submission status: Runtime Error

Solution code:
import numpy as np
N = int(input())
uvw = []
for i in range(N-1):
    u,v,w = map(int,input().split())
    uvw.append([u,v,w])

uvw = np.array(uvw)
uvw = uvw[np.argsort(uvw[:,0])]

# 初期の木の根とランクを設定（初めはみんな根なのでpar[i]=i）
par = [0 for i in range(N)]
dist = [0 for i in range(N)]
rank = [0 for i in range(N)]
for n in range(N):
    par[n] = n

# 木の根を探索する関数
# 根が自身でない場合は再帰的にたどる
# x,yが同じ集合に属するかの判定はroot(par[x])==root(par[y])か否か
def root(x):
    if par[x] == x:
        return x,d
    else:
        d += dist[]
        par[x], = root(par[x])
        return par[x],d

# 繋げる操作を指定された時に動かす関数
def unite(u,v,w):
    x = par[u]
    y = par[v]
    # rankが高い方に低い方を繋げる
    if rank[x] < rank[y]:
        par[x] = y
        dist[u] += w+dist[v]
    else:
        par[y] = x
        dist[v] += w+dist[u]
        # 同じだった場合xのランクが一つ増える扱いになる
        if rank[x] == rank[y]:
            rank[x] += 1

# 実際にクエリを受け取って動かす
for i in range(N-1):
    u,v,w = uvw[i,0],uvw[i,1],uvw[i,2]
    u = u-1
    v = v-1
    unite(u,v,w)

for i in range(N):
    ,d = root(i)
    if d % 2 == 0:
        print(0)
    else:
        print(1)

Submission status: Runtime Error

Solution code:
import pandas as pd

N = int(input())

u = [0] * (N-1)
v = [0] * (N-1)
w = [0] * (N-1)
ans = [0] * N

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

df = pd.DataFrame({'u': u, 'v': v, 'w': w})
df_sorted = df.sort_values(['u', 'v'])

u = df_sorted['u'].values
v = df_sorted['v'].values
w = df_sorted['w'].values

for i in range(N-1):
    if w[i] % 2 == 1:
        if ans[int(u[i]-1)] == 0:
            ans[int(v[i]-1)] = 1
        elif ans[int(u[i]-1)] == 1:
            ans[int(v[i]-1)] = 0
    elif w[i] % 2 == 0:
        if ans[int(u[i]-1)] == 0:
            ans[int(v[i]-1)] = 0
        elif ans[int(u[i]-1)] == 1:
            ans[int(v[i]-1)] = 1

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

Submission status: Runtime Error

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

uvw = np.array(uvw)
uvw = uvw[np.argsort(uvw[:,0])]

# 初期の木の根とランクを設定（初めはみんな根なのでpar[i]=i）
par = [0 for i in range(N)]
dist = [0 for i in range(N)]
rank = [0 for i in range(N)]
for n in range(N):
    par[n] = n

# 木の根を探索する関数
# 根が自身でない場合は再帰的にたどる
# x,yが同じ集合に属するかの判定はroot(par[x])==root(par[y])か否か
def root(x):
    if par[x] == x:
        return x
    else:
        par[x] = root(par[x])
        return par[x]

# 繋げる操作を指定された時に動かす関数
def unite(u,v,w):
    x = par[u]
    y = par[v]
    # rankが高い方に低い方を繋げる
    if rank[x] < rank[y]:
        par[x] = y
        dist[u] += w+dist[v]
    else:
        par[y] = x
        dist[v] += w+dist[u]
        # 同じだった場合xのランクが一つ増える扱いになる
        if rank[x] == rank[y]:
            rank[x] += 1

# 実際にクエリを受け取って動かす
for i in range(N-1):
    u,v,w = uvw[i,0],uvw[i,1],uvw[i,2]
    u = u-1
    v = v-1
    unite(u,v,w)

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

Submission status: Runtime Error

Solution code:
n = int(input())
v = [list(map(int,input().split())) for _ in range(n-1)]
g = {}
for a,b,w in v:
    if a not in g:
        g[a] = []
    g[a].append([b,w])
from collections import deque
queue = deque([[1,0]])
b = deque()
done = set([])
while queue:
    q,d = queue.popleft()
    if d%2==1:
        b.appendleft(q)
    done |= set([q])
    for new_q in g[q]:
        v_,d_ = new_q
        if v_ not in done:
            queue.appendleft([v_,d+d_])
for i in range(1,n+1):
    if i in b:
        print(1)
    else:
        print(0)

Submission status: Runtime Error

Solution code:
n = int(input())
uvw = [tuple(int(x) for x in input().split()) for _ in range(n-1)]

c = [-1] * n

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

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

def f(p):
    count = 0
    for x, w in r[p]:
        if c[x] == -1:
            if w % 2 == 0:
                c[x] = c[p]
                f(x)
            else:
                c[x] = (c[p] + 1) % 2
                f(x)
            count += 1
    #print(count)

c[0] = 0
f(0)

for x in c:
    print(x)

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
import sys

sys.setrecursionlimit(10000)
G = []
R = []

def dfs(v, p, c):
    R[v] = c
    for nv,w in G[v].items():
        if nv == p:
            continue

        nc = c
        if w % 2 == 1:
            nc = 1 - c

        dfs(nv,v,nc)
        

def solve(N: int, U: "List[int]", V: "List[int]", W: "List[int]"):
    global G
    global R
    G = [{} for i in range(N) ]
    R = [2 for i in range(N)]

    for u,v,w in zip(U,V,W):
        G[u-1][v-1] = w
        G[v-1][u-1] = w


    dfs(0,-1,0)

    for r in R:
        print(r)

    return


# Generated by 1.1.4 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: Runtime Error

Solution code:
#!/usr/bin/env python3
import sys

sys.setrecursionlimit(10000)

def dfs(v, p, c, G, R):
    R[v] = c
    for nv,w in G[v].items():
        if nv == p:
            continue

        nc = c
        if w % 2 == 1:
            nc = 1 - c

        dfs(nv,v,nc,G,R)
        

def solve(N: int, U: "List[int]", V: "List[int]", W: "List[int]"):

    G = [{} for i in range(N) ]
    for u,v,w in zip(U,V,W):
        G[u-1][v-1] = w
        G[v-1][u-1] = w


    R = [2 for i in range(N)]
    dfs(0,-1,0,G,R)

    for r in R:
        print(r)

    return


# Generated by 1.1.4 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: Runtime Error

Solution code:
#!/usr/bin/env python3
import sys


def dfs(v, p, c, G, R):
    R[v] = c
    for nv,w in G[v].items():
        if nv == p:
            continue

        nc = c
        if w % 2 == 1:
            nc = 1 - c

        dfs(nv,v,nc,G,R)
        

def solve(N: int, U: "List[int]", V: "List[int]", W: "List[int]"):

    G = [{} for i in range(N) ]
    for u,v,w in zip(U,V,W):
        G[u-1][v-1] = w
        G[v-1][u-1] = w


    R = [2 for i in range(N)]
    dfs(0,-1,0,G,R)

    for r in R:
        print(r)


    return


# Generated by 1.1.4 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: Runtime Error

Solution code:
n,m=map(int,input().split())
ans=[0]*n
for i in range(m):
  u,v,w=map(int,input().split())
  if w%2==1:
    if ans[u-1]==0:
      ans[v-1]=1
    elif ans[v-1]==0:
      ans[u-1]=1
for i in range(n):
  print(ans[i])

Submission status: Runtime Error

Solution code:
def visit(current, v, dist, color):
    for ele in v[current]:
        if color[ele] != -1:
            continue
        if dist[(ele, current)] % 2 == 0:
            color[ele] = color[current]
        else:
            if color[current] == 0:
                color[ele] = 1
            else:
                color[ele] = 0
        visit(ele, v, dist, color)

def main():

    num = int(input())

    v = [[] for i in range(num + 1)]

    dist = {}

    for i in range(1, num):
        a, b, d = map(int, input().split())
        v[a].append(b)
        v[b].append(a)
        dist[(a, b)] = d
        dist[(b, a)] = d

    color = [-1 for i in range(num + 1)]
    color[1] = 0
    visit(1, v, dist, color)

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

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
n = int(input())
g = [[] for i in range(n)]
c = [-1 for i in range(n)]

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


def dfs(p, d):
    if c[p] == -1:
        c[p] = d
        for x, w in g[p]:
            dfs(x, d ^ w)


dfs(0, 0)

for i in range(len(c)):
    print(c[i])

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
n = int(input())
g = [[] for i in range(n)]
c = [-1 for i 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 % 2])
    g[v].append([u, w % 2])


def dfs(p, d):
    if c[p] == -1:
        c[p] = d
        for x, w in g[p]:
            dfs(x, (d + w) % 2)


dfs(0, 0)

for i in range(len(c)):
    print(c[i])

Submission status: Runtime Error

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

import sys
sys.setrecursionlimit(10000)

def dfs(graph, color, visit, idx):
    visit[idx] = True
    if len(graph[idx]) == 0:
        return
    for i, w in graph[idx]:
        if visit[i] is True:
            continue
        if w%2 == 0:    # 同色で塗る
            color[i] = color[idx]
        else:   # 異色で塗る
            color[i] = 1 - color[idx]   # 1-cで異色になる
        dfs(graph, color, visit, i)


N = int(input())
L = N-1
graph = [[] for _ in range(N)]
color = [-1 for _ in range(N)]
visit = [False for _ in range(N)]

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

color[0] = 0    # 添え字0をcolor0と置く
dfs(graph, color, visit, 0)

for c in color:
    print(c)

Submission status: Runtime Error

Solution code:
N=int(input())
G=[[] for i in range(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))
res=[-1]*N
def dfs(v,p,c):
    res[v]=c
    for nv,w in G[v]:
        if res[nv]>=0:
            continue
        dfs(nv,v,(c+w)%2)
        """
        if w&1:
            dfs(nv,v,1-c)
        else:
            dfs(nv,v,c)
        """
dfs(0,-1,0)
for i in res:
    print(i)

Submission status: Runtime Error

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

import sys
sys.setrecursionlimit(10000)

def dfs(graph, color, visit, idx):
    visit[idx] = True
    for i, w in graph[idx]:
        if visit[i] is True:
            continue
        if w%2 == 0:    # 同色で塗る
            color[i] = color[idx]
            dfs(graph, color, visit, i)
        else:   # 異色で塗る
            color[i] = 1 - color[idx]   # 1-cで異色になる
            dfs(graph, color, visit, i)


N = int(input())
L = N-1
graph = [[] for _ in range(N)]
color = [-1 for _ in range(N)]
visit = [False for _ in range(N)]

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

color[0] = 0    # 添え字0をcolor0と置く
dfs(graph, color, visit, 0)

for c in color:
    print(c)

Submission status: Runtime Error

Solution code:
N=int(input())
G=[[] for i in range(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))
res=[-1]*N
res[0]=0
def dfs(v,p,c):
    res[v]=c
    for nv,w in G[v]:
        if res[nv]>=0:
            continue
        if w&1:
            dfs(nv,v,1-c)
        else:
            dfs(nv,v,c)
dfs(0,-1,0)
for i in res:
    print(i)

Submission status: Runtime Error

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

def dfs(graph, color, visit, idx):
    visit[idx] = True
    for i, w in graph[idx]:
        if visit[i] is True:
            continue
        if w%2 == 0:    # 同色で塗る
            color[i] = color[idx]
            dfs(graph, color, visit, i)
        else:   # 異色で塗る
            color[i] = 1 - color[idx]   # 1-cで異色になる
            dfs(graph, color, visit, i)


N = int(input())
L = N-1
graph = [[] for _ in range(N)]
color = [-1 for _ in range(N)]
visit = [False for _ in range(N)]

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

color[0] = 0    # 添え字0をcolor0と置く
dfs(graph, color, visit, 0)

for c in color:
    print(c)

Submission status: Runtime Error

Solution code:
N=int(input())
G=[[] for i in range(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))
res=[-1]*N
res[0]=0
def dfs(v,p,c):
    res[v]=c
    for nv,w in G[v]:
        if nv==p:
            continue
        if w&1:
            dfs(nv,v,1-c)
        else:
            dfs(nv,v,c)
dfs(0,-1,0)
for i in res:
    print(i)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
n = int(input())
g = [[] for i in range(n)]
c = [-1 for i 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])


def dfs(p, d):
    if c[p] == -1:
        c[p] = d
        for x, w in g[p]:
            dfs(x, (d + w) % 2)


dfs(0, 0)

for i in range(len(c)):
    print(c[i])

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
n = int(input())
g = [[] for i in range(n)]
c = [-1 for i 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])


def distance(p, d):
    if c[p] == -1:
        c[p] = d
        for x, w in g[p]:
            distance(x, (d + w) % 2)


distance(0, 0)

for v in c:
    print(v)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
n = int(input())
g = [[] for i in range(n)]
c = [-1 for i 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])


def distance(p, d):
    if c[p] == -1:
        c[p] = d % 2
        print(p, d, c[p])
        for x, w in g[p]:
            distance(x, d + w)


distance(0, 0)

for v in c:
    print(v)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10100)
n=int(input())
route=[[] for i in range(n)]
for i in range(n-1):
	u,v,w=map(int,input().split())
	route[u-1].append((v-1,w))
	route[v-1].append((u-1,w))
ans=[-1]*n
def dfs(p,d):
	ans[p]=d
	for i,j in route[p]:
		if ans[i]<0:dfs(i,(d+j)%2)
dfs(0,0)
for i in range(n):
	print(ans[i])

Submission status: Runtime Error

Solution code:
import numpy as np
from sys import stdin, stdout
import numpy as np
from numpy import loadtxt, savetxt, hstack
from scipy.sparse import coo_matrix
from scipy.sparse.linalg import eigsh

N = int(stdin.readline())
u, v, w = loadtxt(stdin, dtype=np.int).T

w_ = (w%2)*2 - 1.0
w_ = hstack((w_, w_))
irow = hstack((u, v)) - 1
icol = hstack((v, u)) - 1
A = coo_matrix((w_, (irow, icol)), shape=(N, N))
vs, ks = eigsh(A, k=1, which='SA')
savetxt(stdout.buffer, (ks[:, 0] > 0) * 1, fmt='%d')

Submission status: Runtime Error

Solution code:
n=int(input())
route=[[] for i in range(n)]
for i in range(n-1):
	u,v,w=map(int,input().split())
	route[u-1].append((v-1,w))
	route[v-1].append((u-1,w))
ans=[-1]*n
def dfs(p,d):
	ans[p]=d
	for i,j in route[p]:
		if ans[i]<0:dfs(i,(d+j)%2)
dfs(0,0)
for i in range(n):
	print(ans[i])

Submission status: Runtime Error

Solution code:
import numpy as np
from sys import stdin, stdout
import numpy as np
from numpy import loadtxt, savetxt, hstack
from scipy.sparse import coo_matrix
from scipy.sparse.linalg import eigsh

N = int(stdin.readline())
u, v, w = loadtxt(stdin, dtype=np.int).T

w_ = (w%2)*2 - 1.0
w_ = hstack((w_, w_))
irow = hstack((u, v)) - 1
icol = hstack((v, u)) - 1
A = coo_matrix((w_, (irow, icol)), shape=(N, N))
vs, ks = eigsh(A, k=1, which='SA')
savetxt(stdout, (ks[:, 0] > 0) * 1, fmt='%d')

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(15000)

*D, = open(0)
n = int(D[0])
 
v = [[] for _ in range(n+1)]
 
dist = {}
 
for i in range(1, n):
    a, b, d = map(int, D[i].split())
    v[a].append(b)
    v[b].append(a)
    dist[(a,b)]=d
    dist[(b,a)]=d
 
def visit(current, v, dist, color):
   
    for it in v[current]:
        if color[it] != None:
            continue
        if dist[(it, current)]%2 == 0:
            color[it] = color[current]
        else:
            color[it] = not color[current]
        visit(it, v, dist, color)
        
color = [None for _ in range(n+1)]
color[1]=True
visit(1, v, dist, color)
 
for i in range(1, n+1):
    if color[i]:
        print('0')
    else:
        print('1')

Submission status: Runtime Error

Solution code:
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)
        # xの木の高さ < yの木の高さ
        if self.rank[rx] < self.rank[ry]:
            self.par[rx] = ry
            self.weight[rx] = w - self.weight[x] + self.weight[y]
        # xの木の高さ ≧ 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)

    # xからyへのコスト
    def diff(self, x, y):
        return self.weight[x] - self.weight[y]

N = int(input())
ps = [list(map(int, input().split())) for _ in range(N-1)]
ps.sort()
tree = WeightedUnionFind(N)
for i, j, d in ps:
    tree.union(i, j, d)
for i in range(1, N+1):
    if diff(1, i) % 2 == 0:
        print(1)
    else:
        print(0)

Submission status: Runtime Error

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

n = int(input())
if n==1:
  print(0)
  exit()
from collections import defaultdict
edge = defaultdict(list)
for i in range(n-1):
  u, v, w = list(map(int, input().split()))
  edge[u].append((v, w))
  edge[v].append((u, w))
graph = [-1 for i in range(n+1)]

def dfs(x, c):
  nexts = edge.get(x)
  if nexts is None:
    return
  if graph[x]!=-1:
    return
  else:
    graph[x] = c
  for y, w in nexts:
    if w%2:
      dfs(y, not c)
    else:
      dfs(y, c)

dfs(1, 0)
for i in range(1, n+1):
  print(int(graph[i]))

Submission status: Runtime Error

Solution code:
N = int(input())
graph = {}
root = -1
for n in range(N-1):
    u, v, w = map(int, input().split())
    u -= 1
    v -= 1

    if root == -1:
        root = u
    if u not in graph:
        graph[u] = {}
    if v not in graph:
        graph[v] = {}
    graph[u][v] = w
    graph[v][u] = w    

answer = [-1] * N
def search(node, depth):
    answer[node] = depth
    for n in graph.get(node, {}):
        if answer[n] == -1:
            search(n,depth + graph[node][n])
if N == 1:
    print('0')
else:
    search(root, 0)
    for a in answer:
        print('0' if a % 2 else '1')

Submission status: Runtime Error

Solution code:
N=int(input())

G=[[] for i in range(N)]
res=[0]*N
def dfs(v,p,c):
  res[v]=c
  for nv,w in G[v]:
    if nv==p:
      continue
    if (w & 1):
      dfs(nv,v,1-c)
    else:
      dfs(nv,v,c)
 
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))
dfs(0,-1,0)
for i in range(N):
  print(res[i])

Submission status: Runtime Error

Solution code:
N = int(input())
graph = {}
root = -1
for n in range(N-1):
    u, v, w = map(int, input().split())
    u -= 1
    v -= 1

    if root == -1:
        root = u
    if u not in graph:
        graph[u] = {}
    if v not in graph:
        graph[v] = {}
    graph[u][v] = w
    graph[v][u] = w    

answer = [-1] * N
def search(node, depth):
    answer[node] = depth
    for n in graph[node]:
        if answer[n] == -1:
            search(n,depth + graph[node][n])
if N == 1:
    print('0')
else:
    search(root, 0)
    for a in answer:
        print('0' if a % 2 else '1')

Submission status: Runtime Error

Solution code:
N = int(input())
ans = ['NIL' for i in range(N+1)]
appeared_num = []
 
if N == 1:
    print(1)
else:
 
    #1回目
    line = list(map(int, input().split()))
    appeared_num += [line[0], line[1]]
    if line[2] % 2 == 0:
        ans[line[0]] = 1
        ans[line[1]] = 1
    else:
        ans[line[0]] = 1
        ans[line[1]] = 0
 
    #2回目以降
    remain = []
    for i in range(N-2):
        line = list(map(int, input().split()))
        length = line[2] % 2
        if line[0] in appeared_num:
            if ans[line[0]] == 1:
                ans[line[1]] = (1 + length) % 2
            else:
                ans[line[1]] = length
            appeared_num += [line[1]]
 
 
        elif line[1] in appeared_num:
            if ans[line[1]] == 1:
                ans[line[0]] = (1 + length) % 2
            else:
                ans[line[0]] = length
                appeared_num += [line[0]]
 
        else:
            remain += line
 
    #2周目以降
    while len(remain) != 0:
        l = len(remain)
        for i in range(l):
            line = remain[i]
            length = line[2] % 2
            if line[0] in appeared_num:
                if ans[line[0]] == 1:
                    ans[line[1]] = (1 + length) % 2
                else:
                    ans[line[1]] = length
                appeared_num += [line[1]]
                remain.pop(i)
 
 
            elif line[1] in appeared_num:
                if ans[line[1]] == 1:
                    ans[line[0]] = (1 + length) % 2
                else:
                    ans[line[0]] = length
                    appeared_num += [line[0]]
                remain.pop(i)
 
            else:
                pass
 
    Ans = ans[1:]
    for i in range(N):
        print(Ans[i])

Submission status: Runtime Error

Solution code:
N = int(input())
graph = {}
root = -1
for n in range(N-1):
    u, v, w = map(int, input().split())
    u -= 1
    v -= 1

    if root == -1:
        root = u
    if u not in graph:
        graph[u] = {}
    if v not in graph:
        graph[v] = {}
    graph[u][v] = w
    graph[v][u] = w    

answer = [-1] * N
def search(node, depth):
    answer[node] = depth
    for n in graph[node]:
        if answer[n] == -1:
            search(n,depth + graph[node][n])

search(root, 0)
for a in answer:
    print('0' if a % 2 else '1')

Submission status: Runtime Error

Solution code:
N=int(input())
if N>=5*1e4:
  quit()
G=[[] for i in range(N)]
res=[0]*N
def dfs(v,p,c):
  res[v]=c
  for nv,w in G[v]:
    if nv==p:
      continue
    if (w & 1):
      dfs(nv,v,1-c)
    else:
      dfs(nv,v,c)
 
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))
dfs(0,-1,0)
for i in range(N):
  print(res[i])

Submission status: Runtime Error

Solution code:
N = int(input())
graph = {}
root = -1
for n in range(N-1):
    u, v, w = map(int, input().split())
    u -= 1
    v -= 1

    if root == -1:
        root = u
    if u not in graph:
        graph[u] = {}
    if v not in graph:
        graph[v] = {}
    graph[u][v] = w
    graph[v][u] = w    

print(graph)

answer = [-1] * N
def search(node, depth):
    answer[node] = depth
    for n in graph[node]:
        if answer[n] == -1:
            search(n,depth + graph[node][n])

search(root, 0)
for a in answer:
    print('0' if a % 2 else '1')