結果

問題 No.2342 Triple Tree Query (Hard)
コンテスト
ユーザー vjudge1
提出日時 2024-10-15 13:13:28
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
MLE  
実行時間 -
コード長 8,074 bytes
コンパイル時間 4,810 ms
コンパイル使用メモリ 296,064 KB
実行使用メモリ 816,452 KB
最終ジャッジ日時 2024-10-15 13:13:39
合計ジャッジ時間 9,652 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample MLE * 1 -- * 1
other -- * 36
権限があれば一括ダウンロードができます

ソースコード

diff # 

#pragma GCC optimize(3,"Ofast","no-stack-protector","fast-math")
#include <bits/stdc++.h>
#define ALL(x) begin(x), end(x)
#define All(x, l, r) &x[l], &x[r] + 1
using namespace std;
void file() {
  freopen("tour.in", "r", stdin);
  freopen("tour.out", "w", stdout);
}
using ll = long long;
template <typename T> using vec = vector<T> ;

const int mod = 998244353;
void Add(int& x, int y) { ((x += y) >= mod) && (x -= mod); }
void Sub(int& x, int y) { ((x -= y) < 0) && (x += mod); }
int Sum(int x, int y) { return Add(x, y), x; }
int Dif(int x, int y) { return Sub(x, y), x; }
int qpow(int x, int y) {
  int b = x, r = 1;
  for(; y; b = (ll)b * b % mod, y /= 2)
    if(y & 1) r = (ll)r * b % mod;
  return r;
}

const int kL = 1e5 + 5, inf = 1e9;
int sub, n, q, dtot;
array<vec<int>, kL> g;
array<int, kL> a, dep, dfn, siz, son, top, fa, drev;

namespace Init {
  void dfs(int x, int Fa) {
    siz[x] = 1;
    dep[x] = dep[fa[x] = Fa] + 1;
    for(int to : g[x]) {
      if(to == Fa) continue;
      dfs(to, x);
      siz[x] += siz[to];
      if(siz[son[x]] < siz[to])
        son[x] = to;
    }
  }
  void dfs2(int x, int tp) {
    top[x] = tp;
    drev[dfn[x] = ++dtot] = x;
    if(son[x]) dfs2(son[x], tp);
    for(int to : g[x])
      if((to ^ fa[x]) && (to ^ son[x]))
        dfs2(to, to);
  }
}

struct info {
  int k, b;
  info() { k = 1; b = 0; }
  info(int _k, int _b) { k = _k; b = _b; }
  int operator () (int x) { return ((ll)k * x + b) % mod; }
};
info& operator *= (info& x, const info& y) {
  x.k = (ll)x.k * y.k % mod;
  x.b = ((ll)y.k * x.b + y.b) % mod;
  return x;
}
info operator * (info x, info y) { return x *= y, x; }
info Inv(const info& x) {
  int inv = qpow(x.k, mod - 2);
  return info(inv, (ll)(mod - x.b) * inv % mod);
}

namespace Task1 {
  int btot, bsc, dsc;
  array<int, kL> bfn, brev;
  array<info, kL> val;
  pair<int, int> seg[kL][13];
  array<int, 501> bl, br, dl, dr;

  void bfs(int s) {
    queue<int> q; q.push(s);
    while(q.size()) {
      int x = q.front(); q.pop();
      brev[bfn[x] = ++btot] = x;
      for(int to : g[x])
        if(!bfn[to]) q.push(to);
    }
  }

  void updated(int l, int r, const info& v) {
    for(int i = l; i <= r; i++) val[drev[i]] *= v;
  }
  void updateb(int l, int r, const info& v) {
    for(int i = l; i <= r; i++) val[brev[i]] *= v;
  }

  void getd(int x, int y) {
    while(top[x] ^ top[y]) {
      if(dep[top[x]] < dep[top[y]]) swap(x, y);
      dsc++;
      dl[dsc] = dfn[top[x]];
      dr[dsc] = dfn[x];
      x = fa[top[x]];
    }
    if(dfn[x] > dfn[y]) swap(x, y);
    dsc++;
    dl[dsc] = dfn[x];
    dr[dsc] = dfn[y];
  }
  void getb(int x, int d) {
    int last = 0;
    for(int p = x, i = 0; i <= d; p = fa[last = p], i++) {
      bsc++;
      bl[bsc] = br[bsc] = bfn[p];
      for(int j = 1; i + j <= d; j++) {
        int tl, tr, l, r;
        tie(l, r) = seg[p][j];
        tie(tl, tr) = seg[last][j - 1];
        if(l > r) break;
        if(tl > tr) {
          bsc++;
          bl[bsc] = l; br[bsc] = r;
        }else {
          if(l < tl) {
            bsc++;
            bl[bsc] = l; br[bsc] = tl - 1;
          }
          if(r > tr) {
            bsc++;
            bl[bsc] = tr + 1; br[bsc] = r;
          }
        }
      }
    }
  }

