D - Even Relation

D - Even Relation。
深さ優先探索と偶奇の性質を理解しているとできる。

import sys  
sys.setrecursionlimit(20000000)


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

u と v の距離は du + dv − 2dw と書くことができます。
この式の第 3 項は偶数なので、du と dw の偶奇が等しいときに限り、u と w の距離は偶数になります。
よって例えば di が偶数の頂点は白に、奇数の頂点は黒に塗ることで条件を満たす塗り分けができます

と。