コラム一覧に戻る
heavy-light decomposition の DFS は DFS 順をとるだけだから DFS じゃなくてもいい！
BFS 順で探索しながら、各頂点以下の部分木のサイズを参照すると、 DFS 順を構築することができます。
各頂点の深さを管理していれば、行きがけと帰りがけを両方記録した場合の番号を行きがけ順のみから計算することができます。
TOP PAGE