  void solve() {
    bfs(1);
    for(auto& k : seg)
	  for(auto& t : k) t = pair<int, int> {inf, 0};
    for(int i = 1; i <= n; i++)
      seg[i][0] = pair<int, int> {bfn[i], bfn[i]};
    for(int i = 1; i < 12; i++)
      for(int j = 1; j <= n; j++) {
        int l = inf, r = 0;
        for(int to : g[j])
          if(bfn[to] > bfn[j]) {
            l = min(l, seg[to][i - 1].first);
            r = max(r, seg[to][i - 1].second);
          }
        seg[j][i] = pair<int, int> {l, r};
      }
    for(int op, x, y, k, b; q--; ) {
      cin >> op;
      if(op == 1) {
        cin >> x;
        cout << val[x](a[x]) << "\n";
      }else if(op == 2) {
        cin >> x >> y >> k >> b;
        const info val (k, b);
        dsc = 0;
        getd(x, y);
        for(int i = 1; i <= dsc; i++)
          updated(dl[i], dr[i], val);
      }else if(op == 3) {
        cin >> x >> k >> b;
        const info val (k, b);
        updated(dfn[x], dfn[x] + siz[x] - 1, val);
      }else {
        cin >> x >> y >> k >> b;
        const info val (k, b);
        bsc = 0; getb(x, y);
        for(int i = 1; i <= bsc; i++)
          updateb(bl[i], br[i], val);
      }
    }
  }
}

namespace Task2 {
  array<array<info, 13>, kL> tag, invtag;

  void subtree(int x, int y, const info& val, const info& invval) {
    for(int i = 0; i <= y; i++) {
      info sum, inv;
      for(int p = fa[x], j = i + 1; p && (j <= 10); p = fa[p], j++) {
        sum = sum * tag[p][j];
        inv = invtag[p][j] * inv;
      }
      tag[x][i] = tag[x][i] * sum * val * inv;
      invtag[x][i] = sum * invval * inv * invtag[x][i];
    }
  }

  void update(int x, int y, int k, int b) {
    const info val (k, b), inv = Inv(val);
    info tmp = val * inv;
    for(int last = 0, p = x, i = y; p && ~i; p = fa[last = p], i--) {
      if(last && i)
        subtree(last, i - 1, inv, val);
      subtree(p, i, val, inv);
    }
  }

  ll query(int x) {
    info cur = tag[x][0];
    for(int p = fa[x], i = 1; p && (i <= 10); p = fa[p], i++)
      cur *= tag[p][i];
    return cur (a[x]);
  }

  void solve() {
    for(int op, x, y, k, b; q--; ) {
      cin >> op >> x;
      if(op == 1) cout << query(x) << "\n";
      else {
        cin >> y >> k >> b;
        update(x, y, k, b);
      }
    }
  }
}

namespace Task3 {
  const int sL = 4e5 + 5;
  #define ls (o << 1)
  #define rs (o << 1 | 1)

  struct SGT {
    array<info, sL> s, t;
    void pu(int o) { s[o] = s[ls] * s[rs]; }
    void ad(int o, const info& v) { s[o] *= v; t[o] *= v; }
    void pd(int o) {
      if((t[o].k ^ 1) || (t[o].b)) {
        ad(ls, t[o]); ad(rs, t[o]); t[o] = info();
      }
    }
    void update(int o, int l, int r, int x, int y, const info& v) {
      if((l > y) || (r < x)) return ;
      if((l >= x) && (r <= y)) return ad(o, v);
      pd(o); int mid = (l + r) >> 1;
      update(ls, l, mid, x, y, v);
      update(rs, mid + 1, r, x, y, v);
      pu(o);
    }
    info query(int o, int l, int r, int x) {
      if(l == r) return s[o];
      pd(o); int mid = (l + r) >> 1;
      if(mid < x) return query(rs, mid + 1, r, x);
      return query(ls, l, mid, x);
    }
  }sgt;

  int query(int x) {
    return sgt.query(1, 1, n, dfn[x])(a[x]);
  }
  void update(int x, int y, int k, int b) {
    const info val (k, b);
    while(top[x] ^ top[y]) {
      if(dep[top[x]] < dep[top[y]]) swap(x, y);
      sgt.update(1, 1, n, dfn[top[x]], dfn[x], val);
      x = fa[top[x]];
    }
    if(dfn[x] > dfn[y]) swap(x, y);
    sgt.update(1, 1, n, dfn[x], dfn[y], val);
  }
  void tree(int x, int k, int b) {
    const info val (k, b);
    sgt.update(1, 1, n, dfn[x], dfn[x] + siz[x] - 1, val);
  }

  void solve() {
    for(int op, x, y, k, b; q--; ) {
      cin >> op >> x;
      if(op == 1) cout << query(x) << "\n";
      else if(op == 2) {
        cin >> y >> k >> b;
        update(x, y, k, b);
      }else { cin >> k >> b; tree(x, k, b); }
    }
  }
}

namespace Task4 {
  void solve() {
    for(int op, x, y, k, b; q--; ) {
      cin >> op >> x;
      if(op == 1)
        cout << ((Task2::query(x) + Task3::query(x) - a[x]) % mod + mod) % mod << "\n";
      else if(op == 2) {
        cin >> y >> k >> b;
        Task3::update(x, y, k, b);
      }else if(op == 3) {
        cin >> k >> b;
        Task3::tree(x, k, b);
      }else {
        cin >> y >> k >> b;
        Task2::update(x, y, k, b);
      }
    }
  }
}

int main() {
  ios::sync_with_stdio(0); cin.tie(0);
  cin >> sub >> n >> q;
  for(int i = 1, u, v; i < n; i++) {
    cin >> u >> v;
    g[u].push_back(v);
    g[v].push_back(u);
  }
  for(int i = 1; i <= n; i++) cin >> a[i];
  Init::dfs(1, 0); Init::dfs2(1, 1);
  if((sub == 1) || (sub == 2) || (sub == 3) || (sub == 5) || (sub == 7) || (sub == 8))
    return Task1::solve(), 0;
  if(sub == 4) return Task3::solve(), 0;
  if(sub == 6) return Task4::solve(), 0;
  return 0;
}
0