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:
N = int(input())

A = {}
B = []
C = [-1] * (N)

for _ in range(N - 1):
  u, v, w = map(int, input().strip().split(' '))
  if u not in A: A[u] = {}
  if v not in A: A[v] = {}

  for key, val in A[u].items():
    s = val + w
    A[v][key] = s
    A[key][v] = s
    if s % 2 == 1:
      B.append((v, key))

  for key, val in A[v].items():
    s = val + w
    A[u][key] = s
    A[key][u] = s
    if s % 2 == 1:
      B.append((u, key))

  A[u][v] = w
  A[v][u] = w
  if w % 2 == 1:
    B.append((u, v))

for k0, k1 in B:
  del A[k0][k1]
  del A[k1][k0]

k, v = A.popitem()
C[k - 1] = 0
for i in v.keys():
  C[i - 1] = 0
  del A[i]

for i in A.keys():
  C[i - 1] = 1

for i in C:
  print(i)

Submission status: Runtime Error

Solution code:
from collections import deque
N=int(input())
uvw=list(list(map(int,input().split())) for _ in range(N-1))

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

colors=[2]*N
nonvisited=[p for p in range(1,N+1)]
queue=deque([1])
colors[0]=0
while len(queue)>0:
    x=queue.popleft()
    if x!=0:
        nonvisited.pop(nonvisited.index(x))
    if len(nonvisited)==0:
        break
    for j in graph_list[x-1]:
        if j[0] in nonvisited:
            queue.append(j[0])
            colors[j[0]-1]=(colors[x]+j[1])%2
for p in colors:
    print(p)

Submission status: Runtime Error

Solution code:
"""
解説と提出 #5739708をもとに作成
"""


def solve():
    N = int(input())
    result = [-1] * N
    uvw_map = [[] for _ in range(N)]
    '''枝毎の距離相関図を作る'''
    for i in range(N - 1):
        u, v, w = map(int, input().split())
        u -= 1
        v -= 1
        uvw_map[u].append([v, w])
        uvw_map[v].append([u, w])
    # 木の頂点を求める
    # -> 任意の場所で良い. 1 とする.
    # 頂点から順に塗っていく
    result[0] = False
    result = paint(uvw_map, 0, result)
    for i in result:
        print(int(i))


def paint(uvw_map, num, result):
    # num に紐づくノードの一覧を取得する
    num_map = uvw_map[num]
    # num との距離に応じて色を決定する
    nums = []
    for v, w in num_map:
        if result[v] != -1:
            continue
        result[v] = result[num] if w % 2 == 0 else not(result[num])
        # # 色分けを行ったものについてのみ記録しておく(num')
        nums.append(v)
    # num' すべてに対して同様の操作を行う
    for n in nums:
        result = paint(uvw_map, n, result)
    return result


if __name__ == '__main__':
    solve()

Submission status: Runtime Error

Solution code:
class dfs():
    
    def __init__(self, n, el):
        self.n = n
        self.el = el

        self.evenl = [1 for i in range(n)]
        self.neibors = dict([(i,[[],[]]) for i in range(n)])


    def calc(self, nf, used):
        used.append( nf )
        for node in set( self.neibors[nf][0] ) - set(used) :
            if self.evenl[nf] == 1:
                self.evenl[node] = 1
            else:
                self.evenl[node] = 0

            self.calc(node, used)

        for node in set( self.neibors[nf][1] ) - set(used) :
            if self.evenl[nf] == 1:
                self.evenl[node] = 0
            else:
                self.evenl[node] = 1

            self.calc(node, used)


    def set_neibors(self):
        for e in self.el:
            u,v,w = e
            if w % 2 == 0:
                self.neibors[u-1][0].append(v-1)
                self.neibors[v-1][0].append(u-1)
            else:
                self.neibors[u-1][1].append(v-1)
                self.neibors[v-1][1].append(u-1)

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

m = dfs(n,el)
m.set_neibors()
m.calc(0, [])

for item in m.evenl:
    print(item)

Submission status: Runtime Error

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

V = [0] * N
D = [0] * N
C = [0] * N


def dfs(n, c):
    if V[n] == 1:
        return
    C[n] = c
    V[n] = 1
    for w in M[n]:
        if w[1] % 2 == 0:
            dfs(w[0], c)
        else:
            dfs(w[0], (c + 1) % 2)

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

