AOJ520 最軽量のモビール

最軽量のモビール

本日2つ目のACなんですが、とくのに時間がかかった自分にキレそうなためブログにします。

コレなんですが、問題の概要としては

木が与えられます。
それぞれの節点には重さw、2つの整数a,bが含まれています。
2つの子の重さをそれぞれとしたときとなるようにします。

根の重さを求めましょう

まともにまとめられていませんが、まあ問題を自分で読めって感じです（は？）
最初は、を満たすにはwはa+bの倍数であるはずということがわかったため,wをa+bの倍数とする
そしたらともわかります。そしたら,の子の重さもわかります。...とすすめていき
どこかで整数では無くなったらそのwでは成り立たない。
もしすべてが整数で成り立った場合はそのwが最小ということになるのでうぇいってやったらTLEでした。
そもそもなぜか途中から答えが合わなくなってたので今度は方針を変えます

w1とw2を仮に定めていた場合、wも仮で定まるのでは無いか？となってもちろん定まります。
なので下から決めていけば根の重さも決められることがわかりますね
ほんとか？って今書きながら思ってますが通ってたのでそうなのでしょう
ここで、葉は重さ1とします。

これで更新していくことが出来ます。
なんで思いついたんでしょうね
今の僕は正当性がよくわからないです
他の人の解説見てきたいと思います

struct stick{
    int l_d, r_d;
    int par, l, r;
};

stick s[101];

ll gcd(ll x, ll y){
    if(y == 0) return x;
    return gcd(y, x%y);
}

ll dfs(ll st){
    if(st == 0) return 1;
    ll l_w = dfs(s[st].l);
    ll r_w = dfs(s[st].r);
    ll res = (l_w*r_w*s[st].l_d*s[st].r_d)/gcd(l_w*s[st].l_d, r_w*s[st].r_d);
    res = res/s[st].l_d + res/s[st].r_d;
    return res;
}

int main(void){
    int n;

    while(cin >> n && n){
        memset(s, 0, sizeof s);
        FOR(i, 1, n+1){
            s[i].par = i;
        }
        FOR(i, 1, n+1){
            int a;
            cin >> s[i].l_d >> s[i].r_d >> s[i].l >> s[i].r;
            a = gcd(s[i].l_d, s[i].r_d);
            s[i].l_d /= a; s[s[i].l].par = i;
            s[i].r_d /= a; s[s[i].r].par = i;
        }
        int start = 1;
        while(s[start].par != start){
            start = s[start].par;
        }
        cout << dfs(start) << endl;
    }
}