1. 题意

一种药品有有n种成分，成分i与成分j之间的比例为x:y，给n - 1条比例数据，在所有成分均为整数的情况下，输出所有成分的和（结果唯一），结果可能较大，需要模998244353.

2. 思路

根据题意中n个点和n-1条边，结果唯一，可得到图为树。进而可假设从顶点1出发，成分为1,用1次dfs得到所有成分的分数形式，求分母的最小公倍数为lcm,让每个成分乘以lcm即可得到结果。但这种做法存在爆掉long long的情况，则需要用数组根据质因数去维护最小公倍数，而后再用一次dfs求得结果。另外，需要用set维护所所涉及到的质因数，否则会超时。

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int N = 2e5 + 10, M = 2 * N;
const ll mod = 998244353;
int d[N];
int n;
int h[N], e[M], ne[M], idx;
int w1[M], w2[M];
int cnt[N], mx[N];
vector<int> mp[N];
set<int> s;

ll qpow(ll a, ll b){
    b %= mod;
    ll res = 1;
    while (b){
        if (b & 1) res = (res * a) % mod;
        a = (a * a) % mod; b /= 2;
    }
    return res;
}

void init(){
    for (int i = N - 1; i > 1; i --)
        for (int j = i; j < N; j += i)
            d[j] = i;
    for (int i = 2; i < N; i ++)
        for (int j = i; j > 1; j /= d[j])
            mp[i].push_back(d[j]);
}

void add(int a, int b, int x, int y){ // x为分母
    e[idx] = b, ne[idx] = h[a], w1[idx] = x, w2[idx] = y, h[a] = idx ++;
}


void dfs1(int u, int fa){
    for (int i = h[u]; ~i; i = ne[i]){
        int j = e[i], x = w1[i], y = w2[i];
        if (j == fa) continue;
        for (auto p : mp[y]) cnt[p] --, s.insert(p);
        for (auto p : mp[x]) cnt[p] ++, mx[p] = max(mx[p], cnt[p]), s.insert(p);
        dfs1(j, u);
        for (auto p : mp[y]) cnt[p] ++;
        for (auto p : mp[x]) cnt[p] --;
    }
}
ll ans = 0;
void dfs2(int u, int fa, ll be){
    ans = (ans + be) % mod;
    ll copy = be; 
    for (int i = h[u]; ~i; i = ne[i]){
        int j = e[i];
        if (j == fa) continue;
        be = be * w2[i] % mod;
        be = be * qpow(1ll * w1[i], mod - 2) % mod;
        dfs2(j, u, be);
        be = copy;
    }
}

void solve(){
    s.clear();
    scanf("%d", &n);
    memset(h, -1, sizeof h); idx = 0;
    memset(mx, 0, sizeof mx);
    ans = 0;
    for (int i = 1; i < n; i ++){
        int s, t, x, y;
        scanf("%d%d%d%d", &s, &t, &x, &y);
        add(s, t, x, y), add(t, s, y, x);
    }
    dfs1(1, -1);
    dfs2(1, -1, 1ll);

    for (auto x: s) ans = ans * qpow(x, mx[x]) % mod;
    cout << ans << endl;
}

int main (){
    int T;
    scanf("%d", &T);
    init();
    while (T --){
        solve();
    }
    return 0;
}