Submission status: Runtime Error

Solution code:
n = int(input())
tree = [[] for i in range(n+1)]

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

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

while stack:
    cur = stack.pop()
    visitted.append(cur)
    for v, w in tree[cur]:
        if v in visitted:
            continue
        #if v in stack:
        #    continue
        if w % 2 == 1:
            ans[v-1]=(ans[cur]+1)%2
        else:
            ans[v-1]=ans[cur]
        stack.append(v)

for i in ans:
    print(i)

Submission status: Runtime Error

Solution code:
def dfs(v, p, c):
    res[v] = c
    for next in link[v]:
        if next[0] == p:
            continue
        if c == next[1]:
            dfs(next[0], v, c)
        else:
            dfs(next[0], v, 1-c)


N = int(input())
link = [[] * N for _ in range(N)]
res = [0] * N
for i in range(N-1):
    u, v, w = map(int, input().split())
    link[u-1].append([v-1, w % 2])
    link[v-1].append([u-1, w % 2])
print(link)
dfs(0, -1, 1)

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

Submission status: Runtime Error

Solution code:
def dfs(v, p, c):
    res[v] = c
    for next in link[v]:
        if next[0] == p:
            continue
        if next[1]:
            dfs(next[0], v, c)
        else:
            dfs(next[0], v, 1-c)


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

dfs(0, -1, 1)

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

Submission status: Runtime Error

Solution code:
N = int(raw_input())
edges = [[] for i in xrange(N)]

for i in xrange(N-1):
    u, v, w = map(int, raw_input().split())
    edges[u-1].append((v-1, w))
    edges[v-1].append((u-1, w))
    
visited = [False for i in xrange(N)]
color = [-1 for i in xrange(N)]
color[0] = 0

def bfs(node, s):
    visited[node] = True
    for (a, w) in edges[node]:
        if not visited[a]:
            if (s + w) % 2 == 0:
                color[a] = 0
                bfs(a, 0)
            else:
                color[a] = 1
                bfs(a, 1)
if N > 1:
    bfs(0, 0)

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

Submission status: Runtime Error

Solution code:
N = int(raw_input())
edges = [[] for i in xrange(N)]

for i in xrange(N-1):
    u, v, w = map(int, raw_input().split())
    edges[u-1].append((v-1, w))
    edges[v-1].append((u-1, w))
    
visited = [False for i in xrange(N)]
color = [-1 for i in xrange(N)]
color[0] = 0

def bfs(node, s):
    visited[node] = True
    for (a, w) in edges[node]:
        if not visited[a]:
            visited[a] = True
            if (s + w) % 2 == 0:
                color[a] = 0
                bfs(a, 0)
            else:
                color[a] = 1
                bfs(a, 1)
if N > 1:
    bfs(0, 0)

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

Submission status: Runtime Error

Solution code:
N = int(raw_input())
edges = [[] for i in xrange(N)]

for i in xrange(N-1):
    u, v, w = map(int, raw_input().split())
    edges[u-1].append((v-1, w))
    edges[v-1].append((u-1, w))
    
visited = [False for i in xrange(N)]
color = [-1 for i in xrange(N)]
color[0] = 0

def bfs(node, s):
    visited[node] = True
    for (a, w) in edges[node]:
        if not visited[a]:
            visited[a] = True
            if (s + w) % 2 == 0:
                color[a] = 0
                bfs(a, 0)
            else:
                color[a] = 1
                bfs(a, 1)

bfs(0, 0)
for i in xrange(N):
    print color[i]

Submission status: Runtime Error

Solution code:

Copy
Copy
import sys
sys.setrecursionlimit(20000000)
#input = sys.stdin.readline
n = int(input())
g = [[] 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])
ans = [-1]*n
def dfs(x,y):
    for i,j in g[x]:
        if ans[i] == -1:
            ans[i] = (y+j)%2
            dfs(i,y+j)
dfs(0,0)
for i in ans:
    print(i)

Submission status: Runtime Error

Solution code:
def dfs(node, distance):
    for next_node, edge_size in G[node]:
        if ans[next_node] == -1:
            ans[next_node] = ((distance+edge_size) % 2)
            dfs(next_node, distance+edge_size)


