Submission #1983911

---

Source Code Expand

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <queue>
#include <set>
#include <map>
using namespace std;

typedef long long ll;

int n;

struct stick
{
    ll p;
    ll q;
    int r;
    int b;
};

vector<stick> ss;

ll node[110];

ll gcd(ll a, ll b)
{
    if (b == 0)
        return a;
    return gcd(b, a % b);
}

ll rec(int in)
{
    if(in == 0) return 1;
    int p = ss[in].p;
    int q = ss[in].q;
    int r = ss[in].r;
    int b = ss[in].b;
    {
        ll rt = rec(r);
        ll bt = rec(b);
        ll rt2 = rt * p;
        ll bt2 = bt * q;
        ll g = gcd(rt2, bt2);
        node[in] = rt2 / g * bt + bt2 / g * rt;
    }
    return node[in];
}

int main()
{
    cin >> n;
    ss.resize(110);
    vector<int> memo(n + 1, true);

    for (int i = 1; i <= n; ++i)
    {
        cin >> ss[i].p >> ss[i].q >> ss[i].r >> ss[i].b;
        if (ss[i].r != 0)
        {
            memo[ss[i].r] = false;
        }
        if (ss[i].b != 0)
        {
            memo[ss[i].b] = false;
        }
    }
    for (int i = 1; i <= n; ++i)
    {
        if (memo[i])
            cout << rec(i) << endl;
    }

    return 0;
}

Submission Info

Judge Result