AOJ 0520: Status of Lightest Mobile

メモ化再帰で解きました。
順番にモビールを選び、そこから下のモビールの重さ(の最小値)を再帰的に求めます。
重さ * 長さ = モーメント
なので、両方のモーメントを求めて、整数倍(最小公倍数を求める)し釣り合わせます。
重さ = モーメント / 長さ
で、重さを更新します。

#include<cstdio>
#include<vector>
using namespace std;

struct sp{
	int p;
	int q;
	int l;
	int r;
	int w;//モビール全体の最小の重さ(0のとき未確定)
	sp(int p,int q,int l,int r,int w = 0)
		:p(p),q(q),l(l),r(r),w(w){}
};

int solve(vector<sp>&);
int figure(vector<sp>&,int);
int lcm(int,int);

int main(){
	int n;
	while(scanf("%d",&n),n){
		vector<sp> s;
		s.push_back(sp(0,0,0,0,1));//錘
		
		for(int i = 1; i <= n; i++){
			int p,q,l,r;
			scanf("%d%d%d%d",&p,&q,&l,&r);
			s.push_back(sp(p,q,l,r));
		}
		
		printf("%d\n",solve(s));
	}
	return 0;
}

int solve(vector<sp>& s){
	int res = 1;
	for(int i = 1,l = s.size(); i < l; i++){
		res = max(res,figure(s,i));//一番上のモビールを調べてないので、全部調べる
	}
	return res;
}

//最小の重さを求める
int figure(vector<sp>& s,int x){
	if(s[x].w)return s[x].w;
	int moment = lcm(figure(s,s[x].l)*s[x].p, figure(s,s[x].r)*s[x].q);
	return s[x].w = moment/s[x].p + moment/s[x].q;
}

//最小公倍数
int lcm(int a,int b){
	if(a>b)swap(a,b);
	int k = 1;
	for(int i = 2; i <= a ; i++){
		while(!(a%i)&&!(b%i)){
			a /= i;
			b /= i;
			k *= i;
		}
	}
	return a*b*k;
}