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: Wrong Answer

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

N = int(input())
d = [[] for _ in range(N)]
iro = [0] * (N)

def dfs(n, v):
    for i in d[n]:
        if v == i[0]:
            continue
        if i[1] % 2 != 0:
            iro[i[0]] = 1
        dfs(i[0], n)

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

dfs(0, 0)
for i in iro:
    print(i)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict, deque

N = int(input())

edges = defaultdict(list)

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


colors = [None] * N
colors[0] = 0
que = deque([0])

while que:
    u = que.popleft()
    for v, w in edges[u]:
        if colors[v] != None:
            continue
        if edges[v] != []:
            que.append(v)

        if w % 2 == 0:
            colors[v] = colors[u]
        else:
            colors[v] = 1 ^ colors[u]

for c in colors:
    print(c)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict, deque

N = int(input())

g = defaultdict(list)

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


def bfs(g, start, N):
    dist = [0] * (N + 1)
    checked = [False] * (N+1)
    q = deque()
    q.append([start, 1])

    while len(q) > 0:
        node = q.popleft()
        # u -(w)> v
        u = node[1]
        v = node[0][0]
        w = node[0][1]
        # print(u, v, w, g[v])

        if checked[v]:
            continue
        checked[v] = True
        dist[v] = w

        for next_v in g[v]:
            q.append([[next_v[0], w + next_v[1]], v])

    return dist


dist = bfs(g, g[1][0], N)
ans = [0] * (N+1)
for i in range(2, N+1):
    if (dist[i] + dist[i-1]) % 2 == 0:
        ans[i] = ans[i-1]
    else:
        ans[i] = (ans[i-1] + 1) % 2

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

Submission status: Wrong Answer

Solution code:
from collections import defaultdict, deque

N = int(input())

g = defaultdict(list)

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


def bfs(g, start, N):
    ret = [0] * (N + 1)
    checked = [False] * (N+1)
    q = deque()
    q.append([start, 1])

    while len(q) > 0:
        node = q.popleft()
        # u -(w)> v
        u = node[1]
        v = node[0][0]
        w = node[0][1]
        #print(u, v, w, g[v])

        if checked[v]:
            continue
        checked[v] = True

        ret[v] = ret[u] if w % 2 == 0 else (ret[u] + 1) % 2

        for next_v in g[v]:
            q.append([next_v, v])

    return ret


ans = bfs(g, g[1][0], N)
for i in range(1, N+1):
    print(ans[i])

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
n=int(input())
if n<2:
    print(1)
    exit()
A=[0 for _ in range(n)]
for i in range(n-1):
    u,v,w=map(int,input().split())
    if w%2>0 and A[u-1]<1:A[v-1]=1
    elif w%2<1 and A[u-1]!=A[v-1]:A[u-1]=A[v-1]=1
for a in A:print(a)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

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

dis = [0]*n
dis[0]=0

while Q:
    num=Q.popleft()

    for tmp in l:
        if tmp[0]-1 == num:
            nxt=tmp[1]-1
            Q.append(nxt)
            dis[nxt] = dis[num] + tmp[2]

for a in dis:
    print(a%2)

Submission status: Wrong Answer

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

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

ans = [0]*n
ans[0]=0 # first white

while Q:
    num=Q.popleft()

    for tmp in l:
        if tmp[0]-1 == num:
            nxt=tmp[1]-1
            Q.append(nxt)
            if tmp[2] %2 == 0:
                ans[nxt] = ans[num]
            else:
                ans[nxt] = (ans[num] + 1)%2

for a in ans:
    print(a)

Submission status: Wrong Answer

Solution code:
from collections import deque

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

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

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


def dfs(g, s):
    stack = deque()

Submission status: Wrong Answer

Solution code:
n = int(input())
ab = []
for _ in range(n-1):
    a, b, c = (int(x) for x in input().split())
    ab.append([a-1, b-1, c])

ab.sort()
dp = [-1] * n
dp[0] = 0

for a, b ,c in ab:
    if dp[b] == -1 and dp[a] != -1 and c%2 == 0:
        dp[b] = dp[a]
    elif dp[b] == -1 and dp[a] != -1 and c%2 == 1:
        if dp[a] == 0:
            dp[b] = 1
        else:
            dp[b] = 0
    elif dp[b] == -1 and dp[a] == -1 and c%2 == 0:
        dp[b] = 0
        dp[a] = 0
    elif dp[b] == -1 and dp[a] == -1 and c%2 == 1:
        dp[b] = 1
        dp[a] = 0

