[AtCoder] ABC 126 D – Even Relation

問題

方針

最小共通祖先

根から 頂点 \( i \) までの距離を \(d_i \) とすると、頂点 \( u \) と 頂点 \( v \) の距離は、\( u \) と \( v \) の最小共通祖先までの距離 \( lca(u, v) \) を用いて、\( d_u + d_v – 2lca(u, v) \) で表せるそうです。参考として、競技プログラミングにおけるLAC問題で言及されていました。

ある頂点からの距離

上記の事実を利用すると、同じ色に塗った頂点間の距離が偶数ということは、ある頂点から同じ色の別の頂点までの距離が偶数ということです。全ての頂点間の距離を調べる必要はなく、一つの頂点からの距離を調べるだけでよいです。また、ある頂点からの距離が奇数の場合、その頂点は別の色で塗れば良いです。

例えば、頂点 \( 1 \) を基準として、全ての頂点の距離をしらべ、その距離が偶数であれば、\( 1 \) と同じ色、そうでなければ違う色にします。どう距離を求めるかですが、僕はダイクストラ法を用いて解きました。

コード

提出したコード (Java)

ダイクストラ法をC++で書き直したものを後で追加しようと思います。

提出したコード (C++)

ダイクストラ法