Problem:


最軽量のモビール

問題

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

  
 棒の一方の端は青に,もう一方の端は赤に塗られている. 

  
 棒は両端以外の 1 箇所を支点として紐でつるされる.

  
 支点から赤の端までの長さも支点から青の端までの長さも正整数である.

  
 棒の両端には,紐で錘か他の棒をつるす.

  
 錘は紐を用いてどれかの棒の一端につるされる.

  
 錘には何もつるさない.

  
 錘の重さは正整数である.

  
 紐のうち 1 本だけは,片方の端をある棒をつるすためにその棒の支点に結ばれ,
    もう一方の端は他のどの構成要素とも結ばれていない.他の紐は全て次のいず
    れかを満たす.

    

     
 ある棒の端とある棒の支点を結ぶ.

     
 ある棒の端とある錘を結ぶ.

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

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

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

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

  棒の本数 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 < 231 を満たす.

データセットの数は 15 を超えない．

出力

データセットごとにモビールの重量を１行に出力する．

入出力例

入力例

1
6 9 0 0
4
3 2 0 4
1 3 0 0
4 4 2 1
2 2 0 0
0

出力例

5
40

上記問題文と自動審判に使われるデータは、情報オリンピック日本委員会が作成し公開している問題文と採点用テストデータです。



Sample input:
1
6 9 0 0
4
3 2 0 4
1 3 0 0
4 4 2 1
2 2 0 0
0


Sample output:
5
40

Submission status: Wrong Answer

Solution code:
def gcd(a, b):
    r = a % b
    if r:
        return gcd(b, r)
    return b


def lcm(a, b):
    if a < b:
        a, b = b, a
    return a * b // gcd(a, b)


def min_weight(m):
    p, q, r, b = bars[m - 1]
    red = q * (min_weight(r) if r else 1)
    blue = p * (min_weight(b) if b else 1)
    equilibrium = lcm(red, blue)
    return equilibrium // p + equilibrium // q


while True:
    n = int(input())
    if not n:
        break

    bars = [tuple(map(int, input().split())) for _ in range(n)]

    root_bar = set(range(1, n + 1))
    for _, _, r, b in bars:
        if r: root_bar.remove(r)
        if b: root_bar.remove(b)

    print(min_weight(root_bar.pop()))

Submission status: Wrong Answer

