ユニオンファインド木を使いこなそう Scala編（paizaランク B 相当）

前問では、ランクという考えを取り入れて、ユニオン操作を工夫しました。しかし、数列 A のほかに別の数列 R を用意する必要がありました。最後に、数列 A と数列 R を合体させた数列を用いて、ユニオンファインド木というデータ構造を使いこなしましょう。

長さ n の数列 A を考え、数列 A の初期値を [-1, -1, ..., -1] とします。A の i 番目 (0 ≦ i ≦ n-1) の要素 A_i が負ならば整数 i は根であり、整数 i のランクが -A_i であることを表しています。A_i が非負ならば整数 i の親を表しています。ランクとは前問と同様に、整数 i が属する木の末端までの最大の長さのことです。

ここで、ある整数 p の親を順々にたどっていった、p の祖先（または p 自身）である q について、A の q 番目の要素が負であるとき「 p は q の根である」と定義します。つまり、A の初期値では、すべての i (0 ≦ i ≦ n-1) において、i 自身が根となっています。

整数の組 (a,b) が合計 q 組与えられます。(a_j, b_j) (1 ≦ j ≦ q) に対して a_j の根を root(a_j)、b_j の根を root(b_j) として、次の操作を与えられた順番に処理し、最後に処理がすべて終了したあとの数列 A を出力してください。

root(a_j) と root(b_j) が同じでないなら、ランクが低いほうの根の親をランクが高いほうの根とする。ランクが同じ場合、root(b_j) の親を root(a_j) の親とする。
root(a_j) と root(b_j) の値が同じならば何もしない。

ただし、p の根 root(p) は、p を入力として root(p) を返す次の関数 improved_find を用いて求めてください。（この関数で求めない場合、処理終了後の数列 A が正しく出力されない可能性があります。）

def improved_find(p)
  if A_p < 0 then
    return p
  else
    A_p = improved_find(A_p)
    return A_p
  end if