AOJ 0520 - Lightest Mobile

再帰的に紐がつり合う最小の重さを求めていけばいいです．
考えはすぐ(2日目)浮かんだけど凡ミス．
今後，スコープとあとでつかう変数の値を変えていないか確認します．

#include<iostream>

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

struct Pole{
	int left, right;
	Pole *red, *blue, *rred, *rblue;
};

// 中和をとった時の重さを返す
int trace(Pole pole){
	int red_w, blue_w;
	if(pole.red == nullptr && pole.blue == nullptr){
		red_w = pole.right;
		blue_w = pole.left;
	}else if(pole.red != nullptr && pole.blue != nullptr){
		red_w = trace(*pole.red);
		blue_w = trace(*pole.blue);

		int g = gcd(pole.left * red_w, pole.right * blue_w),
			_red_w = red_w;

		red_w = pole.right * blue_w / g * _red_w;
		blue_w = pole.left * _red_w / g * blue_w;
	}else{
		if(pole.red == nullptr){
			std::swap(pole.red, pole.blue);
			std::swap(pole.left, pole.right);
		}

		int _red_w = trace(*pole.red),
			g = gcd(pole.left * _red_w, pole.right);
			
		red_w = pole.right / g * _red_w;
		blue_w = pole.left * _red_w / g;
	}

	return red_w + blue_w;
}

int main(){
	int n;
	while(std::cin >> n, n){
		Pole ps[100];

		for(int i=0;i<100;i++){
			ps[i].red = nullptr;
			ps[i].blue = nullptr;
			ps[i].rred = nullptr;
			ps[i].rblue = nullptr;
			ps[i].left = 0;
			ps[i].right = 0;
		}

		for(int i=0;i<n;i++){
			int p, q, r, b;
			std::cin >> p >> q >> r >> b;
			r--;b--;

			int g = gcd(p, q);
			ps[i].left = p / g;
			ps[i].right = q / g;

			if(r != -1){
				ps[i].red = &ps[r];
				ps[r].rred = &ps[i];
			}
		
			if(b != -1){
				ps[i].blue = &ps[b];
				ps[b].rblue = &ps[i];
			}
		}
	
		int parent = 0;
		{
			Pole *p = &ps[0];
			while(p->rred != nullptr || p->rblue != nullptr){
				if(p->rred != nullptr){
					p = p->rred;
				}else{
					p = p->rblue;
				}
			}

			parent = p - &ps[0];
		}

		std::cout << trace(ps[parent]) << std::endl;
	}
}