Solution code:
from math import gcd
while True:
  try:
    n = int(input())
    if not n: break
    lst = [[]]
    weight = [-1 for i in range(n + 1)]
    def setWeight(n):
      p,q,r,b = lst[n]
      if weight[n] != -1:pass
      elif r == 0 and b == 0:
        weight[n] = (p + q) // gcd(p,q)
      elif r == 0:
        setWeight(b)
        wb = weight[b]
        g = gcd(wb * q, p)
        lcm = wb * q * p // g
        weight[n] = lcm // q + lcm // p
        print("wr:",str(lcm//p),"wb:",str(wb),"g:",g,"p:",p,"lcm",lcm)
      elif b == 0:
        setWeight(r)
        wr = weight[r]
        g = gcd(wr * p, q)
        lcm = wr * p * q // g
        weight[n] = lcm // p + lcm // q
      else:
        if weight[r] == -1: setWeight(r)
        if weight[b] == -1: setWeight(b)
        wr = weight[r]
        wb = weight[b]
        g = gcd(wr * p, wb * q)
        lcm = wr * p * wb  * q // g
        weight[n] = lcm // p + lcm // q
    for i in range(n):
      lst.append(list(map(int,input().split())))
    for i in range(0,n):
      if weight[i + 1] == -1:
        setWeight(i+1)
    print(max(weight))
    print(weight)
  except EOFError:
    break

Submission status: Accepted

Solution code:
from fractions import gcd
def dfs(p, q, r, b, s):
    if s == 0: return 1
    x = dfs(p, q, r, b, r[s]) * p[s]
    y = dfs(p, q, r, b, b[s]) * q[s]
    z = x / gcd(x, y) * y
    return z / p[s] + z / q[s]
while 1:
    n = input()
    if n == 0: break
    ret = n*(n+1) / 2
    p = [0]*(n+1); q = [0]*(n+1); r = [0]*(n+1); b = [0]*(n+1)
    for i in range(1, n+1):
        p[i],q[i],r[i],b[i] = map(int, raw_input().split())
        ret -= r[i] + b[i]
    print dfs(p, q, r, b, ret)

Submission status: Accepted

Solution code:
def gcd(a, b):
    r = a % b
    if r:
        return gcd(b, r)
    return b


def lcm(a, b):
    if a < b:
        a, b = b, a
    return a * b // gcd(a, b)


def min_weight(m):
    p, q, r, b = bars[m - 1]
    red = p * (min_weight(r) if r else 1)
    blue = q * (min_weight(b) if b else 1)
    equilibrium = lcm(red, blue)
    return equilibrium // p + equilibrium // q


while True:
    n = int(input())
    if not n:
        break

    bars = [tuple(map(int, input().split())) for _ in range(n)]

    root_bar = set(range(1, n + 1))
    for _, _, r, b in bars:
        if r: root_bar.remove(r)
        if b: root_bar.remove(b)

    print(min_weight(root_bar.pop()))

Submission status: Accepted

Solution code:
'''
Created on 2017/03/09

@author: 03key
'''

def gcd(x,y):
    if x<y:
        tmp = x
        x = y
        y = tmp
    ans = y
    if x%y != 0:
        ans = gcd(y,x%y)
    return ans

class Mobile:
    def __init__(self,leftratio=0,rightratio=0,left=-1,right=-1):
        self.weight = 0
        self.leftratio = leftratio
        self.rightratio = rightratio
        self.left = left
        self.leftweight = 0
        self.right = right
        self.rightweight = 0

    def calc(self):
        if self.weight != 0 : return self.weight

        if self.left == -1:
            self.leftweight = 1
        else:
            self.leftweight = Mobile.calc(self.left)
        if self.right == -1:
            self.rightweight = 1
        else:
            self.rightweight = Mobile.calc(self.right)

        lmoment = self.leftratio*self.leftweight
        rmoment = self.rightratio*self.rightweight
        lcs = lmoment * rmoment // gcd(lmoment,rmoment)
        self.weight = (lcs//self.leftratio) + (lcs//self.rightratio)

        return self.weight

    def stdout(self):
        print(self.left, self.right)

while True:
    n = int(input())
    if n==0: break
    barlist = [Mobile() for i in range(n)]
    for i in range(n):
        p,q,r,b = map(int, input().split())
        barlist[i].leftratio = p
        barlist[i].rightratio = q
        if r != 0 : barlist[i].left = barlist[r-1]
        if b != 0 : barlist[i].right = barlist[b-1]

    maxi = 0
    for i in range(n):
        maxi = max(barlist[i].calc(),maxi)

    print(maxi)

Submission status: Accepted

Solution code:
from math import gcd
while True:
  try:
    n = int(input())
    if not n: break
    lst = [[]]
    weight = [-1 for i in range(n + 1)]
    def setWeight(n):
      p,q,r,b = lst[n]
      if weight[n] != -1:pass
      elif r == 0 and b == 0:
        weight[n] = (p + q) // gcd(p,q)
      elif r == 0:
        setWeight(b)
        wb = weight[b]
        g = gcd(wb * q, p)
        lcm = wb * q * p // g
        weight[n] = lcm // q + lcm // p
#        print("wr:",str(lcm//p),"wb:",str(wb),"g:",g,"p:",p,"lcm",lcm)
      elif b == 0:
        setWeight(r)
        wr = weight[r]
        g = gcd(wr * p, q)
        lcm = wr * p * q // g
        weight[n] = lcm // p + lcm // q
      else:
        if weight[r] == -1: setWeight(r)
        if weight[b] == -1: setWeight(b)
        wr = weight[r]
        wb = weight[b]
        g = gcd(wr * p, wb * q)
        lcm = wr * p * wb  * q // g
        weight[n] = lcm // p + lcm // q
    for i in range(n):
      lst.append(list(map(int,input().split())))
    for i in range(0,n):
      if weight[i + 1] == -1:
        setWeight(i+1)
    print(max(weight))
#    print(weight)
  except EOFError:
    break

Submission status: Accepted

Solution code:

from math import gcd
def lcm(i, j):
  return i * j // gcd(i, j)
def main():
  while True:
    n = int(input())
    if not n: break
    lst = [[]]
    weight = [-1 for i in range(n + 1)]
    def setWeight(n):
      p, q, r, b = lst[n]
      if weight[n] != -1: pass
      elif r == 0 and b == 0:
        weight[n] = (p + q) // gcd(p, q)
      elif r == 0:
        setWeight(b)
        l = lcm(weight[b] * q, p)
        weight[n] = l // q + l // p
      elif b == 0:
        setWeight(r)
        l = lcm(weight[r] * p, q)
        weight[n] = l // p + l // q
      else:
        if weight[r] == -1: setWeight(r)
        if weight[b] == -1: setWeight(b)
        l = lcm(weight[r] * p, weight[b]  * q)
        weight[n] = l // p + l // q
    for i in range(n):
      lst.append(list(map(int,input().split())))
    for i in range(0, n):
      if weight[i + 1] == -1:
        setWeight(i + 1)
    print(max(weight))

if __name__ == '__main__':
  main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python

def GCD(a, b):
	dummy1 = max(a, b)
	dummy2 = min(a, b)
	while True:
		dummy = dummy1 % dummy2
		dummy1 = dummy2
		dummy2 = dummy
		if(dummy == 0):
			break

	return dummy1

while True:
	N = input()
	if not N:
		break
	cost = []
	E = []
	root = N * (N - 1) / 2
	for i in range(N):
		S = raw_input().split()
		c1, c2, e1, e2 = list(map(int,S))
		cost.append((c1, c2))
		root -= e1 + e2
		e1 -= 1
		e2 -= 1
		E.append((e1, e2))
	def nums(e):
		N_lst1 = []
		N_lst2 = []
		val_lst1 = []
		val_lst2 = []
		if E[e][0] != -1:
			N_lst1, val_lst1 = nums(E[e][0])
		else:
			N_lst1 = [1]
			val_lst1 = []
		
		if E[e][1] != -1:
			N_lst2, val_lst2 = nums(E[e][1])
		else:
			N_lst2 = [1]
			val_lst2 = []
		
		mul1 = cost[e][0]
		for num in val_lst1:
			mul1 *= num
		mul2 = cost[e][1]
		for num in val_lst2:
			mul2 *= num
		for i in range(len(N_lst1)):
			N_lst1[i] *= mul2
		for i in range(len(N_lst2)):
			N_lst2[i] *= mul1
		
		return N_lst1 + N_lst2, val_lst1 + val_lst2 + [cost[e][0] + cost[e][1]]
	N_lst, v_lst = nums(root - 1)
	#print N_lst
	num_GCD = N_lst[0]
	for num in N_lst:
		num_GCD = GCD(num, num_GCD)
	
	for i in range(len(N_lst)):
		N_lst[i] //= num_GCD
	#print N_lst
	print sum(N_lst)

Submission status: Accepted

Solution code:
# AOJ 0520: Lightest Mobile
# Python3 2018.6.30 bal4u

def lcm(a, b):
	return a // gcd(a, b) * b

def gcd(a, b):
	while b != 0:
		r = a % b
		a, b = b, r
	return a

def calc(i):
	wr = calc(t[i][2]) if t[i][2] > 0 else 1
	wb = calc(t[i][3]) if t[i][3] > 0 else 1
	w = lcm(t[i][0] * wr, t[i][1] * wb)
	return w//t[i][0] + w//t[i][1]

while True:
	n = int(input())
	if n == 0: break
	f = [0]*(n+1)
	t = [(0,0,0,0)]
	for i in range(1, n+1):
		p, q, r, b = map(int, input().split())
		t.append((p, q, r, b))
		if r > 0: f[r] = i
		if b > 0: f[b] = i
	for i in range(1, n+1):
		if f[i] == 0: break
	print(calc(i))

Submission status: Accepted

Solution code:
import sys

#fp = open("input.txt", "r")
fp = sys.stdin

def gcd(a, b):
    return a if b == 0 else gcd(b, a%b)

class Mobile:
    def __init__(self):
        self.len_l = 0
        self.len_r = 0
        self.mob_l = None
        self.mob_r = None
        self.parent = None

    def getWeight(self):
        weight_l = 1 if self.mob_l == None else self.mob_l.getWeight()
        weight_r = 1 if self.mob_r == None else self.mob_r.getWeight()

        moment_l = self.len_l * weight_l
        moment_r = self.len_r * weight_r

        g = gcd(moment_l, moment_r)

        n_l = moment_r / g
        n_r = moment_l / g
        
        return weight_l * n_l + weight_r * n_r

    def getRoot(self):
        if self.parent == None:
            return self
        else:
            return self.parent.getRoot()

    def printTest(self):
        print self.len_l,
        print ", ",
        print self.len_r

while True:
    n = int(fp.readline()[:-1])
    if n == 0:
        break

    li = [Mobile() for i in xrange(n)]

    for i in xrange(n):
        ele = map(int, fp.readline()[:-1].split(" "))
        li[i].num = i+1
        li[i].len_l = ele[0]
        li[i].len_r = ele[1]
        if ele[2] != 0:
            child = li[ele[2]-1]
            li[i].mob_l = child
            child.parent = li[i]
        if ele[3] != 0:
            child = li[ele[3]-1]
            li[i].mob_r = child
            child.parent = li[i]

    print li[0].getRoot().getWeight()

Submission status: Accepted

Solution code:
# AOJ0520

import sys

def gcd(x, y):
    if x < y:
        x, y = y, x
    while x % y != 0:
        x, y = y, x % y
    return y
    
class frac:
    def __init__(self, n, d):
        self.num = n
        self.den = d
    
    def mul(self, yn, yd):
        xn, xd = self.num, self.den
        xn *= yn
        xd *= yd
        if xn != 0 and xd != 0:
            g = gcd(xn, xd)
            xn /= g
            xd /= g
        return frac(xn, xd)
    
    def is_zero(self):
        return self.num == 0
    
    def output(self):
        return "{}/{}".format(self.num, self.den)      
            
class LightestMobile:
    def __init__(self, n):
        self.n = n + 1
        self.mobile = [[0,0,0,0]]
        self.weight = [[frac(0,1), frac(0,1)]]
        self.denom = []

    def read(self, p, q, r, b):
        self.mobile.append([p, q, r, b])
        self.weight.append([frac(0,1), frac(0,1)])
    
    
    def root(self):
        for i in range(1, self.n):
            m = self.mobile[i]
            if m[2] == 0 and m[3] == 0:
                return self.parent(i)
    
    def parent(self, c):
        for i in range(1, self.n):
            m = self.mobile[i]
            if i != c and (m[2] == c or m[3] == c):
                return self.parent(i)
        return c
    
    def solve(self, i):
        self.solve2(i, frac(0,1))
        lcm = 1
        for d in self.denom:
            lcm = lcm * d / gcd(lcm, d)
        answer = self.weight[i][0].mul(lcm, 1).num + self.weight[i][1].mul(lcm, 1).num
        return int(answer)
    
    def solve2(self, i, wlr):
        p, q, r, b = self.mobile[i]
#        print("p,q,r,b=", self.mobile[i])
#        print("i, wlr=", i, wlr.output())
        if wlr.is_zero():
            g = gcd(p, q)
            p /= g
            q /= g
            self.weight[i] = [frac(q, 1), frac(p, 1)]
        else:
            self.weight[i] = [wlr.mul(q, p + q), wlr.mul(p, p + q)]
        if r != 0:
            self.solve2(r, self.weight[i][0])
        if b != 0:
            self.solve2(b, self.weight[i][1])
        if r == 0 and b == 0:
            if not self.weight[i][0].is_zero() and not self.weight[i][1].is_zero():
                self.denom.append(self.weight[i][0].den)
                self.denom.append(self.weight[i][1].den)
        return

if __name__ == '__main__':
    while True:
        line = input()
        n = int(line)
        if n == 0:
            break
        lm = LightestMobile(n)
        for _ in range(0, n):
            p, q, r, b = map(int, list(input().split()))
            lm.read(p, q, r, b)
        rt = lm.root()
        print(lm.solve(rt))
        del lm

Submission status: Accepted

Solution code:
def solve():
    from math import gcd
    
    # Post-order tree traversal
    def traversal(bar_id):
        if bar_id == 0:
            return 1
        p, q, r, b = nodes[bar_id]
        r_w = traversal(r)
        b_w = traversal(b)
        cf = gcd(p * r_w, q * b_w)
        
        return r_w * b_w * (p + q) // cf
    
    from sys import stdin
    file_input = stdin
    
    while True:
        n = int(file_input.readline())
        if n == 0:
            break
        
        root_id = n * (n + 1) // 2
        nodes = [None]
        for i in range(1, n + 1):
            p, q, r, b = map(int, file_input.readline().split())
            g = gcd(p, q)
            nodes.append((p // g, q // g, r, b))
            root_id -= (r + b)
        
        print(traversal(root_id))

solve()

Submission status: Accepted

Solution code:
def gcd(x, y):
    while y > 0:
        x, y = y, x%y
    return x

while True:
    N = int(input())
    if not N:
        break
    a = [list(map(int, input().split())) for _ in [0]*N]
    root = (set(range(1, N+1)) - set(n for bar in a for n in bar[2:])).pop()

    def solve(ratio_r, ratio_l, left, right):
        d = gcd(ratio_r, ratio_l)
        ratio_r //= d
        ratio_l //= d

        w_left = solve(*a[left-1]) if left else 0
        w_right = solve(*a[right-1]) if right else 0

        if w_left == w_right == 0:
            w_left, w_right = ratio_l, ratio_r
        elif w_left == 0:
            w_right = (w_right * ratio_r) // gcd(w_right, ratio_r)
            w_left = ratio_l * (w_right // ratio_r)
        elif w_right == 0:
            w_left = (w_left * ratio_l) // gcd(w_left, ratio_l)
            w_right = ratio_r * (w_left // ratio_l)
        else:
            _r, _l = w_left*ratio_r, w_right*ratio_l
            d = gcd(_l, _r)
            w_right, w_left = w_right*(_r // d), w_left*(_l // d)

        return w_right + w_left

    print(solve(*a[root-1]))

Submission status: Runtime Error

Solution code:
import math
class Mobile:
    def __init__(self,leftratio=0,rightratio=0,left=-1,right=-1):
        self.weight = 0
        self.leftratio = leftratio
        self.rightratio = rightratio
        self.left = left
        self.leftweight = 0
        self.right = right
        self.rightweight = 0

    def calc(self):
        if self.weight != 0 : return self.weight

        if self.left == -1:
            self.leftweight = 1
        else:
            self.leftweight = Mobile.calc(self.left)
        if self.right == -1:
            self.rightweight = 1
        else:
            self.rightweight = Mobile.calc(self.right)

        lmoment = self.leftratio*self.leftweight
        rmoment = self.rightratio*self.rightweight
        lcs = lmoment * rmoment // math.gcd(lmoment,rmoment)
        self.weight = (lcs//self.leftratio) + (lcs//self.rightratio)

        return self.weight

    def stdout(self):
        print(self.left, self.right)

n = int(input())
barlist = [Mobile() for i in range(n)]
for i in range(n):
    p,q,r,b = map(int, input().split())
    barlist[i].leftratio = p
    barlist[i].rightratio = q
    if r != 0 : barlist[i].left = barlist[r-1]
    if b != 0 : barlist[i].right = barlist[b-1]

maxi = 0
for i in range(n):
    maxi = max(barlist[i].calc(),maxi)

print(maxi)

Submission status: Runtime Error

Solution code:
import math
class Mobile:
    def __init__(self,leftratio=0,rightratio=0,left=-1,right=-1):
        self.weight = 0
        self.leftratio = leftratio
        self.rightratio = rightratio
        self.left = left
        self.leftweight = 0
        self.right = right
        self.rightweight = 0

    def calc(self):
        if self.weight != 0 : return self.weight

        if self.left == -1:
            self.leftweight = 1
        else:
            self.leftweight = Mobile.calc(self.left)
        if self.right == -1:
            self.rightweight = 1
        else:
            self.rightweight = Mobile.calc(self.right)

        lmoment = self.leftratio*self.leftweight
        rmoment = self.rightratio*self.rightweight
        lcs = lmoment * rmoment // math.gcd(lmoment,rmoment)
        self.weight = (lcs//self.leftratio) + (lcs//self.rightratio)

        return self.weight

    def stdout(self):
        print(self.left, self.right)
while True:
    n = int(input())
    if n==0: break
    barlist = [Mobile() for i in range(n)]
    for i in range(n):
        p,q,r,b = map(int, input().split())
        barlist[i].leftratio = p
        barlist[i].rightratio = q
        if r != 0 : barlist[i].left = barlist[r-1]
        if b != 0 : barlist[i].right = barlist[b-1]

    maxi = 0
    for i in range(n):
        maxi = max(barlist[i].calc(),maxi)

    print(maxi)

Submission status: Runtime Error

Solution code:

def gcd(x,y):
    if x<y:
        tmp = x
        x = y
        y = tmp
    if x%y == 0:
        return y
    else:
        gcd(y,x%y)

class Mobile:
    def __init__(self,leftratio=0,rightratio=0,left=-1,right=-1):
        self.weight = 0
        self.leftratio = leftratio
        self.rightratio = rightratio
        self.left = left
        self.leftweight = 0
        self.right = right
        self.rightweight = 0

    def calc(self):
        if self.weight != 0 : return self.weight

        if self.left == -1:
            self.leftweight = 1
        else:
            self.leftweight = Mobile.calc(self.left)
        if self.right == -1:
            self.rightweight = 1
        else:
            self.rightweight = Mobile.calc(self.right)

        lmoment = self.leftratio*self.leftweight
        rmoment = self.rightratio*self.rightweight
        lcs = lmoment * rmoment // gcd(lmoment,rmoment)
        self.weight = (lcs//self.leftratio) + (lcs//self.rightratio)

        return self.weight

    def stdout(self):
        print(self.left, self.right)

while True:
    n = int(input())
    if n==0: break
    barlist = [Mobile() for i in range(n)]
    for i in range(n):
        p,q,r,b = map(int, input().split())
        barlist[i].leftratio = p
        barlist[i].rightratio = q
        if r != 0 : barlist[i].left = barlist[r-1]
        if b != 0 : barlist[i].right = barlist[b-1]

    maxi = 0
    for i in range(n):
        maxi = max(barlist[i].calc(),maxi)

    print(maxi)

Submission status: Runtime Error

Solution code:
from math import gcd
def lcm(i,j):
  return i * j // gcd(i,j)
def main():
  while True:
    n = int(input())
    if not n: break
    lst = [[]]
    weight = [-1 for i in range(n + 1)]
    def setWeight(n):
      p,q,r,b = lst[n]
      if weight[n] != -1:pass
      elif r == 0 and b == 0:
        weight[n] = (p + q) // gcd(p,q)
      elif r == 0:
        setWeight(b)
        l = lcm(weight[b] * q, p)
        weight[n] = l // q + l // p
      elif b == 0:
        setWeight(r)
        l = lcm(weight(r) * p, q)
        weight[n] = l // p + l // q
      else:
        if weight[r] == -1: setWeight(r)
        if weight[b] == -1: setWeight(b)
        l = lcm(weight[r] * p, weight[b]  * q)
        weight[n] = l // p + l // q
    for i in range(n):
      lst.append(list(map(int,input().split())))
    for i in range(0,n):
      if weight[i + 1] == -1:
        setWeight(i+1)
    print(max(weight))
if __name__ == '__main__':
  main()

Submission status: Runtime Error

Solution code:

from math import gcd
def lcm(i, j):
  return i * j // gcd(i, j)
def main():
  while True:
    n = int(input())
    if not n: break
    lst = [[]]
    weight = [-1 for i in range(n + 1)]
    def setWeight(n):
      p, q, r, b = lst[n]
      if weight[n] != -1: pass
      elif r == 0 and b == 0:
        weight[n] = (p + q) // gcd(p, q)
      elif r == 0:
        setWeight(b)
        l = lcm(weight[b] * q, p)
        weight[n] = l // q + l // p
      elif b == 0:
        setWeight(r)
        l = lcm(weight(r) * p, q)
        weight[n] = l // p + l // q
      else:
        if weight[r] == -1: setWeight(r)
        if weight[b] == -1: setWeight(b)
        l = lcm(weight[r] * p, weight[b]  * q)
        weight[n] = l // p + l // q
    for i in range(n):
      lst.append(list(map(int,input().split())))
    for i in range(0, n):
      if weight[i + 1] == -1:
        setWeight(i + 1)
    print(max(weight))

if __name__ == '__main__':
  main()

Submission status: Runtime Error

Solution code:

from math import gcd
def lcm(i, j):
  return i * j // gcd(i, j)
def main():
  while True:
    n = int(input())
    if not n: break
    lst = [[]]
    weight = [-1 for i in range(n + 1)]
    def setWeight(n):
      p, q, r, b = lst[n]
      if weight[n] != -1: pass
      elif r == 0 and b == 0:
        weight[n] = (p + q) // gcd(p, q)
      elif r == 0:
        setWeight(b)
        l = lcm(weight[b] * q, p)
        weight[n] = l // q + l // p
      elif b == 0:
        setWeight(r)
        l = lcm(weight(r) * p, q)
        weight[n] = l // p + l // q
      else:
        if weight[r] == -1: setWeight(r)
        if weight[b] == -1: setWeight(b)
        l = lcm(weight[r] * p, weight[b]  * q)
        weight[n] = l // p + l // q
    for i in range(n):
      lst.append(list(map(int,input().split())))
    for i in range(0, n):
      if weight[i + 1] == -1:
        setWeight(i + 1)
    print(max(weight))

main()

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python

import numpy as np

def GCD(a, b):
	dummy1 = max(a, b)
	dummy2 = min(a, b)
	while True:
		dummy = dummy1 % dummy2
		dummy1 = dummy2
		dummy2 = dummy
		if(dummy == 0):
			break

	return dummy1

while True:
	N = input()
	if not N:
		break
	cost = []
	E = []
	root = N * (N - 1) / 2
	for i in range(N):
		S = raw_input().split()
		c1, c2, e1, e2 = list(map(int,S))
		cost.append((c1, c2))
		root -= e1 + e2
		e1 -= 1
		e2 -= 1
		E.append((e1, e2))
	def nums(e):
		N_lst1 = []
		N_lst2 = []
		val_lst1 = []
		val_lst2 = []
		if E[e][0] != -1:
			N_lst1, val_lst1 = nums(E[e][0])
		else:
			N_lst1 = [1]
			val_lst1 = []
		
		if E[e][1] != -1:
			N_lst2, val_lst2 = nums(E[e][1])
		else:
			N_lst2 = [1]
			val_lst2 = []
		
		mul1 = cost[e][0]
		for num in val_lst1:
			mul1 *= num
		mul2 = cost[e][1]
		for num in val_lst2:
			mul2 *= num
		for i in range(len(N_lst1)):
			N_lst1[i] *= mul2
		for i in range(len(N_lst2)):
			N_lst2[i] *= mul1
		
		return N_lst1 + N_lst2, val_lst1 + val_lst2 + [cost[e][0] + cost[e][1]]
	N_lst, v_lst = nums(root - 1)
	#print N_lst
	num_GCD = N_lst[0]
	for num in N_lst:
		num_GCD = GCD(num, num_GCD)
	
	for i in range(len(N_lst)):
		N_lst[i] //= num_GCD
	#print N_lst
	print sum(N_lst)