for i in dp:
    print(i)

Submission status: Wrong Answer

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

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

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

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

Submission status: Wrong Answer

Solution code:
N = int(input())
color = [0]*(N+1)
color_val = 0
finded = set()
codebook = {-1:0, 1:1}

for _ in range(N-1):
    u, v, w = map(int, input().split())
    if u in finded and v in finded:
        if color[u] not in codebook and color[v] not in codebook:
            codebook[color[u]] = (1 - 2*(w % 2)) * color[v]
            codebook[- color[u]] = - codebook[color[u]]
            codebook[color[v]] = (1 - 2*(w % 2)) * color[u]
            codebook[- color[v]] = - codebook[color[v]]
        elif color[u] not in codebook:
            codebook[color[u]] = (1 - 2*(w % 2)) * codebook[color[v]]
            codebook[- color[u]] = - codebook[color[u]]
        elif color[v] not in codebook:
            codebook[color[v]] = (1 - 2*(w % 2)) * codebook[color[u]]
            codebook[- color[v]] = - codebook[color[v]]
        else:
            if abs(codebook[color[u]]) > abs(codebook[color[v]]):
                codebook[color[u]] = (1 - 2*(w % 2)) * codebook[color[v]]
                codebook[- color[u]] = - codebook[color[u]]
            else:
                codebook[color[v]] = (1 - 2*(w % 2)) * codebook[color[u]]
                codebook[- color[v]] = - codebook[color[v]]
    elif u in finded:
        finded.add(v)
        color[v] = (1 - 2*(w % 2)) * color[u] 
    elif v in finded:
        finded.add(u)
        color[u] = (1 - 2*(w % 2)) * color[v]
    else:
        finded.add(u)
        finded.add(v)
        color_val += 1
        if w % 2 == 0:
            color[u], color[v] = color_val, color_val
        if w % 2 != 0:
            color[u], color[v] = color_val, - color_val

while len(set(codebook.values())) != 2:
    for i in range(2, color_val + 1):
        inds = set()
        while codebook[i] != (0 and 1):
            inds.add(i)
            i = codebook[i]
        for ind in inds:
            codebook[ind] = codebook[i]

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

Submission status: Wrong Answer

Solution code:
def root(v):
    if v == par[v]:
        return v
    r = root(par[v])
    diff_dist[v] += diff_dist[par[v]]
    par[v] = r
    return r

def dist(v):
    root(v)
    return diff_dist[v]

def unite(u, v, w):
    w += (dist(u) - dist(v))
    u = root(u)
    v = root(v)
    if u == v:
        return 
    if rank[u] < rank[v]:
        u, v = v, u
        w = -w
    par[v] = u
    diff_dist[v] = w
    if rank[u] == rank[v]:
        rank[u] += 1

N = int(input())
par = list(range(N+1))
rank = [0] * (N + 1)
diff_dist = [0] * (N + 1)
for _ in range(N-1):
    u, v, w = map(int, input().split())
    unite(u, v, w)

print(*[diff_dist[v] % 2 for v in range(1, N+1)], sep="\n")

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
class branch:
    def __init__(self, num:int, top:int, long:int):
        self.num = num

        self.top = [top]
        self.long = [long]

def my_index(l, x):
    if x in l:
        return l.index(x)
    else:
        return -1


def make_list(num,top,long):
    if num == top:
        return

    global list
    if list[num]==None:
        list[num] = branch(1,top,long)
    else:
        if my_index(list[num].top,top)==-1:
            list[num].num += 1
            list[num].top.append(top)
            list[num].long.append(long)
            for i in range(list[num].num):
                make_list(top,list[num].top[i],long+(list[num].long[i]))
        else:
            if list[num].long[my_index(list[num].top,num)] > long:
                list[num].long[my_index(list[num].top,num)] = long
                for i in range(list[num].num):
                    make_list(top,list[num].top[i],long+(list[num].long[i]))

    if list[top]==None:
        list[top] = branch(1,num,long)
    else:
        if my_index(list[top].top,num)==-1:
            list[top].num += 1
            list[top].top.append(num)
            list[top].long.append(long)
            for i in range(list[top].num):
                make_list(num,list[top].top[i],long+(list[top].long[i]))
        else:
            if list[top].long[my_index(list[top].top,top)] > long:
                list[top].long[my_index(list[top].top,top)] = long
                for i in range(list[top].num):
                    make_list(num,list[top].top[i],long+(list[top].long[i]))




