解法
まず、モビール全体をグラフと考えると木となる。そして根も簡単に見つけられる(入次数が0の頂点)。
あとはlcmとかを使って再帰的に重さを計算していけばよい。
コード
#include<bits/stdc++.h>
using namespace std;
int N;
int p[100],q[100],r[100],b[100];
int gcd(int x,int y){
return y?gcd(y,x%y):x;
}
int lcm(int x,int y){
return x/gcd(x,y)*y;
}
int dfs(int pos){
if(!~pos)return 1;
int x=dfs(r[pos])*p[pos],y=dfs(b[pos])*q[pos];
int l=lcm(x,y);
return l/p[pos]+l/q[pos];
}
void solve(){
int D[100]={0};
for(int i=0;i<N;i++){
scanf("%d%d%d%d",&p[i],&q[i],&r[i],&b[i]);
r[i]--;b[i]--;
if(~r[i])D[r[i]]++;
if(~b[i])D[b[i]]++;
}
for(int i=0;i<N;i++){
if(!D[i]){
printf("%d\n",dfs(i));
return;
}
}
}
int main(){
while(scanf("%d",&N),N)solve();
return 0;
}