005 - 最軽量のモビール

問題

モビールは動く芸術品として広く親しまれている.IOI 日本委員会では,JOI を 広報するためにモビールを作成することになった.JOI 広報用モビールは,棒,紐 (ひも),錘(おもり)の 3 種類の要素を用いて,次のように構成される.

• 棒の一方の端は青に,もう一方の端は赤に塗られている.
• 棒は両端以外の 1 箇所を支点として紐でつるされる.
• 支点から赤の端までの長さも支点から青の端までの長さも正整数である.
• 棒の両端には,紐で錘か他の棒をつるす.
• 錘は紐を用いてどれかの棒の一端につるされる.
• 錘には何もつるさない.
• 錘の重さは正整数である.
• 紐のうち 1 本だけは,片方の端をある棒をつるすためにその棒の支点に結ばれ, もう一方の端は他のどの構成要素とも結ばれていない.他の紐は全て次のいず れかを満たす.
• ある棒の端とある棒の支点を結ぶ.
• ある棒の端とある錘を結ぶ.

ただし,どの棒においても,バランスが取れている必要がある.棒と紐の重さは無 視できるほど軽いので,棒と紐の重さは全て 0 であるとみなして解答せよ.つまり, それぞれの棒について,

(その棒の赤の端より下につるされている錘の重さの総計) × (その棒の支点から赤の端までの長さ) = (その棒の青の端より下につるされている錘の重さの総計) × (その棒の支点から青の端までの長さ)

であるとき,その棒はバランスが取れているとせよ.

どのような長さの棒をどのように結びモビールを構成するかは既に決まっている のだが,錘の重さがまだ決まっていない.モビールは軽い方がつりやすいため, なる べく軽いモビールを作りたい.前述したようにどの棒もバランスを取りながら, モ ビールの総重量を最小にするような錘の付け方を求め, そのときのモビールの総重量 を出力するプログラムを作れ. プログラムには以下のモビールの構成に関する情報 が与えられる.

• 棒の本数 n
• 各棒ごとの情報(棒の番号は 1 から n)
• 支点から赤の端までの長さと支点から青の端までの長さの比
• 赤の端につるす棒の番号 (錘をつるす場合は 0)
• 青の端につるす棒の番号 (錘をつるす場合は 0)

入力

入力の1 行目にはモビールに使われて いる棒の本数 n が書かれている.続く n 行 (1 ≤ n ≤ 100) には,各々の棒のデー タが書かれている.i + 1 行目 (1 ≤ i ≤ n) には,4 つの整数 p, q, r, b が空白を区 切りとして書かれており,棒 i において,支点から赤の端までの長さと支点から青 の端までの比が p : q であり,赤の端につるされる棒の番号が r であり,青の端につ るされる棒の番号が b であることを表している.ただし,棒番号 0 は錘がつるされ ることを表している.また,どの入力においても,モビールの重量の最小値を w と し,入力中で比を表すのに用いられる正整数の最大値を L とすると,wL < 2³¹ を 満たす.

出力

出力は 1 行だけであり,モビールの重量を出力する.

入出力の例

入力例１

1
6 9 0 0

出力例１

5

入力例２

4
3 2 0 4
1 3 0 0
4 4 2 1
2 2 0 0

出力例２

40