結果

問題 No.2342 Triple Tree Query (Hard)
ユーザー vjudge1
提出日時 2025-08-11 15:04:48
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 1,027 ms / 10,000 ms
コード長 5,427 bytes
コンパイル時間 4,192 ms
コンパイル使用メモリ 298,600 KB
実行使用メモリ 112,472 KB
最終ジャッジ日時 2025-08-11 15:05:17
合計ジャッジ時間 27,248 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 36
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int> ;

const int mod = 998244353;
void Add(int &x, ll y) { x = (x + y) % mod; }
const int kN = 1e5 + 5, kR = 15, kS = kN * 4;
int cid, n, q, K, tot;
int a[kN];
int fa[kN], dep[kN], siz[kN], son[kN], top[kN], dfn[kN], rev[kN];
vector<int> g[kN];
vector<pii> sub[kN], ch[kN];
vector<pii> subr[kN][kR];

struct Tag {
  int a, b;
  Tag() { a = 1, b = 0; }
  Tag(int _a, int _b) { a = _a, b = _b; }
  bool Empty() { return (a == 1) && !b; }
};
Tag& operator *= (Tag &x, Tag y) { return x = Tag((ll)x.a * y.a % mod, ((ll)x.b * y.a + y.b) % mod); }
int& operator *= (int &x, Tag y) { return x = ((ll)x * y.a + y.b) % mod; }

#define ls (o << 1)
#define rs (o << 1 | 1)
struct SGT {
  int sum[kS];
  Tag tag[kS];
  void Up(int o) { sum[o] = (sum[ls] + sum[rs]) % mod; }
  void Build(int o, int l, int r) {
    if(l == r) return void(sum[o] = a[rev[l]]);
    int mid = (l + r) >> 1;
    Build(ls, l, mid);
    Build(rs, mid + 1, r);
    Up(o);
  }
  void Adt(int o, Tag t) { sum[o] *= t, tag[o] *= t; }
  void Dn(int o) {
    if(!tag[o].Empty()) {
      Adt(ls, tag[o]), Adt(rs, tag[o]), tag[o] = Tag();
    }
  }
  void Update(int o, int l, int r, int x, int y, Tag t) {
    if((l > y) || (r < x)) return ;
    if((l >= x) && (r <= y)) return Adt(o, t);
    Dn(o);
    int mid = (l + r) >> 1;
    Update(ls, l, mid, x, y, t);
    Update(rs, mid + 1, r, x, y, t);
    Up(o);
  }
  int Get(int o, int l, int r, int x) {
    if(l == r) return sum[o];
    Dn(o);
    int mid = (l + r) >> 1;
    if(mid < x) return Get(rs, mid + 1, r, x);
    return Get(ls, l, mid, x);
  }
}sgt;

