結果

問題 No.3250 最小公倍数
ユーザー jiangxinyang
提出日時 2025-08-06 11:55:13
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 1,581 ms / 2,000 ms
コード長 3,551 bytes
コンパイル時間 930 ms
コンパイル使用メモリ 90,456 KB
実行使用メモリ 46,752 KB
最終ジャッジ日時 2025-08-29 20:52:40
合計ジャッジ時間 15,796 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 21
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <map>
#include <numeric>
#include <algorithm>

using namespace std;

// 定数
const int MAXN = 500005;
const int MAXA = 1000001;
const int MOD = 998244353;

// グローバル変数
vector<int> adj[MAXN];
int a[MAXN];
int sz[MAXN];
long long ans[MAXN];
int spf[MAXA]; // Smallest Prime Factor

// エラトステネスの篩で最小の素因数を求める
void sieve() {
    iota(spf, spf + MAXA, 0); // spf[i] = i で初期化
    for (int i = 2; i * i < MAXA; ++i) {
        if (spf[i] == i) { // iが素数
            for (int j = i * i; j < MAXA; j += i) {
                if (spf[j] == j) { // まだ最小素因数が更新されていない
                    spf[j] = i;
                }
            }
        }
    }
}

// 高速な素因数分解
map<int, int> get_factors(int n) {
    map<int, int> factors;
    while (n != 1) {
        factors[spf[n]]++;
        n /= spf[n];
    }
    return factors;
}

// mod上のべき乗
long long power(long long base, long long exp) {
    long long res = 1;
    base %= MOD;
    while (exp > 0) {
        if (exp % 2 == 1) res = (res * base) % MOD;
        base = (base * base) % MOD;
        exp /= 2;
    }
    return res;
}

// DFSで部分木のサイズを計算し、重い子を特定する
void dfs_size(int u, int p) {
    sz[u] = 1;
    int heavy_child_idx = -1;
    int max_sz = 0;
    for (size_t i = 0; i < adj[u].size(); ++i) {
        int v = adj[u][i];
        if (v == p) continue;
        dfs_size(v, u);
        sz[u] += sz[v];
        if (sz[v] > max_sz) {
            max_sz = sz[v];
            heavy_child_idx = i;
        }
    }
    // 重い子を隣接リストの先頭に持ってくる
    if (heavy_child_idx != -1) {
        swap(adj[u][0], adj[u][heavy_child_idx]);
    }
}

// DSU on Trees を用いたメインのDFS
map<int, int> dfs_solve(int u, int p) {
    map<int, int> u_lcm_factors;

    // 重い子が存在すれば、その結果を再利用する
    int heavy_child = -1;
    if (!adj[u].empty() && adj[u][0] != p) {
        heavy_child = adj[u][0];
    }

    if (heavy_child != -1) {
        u_lcm_factors = dfs_solve(heavy_child, u);
    }

    // 軽い子の結果をマージする
    for (int v : adj[u]) {
        if (v == p || v == heavy_child) continue;
        map<int, int> lc_lcm_factors = dfs_solve(v, u);
        for (auto const& [prime, exponent] : lc_lcm_factors) {
            u_lcm_factors[prime] = max(u_lcm_factors[prime], exponent);
        }
    }

    // 現在のノードの重みをマージする
    map<int, int> current_factors = get_factors(a[u]);
    for (auto const& [prime, exponent] : current_factors) {
        u_lcm_factors[prime] = max(u_lcm_factors[prime], exponent);
    }

    // uを根とする部分木の答えを計算する
    long long current_ans = 1;
    for (auto const& [prime, exponent] : u_lcm_factors) {
        current_ans = (current_ans * power(prime, exponent)) % MOD;
    }
    ans[u] = current_ans;

    return u_lcm_factors;
}

int main() {
    // 高速化
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    sieve();

    int n;
    cin >> n;

    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
    }

    for (int i = 0; i < n - 1; ++i) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    // 1を根として処理を開始
    dfs_size(1, 0);
    dfs_solve(1, 0);

    for (int i = 1; i <= n; ++i) {
        cout << ans[i] << "\n";
    }

    return 0;
}
0