N = int(input())

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

ans = [-1]*N
dfs(0, 0)
print(*ans, sep='\n')

Submission status: Runtime Error

Solution code:
def dfs(node, distance, ans, G):
    for next_node, edge_size in G[node]:
        if ans[next_node] == -1:
            ans[next_node] = ((distance+edge_size) % 2)
            dfs(next_node, distance+edge_size, ans, G)
    return ans


N = int(input())

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

ans = [-1]*N
ans = dfs(0, 0, ans, G)
print(*ans, sep='\n')

Submission status: Runtime Error

Solution code:
class UnionFind:
    def __init__(self,n):
        self.parent = [-1 for i in range(n)]

    def find(self, x):
        if self.parent[x] < 0:
            return x

        else:
            self.parent[x] = self.find(self.parent[x])
            return self.parent[x]

    def union(self, x, y):
        x, y = self.find(x), self.find(y)
        if (x == y):
            pass
        else:
            self.parent[x] = self.parent[y]
            self.parent[y] = x

    def isgroup(self, x, y):
        return True if self.find(x) == self.find(y) else False

n = int(input())
uf = UnionFind(n)

for i in range(n-1):
    u, v, w = map(int, input().split())
    if w % 2 == 0:
        uf.union(u-1,v-1)

for i in range(n):
    print("1" if uf.isgroup(0,i) else "0")

Submission status: Runtime Error

Solution code:
class UnionFind:
    def __init__(self,n):
        self.par = [i for i in range(n+1)]
        #木の高さを格納する
        self.rank=[0]*(n+1)
        
    def find(self,x):
        if self.par[x]==x:#根ならその番号を返す
            return x
        else:#根じゃないなら親を指定して再検索
            self.par[x]=self.find(self.par[x])
            return self.find(self.par[x])
    def same_chk(self,x,y):#x,yが同じグループに所属するか確認
        return self.find(x)==self.find(y)
    def union(self,x,y):
        x=self.find(x)
        y=self.find(y)
        if self.rank[x]<self.rank[y]:
            self.par[x]=y
        else:
            self.par[y]=x
            if self.rank[x]==self.rank[y]:
                self.rank[x]+=1
#奇数の辺でグループを分割
#→切り離されたグループ同士の距離が偶数にならないといけない
n=int(input())
uvw=[]
for i in range(n-1):
    uvw.append(list(map(int, input().split())))
#n=5
#uvw=[[2,5,2],[2,3,10],[1,3,8],[3,4,2]]
uf=UnionFind(n)
ans_list=[0 for i in range(n)]
root_list=[]
prev_group = 0
for i in range(len(uvw)):
    if uvw[i][2]%2==0:
        uf.union(uvw[i][0],uvw[i][1])
        #ans_list[uvw[i][0]-1]=0
        #ans_list[uvw[i][1]-1]=0
        if len(root_list)==0:
            root_list.append(uvw[i][0])
    else:
        another = 0
        if uf.same_chk(root_list[0],uvw[i][0]):
            if len(root_list)==1:
                root_list.append(uvw[i][1])
            another = uvw[i][1]
        else:
            if len(root_list)==1:
                root_list.append(uvw[i][0])
            another = uvw[i][0]
        ans_list[another-1]=1
        if len(root_list)>1:
            uf.union(root_list[1],another)
for i in range(n):
    print(ans_list[i])

Submission status: Runtime Error

Solution code:
#奇数の辺でグループを分割
#→切り離されたグループ同士の距離が偶数にならないといけない
n=int(input())
uvw=[]
for i in range(n-1):
    uvw.append(list(map(int, input().split())))
#n=5
#uvw=[[2,5,2],[2,3,10],[1,3,8],[3,4,2]]
uf=UnionFind(n)
ans_list=[0 for i in range(n)]
root_list=[]
prev_group = 0
for i in range(len(uvw)):
    if uvw[i][2]%2==0:
        uf.union(uvw[i][0],uvw[i][1])
        #ans_list[uvw[i][0]-1]=0
        #ans_list[uvw[i][1]-1]=0
        if len(root_list)==0:
            root_list.append(uvw[i][0])
    else:
        another = 0
        if uf.same_chk(root_list[0],uvw[i][0]):
            if len(root_list)==1:
                root_list.append(uvw[i][1])
            another = uvw[i][1]
        else:
            if len(root_list)==1:
                root_list.append(uvw[i][0])
            another = uvw[i][0]
        ans_list[another-1]=1
        if len(root_list)>1:
            uf.union(root_list[1],another)
