結果

問題 No.3250 最小公倍数
ユーザー areik
提出日時 2025-08-30 02:50:33
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 1,846 ms / 2,000 ms
コード長 2,459 bytes
コンパイル時間 3,868 ms
コンパイル使用メモリ 259,884 KB
実行使用メモリ 119,536 KB
最終ジャッジ日時 2025-08-30 02:51:14
合計ジャッジ時間 30,198 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 21
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

using i32 = int;
using i64 = long long;
using f64 = double;
using p2 = pair<i64, i64>;
using el = tuple<i64, i64, i64>;
using mint = atcoder::modint998244353;

void _main();
int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  _main();
}

i32 n;
i32 siz[500000];
i32 idx[500000], jdx[500000];
mint inv[1000001];
vector<i32> preo;
vector<i32> g[500000];
vector<i32> P;
vector<pair<i32, i32>> fac[500000];
void dfs1(i32 v, i32 par) {
  siz[v] = 1;
  idx[v] = jdx[v] = preo.size();
  preo.push_back(v);
  for (i32 nv : g[v]) {
    if (nv != par) {
      dfs1(nv, v);
      siz[v] += siz[nv];
      jdx[v] = jdx[nv];
    }
  }
}
vector<i32> mxp;
mint now;
mint ans[500000];
void dfs2(i32 v, i32 par, bool keep) {
  i32 mxc = -1, vh = -1;
  for (i32 nv : g[v]) if (nv != par && mxc < siz[nv]) mxc = siz[nv], vh = nv; 
  for (i32 nv : g[v]) if (nv != par && nv != vh) {
    dfs2(nv, v, false);
  }
  if (vh != -1) dfs2(vh, v, true);
  else now = 1;
  for (i32 nv : g[v]) if (nv != par && nv != vh) {
    for (i32 i = idx[nv]; i <= jdx[nv]; i++) {
      for (auto [id, s] : fac[preo[i]]) {
        if (mxp[id] < s) {
          now *= inv[mxp[id]];
          now *= s;
          mxp[id] = s;
        }
      }
    }
  }
  for (auto [id, s] : fac[v]) {
    if (mxp[id] < s) {
      now *= inv[mxp[id]];
      now *= s;
      mxp[id] = s;
    }
  }
  ans[v] = now;
  if (keep) return;
  for (i32 i = idx[v]; i <= jdx[v]; i++) {
    for (auto [id, s] : fac[preo[i]]) {
      mxp[id] = 1;
    }
  }
  now = 1;
}
void _main() {
  static i32 mod = 998244353;
  inv[1] = 1;
  for (i32 i = 2; i <= 1000000; i++) inv[i] = -inv[mod % i] * (mod / i);
  cin >> n;
  {
    vector<vector<pair<i32, i32>>> prime(1000001);
    for (i32 i = 2; i <= 1000000; i++) {
      if (!prime[i].empty()) continue;
      i32 id = P.size();
      P.push_back(i);
      prime[i].emplace_back(id, i);
      for (i32 j = i * 2; j <= 1000000; j += i) {
        i32 x = 1;
        while (j % (x * i) == 0) x *= i;
        prime[j].emplace_back(id, x);
      }
    }
    for (i32 i = 0; i < n; i++) {
      i32 x; cin >> x;
      fac[i] = prime[x];
    }
  }
  for (i32 i = 0; i < n - 1; i++) {
    i32 u, v;
    cin >> u >> v;
    u--, v--;
    g[u].push_back(v);
    g[v].push_back(u);
  }
  mxp = vector<i32>(P.size(), 1);
  dfs1(0, -1);
  dfs2(0, -1, false);
  for (i32 i = 0; i < n; i++) cout << ans[i].val() << "\n";
}
0