AOJ0520 Lightest Mobile

明らかに二分木なのでメモ化再帰するだけ
lcmを求めるところで先に２つをかけていたのでオーバーフローしてずっと悩んでました　そこでみすってるとは...

#include <cstdio>
using namespace std;

typedef struct stick{
	int lren, rren, sl, sr, weight; 
} STICK;

int n, tmp, top;
int depth[101];
STICK st[101];

void init(int k){
	for(int i = 0; i <= k; i++){
		depth[i] = 0;
		st[i].weight = 0;
	}
}

int gcd(int a, int b){
	if(b == 0) return a;
	return gcd(b, a % b);
}

int lcm(int c, int d){
	return c / gcd(c, d) * d;
}

int solve(int k){
	if(st[k].weight > 0){
		return st[k].weight;
	}else{
		tmp = lcm(solve(st[k].sl) * st[k].lren, solve(st[k].sr) * st[k].rren);
		return st[k].weight = tmp / st[k].lren + tmp / st[k].rren;
	}
}

int main(){
	while(scanf("%d", &n)){
		if(n == 0) break;
		init(n);
		st[0].weight = 1;
		for(int i = 1; i <= n; i++){
			scanf("%d %d %d %d", &st[i].lren, &st[i].rren, &st[i].sl, &st[i].sr);
			tmp = gcd(st[i].lren, st[i].rren);
			st[i].lren /= tmp;
			st[i].rren /= tmp;
			if(st[i].sl != 0) depth[st[i].sl]++;
			if(st[i].sr != 0) depth[st[i].sr]++;
		}
		for(int i = 1; i<= n; i++){
			if(depth[i] == 0){
				top = i;
			}
		}
		printf("%d\n", solve(top));
	}
	return 0;
}