AT_yuha_c83_03 Dendrogram - 樹形図

[problemUrl]: https://atcoder.jp/contests/yuha-c83/tasks/yuha_c83_03 Nathan. O. Davisは情報工学科に所属する学生である。 彼は学科の『人工知能概論』という授業の期末課題のため、 階層的クラスタリングのプログラムを書いている。 クラスタリングとは、オブジェクトの集合をクラスタと呼ばれる複数の部分集合に分ける処理である。 ここで同一のクラスタに所属するオブジェクトは何らかの基準により似ていると判定されたものとなるようにする。 階層的クラスタリングはこれを間接的に行う手法の一つで、オブジェクトの集合を樹形図と呼ばれる木構造で扱う。 ただし、本問題では木の集合も樹形図として扱う。 樹形図はオブジェクト間の類似度を表現する。以下に樹形図の例を示す。 上記の図において、末端の葉は各オブジェクトを表す。 水平の線分はオブジェクトの集合の2つ以上のサブグループへの分割を表す。 別のサブグループに所属するオブジェクトは類似度が低く、 同一のサブグループに所属するオブジェクトは類似度が高いことを表す。 これは水平線が上に位置するほど、その水平線に所属するオブジェクトやオブジェクトの集合の類似度が低いことを表している。 例として、上の図の上から2本目の水平線によって、オブジェクトの集合が3つのクラスタに分けられていることが分かる。 Nathanの書いたプログラムは系統樹を出力すること自体はできるのだが、 2つのバグが含まれていた。 一点目は系統樹が連結になっていない点、つまり出力された系統樹が複数の木構造からなる点である。 これについては本問題では扱わないことにする。 二点目は出力された系統樹の見た目が非常に汚いことである。 具体的には(図:汚い樹形図)のように線分同士が交差してしまっており、 読み取りづらくなってしまっているのである。 あなたの仕事は入力としてNathanの出力した系統樹を受け取り、 綺麗な系統樹を出力するプログラムを書くことである。 ここで綺麗な系統樹とは垂直の線分と水平の線分が接点以外で接触せず、 かつ末端の葉の番号の並びが辞書順で最も若いものとする。 詳細な仕様については入力と出力の欄を参考にせよ。 入力形式は以下の通りである。 初めの行は3つの整数 $ N $ ( $ 1\

N/A

N/A