結果

問題 No.2342 Triple Tree Query (Hard)
コンテスト
ユーザー vjudge1
提出日時 2024-10-15 13:10:41
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 4,497 bytes
コンパイル時間 5,282 ms
コンパイル使用メモリ 279,288 KB
実行使用メモリ 34,688 KB
最終ジャッジ日時 2024-10-15 13:12:14
合計ジャッジ時間 88,742 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 20 TLE * 1 -- * 15
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
#define QWQ
#define int long long

using namespace std;
const int MAXN = 1e5 + 5, Mod = 998244353;
int sub, n, t, a[MAXN], sd[MAXN], top[MAXN], fa[MAXN], sz[MAXN], son[MAXN];
int dfn[MAXN], id[MAXN], cnt;
struct Node{
  int sum, lzk = 1, lzb;
}tr[4 * MAXN];
vector<int> g[MAXN];
void dfs1(int x, int fa){
  ::fa[x] = fa;
  sz[x] = 1;
  sd[x] = sd[fa] + 1;
  for (auto v : g[x]){
    if (v != fa){
      dfs1(v, x);
      if (sz[v] > sz[son[x]]){
        son[x] = v;
      }
      sz[x] += sz[v];
    }
  }
}
void dfs2(int x, int fa){
  top[x] = fa;
  dfn[x] = ++cnt;
  id[cnt] = x;
  if (son[x]){
    dfs2(son[x], fa);
  }
  for (auto v : g[x]){
    if (v != ::fa[x] && v != son[x]){
      dfs2(v, v);
    }
  }
}
#define mid ((l + r) >> 1)
void js(int id, int l, int r){
  if (l == r){
    tr[id].sum = a[::id[l]];
    return ;
  }
  js(id * 2, l, mid);
  js(id * 2 + 1, mid + 1, r);
  // tr[id].sum = (tr[id * 2].sum + tr[id * 2 + 1].sum) % Mod;
}
void pushdown(int id, int l, int r){
  tr[id * 2].sum = ((tr[id * 2].sum * tr[id].lzk) % Mod + tr[id].lzb * (mid - l + 1) % Mod) % Mod;
  tr[id * 2].lzk = (tr[id * 2].lzk * tr[id].lzk) % Mod;
  tr[id * 2].lzb = (tr[id * 2].lzb * tr[id].lzk % Mod + tr[id].lzb) % Mod;
  tr[id * 2 + 1].sum = ((tr[id * 2 + 1].sum * tr[id].lzk) % Mod + tr[id].lzb * (r - mid) % Mod) % Mod;
  tr[id * 2 + 1].lzk = (tr[id * 2 + 1].lzk * tr[id].lzk) % Mod;
  tr[id * 2 + 1].lzb = (tr[id * 2 + 1].lzb * tr[id].lzk % Mod + tr[id].lzb) % Mod;
  tr[id].lzk = 1;
  tr[id].lzb = 0;
}
int find(int id, int l, int r, int ql, int qr){
  if (l > qr || r < ql){
    return 0;
  }else if (ql <= l && r <= qr){
    return tr[id].sum;
  }
  pushdown(id, l, r);
  return find(id * 2, l, mid, ql, qr) + find(id * 2 + 1, mid + 1, r, ql, qr);
}
void xg(int id, int l, int r, int ql, int qr, int k, int b){
  if (l > qr || r < ql){
    return ;
  }else if (ql <= l && r <= qr){
    tr[id].sum = (tr[id].sum * k % Mod + b * (r - l + 1) % Mod) % Mod;
    tr[id].lzb = (tr[id].lzb * k % Mod + b) % Mod;
    tr[id].lzk = (tr[id].lzk * k % Mod);
    return ;
  }
  pushdown(id, l, r);
  xg(id * 2, l, mid, ql, qr, k, b);
  xg(id * 2 + 1, mid + 1, r, ql, qr, k, b);
  // tr[id].sum = (tr[id * 2].sum + tr[id * 2 + 1].sum) % Mod;
}
void update(int x, int y, int k, int b){
  while (top[x] != top[y]){
    if (sd[top[x]] < sd[top[y]]){
      swap(x, y);
    }
    xg(1, 1, n, dfn[top[x]], dfn[x], k, b);
    x = fa[top[x]];
  }
  if (sd[x] > sd[y]){
    swap(x, y);
  }
  xg(1, 1, n, dfn[x], dfn[y], k, b);
}
void walk(int x, int r, int k, int b, int fa){
  if (r < 0){
    return ;
  }
  xg(1, 1, n, dfn[x], dfn[x], k, b);
  for (auto v : g[x]){
    if (v != fa){
      walk(v, r - 1, k, b, x);
    }
  }
}

namespace fastIO{
  char Buf[1 << 23], *P1 = Buf, *P2 = Buf;
  #define getchar() (P1 == P2 && (P2 = (P1 = Buf) + fread(Buf, 1, 1 << 23, stdin), P1 == P2) ? EOF : *P1++)
  template<typename type>
  inline void read(type &x){
    x=0;
    bool f = 0;
    char ch = getchar();
    while(ch < '0' || ch > '9'){
      f |= ch == '-', ch = getchar();
    }
    while(ch >= '0' && ch <= '9'){
      x = x * 10 + (ch ^ 48), ch = getchar();
    }
    if(f){
      x = -x;
    }
  }
  template<typename type,typename... args>
  inline void read(type &x,args&... y){
    read(x), read(y...);
  }
  template<typename type>
  inline void print(type x, char s = ' ') {
    static int sta[130];
    int top = 0;
    do {
      sta[top++] = x % 10, x /= 10;
    } while (x);
    while (top) putchar(sta[--top] + '0'); 
    putchar(s);
  }
  template<typename type,typename... args>
  inline void print(type &x, args &... y, char s = ' '){
    print(x, s), print(y..., s);
  }
}
using namespace fastIO;
signed main(){
  #ifndef QWQ
  freopen("tour.in", "r", stdin);
  freopen("tour.out", "w", stdout);
  #endif
  read(n, t);
  for (int i = 1, u, v; i < n; i++){
    read(u, v);
    g[u].push_back(v);
    g[v].push_back(u);
  }
  for (int i = 1; i <= n; i++){
    read(a[i]);
  }
  dfs1(1, 0);
  dfs2(1, 1);
  js(1, 1, n);
  while (t--){
    int op;
    read(op);
    if (op == 1){
      int x;
      read(x);
      print(find(1, 1, n, dfn[x], dfn[x]), '\n');
    }else if (op == 4){
      int x, y, k, b;
      read(x, y, k, b);
      update(x, y, k, b);
    }else if (op == 3){
      int x, k, b;
      read(x, k, b);
      xg(1, 1, n, dfn[x], dfn[x] + sz[x] - 1, k, b);
    }else {
      int x, r, k, b;
      read(x, r, k, b);
      walk(x, r, k, b, 0);
    }
  }
  return 0;
}
0