#1142323 (C++23) No.3250 最小公倍数

• 問題: No.3250 最小公倍数
• ユーザー: zoidzium (zz)
• 提出日時: 2025-12-30 14:39:18
• 言語: C++23 (gcc 13.3.0 + boost 1.89.0)
• 結果: RE
• 実行時間: -
• コード長: 15,870 bytes
• コンパイル時間: 3,865 ms
• コンパイル使用メモリ: 297,668 KB
• 実行使用メモリ: 45,264 KB
• 最終ジャッジ日時: 2025-12-30 14:39:43
• 合計ジャッジ時間: 24,576 ms
• ジャッジサーバーID （参考情報）: judge1 / judge2

ファイルパターン	結果
sample	AC * 1
other	AC * 1 RE * 22

ソースコード

#include <bits/stdc++.h>

#include <cassert>
using namespace std;
using ull = unsigned long long;
using ll = long long;
using xy = pair<ll, ll>;
using coord = pair<double, double>;
using bs8 = bitset<8>;
using bs16 = bitset<16>;
using bs32 = bitset<32>;
using bs64 = bitset<64>;
using vl = vector<ll>;
using vvl = vector<vl>;
using vvvl = vector<vvl>;
using vd = vector<double>;
using vvd = vector<vd>;
using vs = vector<string>;
using vvs = vector<vs>;
using vxy = vector<xy>;
using vvxy = vector<vxy>;
using vcoord = vector<coord>;
using vvcoord = vector<vcoord>;
#define rep(var, n) for (ll var = 0; var < (ll)(n); var++)
#define cnt(var, n, m) for (ll var = (n); var <= (ll)(m); var++)
#define rcnt(var, n, m) for (ll var = (n); var >= (ll)(m); var--)
#define each(ite, C) for (auto ite = (C).begin(); ite != (C).end(); ite++)
#define reach(ite, C) for (auto ite = (C).rbegin(); ite != (C).rend(); ite++)
#define yn(b) cout << (((b) > 0) ? "Yes" : "No") << endl;
#define ZINIT 1

#if __has_include("zout.h")
#include "zout.h"
#else
namespace zz_print {
class dbg {
 public:
  static inline string margin = "", separated = "", indentS = "";
  static inline int hierarchical = 0, topHier = 0, precision = 6;
  static inline bool unprint = false, exponential = false;
  static void setFloat(const int& prec, const bool& expo) {
    precision = prec;
    exponential = expo;
  }
  template <int hier = 0, int sep = 2, int mgn = 1, typename... Args>
  static void zout(Args&&... args) {}
};
}  // namespace zz_print
using namespace zz_print;
#endif

namespace zz_random {
struct Xoshiro256 {
  static inline ull rotl(ull x, int k) { return (x << k) | (x >> (64 - k)); }
  static inline ull splitmix64(ull& x) {
    ull z = (x += 0x9e3779b97f4a7c15ULL);
    z = (z ^ (z >> 30)) * 0xbf58476d1ce4e5b9ULL;
    z = (z ^ (z >> 27)) * 0x94d049bb133111ebULL;
    return z ^ (z >> 31);
  }
  ull s[4];
  explicit Xoshiro256(ull seed = 1) {
    ull x = seed;
    rep(i, 4) s[i] = splitmix64(x);
  }
  inline ull next() {
    ull res = rotl(s[1] * 5, 7) * 9, t = s[1] << 17;
    s[2] ^= s[0], s[3] ^= s[1], s[1] ^= s[2], s[0] ^= s[3], s[2] ^= t;
    s[3] = rotl(s[3], 45);
    return res;
  }
  inline ull operator()() { return next(); }

  /// integer [0, n)
  inline ll intn(const ll& n = 2) { return (ll)(next() % (ull)n); }
  /// integer [l, r]
  inline ll range(const ll& l, const ll& r) { return l + intn(r - l + 1); }
  /// real (0, 1)
  inline double real() { return (next() >> 11) * (1.0 / (1ULL << 53)); }
  inline double real(const double& r) { return real() * r; }
  inline double real(const double& l, const double& r) { return (l + real() * (r - l)); }
  // Box–Muller 用キャッシュ
  bool has_spare = false;
  double spare;
  /// 標準正規分布 N(0,1)
  inline double normal01() {
    if (has_spare) {
      has_spare = false;
      return spare;
    }
    double u = 0.0, v;
    while (u <= 0.0) u = real();  // (0,1)
    v = real();
    double r = sqrt(-2.0 * log(u)), theta = 2.0 * M_PI * v;
    spare = r * sin(theta), has_spare = true;
    return r * cos(theta);
  }
  /// 正規分布 N(mean, stddev^2)
  inline double normal(const double& mean, const double& stddev) { return mean + stddev * normal01(); }
};
}  // namespace zz_random
using namespace zz_random;

