AOJ : 0520 - 最軽量のモビール (Lightest Mobile)

問題概要

http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=0520&lang=jp
日本語の問題文なので, 説明はなしです

アルゴリズム

この問題の入力は, かならず2分木になることがわかります.
この木のルートから探索を始めて, 深さ優先で木を探索していきます.
再帰関数の戻り値として, 「現在見ている棒より下のモビールの最小重量」を返すようにしておきます. そうすれば, 木の深いところから順番に, 最小の重量が決まっていき, 最終的に全体の最小重量が決定できます.

モビールの最小重量は,

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

となるように, 「最小公倍数」で決定できます.

プログラム

#include <iostream>
#include <cstring>
using namespace std;

int n,p[101],q[101],r[101],b[101];
bool flg[101]; //上からつるされているかのフラグ

//最大公約数
int gcd(int a,int b){
  return b == 0 ? a : gcd(b,a%b);
}

//最小公倍数
int lcm(int a,int b){
  return a / gcd(a,b) * b;
}

int solve(int idx){
  int res = 0;

  int rcost = r[idx] ? solve(r[idx]) : 1;
  int bcost = b[idx] ? solve(b[idx]) : 1;
  int l = lcm(p[idx] * rcost, q[idx] * bcost);

  return l / p[idx] + l / q[idx];
}

int main(void){
  while(cin>>n, n){
    memset(flg,0,sizeof(flg));
    for(int i=1;i<=n;i++){
      cin>>p[i]>>q[i]>>r[i]>>b[i];
      flg[r[i]] = flg[b[i]] = true; //上からつるされている棒をtrueにする
    }

    for(int i=1;i<=n;i++){
      //上からつるされていない棒ならば, ルートノード
      if(!flg[i]){
        cout<<solve(i)<<endl;
        break;
      }
    }
  }

  return 0;
}