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

def dk(start,node,edge):
  d = [0]*node
  d[start] = 0
  q = [(0, start)]
  
  while(len(q) != 0):
    ci, i = heappop(q)
    for j in edge[i]:
      nc = ci + cost[i][j]
      if nc%2 == 1:
        d[j] = 1
      heappush(q,(nc, j))
  return d

#入力
N = int(input())
#エッジ
E = [[] for _ in [0]*N]
cost = np.zeros((N, N))

for i in range(N-1):
  a,b,w = (int(x) for x in input().split())
  E[a-1].append(b-1)
  cost[a-1][b-1] = w
  cost[b-1][a-1] = w


d = dk(0, N, E)

#出力
print(*d, sep = "\n")

Submission status: Runtime Error

Solution code:
n=int(input())
graph=[[] for i in range(n)]
color=[-1]*n
for i in range(n-1):
    a,b,c=map(int,input().split())
    graph[a-1].append([b-1,c%2])
    graph[b-1].append([a-1,c%2])
def coloring(pre,c):
  color[pre]=c
  for i,j in graph[pre]:
    if color[i]<0:
      coloring(i,color[pre]^j)
coloring(0,1)
for i in color:
  print(i)

Submission status: Runtime Error

Solution code:
def dfs(graph, node, dist):
    if graph[node-1][2] == 1:
        return
    else:
        graph[node-1][2] = 1
        graph[node-1][3] += dist
        if graph[node-1][3] % 2 == 0:
            graph[node-1][4] = 1
        else:
            pass
        ll = graph[node-1][0]
        for i in range(len(ll)):
            dfs(graph, ll[i], graph[node-1][3] + graph[node-1][1][i]);

def main():
    n = int(input())
    edge = []
    for i in range(n-1): edge.append(list(map(int,input().split())))

# graph[[node, node, ...], [dist, dist, ...], [reached or not], 
#       [dist from root], [color]]
    graph = [[[],[],0,0,0] for i in range(n)]
    for i in range(n-1):
        node1 = edge[i][0]
        node2 = edge[i][1]
        weight = edge[i][2]
        graph[node1-1][0].append(node2)
        graph[node2-1][0].append(node1)
        graph[node1-1][1].append(weight)
        graph[node2-1][1].append(weight)
    
    dfs(graph, 1, 0)
    for i in range(n):
        print(graph[i][4])

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
n=int(input())
graph=[[False]*n for i in range(n)] #点の隣接連結を示す
color=[0]*n
visited=[False]*n #dfsを書くときに訪問した点を記録する
for i in range(n-1):
    a,b,c=map(int,input().split())
    graph[a-1][b-1][0],graph[b-1][a-1][0],graph[a-1][b-1][1],graph[b-1][a-1][1]=True,True,c,c
def dfs(v):
    visited[v]=True
    for i in range(n):
        if graph[v][i]==False:continue
        if visited[i]==True:continue
        color[i]=color[v]^(graph[v][i][1]%2)
        dfs(i)#訪問済みでなく辺によってつながれている頂点に対して同じ操作を繰り返す
for i in range(n):
  dfs(i)
print(ans)

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
graph=[[False]*n for i in range(n)] #点の隣接連結を示す
color=[0]*n
visited=[False]*n #dfsを書くときに訪問した点を記録する
for i in range(m):
    a,b,c=map(int,input().split())
    graph[a-1][b-1][0],graph[b-1][a-1][0],graph[a-1][b-1][1],graph[b-1][a-1][1]=True,True,c,c
def dfs(v):
    visited[v]=True
    for i in range(n):
        if graph[v][i]==False:continue
        if visited[i]==True:continue
        color[i]=color[v]^(graph[v][i][1]%2)
        dfs(i)#訪問済みでなく辺によってつながれている頂点に対して同じ操作を繰り返す
for i in range(n):
  dfs(i)
