ABC126 D - Even Relation

問題原文

atcoder.jp

問題要旨

木の頂点を、「同色で塗られた任意の２頂点間の距離が偶数」となるように、２色で塗り分けよ。

解法１：LCAを考える

LCAの考え方の利用

図より、
この式の第３項は偶数なので、 が偶数の時のみ、 頂点 と 頂点 は同色で塗られる。
よって根付き木と見立てて、根からの各頂点への距離の情報があれば解ける。

N = int(input())
T = [[] for i in range(N)]
for i in range(N - 1):
    u, v, w = map(int, input().split())
    u, v = u - 1, v - 1
    T[u].append([v, w])
    T[v].append([u, w])
 
 
dist = [float('inf')] * N
stack = [[0, 0]]
while stack:
    n, d = stack.pop()
    dist[n] = d
 
    for to, w in T[n]:
        if dist[to] != float('inf'):
            continue
 
        stack.append([to, d + w])
 
ans = [d % 2 for d in dist]
print(*ans, sep='\n')

解法２：貪欲に塗れる色を塗っていく

根から貪欲塗れる色を塗っていっても正しい解が得られる。
というか問題文に この問題の制約下では、そのような塗り分け方が必ず 1つは存在することが証明できます。 って書いてる。
「辺の重みが奇数なら次は違う色で塗る」をやっていけばいい。これは color ^ 1 みたいに書くと少し楽。
「黒から２回色を変えると黒に戻る」と考えるとわかりやすいかも。

N = int(input())
T = [[] for i in range(N)]
for i in range(N - 1):
    u, v, w = map(int, input().split())
    u, v = u - 1, v - 1
    T[u].append([v, w])
    T[v].append([u, w])
 
 
ans = [-1] * N
stack = [[0, 0]]
while stack:
    n, color = stack.pop()
    ans[n] = color
 
    for to, w in T[n]:
        if ans[to] != -1:
            continue
 
        if w % 2 == 0:
            stack.append([to, color])
        else:
            stack.append([to, color ^ 1])
 
print(*ans, sep='\n')