N = 0
top = []
list = []

N = int(input())
for i in range(N+1):
    top.insert(i,2)

for i in range(N+1):
    list.insert(i,None)


for i in range(N-1):
    Input = input().split()
    num = [(int(Input[0]))]
    num.append(int(Input[1]))
    num.append(int(Input[2]))
    make_list(num[0],num[1],num[2])



for i in range(1,N+1,1):
    if list[i]==None:
        top[i] = 0
    else:
        if top[i] == 2:
            top[i] = 0;
            for j in range(list[i].num):
                if top[list[i].top[j]] != 2:
                    if list[i].long[j] % 2:
                        #print("=",j)
                        top[i] = top[list[i].top[j]]^1
                    break

            for j in range(list[i].num):
                if list[i].long[j] % 2:
                    top[list[i].top[j]] = top[i]^1
        else:
            for j in range(list[i].num):
                if list[i].long[j] % 2:
                    top[list[i].top[j]] = top[i]^1
    print(top[i])

Submission status: Wrong Answer

Solution code:
class branch:
    def __init__(self, num:int, top:int, long:int):
        self.num = num

        self.top = [top]
        self.long = [long]



N = 0
top = []
list = []

N = int(input())
for i in range(N+1):
    top.insert(i,2)

for i in range(N+1):
    list.insert(i,None)


for i in range(N-1):
    Input = input().split()
    num = [(int(Input[0]))]
    num.append(int(Input[1]))
    num.append(int(Input[2]))


    if list[num[0]]==None:
        list.insert(num[0],branch(1,num[1],num[2]))
    else:
        list[num[0]].num += 1
        list[num[0]].top.append(num[1])
        list[num[0]].long.append(num[2])

    if list[num[1]]==None:
        list.insert(num[1],branch(1,num[0],num[2]))
    else:
        list[num[1]].num += 1
        list[num[1]].top.append(num[0])
        list[num[1]].long.append(num[2])


for i in range(1,N+1,1):
    if list[i]==None:
        top[i] = 0
    else:
        if top[i] == 2:
            top[i] = 0;
            for j in range(list[i].num):
                if top[list[i].top[j]] != 2:
                    if list[i].long[j] % 2:
                        top[i] = top[list[i].top[j]]^1
                    break

            for j in range(list[i].num):
                if list[i].long[j] % 2:
                    top[list[i].top[j]] = top[i]^1
        else:
            for j in range(list[i].num):
                if list[i].long[j] % 2:
                    top[list[i].top[j]] = top[i]^1
    print(top[i])

Submission status: Wrong Answer

Solution code:
class branch:
    def __init__(self, num:int, top:int, long:int):
        self.num = num
        self.top = []
        self.long = []
        self.top.append(top)
        self.long.append(long)



N = 0
top = []
list = []

def setup():
    global N
    N = int(input())
    global top
    for i in range(N+1):
        top.insert(i,2)
    global list
    for i in range(N):
        list.insert(i,None)



setup();
num = []

for i in range(N-1):
    Input = input().split()
    num.append(int(Input[0]))
    num.append(int(Input[1]))
    num.append(int(Input[2]))


    if list[num[0]]==None:
        list.insert(num[0],branch(1,num[1],num[2]))
    else:
        list[num[0]].num += 1
        list[num[0]].top.append(num[1])
        list[num[0]].long.append(num[2])

    if list[num[1]]==None:
        list.insert(num[1],branch(1,num[0],num[2]))
    else:
        list[num[1]].num += 1
        list[num[1]].top.append(num[0])
        list[num[1]].long.append(num[2])

