結果

問題 No.2342 Triple Tree Query (Hard)
ユーザー 也吏
提出日時 2024-12-02 16:21:31
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 7,912 bytes
コンパイル時間 2,066 ms
コンパイル使用メモリ 147,952 KB
実行使用メモリ 817,664 KB
最終ジャッジ日時 2024-12-02 16:21:45
合計ジャッジ時間 11,411 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample WA * 1 RE * 1
other WA * 6 RE * 28 MLE * 2
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <algorithm>
#include <array>
#include <iostream>
#include <queue>
#include <ranges>
#include <type_traits>
#include <vector>

using i64 = long long;
using u32 = unsigned int;
using u64 = unsigned long long;

void set_io(std::string name)
{
#ifndef NO_FREOPEN
  freopen((name + ".in").c_str(), "r", stdin);
  freopen((name + ".out").c_str(), "w", stdout);
#endif
  std::cin.tie(nullptr);
  std::ios::sync_with_stdio(false);
}

template <int M> struct static_modint
{
  static constexpr u32 UM = M;
  static_assert(UM < 0x80'00'00'00u);

  u32 v;
  constexpr static_modint() : v(0) {}

  template <typename T, std::enable_if_t<std::is_signed_v<T>> * = nullptr>
  constexpr static_modint(T n) : v((n %= M) < 0 ? n + M : n)
  {
  }

  template <typename T, std::enable_if_t<std::is_unsigned_v<T>> * = nullptr>
  constexpr static_modint(T n) : v(n %= UM)
  {
  }

  using mint = static_modint;

  static mint raw(u32 v)
  {
    mint res;
    res.v = v;
    return res;
  }

  constexpr u32 val() const { return v; }

  mint operator-() const { return mint::raw(v == 0 ? 0u : UM - v); }

  mint &operator+=(mint a)
  {
    if ((v += a.v) >= UM) v -= UM;
    return *this;
  }
  mint &operator-=(mint a)
  {
    if ((v += UM - a.v) >= UM) v -= UM;
    return *this;
  }
  mint &operator*=(mint a)
  {
    v = (u64)v * a.v % UM;
    return *this;
  }
  mint &operator/=(mint a) { return *this *= a.inv(); }

  friend mint operator+(mint a, mint b) { return a += b; }
  friend mint operator-(mint a, mint b) { return a -= b; }
  friend mint operator*(mint a, mint b) { return a *= b; }
  friend mint operator/(mint a, mint b) { return a /= b; }

  mint pow(u64 n) const
  {
    mint res = 1, base = *this;
    while (n) {
      if (n & 1) res *= base;
      base *= base;
      n >>= 1;
    }
    return res;
  }

  mint inv() const { return pow(UM - 2); }
};

using mint = static_modint<998'244'353>;

struct AffineMonoid
{
  mint k, b;

  AffineMonoid() : k(1), b(0) {}
  AffineMonoid(mint k, mint b) : k(k), b(b) {}

  AffineMonoid &operator*=(AffineMonoid x)
  {
    k *= x.k;
    b = x.k * b + x.b;
    return *this;
  }

  friend AffineMonoid operator*(AffineMonoid x, AffineMonoid y) { return y *= x; }

  mint operator()(mint x) const { return k * x + b; }
};

int ceil_pow2(int x)
{
  int y = 0;
  while ((1 << y) < x) y++;
  return y;
}

struct Segtree
{
  int n, log, size;
  std::vector<AffineMonoid> s;

  Segtree(int n) : n(n), log(ceil_pow2(n)), size(1 << log), s(size * 2) {}

  void apply_at(int x, const AffineMonoid &tag)
  {
    s[x] *= tag;
  }

  void push(int p)
  {
    apply_at(p * 2, s[p]);
    apply_at(p * 2 + 1, s[p]);
    s[p] = {};
  }

  void apply(int l, int r, const AffineMonoid &tag)
  {
    l += size;
    r += size;

    for (int i = log; i >= 1; i--) {
      if (((l >> i) << i) != l) push(l >> i);
      if (((r >> i) << i) != r) push((r - 1) >> i);
    }

    while (l < r) {
      if (l & 1) apply_at(l++, tag);
      if (r & 1) apply_at(--r, tag);
      l >>= 1;
      r >>= 1;
    }
  }

  AffineMonoid get(int x)
  {
    x += size;
    for (int i = log; i >= 1; i--) push(x >> i);
    return s[x];
  }
};

constexpr int MAXK = 10;

int main()
{
  set_io("tour");

  int sub, n, m;
  std::cin >> sub >> n >> m;

  int n2 = n + MAXK;
  std::vector<std::vector<int>> adj(n2);
  for (int i = 1; i < n; i++) {
    int u, v;
    std::cin >> u >> v;
    u--;
    v--;
    adj[u].emplace_back(v);
    adj[v].emplace_back(u);
  }

  for (int i = n; i < n2; i++) {
    if (i == n) {
      adj[i].emplace_back(0);
      adj[0].emplace_back(i);
    } else {
      adj[i].emplace_back(i - 1);
      adj[i - 1].emplace_back(i);
    }
  }

  std::vector<mint> a(n);
  for (int i = 0; i < n; i++) {
    int x;
    std::cin >> x;
    a[i] = x;
  }

  std::vector<int> bfs_ord;
  std::vector<int> fa(n2, -1), dep(n2);

  {
    std::queue<int> q;
    q.emplace(n2 - 1);
    while (!q.empty()) {
      auto u = q.front();
      q.pop();
      bfs_ord.emplace_back(u);
      for (auto v : adj[u]) {
        std::erase(adj[v], u);
        fa[v] = u;
        dep[v] = dep[u] + 1;
        q.emplace(v);
      }
    }
  }

  std::vector<int> size(n2);
  for (auto u : bfs_ord | std::views::reverse) {
    size[u] = 1;
    for (auto &v : adj[u]) {
      size[u] += size[v];
      if (size[v] > size[adj[u][0]]) {
        std::swap(v, adj[u][0]);
      }
    }
  }

  std::vector<int> chain_idx(n2);
  std::vector<int> top(n2);
  top[n2 - 1] = n2 - 1;
  for (auto u : bfs_ord) {
    for (auto v : adj[u]) {
      if (v == adj[u][0]) chain_idx[v] = chain_idx[u] + 1;
      else chain_idx[v] = 0;
      if (chain_idx[v] > MAXK) top[v] = top[u];
      else top[v] = v;
    }
  }

  std::vector<std::array<std::vector<int>, MAXK + 1>> kadj(n2);
  for (auto u : bfs_ord | std::views::reverse) {
    kadj[u][0].emplace_back(u);
    for (int k = 1; k <= MAXK; k++) {
      for (auto v : adj[u]) {
        for (auto w : kadj[v][k - 1]) {
          kadj[u][k].emplace_back(w);
        }
      }
    }
  }

  std::vector<std::array<int, MAXK + 1>> kchain(n2);
  for (int i = 0; i < n2; i++) {
    kchain[i].fill(-1);
    kchain[i][0] = i;
    for (int k = 1; k <= MAXK; k++) {
      int pre = kchain[i][k - 1];
      if (adj[pre].size() == 0) break;
      kchain[i][k] = adj[pre][0];
    }
  }

  int cnt = 0;
  std::vector<int> idx(n, -1);
  std::vector<int> begin1(n), end1(n);
  auto dfs1 = [&](auto &&self, int u) -> void {
    if (u < n) begin1[u] = cnt;
    if (chain_idx[u] >= MAXK && u < n) idx[u] = cnt++;
    for (auto v : adj[u]) self(self, v);
    if (u < n) end1[u] = cnt;
  };
  dfs1(dfs1, n2 - 1);

  std::vector<int> begin2(n), end2(n);
  auto dfs2 = [&](auto &&self, int u) -> void {
    for (auto v : kadj[u][MAXK]) {
      if (idx[v] == -1) {
        idx[v] = cnt++;
      }
    }
    if (u < n) begin2[u] = cnt;
    for (auto v : adj[u]) self(self, v);
    if (u < n) end2[u] = cnt;
  };
  dfs2(dfs2, n2 - 1);

  std::vector<std::array<int, MAXK + 1>> begin3(n2), end3(n2);
  for (int u = 0; u < n2; u++) {
      for (int k = 0; k <= MAXK; k++) {
      begin3[u][k] = n2;
      end3[u][k] = -1;
      for (auto v : kadj[u][k]) {
        if (v >= n || chain_idx[v] >= MAXK) continue;
        begin3[u][k] = std::min(begin3[u][k], idx[v]);
        end3[u][k] = std::max(end3[u][k], idx[v]);
      }
      end3[u][k]++;
    }
  }

  Segtree s(n);

  auto apply_subtree_distance = [&](int u, int d, const AffineMonoid &affine)
  {
    if (begin3[u][d] != n2) s.apply(begin3[u][d], end3[u][d], affine);
    if (kchain[u][d] != -1 && chain_idx[kchain[u][d]] >= MAXK) s.apply(idx[kchain[u][d]], idx[kchain[u][d]] + 1, affine);
  };

  for (int i = 0; i < m; i++) {
    int type;
    std::cin >> type;

    if (type == 1) {
      int x;
      std::cin >> x;
      x--;
      std::cout << s.get(idx[x])(a[x]).val() << "\n";
    } else if (type == 2) {
      int u, v, k, b;
      std::cin >> u >> v >> k >> b;
      u--;
      v--;
      AffineMonoid affine(k, b);
      while (top[u] != top[v]) {
        if (dep[top[u]] < dep[top[v]]) std::swap(u, v);
        s.apply(idx[top[u]], idx[u] + 1, affine);
        u = fa[top[u]];
      }
      if (idx[u] > idx[v]) std::swap(u, v);
      s.apply(idx[u], idx[v] + 1, affine);
    } else if (type == 3) {
      int u, k, b;
      std::cin >> u >> k >> b;
      u--;
      AffineMonoid affine(k, b);
      s.apply(begin1[u], end1[u], affine);
      s.apply(begin2[u], end2[u], affine);
      for (int j = 0; j <= MAXK; j++) {
        if (begin3[u][j] != n2) {
          s.apply(begin3[u][j], end3[u][j], affine);
        }
      }
    } else if (type == 4) {
      int u, r, k, b;
      std::cin >> u >> r >> k >> b;
      u--;
      AffineMonoid affine(k, b);
      while (r >= 0) {
        apply_subtree_distance(u, r, affine);
        if (r - 1 >= 0) apply_subtree_distance(u, r - 1, affine);
        r--;
        u = fa[u];
      }
    }
  }
}
0