0520 Lightest Mobile

http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=0520

方針

dfsして、先端の方から順番に重さを決める。

ソース

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

#define REP(i,a,b) for(i=a; i<b; ++i)
#define rep(i,n) REP(i,0,n)

struct mobile {
  int lm,rm,lc,rc,ll,rl;
  mobile(int lc,int rc,int ll,int rl) : lc(lc), rc(rc), ll(ll), rl(rl) {
    lm = rm = -1;
  }
};

int gcd(int a,int b) {
  return b != 0 ? gcd(b, a%b) : a;
}

int lcm(int a,int b) {
  return a/gcd(a,b)*b;
}

int dfs(int pos,vector<mobile> &vm) {
  mobile now = vm[pos];
  now.lm = (now.lc == -1) ? 1 : dfs(now.lc,vm);
  now.rm = (now.rc == -1) ? 1 : dfs(now.rc,vm);
  int g = lcm(now.ll*now.lm, now.rl*now.rm);
  now.rm = g / now.rl;
  now.lm = g / now.ll;
  return now.rm+now.lm;
}

int main() {
  int n,i,p,q,r,b;
  while(cin>>n, n) {
    vector<mobile> vm;
    vector<bool> isroot(n+1,true);
    rep(i,n) {
      cin>>p>>q>>r>>b;
      r--,b--;
      if(r >= 0) isroot[r] = false;
      if(b >= 0) isroot[b] = false;
      vm.push_back(mobile(r,b,p,q));
    }

    rep(i,n) if(isroot[i] == true) cout<<dfs(i,vm)<<endl;
  }
}