JOI'07本選 5問目 最軽量のモビール

問題概要

モビールが釣り合うようにおもりを設定するとき,重さの合計の最小値を求めなさい.

解法

モビールの根を探し,再帰的に計算していく.

左右ともに錘のとき

gcd(a,b)/a+gcd(a,b)/bが最小

左右ともにモビールのとき

左のモビールの最小をl,右のモビールの最小をrと置くと,
gcd(l*a,r*b)/l+gcd(l*a,r*b)/rが最小
片方がモビールのとき,l,rを1に置き換えて考えれば良い.
配列外アクセスには気をつけよう…

ソースコード

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define FOR(i,n,m) for(int i=(n);i<(m);i++)
#define REP(i,n) FOR(i,0,n)
#define REPR(i,n) for(int i=(n);i>=0;i--)
#define all(vec) vec.begin(),vec.end()
using vi=vector<int>;
using vvi=vector<vi>;
using vl=vector<ll>;
using vvl=vector<vl>;
using P=pair<ll,ll>;
using PP=pair<ll,P>;
using vp=vector<P>;
using vpp=vector<PP>;
using vs=vector<string>;
#define fi first
#define se second
#define pb push_back
template<class T>bool chmax(T &a,const T &b){if(a<b){a=b;return true;}return false;}
template<class T>bool chmin(T &a,const T &b){if(a>b){a=b;return true;}return false;}
const ll MOD=1000000007LL;
const int INF=1<<30;
const ll LINF=1LL<<60;
ll gcd(ll a,ll b){
    return b==0?a:gcd(b,a%b);
}
ll lcm(ll a,ll b){
    return a/gcd(a,b)*b;
}
vl a,b,c,d;
vl parent;
ll dfs(ll x){
    if(c[x]==-1&&d[x]==-1){
        ll l=lcm(a[x],b[x]);
        return l/a[x]+l/b[x];
    }
    ll p=c[x]==-1?1:dfs(c[x]);
    ll q=d[x]==-1?1:dfs(d[x]);
    ll l=lcm(a[x]*p,b[x]*q);
    return l/a[x]+l/b[x];
}
int main(){
    ll n;
    cin>>n;
    a.resize(n);
    b.resize(n);
    c.resize(n);
    d.resize(n);
    parent.resize(n,-1);
    REP(i,n){
        cin>>a[i]>>b[i]>>c[i]>>d[i];
        c[i]--;d[i]--;
        if(c[i]!=-1){
            parent[c[i]]=i;
        }
        if(d[i]!=-1){
            parent[d[i]]=i;
        }
    }
    ll root;
    REP(i,n){
        if(parent[i]==-1){
            root=i;
        }
    }
    cout<<dfs(root)<<endl;
    return 0;
}