らての精進日記

修行をします

aoj0520:Lightest Mobile

解法

まず、モビール全体をグラフと考えると木となる。そして根も簡単に見つけられる(入次数が0の頂点)。
あとはlcmとかを使って再帰的に重さを計算していけばよい。

コード

#include<bits/stdc++.h>
using namespace std;

int N;
int p[100],q[100],r[100],b[100];

int gcd(int x,int y){
    return y?gcd(y,x%y):x;
}
int lcm(int x,int y){
    return x/gcd(x,y)*y;
}

int dfs(int pos){
    if(!~pos)return 1;
    int x=dfs(r[pos])*p[pos],y=dfs(b[pos])*q[pos];
    int l=lcm(x,y);
    return l/p[pos]+l/q[pos];
}

void solve(){
    int D[100]={0};
    for(int i=0;i<N;i++){
        scanf("%d%d%d%d",&p[i],&q[i],&r[i],&b[i]);
        r[i]--;b[i]--;
        if(~r[i])D[r[i]]++;
        if(~b[i])D[b[i]]++;
    }

    for(int i=0;i<N;i++){
        if(!D[i]){
            printf("%d\n",dfs(i));
            return;
        }
    }

}

int main(){
    while(scanf("%d",&N),N)solve();
    return 0;
}