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; } }