for i in range(1,N+1,1):
    if list[i]==None:
        top[i] = 0
    else:
        if top[i] == 2:
            top[i] = 0;
            for j in range(list[i].num):
                if top[list[i].top[j]] != 2:
                    if list[i].long[j] % 2:
                        top[i] = top[list[i].top[j]]^1
                    break

            for j in range(list[i].num):
                if list[i].long[j] % 2:
                    top[list[i].top[j]] = top[i]^1
                #else:
                    #top[list[i].top[j]] = top[i]
        else:
            for j in range(list[i].num):
                if list[i].long[j] % 2:
                    top[list[i].top[j]] = top[i]^1
                #else:
                    #top[list[i].top[j]] = top[i]
    print(top[i])

Submission status: Wrong Answer

Solution code:
class branch:
    def __init__(self, num:int, top:int, long:int):
        self.num = num
        self.top = []
        self.long = []
        self.top.append(top)
        self.long.append(long)



N = 0
top = []
list = []

def setup():
    global N
    N = int(input())
    global top
    for i in range(N+1):
        top.insert(i,2)
    global list
    for i in range(N):
        list.insert(i,None)



setup();
num = []

for i in range(N-1):
    Input = input().split()
    num.append(int(Input[0]))
    num.append(int(Input[1]))
    num.append(int(Input[2]))


    if list[num[0]]==None:
        list.insert(num[0],branch(1,num[1],num[2]))
    else:
        list[num[0]].num += 1
        list[num[0]].top.append(num[1])
        list[num[0]].long.append(num[2])

    if list[num[1]]==None:
        list.insert(num[1],branch(1,num[0],num[2]))
    else:
        list[num[1]].num += 1
        list[num[1]].top.append(num[0])
        list[num[1]].long.append(num[2])

for i in range(1,N+1,1):
    if list[i]==None:
        top[i] = 0
    else:
        if top[i] == 2:
            top[i] = 0;
            for j in range(list[i].num):
                if top[list[i].top[j]] != 2:
                    if list[i].long[j] % 2:
                        top[i] = top[list[i].top[j]]^1
                    else:
                        top[i] = top[list[i].top[j]]
                    break

            for j in range(list[i].num):
                if list[i].long[j] % 2:
                    top[list[i].top[j]] = top[i]^1
                else:
                    top[list[i].top[j]] = top[i]
        else:
            for j in range(list[i].num):
                if list[i].long[j] % 2:
                    top[list[i].top[j]] = top[i]^1
                else:
                    top[list[i].top[j]] = top[i]
    print(top[i])

Submission status: Wrong Answer

Solution code:
class branch:
    def __init__(self, num:int, top:int, long:int):
        self.num = num
        self.top = []
        self.long = []
        self.top.append(top)
        self.long.append(long)



N = 0
top = []
list = []

def setup():
    global N
    N = int(input())
    global top
    for i in range(N+1):
        top.insert(i,2)
    global list
    for i in range(N):
        list.insert(i,None)



setup();
num = []

for i in range(N-1):
    Input = input().split()
    num.append(int(Input[0]))
    num.append(int(Input[1]))
    num.append(int(Input[2]))


    if list[num[0]]==None:
        list.insert(num[0],branch(1,num[1],num[2]))
    else:
        list[num[0]].num += 1
        list[num[0]].top.append(num[1])
        list[num[0]].long.append(num[2])

    if list[num[1]]==None:
        list.insert(num[1],branch(1,num[0],num[2]))
    else:
        list[num[1]].num += 1
        list[num[1]].top.append(num[0])
        list[num[1]].long.append(num[2])

for i in range(1,N+1,1):
    if list[i]==None:
        top[i] = 0
    else:
        if top[i] == 2:
            top[i] = 0;
            for j in range(list[i].num):
                if top[list[i].top[j]] != 2:
                    if list[i].long[j] % 2:
                        top[i] = top[list[i].top[j]]
                    else:
                        top[i] = top[list[i].top[j]]^1
                    break

            for j in range(list[i].num):
                if list[i].long[j] % 2:
                    top[list[i].top[j]] = top[i]
                else:
                    top[list[i].top[j]] = top[i]^1
        else:
            for j in range(list[i].num):
                if list[i].long[j] % 2:
                    top[list[i].top[j]] = top[i]
                else:
                    top[list[i].top[j]] = top[i]^1
    print(top[i])

Submission status: Wrong Answer

Solution code:
N = int(input())
x = [[0 for i in range(3)] for j in range(N)]
y = [[0 for i in range(3)] for j in range(N)]
black = [0 for i in range(N * N)]
blackNum = 0

