結果

問題 No.3250 最小公倍数
ユーザー pockyny
提出日時 2025-09-02 08:44:10
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 6,865 bytes
コンパイル時間 1,550 ms
コンパイル使用メモリ 105,380 KB
実行使用メモリ 50,240 KB
最終ジャッジ日時 2025-09-02 08:44:34
合計ジャッジ時間 18,719 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 18 TLE * 1 -- * 2
権限があれば一括ダウンロードができます

ソースコード

diff # 

// verified: https://yukicoder.me/submissions/1102184
// verified: https://codeforces.com/contest/2063/submission/326584003
// verified: https://atcoder.jp/contests/abc359/submissions/67289775

#include <iostream>
#include <vector>

using namespace std;

// 参考: https://nyaannyaan.github.io/library/tree/dsu-on-tree.hpp.html
// ただし、パスクエリにもこたえられるように、dfsで探すようにしている
template <typename T = int>
struct DSUonTree {
    vector<vector<T>> g;
    vector<int> sz;
    // 部分木クエリにeuler tourで答えるように、iの子要素を列挙する
    // ただし、lca(u,v)に対して、条件を満たす(u,v)を数える場合はdfs的に潜るので、これらを使って列挙しても意味がない
    vector<int> euler,up,down;
    // eulerとかを途中で使う用のcount
    int idx_;
    // 根
    int root;
    // sub tree計算用
    void dfs1(int cur, int par = -1){
        sz[cur] = 1;
        if ((int)g[cur].size() >= 2 && g[cur][0] == par) swap(g[cur][0], g[cur][1]);
        for(T &v : g[cur]){
            if (v == par) continue;
            dfs1(v,cur);
            sz[cur] += sz[v];
            if (sz[v] > sz[g[cur][0]]) swap(v, g[cur][0]);
        }
    }
    void dfs2(int cur, int par = -1) {
        euler[idx_] = cur;
        down[cur] = idx_++;
        for(auto &v : g[cur]){
            if (v == par) continue;
            dfs2(v, cur);
        }
        up[cur] = idx_;
    }
    
    DSUonTree(vector<vector<T>> &_g,int _root = 0)
      : g(_g),
        sz(_g.size()),
        euler(_g.size()),
        up(_g.size()),
        down(_g.size()),
        idx_(0),
        root(_root){
            dfs1(root);
            dfs2(root);
        }
        
    template <typename UPDATE, typename QUERY, typename CLEAR, typename RESET>
    void run(UPDATE &update, QUERY &query, CLEAR &clear, RESET &reset) {
        auto dfs_update = [&](auto rc,int cur,int par = -1) -> void {
            update(cur);
            for(int u:g[cur]){
                if(u==par) continue;
                rc(rc,u,cur);
            }
            return;
        };
        auto dfs_calc = [&](auto rc,int lca,int cur,int par = -1) -> void {
            query(cur,lca);
            for(int u:g[cur]){
                if(u==par) continue;
                rc(rc,lca,u,cur);
            }
            return;
        };
        auto dsu = [&](auto rc, int cur, int par = -1, bool keep = false) -> void {
            for (int i = 1; i < (int)g[cur].size(); i++){
                if (g[cur][i] != par) rc(rc, g[cur][i], cur, false);
            }
            if(sz[cur]!= 1) rc(rc, g[cur][0], cur, true);
            if (sz[cur] != 1){
                for(int i=1;i<g[cur].size();i++){
                    if(g[cur][i]==par) continue;
                    dfs_calc(dfs_calc,cur,g[cur][i],cur);
                    dfs_update(dfs_update,g[cur][i],cur);
                }
            }
            update(cur);
            query(cur,cur);
            if (!keep){
                for (int i = down[cur]; i < up[cur]; i++) clear(euler[i]);
                reset();
            }
            return;
        };
        dsu(dsu, root);
    }
    // 以下はmainの中に書いてもよい
    // node iの中身をglobalなデータに反映する
    // auto update = [&](int i) {};

    // 片方がiで、lcaを固定したときに条件を満たすクエリに答える (iはlcaの部分木に含まれる)
    // i==lcaのケース: lcaの部分木の任意の頂点iに対して、(lca,i)という頂点対のクエリを一気に計算する (総和みたいな感じ)
    // i≠lcaのケース: lcaの子孫vに対し、(i,v)の組に対するクエリを一気に計算する
    // (i,v)は必ず親子関係ではない。探索順的に、(i,v)と、(v,i)を重複してカウントはしない
    // 総じて、(i,lca)というのは、lcaの子孫 (lca自身も含む) の2頂点に対するクエリを実行して総和を取れる
    // lcaの部分木全体に対するクエリ (総和とか)に答えたいときは、globalなデータ構造に部分木としての情報を載せていって、i==lcaの時に答えに反映とかするのがよい
    // auto query = [&](int i,int lca){};

    // seg木とかの場合、一気にresetするのが難しいのでこっちで頂点ごとにclearする
    // auto clear = [&](int i) {};

    // データ構造を空にする
    // auto reset = [&]() {};
};

#include <atcoder/modint>
#include <unordered_map>

using namespace std;
using namespace atcoder;
using mint = modint998244353;
const int MX = 1000000;
int pr[MX + 10];
int a[500010];
mint ans[500010];
int main(){
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int i,j,n; cin >> n;
    for(i=0;i<n;i++) cin >> a[i];
    for(i=2;i<=MX;i++){
        if(pr[i]) continue;
        for(j=i;j<=MX;j+=i) pr[j] = i;
    }
    vector<vector<int>> g(n);
    for(i=0;i<n - 1;i++){
        int u,v; cin >> u >> v; u--; v--;
        g[u].push_back(v); g[v].push_back(u);
    }

    mint c = 1;
    unordered_map<int,int> um,_um;
    // node iの中身をglobalなデータに反映する
    auto update = [&](int i) {
        _um.clear();
        int x = a[i];
        while(x>1){
            _um[pr[x]]++;
            x /= pr[x];
        }
        for(auto [k,v]:_um){
            if(v>um[k]){
                for(int id=0;id<v - um[k];id++) c *= (mint)k;
                um[k] = v;
            }
        }
    };

    // 片方がiで、lcaを固定したときに条件を満たすクエリに答える (iはlcaの部分木に含まれる)
    // i==lcaのケース: lcaの部分木の任意の頂点iに対して、(lca,i)という頂点対のクエリを一気に計算する (総和みたいな感じ)
    // i≠lcaのケース: lcaの子孫vに対し、(i,v)の組に対するクエリを一気に計算する
    // (i,v)は必ず親子関係ではない。探索順的に、(i,v)と、(v,i)を重複してカウントはしない
    // 総じて、(i,lca)というのは、lcaの子孫 (lca自身も含む) の2頂点に対するクエリを実行して総和を取れる
    // lcaの部分木全体に対するクエリ (総和とか)に答えたいときは、globalなデータ構造に部分木としての情報を載せていって、i==lcaの時に答えに反映とかするのがよい
    auto query = [&](int i,int lca){
        if(i==lca) ans[i] = c;
    };

    // seg木とかの場合、一気にresetするのが難しいのでこっちで頂点ごとにclearする
    auto clear = [&](int i) {};

    // データ構造を空にする
    auto reset = [&]() { c = 1; um.clear();};

    DSUonTree<int> dst(g);
    dst.run(update,query,clear,reset);
    for(i=0;i<n;i++){
        cout << ans[i].val() << "\n";
    }
}
0