print(ans)

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
graph=[[False]*n for i in range(n)] #点の隣接連結を示す
color=[0]*n
visited=[False]*n #dfsを書くときに訪問した点を記録する
for i in range(m):
    a,b,c=map(int,input().split())
    graph[a-1][b-1][0],graph[b-1][a-1][0],graph[a-1][b-1][1],graph[b-1][a-1][1]=True,True,c,c
def dfs(v):
    visited[v]=True
    for i in range(n):
        if graph[v][i]==False:continue
        if visited[i]==True:continue
        color[i]=color[v]^(graph[v][i]%2)
        dfs(i)#訪問済みでなく辺によってつながれている頂点に対して同じ操作を繰り返す
for i in range(n):
  dfs(i)
print(ans)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(20000)

N = int(input())
W = [list(map(int, input().split())) for _ in range(N-1)]
nodes = [[] for _ in range(N+1)]
for w in W:
    nodes[w[0]].append((w[1], w[2]))
    nodes[w[1]].append((w[0], w[2]))
ans = [-1] * (N+1)
ans[1] = 0
def search(num, root, dis):
    for node in nodes[num]:
        sum_d = dis
        if node[0] != root:
            idx = node[0]
            sum_d += node[1]%2
            if sum_d%2 != 0:
                ans[idx] = 1
            else:
                ans[idx] = 0
            search(idx, num, sum_d)

search(1, 0, 0)
for answer in ans[1:]:
    print(answer)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10000)

N = int(input())
W = [list(map(int, input().split())) for _ in range(N-1)]
nodes = [[] for _ in range(N+1)]
for w in W:
    nodes[w[0]].append((w[1], w[2]))
    nodes[w[1]].append((w[0], w[2]))
ans = [-1] * (N+1)
ans[1] = 0
def search(num, root, dis):
    for node in nodes[num]:
        sum_d = dis
        if node[0] != root:
            idx = node[0]
            sum_d += node[1]%2
            if sum_d%2 != 0:
                ans[idx] = 1
            else:
                ans[idx] = 0
            search(idx, num, sum_d)

search(1, 0, 0)
for answer in ans[1:]:
    print(answer)

Submission status: Runtime Error

Solution code:
def paint(point, color):
    colors[point] = color

    # その点とつながる点で、まだ色が塗られていない点にルールに従い色を塗る
    for friend, w in reration[point]:
        if not colors[friend]:  # 塗られてない点
            # print(str(i)+"塗る")
            nextcolor = color*(-1)**w
            paint(friend, nextcolor)


N = int(input())
reration = [[] for i in range(N)]  # その点がつながる点
colors = ["" for i in range(N)]  # 色(作業中は簡単のため1,-1の2つに塗り分ける)
for i in range(N-1):
    U, V, W = map(int, input().split())
    reration[U-1].append((V-1, W % 2))
    reration[V-1].append((U-1, W % 2))

# print(hen)
# print(reration)
for i in range(N):
    if not colors[i]:
        paint(i, 1)
