abc126 d (python)
E が Union-find 木でとけるのでこれもそれでいけるのではと考えたが、辺の重みを更新する挙動をよく理解できていないため出来なかった。
結局いつも通り辺のリストを作成して dfs して解いた。
いつもと違う点は、辺のリストに [u-1,w] という形でいれておいて、dfs では next[0] として次に行く辺だけとるようにしたことぐらい。
import sys input = sys.stdin.readline import sys sys.setrecursionlimit(1000000) n = int(input()) g = [[] * n for i in range(n)] for i in range(n-1): u, v, w = map(int, input().split()) u -= 1 v -= 1 g[u].append((v, w)) g[v].append((u, w)) chk = [0]*n chk[0] = 1 def dfs(now, prev): global chk # 今いる頂点から行ける頂点を順に next に入れてループ for next in g[now]: if next[0] != prev: if next[1]%2 == 0: chk[next[0]] = chk[now] elif next[1]%2 == 1: chk[next[0]] = (chk[now]*-1) dfs(next[0], now) dfs(0,-1) chk = tuple(chk) for i in chk: if i == 1: print(1) else: print(0)