問題
サイズN*Nの配列xが与えられる。サイズNのツリーを考え、配列の各要素はx[i][j]はiからjまでの距離が偶数か奇数かを示している。与えられた配列の条件を満たすツリーを求めよ。
解法
kmjp.hatenablog.jp
ここの解答を参考にした。
ツリーの構築として、偶数か奇数しか制約がないのでひとつのルートを選び、奇数のノードと偶数のノードを接続すれば、条件を満たすツリーを構築できる。
計算量
サイズN*Nの配列xが与えられる。サイズNのツリーを考え、配列の各要素はx[i][j]はiからjまでの距離が偶数か奇数かを示している。与えられた配列の条件を満たすツリーを求めよ。
kmjp.hatenablog.jp
ここの解答を参考にした。
ツリーの構築として、偶数か奇数しか制約がないのでひとつのルートを選び、奇数のノードと偶数のノードを接続すれば、条件を満たすツリーを構築できる。