CF1654D

想到了，但很难实现

Potion Brewing Class

题意

有 $n(n \le 2 \times 10^5)$ 个未知正整数，给定 $n - 1$ 个形如“ $a_i : a_j = x : y(x, y \le n)$ ”的约束条件，要求给这 $n$ 个数赋值，使其满足所有条件，输出最小的 $\sum a_i$ ，答案对 $998244353$ 取模，保证一定有唯一解

思路

由于保证有唯一解，所以可以把数看作点，条件看作边，这就是一棵树，我们发现只要一个数确定了，整棵树就确定了（但最初确定的那个数一定要合法），所以直接把树根先赋值为一个一定正确，但不一定最小的值，然后去确定整棵树，最后所有数字以前约掉公约数；由于有模数（最小共倍数太大了），我们要把每个数存成质因数分解的形式，有人用数组存直接实现，我 太弱了 只会用 map ，比他们多一个 $\log n$

难点在实现上，考场上没打出来，下面是一些细节：

1. 给的 $x : y$ 可能不是最简的
2. 对于把一个数分解质因数，可以在最初筛质数时给每个数记录一个最小质因数，每次把最小质因数除出来，单个时间为 $O(\log n)$

代码

#include <bits/stdc++.h>
#define STC static
#define fi first
#define se second
using LL = long long;
const int N = 2e5 + 100, P = 998244353;
int n, pr[N], ct = 0, mp[N], num[N], ans;
struct Edge{ int to, x, y; };
std::vector<Edge> G[N];
std::map<int, int> ha, as;
int gcd(int a, int b){ return b ? gcd(b, a % b) : a; }
void prev()
{
    STC std::bitset<N> vis;
    memset(mp, 0x3f, sizeof mp);
    vis[1] = 1;
    for (int i = 2; i < N; ++i)
    {
        if (!vis[i]){ pr[++ct] = i, mp[i] = i; }
        for (int j = 1, t; j <= ct && LL(pr[j]) * i < N; ++j)
        {
            mp[pr[j] * i] = std::min(mp[pr[j]], mp[i]), vis[pr[j] * i] = 1;
            if (i % pr[j] == 0) break;
        }
    }
}
int qpow(int x, int y)
{
    int res = 1;
    for (; y; y >>= 1, x = LL(x) * x % P) if (y & 1) res = LL(res) * x % P;
    return res;
}
int get_ans()
{
    int res = 1;
    for (auto i : as) res = LL(res) * qpow(i.fi, i.se) % P;
    return res;
}
bool chkmin(int &x, int &y){ return x > y ? x = y, 1 : 0; }
void dfs(int x, int fa, int now)
{
    for (auto e : G[x]) if (e.to != fa)
    {
        num[e.to] = LL(now) * qpow(e.x, P - 2) % P * e.y % P;
        int t = e.x;
        for (int cnt, tp; t != 1; )
        {
            cnt = 0, tp = mp[t];
            while (t % tp == 0) ++cnt, t /= tp;
            chkmin(as[tp], ha[tp] -= cnt);
        }
        t = e.y;
        for (int cnt, tp; t != 1; )
        {
            cnt = 0, tp = mp[t];
            while (t % tp == 0) ++cnt, t /= tp;
            ha[tp] += cnt;
        }
        dfs(e.to, x, num[e.to]);
        t = e.x;
        for (int cnt, tp; t != 1; )
        {
            cnt = 0, tp = mp[t];
            while (t % tp == 0) ++cnt, t /= tp;
            ha[tp] += cnt;
        }
        t = e.y;
        for (int cnt, tp; t != 1; )
        {
            cnt = 0, tp = mp[t];
            while (t % tp == 0) ++cnt, t /= tp;
            ha[tp] -= cnt;
        }
    }
}
int main()
{
    int T;
    for (prev(), scanf("%d", &T); T--; )
    {
        scanf("%d", &n), ans = 0;
        for (int i = 1; i <= n; ++i) G[i].clear();
        ha.clear(), as.clear();
        for (int i = 1, a, b, c, d, t; i < n; ++i)
        {
            scanf("%d %d %d %d", &a, &b, &c, &d), t = gcd(c, d);
            c /= t, d /= t;
            G[a].push_back({b, c, d}), G[b].push_back({a, d, c});
            for (int cnt, tp; c != 1; )
            {
                cnt = 0, tp = mp[c];
                while (c % tp == 0) ++cnt, c /= tp;
                ha[tp] += cnt;
            }
            for (int cnt, tp; d != 1; )
            {
                cnt = 0, tp = mp[d];
                while (d % tp == 0) ++cnt, d /= tp;
                ha[tp] += cnt;
            }
        }
        as = ha;
        dfs(1, -1, num[1] = get_ans());
        int iv = qpow(get_ans(), P - 2);
        for (int i = 1; i <= n; ++i) num[i] = LL(iv) * num[i] % P;
        for (int i = 1; i <= n; ++i) ans = (ans + num[i]) % P;
        printf("%d\n", ans);
    }
    return 0;
}