void DFS(int x, int fa) {
  siz[x] = 1;
  ::fa[x] = fa;
  dep[x] = dep[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;
  if(son[x]) DFS2(son[x], tp);
  for(int to : g[x]) {
    if((to != son[x]) && (to != fa[x])) DFS2(to, to);
  }
}

void BFS(int x) {
  queue<int> q;
  for(int i = x; i; i = son[i]) {
    for(int to : g[i]) {
      if((to != fa[i]) && (to != son[i])) q.push(to);
    }
  }
  for(int d = 1; d <= K; d++) {
    for(int siz = q.size(); siz--; ) {
      int cur = q.front(); q.pop();
      if(!dfn[cur]) {
        dfn[cur] = ++tot;
        rev[tot] = cur;
      }
      for(int to : g[cur]) {
        if(to != fa[cur]) q.push(to);
      }
    }
  }
}
void Label(int x) {
  if(top[x] == x) {
    int cl = 0, cr = -1;
    int nl = n + 1, nr = 0;
    for(int i = x; i; i = son[i]) {
      if(dfn[i]) {
        if(cr + 1 != dfn[i]) {
          if(cl <= cr) ch[x].emplace_back(cl, cr);
          cl = cr = dfn[i];
        }else cr = dfn[i];
        continue;
      }
      dfn[i] = ++tot;
      rev[tot] = i;
      nl = min(nl, tot);
      nr = max(nr, tot);
    }
    if(cl <= cr) {
      ch[x].emplace_back(cl, cr);
      cl = 0, cr = -1;
    }
    if(nl <= nr) ch[x].emplace_back(nl, nr);
    BFS(x);
  }
  for(int to : g[x]) {
    if(to != fa[x]) Label(to);
  }
}
void DFS3(int x, int fa) {
  vector<int> son;
  for(int to : g[x]) {
    if(to == fa) continue;
    DFS3(to, x);
    son.push_back(to);
  }
  auto Get = [&](vector<pii> tmp, vector<pii> &ans) {
    sort(tmp.begin(), tmp.end());
    int siz = tmp.size();
    for(int l = 0, r; l < siz; l = r + 1) {
      for(r = l; (r + 1 < siz) && (tmp[r + 1].first == tmp[r].second + 1); r++) ;
      ans.emplace_back(tmp[l].first, tmp[r].second);
    }
  };
  subr[x][0].emplace_back(dfn[x], dfn[x]);
  vector<pii> tmp {pii {dfn[x], dfn[x]}};
  for(int to : son) tmp.insert(tmp.end(), sub[to].begin(), sub[to].end());
  Get(tmp, sub[x]);
  for(int d = 1; d <= K; d++) {
    vector<pii> tmp;
    for(int to : son) {
      vector<pii> &vec = subr[to][d - 1];
      tmp.insert(tmp.end(), vec.begin(), vec.end());
    }
    Get(tmp, subr[x][d]);
    if(subr[x][d].empty()) continue;
  }
}

void F(vector<pii> &v, Tag t, int l, int r) {
  for(pii seg : v) {
    int sl = seg.first;
    int sr = seg.second;
    sl = max(sl, l);
    sr = min(sr, r);
    if(sl <= sr) sgt.Update(1, 1, n, sl, sr, t);
  }
}
void Update1(int x, int rng, Tag t) {
  for(int i = x, j = rng; ~j; i = fa[i], j--) {
    if(i == 1) {
      for(int k = 0; k <= j; k++) F(subr[1][k], t, 0, n);
      break;
    }
    F(subr[i][j], t, 0, n);
    if(j) F(subr[i][j - 1], t, 0, n);
  }
}
void Update2(int x, Tag t) { F(sub[x], t, 0, n); }
void Update3(int x, int y, Tag t) {
  while(top[x] != top[y]) {
    if(dep[top[x]] < dep[top[y]]) swap(x, y);
    F(ch[top[x]], t, 0, dfn[x]);
    x = fa[top[x]];
  }
  if(dfn[x] > dfn[y]) swap(x, y);
  F(ch[top[x]], t, dfn[x], dfn[y]);
}

int main() {
  ios::sync_with_stdio(0), cin.tie(0);
  cin >> n >> q, K = 10;
  for(int i = 1; i < n; i++) {
    int u, v;
    cin >> u >> v;
    g[u].push_back(v);
    g[v].push_back(u);
  }
  for(int i = 1; i <= n; i++) cin >> a[i];
  DFS(1, 0), DFS2(1, 1), Label(1);
  DFS3(1, 0);
  sgt.Build(1, 1, n);
  for(int i = 1; i <= q; i++) {
    int op, x, y, p, v;
    cin >> op;
    if(op == 1) {
      cin >> x;
      cout << sgt.Get(1, 1, n, dfn[x]) << "\n";
    }else if(op == 2) {
      cin >> x >> y >> p >> v;
      Update1(x, y, Tag(p, v));
    }else if(op == 3) {
      cin >> x >> p >> v;
      Update2(x, Tag(p, v));
    }else {
      cin >> x >> y >> p >> v;
      Update3(x, y, Tag(p, v));
    }
  }
  return 0;
}
0