def blackf(u):
    global blackNum
    for i in range(blackNum):
        if black[i] == u:
            break

    else:
        black[blackNum] = u
        blackNum = blackNum + 1



for i in range(N - 1):
    x[i] = input().split()

for i in range(len(x)):
    y[i] = [int(j) for j in x[i]]


for i in range(N - 1):
    if y[i][2] % 2 == 0:
        blackf(y[i][0])
        blackf(y[i][1])

for i in range(1, N + 1):
    for j in range(blackNum):
        if i == black[j]:
              print('0')
              break
    else:
        print('1')

Submission status: Wrong Answer

Solution code:
N = int(input())
x = [[0 for i in range(3)] for j in range(N)]
y = [[0 for i in range(3)] for j in range(N)]
black = [0 for i in range(N * N)]
blackNum = 0


def blackf(u, v):
    global blackNum
    black[blackNum] = u
    black[blackNum + 1] = v
    blackNum = blackNum + 2


for i in range(N - 1):
    x[i] = input().split()

for i in range(len(x)):
    y[i] = [int(j) for j in x[i]]


for i in range(N - 1):
    if y[i][2] % 2 == 0:
        blackf(y[i][0], y[i][1])

#for j in range(blackNum):
   # print(black[j])

for i in range(1, N + 1):
    for j in range(blackNum):
        if i == black[j]:
              print('0')
              break
    else:
        print('1')

Submission status: Wrong Answer

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

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

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

Submission status: Wrong Answer

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

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

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

Submission status: Wrong Answer

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

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

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

Submission status: Wrong Answer

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

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

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

Submission status: Wrong Answer

Solution code:
def root(v):
    if v == par[v]:
        return v
    r = root(par[v])
    dist[v] += dist[par[v]]
    par[v] = r
    return r

def unite(u, v, w):
    u = root(u)
    v = root(v)
    if u == v:
        return 
    if rank[u] > rank[v]:
        u, v = v, u
    par[u] = v
    dist[u] = w
    if rank[u] == rank[v]:
        rank[v] += 1

N = int(input())
par = list(range(N+1))
rank = [0] * (N + 1)
dist = [0] * (N + 1)
ans = [0] * (N + 1)
for _ in range(N-1):
    u, v, w = map(int, input().split())
    unite(u, v, w)
    if dist[u] % 2 == 0:
        ans[u] = 0
    else:
        ans[u] = 1
    if dist[v] % 2 == 0:
        ans[v] = 0
    else:
        ans[v] = 1

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

Submission status: Wrong Answer

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

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

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

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

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

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

Submission status: Wrong Answer

Solution code:
n=int(input())
edge=[[] for i in range(n)]
if n==1:
  print(0)
  exit()
col=[-1 for i in range(n)]
for i in range(n-1):
  u,v,w=map(int,input().split())
  u-=1
  v-=1
  if w%2==0:
    if col[u]!=-1 and col[v]==-1:
      col[v]=col[u]
    elif col[v]!=-1 and col[u]==-1:
      col[u]=col[v]
    elif col[u]==-1 and col[v]==-1:
      col[u]=0
      col[v]=0
  else:
    if col[u]!=-1 and col[v]==-1:
      col[v]=(col[u]+1)%2
    elif col[v]!=-1 and col[u]==-1:
      col[u]=(col[v]+1)%2
    elif col[u]==-1 and col[v]==-1:
      col[u]=0
      col[v]=1
for i in range(n):
  print(col[i])

Submission status: Wrong Answer

Solution code:
N = int(input())
uvw = [
  list(int(i) for i in input().split()) for _ in range(N-1)
]
uvw.sort(key=lambda x:x[0])

ans = ['0'] * N
for u, v, w in uvw:
  ans_u = ans[u-1]
  if w % 2 == 0:
    ans[v-1] = ans_u
  else:
    if ans_u == '0':
      ans[v-1] = '1'
    else:
      ans[v-1] = '0'
print(' '.join(ans))

Submission status: Wrong Answer

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 unite(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())
wu = WeightedUnionFind(n)
for _ in range(n-1):
    u,v,w = map(int, input().split())
    u -= 1
    v -= 1
    wu.unite(u,v,w)

col = []
p = wu.find(0)
for i in range(n):
    w = wu.diff(p,i)
    col.append(w%2)
print(*col)