迷いませんか?

プログラミング、電子工作、ゲーム・・・etc、色々やるけど中途半端なブログです。

AOJ520 最軽量のモビール

最軽量のモビール

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


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

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

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

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

\displaystyle w_1 = \frac{LCM(w_1 \times a, w_2 \times b)}{a}
\displaystyle w_2 = \frac{LCM(w_1 \times a, w_2 \times b)}{b}
\displaystyle w = w_1 + w_2

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

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