namespace zz_numeric {
xy gcdex(const ll a, const ll b) {
  xy ans;
  if (abs(a) < abs(b)) {
    ans = gcdex(b, a), swap(ans.first, ans.second);
    return ans;
  }
  if (b == 0) return xy{1, 0};
  ans = gcdex(b, a % b);
  return xy{ans.second, ans.first - (a / b) * ans.second};
}
xy gcdex(const xy ab) { return gcdex(ab.first, ab.second); }
ll gcd(const ll a, const ll b) {
  xy ans = gcdex(a, b);
  return abs(a * ans.first + b * ans.second);
}
ll gcd(const xy ab) { return gcd(ab.first, ab.second); }
ll gcd(const vl& vec) {
  ll n = vec.size();
  if (n == 0) return 1;
  if (n == 1) return vec[0];
  vl subvec;
  rep(i, n / 2) subvec.push_back(gcd(vec[2 * i], vec[2 * i + 1]));
  if (n % 2) subvec.push_back(vec[n - 1]);
  return gcd(subvec);
}
ll lcm(const ll a, const ll b) { return (a * (b / gcd(a, b))); }
ll lcm(const xy ab) { return lcm(ab.first, ab.second); }
ll lcm(const vl& vec) {
  ll n = vec.size();
  if (n == 0) return 1;
  if (n == 1) return vec[0];
  vl subvec;
  rep(i, n / 2) subvec.push_back(lcm(vec[2 * i], vec[2 * i + 1]));
  if (n % 2) subvec.push_back(vec[n - 1]);
  return lcm(subvec);
}
}  // namespace zz_numeric
using namespace zz_numeric;

namespace zz_mod {
template <ll mod = 998244353>
class pp {
 public:
  ll val;
  void weak_flush() {
    if (val < 0) val += mod;
    if (val >= mod) val -= mod;
  }
  pp(ll x = 0) { val = x % mod, weak_flush(); }
  friend std::ostream& operator<<(std::ostream& os, const pp<mod>& x) {
    return os << '{' << x.val << '|' << mod << '}';
  }

  pp<mod>& operator+=(const pp<mod>& p) {
    val += p.val, weak_flush();
    return *this;
  }
  pp<mod>& operator+=(ll x) {
    val += x % mod, weak_flush();
    return *this;
  }
  friend pp<mod> operator+(pp<mod> a, const pp<mod>& b) { return a += b; }
  friend pp<mod> operator+(pp<mod> a, ll x) { return a += x; }
  friend pp<mod> operator+(ll x, pp<mod> a) { return a += x; }

  pp<mod>& operator-=(const pp<mod>& p) {
    val -= p.val, weak_flush();
    return *this;
  }
  pp<mod>& operator-=(ll x) {
    val -= x % mod, weak_flush();
    return *this;
  }
  friend pp<mod> operator-(pp<mod> a, const pp<mod>& b) { return a -= b; }
  friend pp<mod> operator-(pp<mod> a, ll x) { return a -= x; }
  friend pp<mod> operator-(ll x, const pp<mod>& a) { return pp<mod>(x) -= a; }

  pp<mod>& operator*=(const pp<mod>& p) {
    val = ((__int128)val * p.val) % mod, weak_flush();
    return *this;
  }
  pp<mod>& operator*=(ll x) {
    val = ((__int128)val * x) % mod, weak_flush();
    return *this;
  }
  friend pp<mod> operator*(pp<mod> a, const pp<mod>& b) { return a *= b; }
  friend pp<mod> operator*(pp<mod> a, ll x) { return a *= x; }
  friend pp<mod> operator*(ll x, const pp<mod>& a) { return pp<mod>(x) *= a; }

