(defun solve ()
(let* ((n (next-int)) ; 頂点の数
;; 根を除いて各頂点にはたった1つの親頂点があるので、辺の数は
;; 「頂点の数-1」になる。
(from (make-array (1- n))) ; 番号が小さいほうの頂点
(to (make-array (1- n))) ; 番号が大きいほうの頂点
(w (make-array (1- n)))) ; 辺の長さ
(loop for i below (1- n)
do
;; 0ベース配列の添字にしたいので、各頂点番号をデクリメントしておく。
(setf (aref from i) (1- (next-int)))
(setf (aref to i) (1- (next-int)))
(setf (aref w i) (next-int)))
(let ((g (pack-wu n from to w))
(color (make-array n :initial-element +color-unknown+))) ; 頂点の色。
(dfs 0 color g +color-white+)
(loop for i below n
do
(format t "~A~%" (aref color i))))))
(defun dfs (now ; 現在訪問している頂点
color ; 色を出力する配列
g ; 辺の接続先と長さの情報
mod) ; 現在の頂点の色(0 か 1)
(setf (aref color now) mod)
(loop for edge across (aref g now)
do
(destructuring-bind
(next-vertex length) edge
(when (= (aref color next-vertex) +color-unknown+)
(dfs next-vertex color g (mod (+ mod length) 2))))))
(defun next-int ()
(read))
;; 各頂点についてその接続情報を収めた表 g を生成して返す。
;; g[頂点番号][各辺] = (list 辺の長さ 接続先の頂点)
(defun pack-wu (n from to w)
(let ((sup (length from)) ; 辺の数
(g (make-array n))
(p (make-array n :initial-element 0))) ; 各頂点の次数(接続している辺の数)
;; 各頂点の次数を数える。各辺は、2つの頂点の次数をそれぞれ1つずつ
;; 増やす。
(loop for i below sup
do
(incf (aref p (aref from i)))
(incf (aref p (aref to i))))
(loop for i below n
do
;; g[i] に頂点 i 接続している辺の情報を収める配列を割り当てる。
(setf (aref g i) (make-array (aref p i))))
;; 各頂点の持つ辺の情報を配列の後ろから格納する。
(loop for i below sup
do
(let ((v (aref from i))
(u (aref to i))
(len (aref w i)))
(decf (aref p v))
(setf (aref (aref g v) (aref p v)) (list u len))
(decf (aref p u))
(setf (aref (aref g u) (aref p u)) (list v len))))