for i in range(n):
    print(ans_list[i])

Submission status: Runtime Error

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

class UnionFind():
    # 作りたい要素数nで初期化
    # 使用するインスタンス変数の初期化
    def __init__(self, n):
        self.n = n
        # root[x]<0ならそのノードが根かつその値が木の要素数
        # rootノードでその木の要素数を記録する
        self.root = [-1]*(n+1)
        # 木をくっつける時にアンバランスにならないように調整する
        self.rnk = [0]*(n+1)
        
        self.par = [0]*(n+1)

    # ノードxのrootノードを見つける
    def Find_Root(self, x):
        if(self.root[x] < 0):
            return x
        else:
            # ここで代入しておくことで、後の繰り返しを避ける
            self.root[x] = self.Find_Root(self.root[x])
            
            return self.root[x]
    # 木の併合、入力は併合したい各ノード
    def Unite(self, x, y):
        tmpx,tmpy=x,y
        # 入力ノードのrootノードを見つける
        x = self.Find_Root(x)
        y = self.Find_Root(y)
        # すでに同じ木に属していた場合
        if(x == y):
            return 
        # 違う木に属していた場合rnkを見てくっつける方を決める
        elif(self.rnk[x] > self.rnk[y]):
            self.root[x] += self.root[y]
            self.root[y] = x
            self.par[tmpy]  =tmpx

        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            self.par[tmpx]  = tmpy
            # rnkが同じ（深さに差がない場合）は1増やす
            if(self.rnk[x] == self.rnk[y]):
                self.rnk[y] += 1
    # xとyが同じグループに属するか判断
    def isSameGroup(self, x, y):
        return self.Find_Root(x) == self.Find_Root(y)

    # ノードxが属する木のサイズを返す
    def Count(self, x):
        return -self.root[self.Find_Root(x)]


def cur(i):
    if memo[i]==-1: memo[i]=(cur(tree.par[i])+state[i])%2
    return memo[i]

N=int(input())
tree=UnionFind(N)

state=[-1]*(N+1)
for i in range(N-1):
    u,v,w=map(int,input().split())
    tree.Unite(u,v)
    if tree.par[u]==v: state[u]=w%2
    if tree.par[v]==u: state[v]=w%2

memo=[-1]*(N+1)
memo[tree.Find_Root(1)]=0
for i in range(1,N+1):
    print(cur(i))

Submission status: Runtime Error

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

def cur(current,e,dist,color):
    for it in e[current]:
        if color[it]!=-1: continue
        color[it]=(color[current]+dist[(it,current)])%2
        cur(it,e,dist,color)

N=int(input())
e=[[] for i in range(N+1)]
dist={}
for i in range(N-1):
    u,v,w=map(int,input().split())
    e[u].append(v)
    e[v].append(u)
    dist[(u,v)],dist[(v,u)]=w,w
memo=[-1]*N




color=[-1]*(N+1)
color[1]=0
cur(1,e,dist,color)

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

Submission status: Runtime Error

Solution code:
def cur(current,e,dist,color):
    for it in e[current]:
        if color[it]!=-1: continue
        color[it]=(color[current]+dist[(it,current)])%2
        cur(it,e,dist,color)

N=int(input())
e=[[] for i in range(N+1)]
dist={}
for i in range(N-1):
    u,v,w=map(int,input().split())
    e[u].append(v)
    e[v].append(u)
    dist[(u,v)],dist[(v,u)]=w,w
memo=[-1]*N




color=[-1]*(N+1)
color[1]=0
cur(1,e,dist,color)

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

Submission status: Runtime Error