  pp<mod> inv() {
    xy ans = gcdex(mod, val);
    assert((mod * ans.first + val * ans.second) == 1);
    pp<mod> p(ans.second);
    return p;
  }
  pp<mod>& operator/=(const pp<mod>& p) { return *this *= p.inv(); }
  pp<mod>& operator/=(ll x) { return *this *= pp<mod>(x).inv(); }
  friend pp<mod> operator/(pp<mod> a, const pp<mod>& b) { return a /= b; }
  friend pp<mod> operator/(pp<mod> a, ll x) { return a /= x; }
  friend pp<mod> operator/(ll x, const pp<mod>& a) {
    a = a.inv();
    return a /= x;
  }

  pp<mod> exp(ll n) {
    if (n < 0) return inv().exp(-n);
    pp<mod> p = *this, ans(1);
    while (n > 1) {
      if (n & 1) ans *= p;
      p *= p, n >>= 1;
    }
    if (n > 0) ans *= p;
    return ans;
  }
};
}  // namespace zz_mod
using namespace zz_mod;

namespace zz_prime {
class prime {
 public:
  static inline vl sieves = vl{};
  static constexpr array<ll, 14> pre_trial_division =
      array<ll, 14>{3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47};
  static void set(const ll n) {
    sieves = vl(n + 1, 1);
    ll i = 1;
    cnt(i, 2, n) {
      if (sieves[i] != 1) continue;
      ll j = i;
      j += i;
      while (j <= n) {
        if (sieves[j] == 1) sieves[j] = i;
        j += i;
      }
    }
  }
  prime(const ll n) { set(n); }
  static void resize(const ll n) {
    if (sieves.size() < (n + 1)) set(n);
  }
  static bool millerRabin(const ll n) {
    if (n < 2) return false;
    if (n == 2) return true;
    if ((n % 2) == 0) return false;
    bool ans = false;
    vl a = vl{2, 7, 61};
    if (n >= 4759123141) a = vl{2, 325, 9375, 28178, 450775, 9780504, 1795265022};

    each(ite_a, a) {
      if ((*ite_a) >= n) break;
      ll d = n - 1;
      while ((d % 2) == 0) d >>= 1;
      ll x = 1, b = (*ite_a) % n, c = d;
      while (c > 0) {
        if (c & 1) x = ((__int128)x * b) % n;
        b = ((__int128)b * b) % n, c >>= 1;
      }
      if (x == 1 || x == (n - 1)) continue;
      bool OK = false;
      while (d < (n - 1)) {
        if (x == (n - 1)) {
          OK = true;
          break;
        }
        x = ((__int128)x * x) % n, d <<= 1;
      }
      if (OK) continue;
      return false;
    }
    return true;
  }
  static bool isPrime(const ll x) {
    if (sieves.size() <= x) return millerRabin(x);
    if (x < 2) return false;
    return (sieves[x] == 1);
  }
  static vxy pollardsRho(ll x) {
    if (x < 2) return vxy();
    vl prms;
    Xoshiro256 rnd;
    function<ll(ll, const ll, const ll)> F = [&rnd](ll x, const ll c, const ll m) -> ll {
      return (((__int128)x * x + c) % m);
    };
    function<void(ll)> Pollards = [&rnd, &F, &prms, &Pollards](const ll n) {
      if (n < 2) return;
      if (millerRabin(n)) {
        prms.push_back(n);
        return;
      }
      ll r = sqrtl(n);
      if ((r * r) == n) {
        Pollards(r), Pollards(r);
        return;
      }

      while (true) {
        ll a = rnd.range(2, n - 1), b = a, c = rnd.range(1, n - 1), d = 1, loopCnt = 0;
        do {
          loopCnt++;
          ll e = 1, k = 64;
          while (k > 0) {
            a = F(a, c, n), b = F(F(b, c, n), c, n);
            ll tmp = ((__int128)e * abs(a - b)) % n;
            if (tmp == 0) break;
            e = tmp, k--;
          }
          d = gcd(e, n);
        } while (d == 1 && loopCnt < 20);
        if (loopCnt >= 20) continue;
        if (d != n) {
          Pollards(d), Pollards(n / d);
          return;
        }
      }
    };
    while ((x & 1) == 0) {
      x >>= 1, prms.push_back(2);
    }
    each(ite, pre_trial_division) {
      if (x < (*ite)) break;
      while ((x % (*ite)) == 0) {
        x /= (*ite), prms.push_back(*ite);
      }
    }
    Pollards(x);
    vxy ans;
    sort(prms.begin(), prms.end());
    each(ite, prms) {
      if (ans.empty() || ans.back().first != (*ite)) {
        ans.emplace_back(*ite, 1);
      } else {
        ans.back().second++;
      }
    }
    return ans;
  }
  static vxy factor(ll x) {
    if (sieves.size() <= x) return pollardsRho(x);
    vl prms;
    if (x < 2) return vxy();
    while (sieves[x] != 1) {
      x /= sieves[x], prms.push_back(sieves[x]);
    }
    if (x != 1) prms.push_back(x);
    sort(prms.begin(), prms.end());
    vxy ans;
    each(ite, prms) {
      if (ans.empty() || ans.back().first != (*ite)) {
        ans.emplace_back(*ite, 1);
      } else {
        ans.back().second++;
      }
    }
    return ans;
  }
  static vl divisor(const vxy& fac, const bool srt) {
    vl ans;
    function<void(ll, ll)> func = [&ans, &fac, &func](ll at, ll e) -> void {
      if (at == fac.size()) return;
      ll a = 1;
      cnt(i, 0, fac[at].second) {
        if (a != 1) ans.push_back(e * a);
        func(at + 1, e * a), a *= fac[at].first;
      }
    };
    func(0, 1);
    if (srt) sort(ans.begin(), ans.end());
    return ans;
  }
  static vl divisor(const ll n, const bool srt) { return divisor(factor(n), srt); }
};
}  // namespace zz_prime
using namespace zz_prime;

