1033번: 칵테일

https://www.acmicpc.net/problem/1033

#include<cstdio>
#include<vector>
using namespace std;
typedef long long ll;
ll gcd(ll x, ll y) { return y ? gcd(y, x%y) : x; }
int n;
ll m[10], g;
vector<int> adj[10];
void f(int h, int p, int x) {
    m[h] *= x;
    for (auto it : adj[h]) if (it^p) f(it, h, x);
}
void g1(int h, int p) {
    g = gcd(g, m[h]);
    for (auto it : adj[h]) if (it^p) g1(it, h);
}
void g2(int h, int p, int x) {
    m[h] /= x;
    for (auto it : adj[h]) if (it^p) g2(it, h, x);
}
int main() {
    scanf("%d", &n);
    for (int i = 0, a, b, p, q; i < n - 1; i++) {
        scanf("%d%d%d%d", &a, &b, &p, &q);
        g = gcd(p, q);
        p /= g;
        q /= g;
        if (!m[a] && !m[b]) m[a] = p, m[b] = q;
        else if (!m[a]) m[a] = p*m[b], f(b, -1, q);
        else if (!m[b]) m[b] = q*m[a], f(a, -1, p);
        else {
            ll t = m[a];
            f(a, -1, m[b] * p);
            f(b, -1, t*q);
        }
        adj[a].push_back(b);
        adj[b].push_back(a);
        g = m[a];
        g1(a, -1);
        g2(a, -1, g);
    }
    for (int i = 0; i < n; i++) printf("%lld ", m[i]);
    return 0;
}