結果
問題 |
No.3250 最小公倍数
|
ユーザー |
![]() |
提出日時 | 2025-09-02 09:17:32 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
TLE
|
実行時間 | - |
コード長 | 7,006 bytes |
コンパイル時間 | 1,707 ms |
コンパイル使用メモリ | 121,036 KB |
実行使用メモリ | 50,180 KB |
最終ジャッジ日時 | 2025-09-02 09:17:54 |
合計ジャッジ時間 | 20,107 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 18 TLE * 1 -- * 2 |
ソースコード
// 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]; mint pw(mint k,int x){ mint ret = 1; while(x){ if(x&1) ret *= k; k *= k; x /= 2; } return ret; } 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; // node iの中身をglobalなデータに反映する auto update = [&](int i) { int x = a[i]; while(x>1){ int p = pr[x],e = 0; mint y = 1; while(x%p==0){ x /= p; e++; if(e>um[p]) y *= p; } if(um[p]<e){ c *= y; um[p] = e; } } }; // 片方が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"; } }