結果

問題 No.2342 Triple Tree Query (Hard)
ユーザー vjudge1vjudge1
提出日時 2024-10-15 13:10:41
言語 C++23(gcc13)
(gcc 13.2.0 + boost 1.83.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
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 8 ms
12,928 KB
testcase_01 AC 9 ms
12,928 KB
testcase_02 AC 54 ms
13,440 KB
testcase_03 AC 58 ms
13,440 KB
testcase_04 AC 52 ms
13,184 KB
testcase_05 AC 56 ms
13,184 KB
testcase_06 AC 63 ms
13,440 KB
testcase_07 AC 6,372 ms
29,696 KB
testcase_08 AC 5,713 ms
29,824 KB
testcase_09 AC 6,002 ms
29,824 KB
testcase_10 AC 5,665 ms
29,952 KB
testcase_11 AC 6,780 ms
29,824 KB
testcase_12 AC 6,239 ms
29,696 KB
testcase_13 AC 6,440 ms
29,824 KB
testcase_14 AC 6,239 ms
29,696 KB
testcase_15 AC 6,573 ms
29,696 KB
testcase_16 AC 6,981 ms
29,568 KB
testcase_17 AC 416 ms
33,024 KB
testcase_18 AC 404 ms
34,688 KB
testcase_19 AC 435 ms
32,896 KB
testcase_20 AC 412 ms
34,176 KB
testcase_21 AC 440 ms
34,688 KB
testcase_22 TLE -
testcase_23 -- -
testcase_24 -- -
testcase_25 -- -
testcase_26 -- -
testcase_27 -- -
testcase_28 -- -
testcase_29 -- -
testcase_30 -- -
testcase_31 -- -
testcase_32 -- -
testcase_33 -- -
testcase_34 -- -
testcase_35 -- -
testcase_36 -- -
testcase_37 -- -
権限があれば一括ダウンロードができます

ソースコード

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