Solution code:
class UnionFind():
    # 作りたい要素数nで初期化
    # 使用するインスタンス変数の初期化
    def __init__(self, n):
        self.n = n
        # root[x]<0ならそのノードが根かつその値が木の要素数
        # rootノードでその木の要素数を記録する
        self.root = [-1]*(n+1)
        # 木をくっつける時にアンバランスにならないように調整する
        self.rnk = [0]*(n+1)
        
        self.par = [0]*(n+1)

    # ノードxのrootノードを見つける
    def Find_Root(self, x):
        if(self.root[x] < 0):
            return x
        else:
            # ここで代入しておくことで、後の繰り返しを避ける
            self.root[x] = self.Find_Root(self.root[x])
            
            return self.root[x]
    # 木の併合、入力は併合したい各ノード
    def Unite(self, x, y):
        tmpx,tmpy=x,y
        # 入力ノードのrootノードを見つける
        x = self.Find_Root(x)
        y = self.Find_Root(y)
        # すでに同じ木に属していた場合
        if(x == y):
            return 
        # 違う木に属していた場合rnkを見てくっつける方を決める
        elif(self.rnk[x] > self.rnk[y]):
            self.root[x] += self.root[y]
            self.root[y] = x
            self.par[tmpy]  =tmpx

        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            self.par[tmpx]  = tmpy
            # rnkが同じ（深さに差がない場合）は1増やす
            if(self.rnk[x] == self.rnk[y]):
                self.rnk[y] += 1
    # xとyが同じグループに属するか判断
    def isSameGroup(self, x, y):
        return self.Find_Root(x) == self.Find_Root(y)

    # ノードxが属する木のサイズを返す
    def Count(self, x):
        return -self.root[self.Find_Root(x)]


def cur(i):
    if memo[i]==-1: memo[i]=(cur(tree.par[i])+state[i])%2
    return memo[i]

N=int(input())
tree=UnionFind(N)

state=[-1]*(N+1)
for i in range(N-1):
    u,v,w=map(int,input().split())
    tree.Unite(u,v)
    if tree.par[u]==v: state[u]=w%2
    if tree.par[v]==u: state[v]=w%2

memo=[-1]*(N+1)
memo[tree.Find_Root(1)]=0
for i in range(1,N+1):
    print(cur(i))

Submission status: Runtime Error

Solution code:
class UnionFind():
    # 作りたい要素数nで初期化
    # 使用するインスタンス変数の初期化
    def __init__(self, n):
        self.n = n
        # root[x]<0ならそのノードが根かつその値が木の要素数
        # rootノードでその木の要素数を記録する
        self.root = [-1]*(n+1)
        # 木をくっつける時にアンバランスにならないように調整する
        self.rnk = [0]*(n+1)
        
        self.par = [0]*(n+1)

    # ノードxのrootノードを見つける
    def Find_Root(self, x):
        if(self.root[x] < 0):
            return x
        else:
            # ここで代入しておくことで、後の繰り返しを避ける
            self.root[x] = self.Find_Root(self.root[x])
            
            return self.root[x]
    # 木の併合、入力は併合したい各ノード
    def Unite(self, x, y):
        tmpx,tmpy=x,y
        # 入力ノードのrootノードを見つける
        x = self.Find_Root(x)
        y = self.Find_Root(y)
        # すでに同じ木に属していた場合
        if(x == y):
            return 
        # 違う木に属していた場合rnkを見てくっつける方を決める
        elif(self.rnk[x] > self.rnk[y]):
            self.root[x] += self.root[y]
            self.root[y] = x
            self.par[tmpy]  =tmpx

        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            self.par[tmpx]  = tmpy
            # rnkが同じ（深さに差がない場合）は1増やす
            if(self.rnk[x] == self.rnk[y]):
                self.rnk[y] += 1
    # xとyが同じグループに属するか判断
    def isSameGroup(self, x, y):
        return self.Find_Root(x) == self.Find_Root(y)

    # ノードxが属する木のサイズを返す
    def Count(self, x):
        return -self.root[self.Find_Root(x)]


def cur(n):
    if memo[n]==-1: memo[n]=(cur(tree.par[n])+state[n])%2
    return memo[n]

N=int(input())
tree=UnionFind(N)

state=[-1]*(N+1)
for i in range(N-1):
    u,v,w=map(int,input().split())
    tree.Unite(u,v)
    if tree.par[u]==v: state[u]=w%2
    if tree.par[v]==u: state[v]=w%2