namespace zz_ganer {
ll ganer_prefix(vxy& vec, const ll mod) {
  ll n = vec.size();
  rep(i, n) {
    rep(j, i) {
      ll d = gcd(vec[i].second, vec[j].second);
      if ((vec[i].first - vec[j].first) % d != 0) return -1;
      vec[i].second /= d, vec[j].second /= d;
      ll di = gcd(vec[i].second, d), dj = d / di;
      do {
        d = gcd(di, dj), di *= d, dj /= d;
      } while (d != 1);
      vec[i].second *= di, vec[j].second *= dj, vec[i].first %= vec[i].second, vec[j].first %= vec[j].second;
    }
  }
  ll lcm_val = 1;
  each(ite, vec) lcm_val = ((__int128)lcm_val * ite->second) % mod;
  return lcm_val;
}
template <ll m = 1>
ll ganer(vxy vec, bool pos = false) {
  bool zero_possible = true;
  each(ite, vec) {
    if (ite->first > 0) {
      zero_possible = false;
      break;
    }
  }
  ll pre_ans = ganer_prefix(vec, m);
  if (pre_ans == -1) return -1;
  if (pos && zero_possible) return pre_ans;
  ll n = vec.size(), mod = m;
  if (n == 0) return -1;
  if (mod <= 1) {
    mod = lcm([&vec]() {
      vl v;
      each(ite, vec) v.push_back(ite->second);
      return v;
    }());
  }
  vl coef(n + 1, 1), cval(n + 1, 0);
  vec.emplace_back(0, mod);
  rep(i, n) {
    ll r = vec[i].first, p = vec[i].second;
    xy ans = gcdex(coef[i], p);
    ll ta = (r - cval[i]) % p, tb = ans.first % p;
    if (ta < 0) ta += p;
    if (tb < 0) tb += p;
    ll t = ((__int128)ta * tb) % p;
    cnt(j, i + 1, n) {
      cval[j] = (cval[j] + (__int128)t * coef[j]) % vec[j].second;
      coef[j] = ((__int128)coef[j] * p) % vec[j].second;
    }
  }
  return cval.back();
}
}  // namespace zz_ganer
using namespace zz_ganer;

