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 が偶数の頂点は白に、奇数の頂点は黒に塗ることで条件を満たす塗り分けができます
と。