memo=[-1]*(N+1)
memo[tree.Find_Root(1)]=0
for i in range(1,N+1):
    print(cur(i))

Submission status: Runtime Error

Solution code:
class UnionFind():
    # 作りたい要素数nで初期化
    # 使用するインスタンス変数の初期化
    def __init__(self, n):
        self.n = n
        # root[x]<0ならそのノードが根かつその値が木の要素数
        # rootノードでその木の要素数を記録する
        self.root = [-1]*(n+1)
        # 木をくっつける時にアンバランスにならないように調整する
        self.rnk = [0]*(n+1)
        
        self.par = [0]*(n+1)

    # ノードxのrootノードを見つける
    def Find_Root(self, x):
        if(self.root[x] < 0):
            return x
        else:
            # ここで代入しておくことで、後の繰り返しを避ける
            self.root[x] = self.Find_Root(self.root[x])
            
            return self.root[x]
    # 木の併合、入力は併合したい各ノード
    def Unite(self, x, y):
        tmpx,tmpy=x,y
        # 入力ノードのrootノードを見つける
        x = self.Find_Root(x)
        y = self.Find_Root(y)
        # すでに同じ木に属していた場合
        if(x == y):
            return 
        # 違う木に属していた場合rnkを見てくっつける方を決める
        elif(self.rnk[x] > self.rnk[y]):
            self.root[x] += self.root[y]
            self.root[y] = x
            self.par[tmpy]  =tmpx

        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            self.par[tmpx]  = tmpy
            # rnkが同じ（深さに差がない場合）は1増やす
            if(self.rnk[x] == self.rnk[y]):
                self.rnk[y] += 1
    # xとyが同じグループに属するか判断
    def isSameGroup(self, x, y):
        return self.Find_Root(x) == self.Find_Root(y)

    # ノードxが属する木のサイズを返す
    def Count(self, x):
        return -self.root[self.Find_Root(x)]


def cur(n):
    if memo[n]==-1: memo[n]=(cur(tree.par[n])+state[n])%2
    return memo[n]

N=int(input())
tree=UnionFind(N)

state=[-1]*(N+1)
for i in range(N-1):
    u,v,w=map(int,input().split())
    tree.Unite(u,v)
    if tree.par[u]==v: state[u]=w%2
    if tree.par[v]==u: state[v]=w%2

memo=[-1]*(N+1)
memo[tree.Find_Root(1)]=0
for i in range(1,N+1):
    if cur(i)==0: print(0)
    else: print(1)

Submission status: Runtime Error

Solution code:
class UnionFind():
    # 作りたい要素数nで初期化
    # 使用するインスタンス変数の初期化
    def __init__(self, n):
        self.n = n
        # root[x]<0ならそのノードが根かつその値が木の要素数
        # rootノードでその木の要素数を記録する
        self.root = [-1]*(n+1)
        # 木をくっつける時にアンバランスにならないように調整する
        self.rnk = [0]*(n+1)
        
        self.par = [0]*(n+1)

    # ノードxのrootノードを見つける
    def Find_Root(self, x):
        if(self.root[x] < 0):
            return x
        else:
            # ここで代入しておくことで、後の繰り返しを避ける
            self.root[x] = self.Find_Root(self.root[x])
            
            return self.root[x]
    # 木の併合、入力は併合したい各ノード
    def Unite(self, x, y):
        tmpx,tmpy=x,y
        # 入力ノードのrootノードを見つける
        x = self.Find_Root(x)
        y = self.Find_Root(y)
        # すでに同じ木に属していた場合
        if(x == y):
            return 
        # 違う木に属していた場合rnkを見てくっつける方を決める
        elif(self.rnk[x] > self.rnk[y]):
            self.root[x] += self.root[y]
            self.root[y] = x
            self.par[tmpy]  =tmpx

        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            self.par[tmpx]  = tmpy
            # rnkが同じ（深さに差がない場合）は1増やす
            if(self.rnk[x] == self.rnk[y]):
                self.rnk[y] += 1
    # xとyが同じグループに属するか判断
    def isSameGroup(self, x, y):
        return self.Find_Root(x) == self.Find_Root(y)

    # ノードxが属する木のサイズを返す
    def Count(self, x):
        return -self.root[self.Find_Root(x)]