for co in colors:
    print((co+1)//2)

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
write = lambda x: sys.stdout.write(str(x))
LMIIS = lambda : list(map(int,input().split()))
II = lambda : int(input())
dbg = lambda *something : print(*something) if DEBUG is True else 0
DEBUG = False

def main():

    N = II()
    t = [-1] * N


    E = [  [] for _ in range(N)]
 
    reached = [False] * N
    for _ in range(N-1):
        u,v,w = LMIIS()
        u -=1
        v -=1
        E[u].append((v,w))
        E[v].append((u,w))
    dbg(E)
    t[E[0][0][0]] = 0

     
    def search(u):
        for v,w in E[u]:
            if t[v] == -1:
                t[v] = t[u] if w % 2 == 0 else t[u]^1
                search(v)
                

    search(E[0][0][0])

    for i in t:
        write(i)
        write(' ')






    pass
if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(5000)

N = int(input())
W = [list(map(int, input().split())) for _ in range(N-1)]
nodes = [[] for _ in range(N+1)]
for w in W:
    nodes[w[0]].append((w[1], w[2]))
    nodes[w[1]].append((w[0], w[2]))
ans = [-1] * (N+1)
ans[1] = 0
def search(num, root, dis):
    for node in nodes[num]:
        if node[0] != root:
            idx = node[0]
            dis += node[1]%2
            if dis%2 != 0:
                ans[idx] = 1
            else:
                ans[idx] = 0
            search(idx, num, dis)

search(1, 0, 0)
for answer in ans[1:]:
    print(answer)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(5000)

N = int(input())
W = [list(map(int, input().split())) for _ in range(N-1)]
nodes = [[] for _ in range(N+1)]
for w in W:
    nodes[w[0]].append((w[1], w[2]))
    nodes[w[1]].append((w[0], w[2]))
ans = [0] * (N+1)
def search(num, root, dis):
    for node in nodes[num]:
        if node[0] != root:
            idx = node[0]
            dis += node[1]%2
            if dis%2 != 0:
                ans[idx] = 1
            search(idx, num, dis)

search(1, 0, 0)
for answer in ans[1:]:
    print(answer)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(5000)

N = int(input())
W = [list(map(int, input().split())) for _ in range(N-1)]
len_w = N-1
ans = [0] * (N+1)
def search(num, root, dis):
    # nodes = tuple(filter(lambda x:x[0] == num or x[1] == num, W))
    nodes = []
    global len_w
    for i in range(len_w):
        if i == len_w:
            break
        if W[i][0] == num or W[i][1] == num:
            nodes.append(W[i])
            del W[i]
            len_w -= 1
    for node in nodes:
        if node[0] != root and node[1] != root:
            idx = node[1] if node[0] == num else node[0]
            dis += node[2]%2
            if dis%2 != 0:
                ans[idx] = 1
            search(idx, num, dis)
        # else:
        #     dis += node[2]%2
        #     if dis%2 != 0:
        #         idx = node[1] if node[0] == num else node[0]
        #         ans[idx] = 1

search(1, 0, 0)
for answer in ans[1:]:
    print(answer)

Submission status: Runtime Error

Solution code:
import numpy as np
from collections import deque

n = int(input())
matrix = np.zeros((n,n),dtype="int32")
for i in range(n-1):
    v,w,d = map(int,input().split())
    matrix[v-1,w-1] = d
#print(matrix)

queue = deque([0])
no_check = [i for i in range(1,n)]
ans = np.zeros((n),dtype="int32")

while queue:
    x = queue.popleft()
    #print("x:",x)
    if no_check == []:
        break
    for i in no_check:
        if matrix[x,i]!=0:
            if matrix[x,i]%2==0:
                ans[i] = ans[x]
            else:
                if ans[x]==0:
                    ans[i] = 1
                else:
                    ans[i] = 0
            no_check.remove(i)
            queue.append(i)
        
                
for i in ans:
    print(i)

Submission status: Runtime Error

Solution code:
import numpy as np
from collections import deque

n = int(input())
matrix = np.zeros((n,n),dtype="int32")
for i in range(n-1):
    v,w,d = map(int,input().split())
    matrix[v-1,w-1] = d
#print(matrix)

queue = deque([0])
check = [0]
ans = np.zeros((n),dtype="int32")

while queue:
    x = queue.popleft()
    #print("x:",x)
    for i in range(n):
        #print("i:",i,"check:",check)
        if i not in check:
            if matrix[x,i] != 0:
                #print("d:",matrix[x,i])
                if matrix[x,i]%2==0:
                    #print("even")
                    ans[i] = ans[x]
                else:
                    #print("odd")
                    if ans[x] == 0:
                        ans[i] = 1
                    else:
                        ans[i] = 0
                check.append(i)
                queue.append(i)
                #print("APPEND check:",check,"queue:",queue)
                
for i in ans:
    print(i)

Submission status: Runtime Error

Solution code:
N = int(input())

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

ans = [None for _ in range(N)]


def dfs(v, p, c):
    ans[v - 1] = c
    for next_v, distance in neighbors[v]:
        if next_v == p:
            continue
        next_c = c if distance % 2 == 0 else 1 - c
        dfs(next_v, v, next_c)


dfs(1, -1, 0)
for e in ans:
    print(e)

Submission status: Runtime Error

Solution code:
N = int(input())

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

ans = [None for _ in range(N + 1)]


def dfs(v, p, c):
    ans[v] = c
    for next_v, distance in neighbors[v]:
        if next_v == p:
            continue
        next_c = c if distance % 2 == 0 else 1 - c
        dfs(next_v, v, next_c)


dfs(1, -1, 0)
for e in ans[1:]:
    print(e)

Submission status: Runtime Error

Solution code:
N = int(input())

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

ans = [None for _ in range(N + 1)]
ans[1] = 0


def dfs(v, p, c):
    for next_v, distance in neighbors[v]:
        if next_v == p:
            continue
        next_c = c if distance % 2 == 0 else abs(c - 1)
        ans[next_v] = next_c
        dfs(next_v, v, next_c)


dfs(1, -1, 0)
for e in ans[1:]:
    print(e)

Submission status: Runtime Error

Solution code:
N = int(input())

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

ans = [None for _ in range(N + 1)]
ans[1] = 0
seen = set()


def dfs(v, color):
    seen.add(v)
    for next_v, distance in neighbors[v]:
        if next_v in seen:
            continue
        next_color = color if distance % 2 == 0 else abs(color - 1)
        ans[next_v] = next_color
        dfs(next_v, next_color)


dfs(1, 0)
for e in ans[1:]:
    print(e)

Submission status: Runtime Error

Solution code:
MAX=10**5+5
tree=[[] for _ in range(MAX)]
ans = [-1]*(MAX)
def dfs(x,weight):
    if(ans[x]>=0):
        return
    ans[x]=weight&1
    for i,w in tree[x]:
        dfs(i,weight+w)

def resolve():
    n =int(input())
    for i in range(n-1):
        u,v,w = map(int,input().split())
        tree[u].append((v,w))
        tree[v].append((u,w))
    dfs(1,0)
    
    for i in range(1,n+1):
        print(ans[i])


if __name__ == "__main__":
    resolve()

Submission status: Runtime Error

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

class UnionFind:
    def __init__(self, n):
        # 親要素のノード番号を格納。par[x] == xの時そのノードは根
        self.par = [i for i in range(n+1)]
        # 木の高さを格納する（初期状態では0）
        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.par[x]

    # 同じ集合に属するか判定
    def same_check(self, 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
            # 木の高さが同じなら片方を1増やす
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

uf=UnionFind(n)
for i in range(n-1):
    if vvw[i][2]%2==1:
        uf.union(vvw[i][0], vvw[i][1])

ans=[]
for i in range(1,n+1):
    # print(ans)
    if uf.par[i]==i:
        print(0)
        ans.append(0)
    else:
        # print(uf.par[i])
        if ans[uf.par[i]-1]==1:
            print(0)
            ans.append(0)
        else:
            print(1)
            ans.append(1)

    # print(0 if uf.par[i]%2==0 else 1)

Submission status: Runtime Error

Solution code:
n = int(input())
lis = [[] for i in range(n)]

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

li = [-1] * n

def calc(i,c):
    li[i] = c
    for j, w in lis[i]:
        if li[j] < 0:
            calc(j, li[i]^w)

calc(0,0)
for d in li:
    print(d)

Submission status: Runtime Error

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

A = [0] * (N)
L.sort()
for i in L:
    if i[2]%2 != 0 and L[i[0]] == L[i[1]]:
        L[i[0]] = (L[i[0]]+1)%2
    elif i[2]%2 == 0:
        L[i[1]] = L[i[0]]
for i in A:
    print(i)

Submission status: Runtime Error

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

A = [0] * (N)
L.sort()
for i in L:
    if i[2]%2 != 0 and L[i[0]] == L[i[1]]:
        L[i[0]] = !L[i[0]]
    elif i[2]%2 == 0:
        L[i[1]] = L[i[0]]
for i in A:
    print(i)

Submission status: Runtime Error

Solution code:
#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <utility>
#include <stack>
#include <numeric>
#include <algorithm>
#include <bitset>
#include <complex>
#include <iomanip>
using namespace std;
typedef long long ll;
typedef long long int llint;
#define MM 1000000000
#define MOD MM+7
#define pi pair<int,int>
#define pl pair<ll,ll>
#define chmax(a,b) (a<b ? a=b:0)
#define chmin(a,b) (a>b ? a=b:0)
const long double PI = acos(-1);
const long long INF = 1e15;
int dx[8] = {-1,0,1,0,-1,-1,1,1};
int dy[8] = {0,-1,0,1,-1,1,1,-1};
template<typename T>
T GCD(T u,T v){
    return v ? GCD(v,u%v) : u;
}

int main(){
    ll N; cin >> N;
    vector<vector<pair<ll,ll>>> G(N);
    for(int i = 0; i < N-1; i++){
        ll a,b,w; cin >> a >> b >> w;
        a--; b--;
        w %= (ll)2;
        G[a].push_back({b,w});
        G[b].push_back({a,w});
    }
    vector<ll> dist(N,-1);
    queue<ll> que;
    for(ll v = 0; v < N; v++){
        if (dist[v] != -1) continue;
        dist[v] = 0;
        que.push(v);
        while(que.size()){
            ll s = que.front();
            que.pop();
            for(ll nv = 0; nv < G[s].size(); nv++){
                if (dist[G[s][nv].first] == -1){
                    dist[G[s][nv].first] = dist[s]+G[s][nv].second;
                    dist[G[s][nv].first] %= 2;
                    que.push(dist[G[s][nv].first]);
                } 
            }
        }
    }
    for(int i = 0; i < N; i++){
        cout << dist[i] << endl;
    }
}

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(100)

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


if __name__ == '__main__':
	N = int(input())
	tree = [ [] for _ in range(N) ]
	
	for i in range(N-1):
		u,v,w = map(int, input().split())
		tree[u-1].append([v-1, w])
		tree[v-1].append([u-1, w])
	ans = [-1]*(N)
	dfs(0, 0)
	[print(i) for i in ans]

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(1000)

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


if __name__ == '__main__':
	N = int(input())
	tree = [ [] for _ in range(N) ]
	
	for i in range(N-1):
		u,v,w = map(int, input().split())
		tree[u-1].append([v-1, w])
		tree[v-1].append([u-1, w])
	ans = [-1]*(N)
	dfs(0, 0)
	[print(i) for i in ans]

Submission status: Runtime Error

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


if __name__ == '__main__':
	N = int(input())
	tree = [ [] for _ in range(N) ]
	
	for i in range(N-1):
		u,v,w = map(int, input().split())
		tree[u-1].append([v-1, w])
		tree[v-1].append([u-1, w])
	ans = [-1]*(N)
	dfs(0, 0)
	[print(i) for i in ans]

Submission status: Runtime Error

Solution code:
from collections import deque
import sys
sys.setrecursionlimit(5000000000)

ans = {1:1}

def dfs(tree,nodes):
    for node in nodes:
        nexts = tree[node]
        for next,l in nexts.items():
            if l% 2 == 0 :
                ans[next] = ans[node]
            else:
                ans[next] = 1 - ans[node]
            tree[next].pop(node)

        dfs(tree,nexts)

    return 0




if __name__ == "__main__":
    tree= {}
    N = int(input())
    if N == 1:
        u, v, w = list(map(int, input().split(" ")))
        if w %2 == 1:
            print(1)
            print(0)
        else:
            print(0)
            print(0)
    else:
        for i in range(N-1):
            u,v,w = list(map(int,input().split(" ")))

            if u not in tree:
                tree[u] = {}
            tree[u][v] = w

            if v not in tree:
                tree[v] = {}
            tree[v][u] = w
        dfs(tree,[1])
        for i in range(1,N+1):
            print(ans[i])

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(2000)
N = int(input())
es = [[] for i in range(N+1)]
for i in range(N-1):
    u, v, w = map(int, input().split())
    es[u].append([v,w])
    es[v].append([u,w])
dfs_map = [1 for i in range(N+1)]
col = [None] * (N+1)
def dfs(v, c):
    col[v] = c
    for e in es[v]:
        if dfs_map[e[0]]:
            dfs_map[e[0]] = 0
            if e[1] % 2:
                dfs(e[0], c^1)
            else:
                dfs(e[0], c)
dfs_map[1] = 0
dfs(1, 0)
for i in range(1, N+1):
    print(col[i])

Submission status: Runtime Error

Solution code:
N = int(input())
es = [[] for i in range(N+1)]
for i in range(N-1):
    u, v, w = map(int, input().split())
    es[u].append([v,w])
    es[v].append([u,w])
dfs_map = [1 for i in range(N+1)]
col = [None] * (N+1)
def dfs(v, c):
    col[v] = c
    for e in es[v]:
        if dfs_map[e[0]]:
            dfs_map[e[0]] = 0
            if e[1] % 2:
                dfs(e[0], c^1)
            else:
                dfs(e[0], c)
dfs_map[1] = 0
dfs(1, 0)
for i in range(1, N+1):
    print(col[i])

Submission status: Runtime Error

Solution code:
N = int(input())
es = [[] for i in range(N+1)]
for i in range(N-1):
    u, v, w = map(int, input().split())
    es[u].append([v,w])
    es[v].append([u,w])
dfs_map = [1 for i in range(N+1)]
col = [None] * (N+1)
def dfs(v, c):
    col[v] = c
    for e in es[v]:
        if dfs_map[e[0]]:
            dfs_map[e[0]] = 0
            if e[1] % 2:
                dfs(e[0], c^1)
            else:
                dfs(e[0], c)
dfs(1, 0)
for i in range(1, N+1):
    print(col[i])

Submission status: Runtime Error

Solution code:
def find(n,X,V):
	if V[X[n][0]] == None:
		find(X[n][0],X,V)
		find(n,X,V)
	else:
		V[n] = (V[X[n][0]] + X[n][1]) %2

N = int(input())
X = [(0,0)]*(N+1)
V = [None]*(N+1)
V[0] = 0
used = set()
for n in [None]*(N-1):
	a, b, c = map(int,input().split())
	if {a, b} <= used and X[b] != (0,0):
		X[a] = (b, c%2)
	elif {a, b} <= used :
		X[b] = (a, c%2)
	elif {a} <= used :
		X[b] = (a, c%2)
		used.add(b)
	elif {b} <= used :
		X[a] = (b, c%2)
		used.add(a)
	else:
		X [b] = (a, c%2)
		used.add(a)
		used.add(b)
print(X)
print(V)
for k in range(1, N+1):
	if V[k] == None:
		find(k,X,V)
	print(V[k])

Submission status: Runtime Error

Solution code:
def find(n,X,V):
	if V[X[n][0]] == None:
		find(X[n][0],X,V)
		find(n,X,V)
	else:
		V[n] = (V[X[n][0]] + X[n][1]) %2

N = int(input())
X = [(0,0)]*(N+1)
V = [None]*(N+1)
V[0] = 0
used = set()
for n in [None]*(N-1):
	a, b, c = map(int,input().split())
	if {a, b} <= used and X[b] != (0,0):
		X[a] = (b, c%2)
	elif {a, b} <= used :
		X[b] = (a, c%2)
	elif {a} <= used :
		X[b] = (a, c%2)
		used.add(b)
	elif {b} <= used :
		X[a] = (b, c%2)
		used.add(a)
	else:
		X [b] = (a, c%2)
		used.add(a)
		used.add(b)
for k in range(1, N+1):
	if V[k] == None:
		find(k,X,V)
	print(V[k])

Submission status: Runtime Error

Solution code:
def find(n,X,V):
	if V[X[n][0]] == None:
		find(X[n][0],X,V)
		find(n,X,V)
	else:
		V[n] = (V[X[n][0]] + X[n][1]) %2

N = int(input())
X = [(0,0)]*(N+1)
V = [None]*(N+1)
V[0] = 0
used = set()
for n in [None]*(N-1):
	a, b, c = map(int,input().split())
	if {a, b} <= used :
		X[b] = (a, c%2)
	elif {a} <= used :
		X[b] = (a, c%2)
		used.add(b)
	elif {b} <= used :
		X[a] = (b, c%2)
		used.add(a)
	else:
		X [b] = (a, c%2)
		used.add(a)
		used.add(b)
for k in range(1, N+1):
	if V[k] == None:
		find(k,X,V)
	print(V[k])

Submission status: Runtime Error

Solution code:
def find(n,X,V):
	if V[n] != None:
		return
	elif V[X[n][0]] == None:
		find(X[n][0],X,V)
		find(n,X,V)
	else:
		V[n] = (V[X[n][0]] + X[n][1]) %2

N = int(input())
X = [(0,0)]*(N+1)
V = [None]*(N+1)
V[0] = 0
used = set()
for n in [None]*(N-1):
	a, b, c = map(int,input().split())
	if {a, b} <= used :
		X[b] = (a, c%2)
	elif {a} <= used :
		X[b] = (a, c%2)
		used.add(b)
	elif {b} <= used :
		X[a] = (b, c%2)
		used.add(a)
	else:
		X [b] = (a, c%2)
		used.add(a)
		used.add(b)
for k in range(1, N+1):
	find(k,X,V)
	print(V[k])

Submission status: Runtime Error

Solution code:
def find(n,X,V):
	if V[n] != None:
		return
	elif V[X[n][0]] == None:
		find(X[n][0],X,V)
		find(n,X,V)
	else:
		V[n] = (V[X[n][0]] + X[n][1]) %2

N = int(input())
X = [(0,0)]*(N+1)
V = [None]*(N+1)
V[0] = 0
used = set()
for n in [None]*(N-1):
	a, b, c = map(int,input().split())
	if {a, b} <= used :
		print(ERROR)
	elif {a} <= used :
		X[b] = (a, c%2)
		used.add(b)
	elif {b} <= used :
		X[a] = (b, c%2)
		used.add(a)
	else:
		X [b] = (a, c%2)
		used.add(a)
		used.add(b)
for k in range(1, N+1):
	find(k,X,V)
	print(V[k])

Submission status: Runtime Error

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

class Path:
    def __init__(self, next_node, length, num):
        self.next=next_node
        self.len=length
        self.num=num

class Node:
    def __init__(self, index):
        self.index = index
        self.paths = []

    def append(self, next_node, length, num):
        self.paths.append(Path(next_node, length, num))

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

past_paths = [0]*(N-1)
paints = [-1]*N

def rec(pos, color):
    if paints[pos] == -1:
        paints[pos] = color
    for path in nodes[pos].paths:
        # まだ通ってない道を通る
        if past_paths[path.num] == 0:
            past_paths[path.num] = 1
            rec(path.next, (color + path.len) % 2)
        # さっきの道を戻ってくる

rec(0, 0)

for i in paints:
    print(i)

Submission status: Runtime Error

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

class Path:
    def __init__(self, next, length, num):
        self.next=next
        self.len=length
        self.num=num

class Node:
    def __init__(self, index):
        self.index = index
        self.paths = []

    def append(self, next, length, num):
        self.paths.append(Path(next, length, num))

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

past_paths = [0]*(N-1)
paints = [-1]*N

def rec(pos, color):
    if paints[pos] == -1:
        paints[pos] = color
    for path in nodes[pos].paths:
        # まだ通ってない道を通る
        if past_paths[path.num] == 0:
            past_paths[path.num] = 1
            if path.len % 2 == 1:
                rec(path.next, (color + 1) % 2)
            else:
                rec(path.next, color)
        # さっきの道を戻ってくる

rec(0, 0)

for i in paints:
    print(i)

Submission status: Runtime Error

Solution code:
###template###
import sys
def input(): return sys.stdin.readline().rstrip()
def mi(): return map(int, input().split())
###template###

N = int(input())

adj = [set() for _ in range(N)] #adj[i] = (i_adj, 距離0or1)
for _ in range(N-1):
  u, v, w = mi()
  #0スタートに
  u -= 1
  v -= 1
  adj[u].add((v, w%2))
  adj[v].add((u, w%2))

from collections import deque
q = deque([])

seen = [0] * N
bw = [0] * N

#とりあえずノード0から探索をスタートすることにする
#0の距離は0としておく
q.append(0)
bw[0] = 0 #必要無いが、分かりやすくするために
seen[0] = 1


def solve(): #前のノードまでの色（0or1）を引き継ぐ
  try: nownode = q.popleft()
  except: return
  nowcolor = bw[nownode]

  #今のノードから隣接しているものを探索
  for adjidx, w in adj[nownode]:
    if seen[adjidx]!=1:
      q.append(adjidx)
      seen[adjidx]=1
      bw[adjidx] = (nowcolor+w)%2

  solve()

solve()

for color in bw:
  print(color)

Submission status: Runtime Error

Solution code:
N = int(input())
color = [ [] for i in range(N)]

def updateColor( color, i, from_i, c):
    if len(color[i]) == 1 and color[i][0][0] == from_i:
        color[i] = c
    else:
        for l in color[i]:
            if l[1] == 'Same':
                updateColor( color, l[0], c)
            else:
                updateColor( color, l[0], 1-c)


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

            for l in color[v]:
                if l[1] == "Same":
                    updateColor( color, l[0], temp )
                else:
                    updateColor( color, l[0], 1-temp )
            color[v] = temp

        elif color[v] in (0,1):
            if w%2 == 0:
                temp = color[v]
            else:
                temp = 1-color[v]
                
            for l in color[u]:
                if l[1] == "Same":
                    updateColor( color, l[0], temp )
                else:
                    updateColor( color, l[0], 1-temp )
            color[u] = temp

        else:
            if w%2 == 0:
                color[u].append([v, "Same"])
                color[v].append([u, "Same"])
            else:
                color[u].append([v, "Diff"])
                color[v].append([u, "Diff"])

for c in color:
    print(c)

Submission status: Runtime Error

Solution code:
import collections

N = int(input())
lst = []
ctr_lst = []

for n in range(N - 1):
	u, v, w = map(int, input().split())
	# 偶数はどうでもいいので、奇数の場合のみを拾い上げる
	if w % 2 == 1:
		lst.append([u, v])
		for i in [u, v]:
			if len(ctr_lst) == 0 or i != ctr_lst[-1]:
				ctr_lst.append(i)

#頂点数
ver_num = len(ctr_lst)	
# print("ver_num = {}".format(ver_num))

if ver_num == 0:
	for i in range(N):
		print(0)
else:
	for i in range(ver_num):
		flg = 1
		binary = list(str(bin(i)))
		for j in range(ver_num - len(binary) + 2):
			binary.insert(2, "0")
		# print("binary={}".format(binary))
		
		for k in range(len(lst)):
			if (int(binary[lst[k][0]]) + int(binary[lst[k][1]])) % 2 == 0:
				flg = 0
				break
		if flg == 1:
			for n in range(1, N + 1):
				if ctr_lst[0] != n:
					print(0)
				else:
					t = ctr_lst.pop(0)
					# print(t)
					print(binary[1 + t - 1])

Submission status: Runtime Error

Solution code:
N = int(input())

A = {}
COLOR = [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] = {}
  A[u][v] = w
  A[v][u] = w


def test(key, total_w=0):
  if key not in A:
    return

  COLOR[key - 1] = 0 if total_w % 2 == 0 else 1

  v = A.pop(key)
  for k, w in v.items():
    test(k, w + total_w)


test(1)

for c in COLOR:
  print(c)