結果

問題 No.3250 最小公倍数
ユーザー jiangxinyang
提出日時 2025-08-04 01:09:58
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
RE  
(最新)
AC  
(最初)
実行時間 -
コード長 3,430 bytes
コンパイル時間 2,710 ms
コンパイル使用メモリ 240,596 KB
実行使用メモリ 45,912 KB
最終ジャッジ日時 2025-08-29 20:50:41
合計ジャッジ時間 12,996 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 13 RE * 8
権限があれば一括ダウンロードができます

ソースコード

diff # 

#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("Ofast")
#pragma GCC optimize(2)
#pragma GCC optimize(3)

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

#define rep(i, l, r) for (int i = (l); i <= (r); ++i)
#define per(i, l, r) for (int i = (r); i >= (l); --i)
#define pr pair<int, int>
#define fi first
#define se second
#define pb push_back
#define aint(x) (x).begin(), (x).end()
#define bg(x) (x).begin()
#define ed(x) (x).end()
#define sz(x) (int)(x).size()

#define N 200005
#define M 22
#define int long long

const int mod = 998244353;
int n, a[N], ans[N], siz[N], son[N], fa[N];
int iv[N], cnt[N];
int now = 1;
vector<int> e[N], g[N], c[N];
bitset<N> f, tmp;

inline int qpow(int a, int b) {
    int ans = 1;

    while (b) {
        if (b & 1) {
            ans = ans * a % mod;
        }
        a = a * a % mod;
        b >>= 1;
    }

    return ans;
}

inline void dfs0(int k, int f) {
    siz[k] = 1;
    fa[k] = f;

    for (int x : e[k]) {
        if (x == f) {
            continue;
        }

        dfs0(x, k);

        siz[k] += siz[x];

        if (siz[x] > siz[son[k]]) {
            son[k] = x;
        }
    }
}

inline void edit(int k, int d) {
    int len = sz(g[k]);

    rep(i, 0, len - 1) {
        int x = g[k][i], y = c[k][i];

        if (d == -1) {
            cnt[x] = 0;
            continue;
        }

        if (y > cnt[x]) {
            now = now * qpow(x, y - cnt[x]) % mod;
            cnt[x] = y;
        }
    }
}

inline void add(int k, int d) {
    edit(a[k], d);

    for (int x : e[k]) {
        if (x == fa[k]) {
            continue;
        }

        add(x, d);
    }
}

inline void calc(int k, bool r) {
    for (int x : e[k]) {
        if (x == fa[k] || x == son[k]) {
            continue;
        }

        calc(x, 0);
    }

    if (son[k]) {
        calc(son[k], 1);
    }

    edit(a[k], 1);

    for (int x : e[k]) {
        if (x == fa[k] || x == son[k]) {
            continue;
        }

        add(x, 1);
    }

    ans[k] = now;

    if (!r) {
        add(k, -1);
        now = 1;
    }
}

inline void ndiv(int k) {
    int res = k;
    c[k].resize(sz(g[k]));

    rep(i, 0, sz(g[k]) - 1) {
        int x = g[k][i];
        c[k][i] = 0;
        while (res % x == 0) {
            res /= x;
            c[k][i]++;
        }
    }

    // cout<<"div "<<k<<":\n";

    // rep(i,0,sz(g[k])-1){
    //     cout<<g[k][i]<<' '<<c[k][i]<<"\n";
    // }

    // cout<<"\n";
}

inline void init(int lim) {
    f[1] = 1;

    rep(i, 2, lim) {
        if (f[i]) {
            continue;
        }
        if (tmp[i]) {
            g[i].pb(i);
        }

        if (tmp[i]) {
            g[i].pb(i);
        }

        rep(j, 2, lim) {
            if (i * j > lim) {
                break;
            }

            f[i * j] = 1;
            if (tmp[i * j]) {
                g[i * j].pb(i);
            }
        }
    }

    rep(i, 1, n) {
        if (!tmp[a[i]]) {
            continue;
        }

        tmp[a[i]] = 0;
        ndiv(a[i]);
    }
}

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n;
    rep(i, 1, n) {
        cin >> a[i];
        tmp[a[i]] = 1;
    }

    init(*max_element(a + 1, a + 1 + n));

    rep(i, 1, n - 1) {
        int u, v;
        cin >> u >> v;
        e[u].pb(v);
        e[v].pb(u);
    }

    dfs0(1, 0);
    calc(1, 1);

    rep(i, 1, n) { cout << ans[i] << '\n'; }

    return 0;
}
0