namespace zz_poly {
ll resize_2exp(vl& a) {
  ll nb = 0;
  while ((1 << nb) < a.size()) nb++;
  a.resize(1 << nb, 0);
  return nb;
}
template <ll mod>
ll getFFTroot(ll len, bool rvs = false) {
  pp<mod> w;
  switch (mod) {
    case 880803841:  // 880803841 = 105*(2**23)+1
      w = pp<mod>(26);
      break;
    case 897581057:  // 897581057 = 107*(2**23)+1
      w = pp<mod>(3);
      break;
    case 998244353:  // 998244353 = 119*(2**23)+1
      w = pp<mod>(3);
      break;
    default:
      return -1;
  }
  if (rvs) return w.inv().exp((mod - 1) / len).val;
  return w.exp((mod - 1) / len).val;
}
template <ll mod>
vl tran(const vl& vec, ll zeta) {
  ll n = vec.size();
  if (n == 1) return vec;
  vl subvec1, subvec2;
  rep(i, n / 2) {
    subvec1.push_back(vec[2 * i]);
    subvec2.push_back(vec[2 * i + 1]);
  }
  vl SUBVEC1 = tran<mod>(subvec1, (zeta * zeta) % mod);
  vl SUBVEC2 = tran<mod>(subvec2, (zeta * zeta) % mod);
  ll w = 1;
  vl ans(n);
  rep(i, n) {
    ans[i] = (SUBVEC1[i % (n / 2)] + SUBVEC2[i % (n / 2)] * w) % mod;
    w = (w * zeta) % mod;
  }
  return ans;
}
template <ll mod>
vl fft(vl& a) {
  resize_2exp(a);
  ll w = getFFTroot<mod>(a.size(), false);
  return tran<mod>(a, w);
}
template <ll mod>
vl fft_reverse(vl& A) {
  resize_2exp(A);
  ll n = A.size(), w = getFFTroot<mod>(n, true);
  vl a = tran<mod>(A, w);
  rep(i, n) a[i] = (pp<mod>(a[i]) / n).val;
  return a;
}
template <ll mod>
vl convolution_normal(vl a, vl b) {
  ll n = a.size() + b.size() - 1;
  a.resize(n), b.resize(n);
  resize_2exp(a), resize_2exp(b);
  n = a.size();
  vl A = fft<mod>(a), B = fft<mod>(b), C(n);
  rep(i, n) C[i] = pp<mod>(A[i] * B[i]).val;
  vl c = fft_reverse<mod>(C);
  return c;
}
template <ll mod>
vl convolution_ganer(const vl& a, const vl& b) {
  vvl c(4);
  c[0] = convolution_normal<880803841>(a, b);
  c[1] = convolution_normal<897581057>(a, b);
  c[2] = convolution_normal<998244353>(a, b);
  ll n = c[0].size();
  c[3].resize(n);
  rep(i, n) c[3][i] = ganer<mod>(vxy{xy{c[0][i], 880803841}, xy{c[1][i], 897581057}, xy{c[2][i], 998244353}});
  return c[3];
}
template <ll mod>
vl convolution(const vl& a, const vl& b) {
  if (getFFTroot<mod>(mod, mod - 1) == -1) return convolution_ganer<mod>(a, b);
  return convolution_normal<mod>(a, b);
}
}  // namespace zz_poly
using namespace zz_poly;
/////////////////////////////////////////////////

int main() {
  //  dbg::unprint = true;
  ll N;
  cin >> N;

  vl A(N);
  rep(i, N) cin >> A[i];

  vl U(N - 1), V(N - 1);
  rep(i, N - 1) cin >> U[i] >> V[i];

  vvl Edge(N);
  rep(i, N) {
    Edge[U[i] - 1].push_back(V[i] - 1);
    Edge[V[i] - 1].push_back(U[i] - 1);
  }

  vl ans(N, -1);
  function<void(ll, vxy&)> Func = [&A, &Edge, &ans, &Func](ll at, vxy& vec) -> void {
    ans[at] = A[at];
    vec.emplace_back(0, A[at]);
    each(ite, Edge[at]) {
      if (ans[*ite] == -1) {
        ans[*ite] = 1;
        vxy subvec;
        Func(*ite, subvec);
        if (subvec.size() > vec.size()) {
          each(ite, vec) subvec.push_back(*ite);
          swap(subvec, vec);
        } else {
          each(ite, subvec) vec.push_back(*ite);
        }
      }
    }
    ans[at] = ganer<998244353>(vec, true);
  };
  vxy vec;
  Func(0, vec);

  rep(i, N) cout << ans[i] << endl;
  return 0;
}