def cur(n):
    if memo[n]==-1: memo[n]=(cur(tree.par[n])+state[n])%2
    return memo[n]

N=int(input())
tree=UnionFind(N)

state=[-1]*(N+1)
for i in range(N-1):
    u,v,w=map(int,input().split())
    tree.Unite(u,v)
    if tree.par[u]==v: state[u]=w%2
    if tree.par[v]==u: state[v]=w%2

memo=[-1]*(N+1)
memo[tree.Find_Root(0)]=0
for i in range(1,N+1):
    if cur(i)%2==0: print(0)
    else: print(1)

Submission status: Runtime Error

Solution code:
class UnionFind():
    # 作りたい要素数nで初期化
    # 使用するインスタンス変数の初期化
    def __init__(self, n):
        self.n = n
        # root[x]<0ならそのノードが根かつその値が木の要素数
        # rootノードでその木の要素数を記録する
        self.root = [-1]*(n+1)
        # 木をくっつける時にアンバランスにならないように調整する
        self.rnk = [0]*(n+1)
        
        self.par = [0]*(n+1)

    # ノードxのrootノードを見つける
    def Find_Root(self, x):
        if(self.root[x] < 0):
            return x
        else:
            # ここで代入しておくことで、後の繰り返しを避ける
            self.root[x] = self.Find_Root(self.root[x])
            
            return self.root[x]
    # 木の併合、入力は併合したい各ノード
    def Unite(self, x, y):
        tmpx,tmpy=x,y
        # 入力ノードのrootノードを見つける
        x = self.Find_Root(x)
        y = self.Find_Root(y)
        # すでに同じ木に属していた場合
        if(x == y):
            return 
        # 違う木に属していた場合rnkを見てくっつける方を決める
        elif(self.rnk[x] > self.rnk[y]):
            self.root[x] += self.root[y]
            self.root[y] = x
            self.par[tmpy]  =tmpx

        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            self.par[tmpx]  = tmpy
            # rnkが同じ（深さに差がない場合）は1増やす
            if(self.rnk[x] == self.rnk[y]):
                self.rnk[y] += 1
    # xとyが同じグループに属するか判断
    def isSameGroup(self, x, y):
        return self.Find_Root(x) == self.Find_Root(y)

    # ノードxが属する木のサイズを返す
    def Count(self, x):
        return -self.root[self.Find_Root(x)]


def cur(n):
    if memo[n]==-1: memo[n]=cur(tree.par[n])+1
    return memo[n]

N=int(input())
tree=UnionFind(N)


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

memo=[-1]*(N+1)
memo[tree.Find_Root(0)]=0
for i in range(1,N+1):
    if cur(i)%2==0: print(0)
    else: print(1)

Submission status: Runtime Error

Solution code:
import numpy as np
N = int(input())

edge = np.zeros((N,N))
color = [-1] * (N)

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

stack = [(0,0)] # (頂点 , 距離)

while len(stack) > 0 :
    v , d = stack.pop()

    if d % 2 == 0 :
        color[v] = '1'
    else :
        color[v] = '0'

    for u , w in enumerate(edge[v]) :
        if w > 0 and color[u] == -1 :
            color[u] = -2
            stack.append((u,d+w))

for i in color :
    print(i)

Submission status: Runtime Error

Solution code:
import numpy as np
N = int(input())

edge = np.zeros((N,N))
color = [-1] * (N)

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

stack = [(0,0)] # (頂点 , 距離)

while len(stack) > 0 :
    v , d = stack.pop()

    if d % 2 == 0 :
        color[v] = '1'
    else :
        color[v] = '0'

    for u , w in enumerate(edge[v]) :
        if w > 0 and color[u] == -1 :
            stack.append((u,d+w))

for i in color :
    print(i)

Submission status: Runtime Error

Solution code:
import numpy as np
N = int(input())

edge = np.zeros((N,N))
color = [0] * (N)

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

stack = [(0,0)] # (頂点 , 距離)

while len(stack) > 0 :
    v , d = stack.pop()

    print(v+1)

    if d % 2 == 0 :
        color[v] = 1
    else :
        color[v] = 0

    for u , w in enumerate(edge[v]) :
        if w > 0 and color[u] == 0 :
            stack.append((u,d+w))

for i in color :
    print(i)

Submission status: Runtime Error

Solution code:
import numpy as np
N = int(input())

edge = np.zeros((N,N))
color = [0] * (N)

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

stack = [(0,0)] # (頂点 , 距離)

while len(stack) > 0 :
    v , d = stack.pop()

    if d % 2 == 0 :
        color[v] = '1'
    else :
        color[v] = '0'

    for u , w in enumerate(edge[v]) :
        if w > 0 and color[u] == 0 :
            stack.append((u,d+w))

for i in color :
    print(i)

Submission status: Runtime Error

Solution code:
import numpy as np
N = int(input())

edge = np.zeros((N,N))
color = [0] * (N)

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

color[0] = 1
stack = [0]

while len(stack) > 0 :
    v = stack.pop() # 現在の頂点

    for i in range(N) :
        if edge[v][i] > 0 and color[i] == 0 : # 辺があり，色がついていない場合
            if edge[v][i] % 2 == 0 :
                color[i] = color[v]
            else :
                color[i] = color[v] * -1
            stack.append(i)

for i in range(N) :
    if color[i] == 1 :
        print('1')
    else :
        print('0')

Submission status: Runtime Error

Solution code:
N = int(input())


# v0 o v1 o v2
# 1    0    1

# v0 e v1 o v2
# 1    1    0

# v0 e v1 e v2
# 1    1    1

# v0 o v1 e v2
# 1    0    0

class Color:
    def __init__(self, c):
        self.c = c

color = [None] * N
edge = []

for i in range(0, N-1):
    u, v, w = [int(x) for x in input().split()]
    if w & 1 == 0:
        edge.append((u-1, v-1, True))
    else:
        edge.apepnd((u-1, v-1, False))

edge.sort()

for u, v, w in edge:
    cu = color[u]
    if cu:
        if w:
            color[v] = cu
        else:
            if color[v]:
                color[v].c = 1-cu.c
            else:
                color[v] = Color(1-cu.c)
    else:
        if w:
            if color[v]:
                color[u] = color[v]
            else:
                color[v] = Color(0)
                color[u] = color[v]
        else:
            if color[v]:
                color[u].c = 1-color[v].c
            else:
                color[v] = Color(0)
                color[u].c = 1-color[v].c

for e in color[1:]:
    print(e.c)

Submission status: Runtime Error

Solution code:
N = int(input())


# v0 o v1 o v2
# 1    0    1

# v0 e v1 o v2
# 1    1    0

# v0 e v1 e v2
# 1    1    1

# v0 o v1 e v2
# 1    0    0

class Color:
    def __init__(self, c):
        self.c = c

color = [None] * (N+1)
edge = [None] * (N-1)
color[1] = Color(0)

for i in range(0, N-1):
    u, v, w = [int(x) for x in input().split()]
    if w & 1 == 0:
        edge[i] = ((u, v, True))
    else:
        edge[i] = ((u, v, False))

edge.sort()

for u, v, w in edge:
    cu = color[u]
    if cu:
        if w:
            color[v] = cu
        else:
            if color[v]:
                color[v].c = 1-cu.c
            else:
                color[v] = Color(1-cu.c)
    else:
        if w:
            if color[v]:
                color[u] = color[v]
            else:
                color[v] = Color(0)
                color[u] = color[v]
        else:
            if color[v]:
                color[u].c = 1-color[v].c
            else:
                color[v] = Color(0)
                color[u].c = 1-color[v].c

for e in color[1:]:
    print(e.c)

Submission status: Runtime Error

Solution code:
n = int(input())
d = {}
for i in range(n - 1):
  u, v, w = map(int, input().split())
  u -= 1
  v -= 1
  if u in d:
    d[u].append([v, w])
  else:
    d[u] = [[v, w]]
  if v in d:
    d[v].append([u, w])
  else:
    d[v] = [[u, w]]

rem = {}

for i in range(n):
  rem[i] = 1
  
ans = [0 for _ in range(n)]

def check(p, tmp):
  rem.pop(p)
  for n, w in d[p]:
    if n in rem:
      ntmp = (tmp + w) % 2
      ans[n] = ntmp
      check(n, ntmp)
      
check(0, 0)

for res in ans:
  print(res)