結果
問題 | No.2342 Triple Tree Query (Hard) |
ユーザー |
![]() |
提出日時 | 2023-05-30 16:44:06 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 1,172 ms / 10,000 ms |
コード長 | 8,078 bytes |
コンパイル時間 | 3,472 ms |
コンパイル使用メモリ | 208,532 KB |
実行使用メモリ | 62,656 KB |
最終ジャッジ日時 | 2024-12-28 12:32:22 |
合計ジャッジ時間 | 25,029 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 36 |
ソースコード
// #define _GLIBCXX_DEBUG#include <bits/stdc++.h>// #include "debug.h"// #include "utils.h"int ri() {int n;scanf("%d", &n);return n;}struct decomp {int n;int k;std::vector<std::vector<int> > hen;decomp (int n_, int k) : n(n_ + k), k(k), hen(n) {for (int i = 0; i < k; i++) hen[i].push_back(i + 1), hen[i + 1].push_back(i);}void add_hen(int a, int b) {hen[a + k].push_back(b + k);hen[b + k].push_back(a + k);}std::vector<int> size;std::vector<int> par;void dfs0(int i, int prev) {par[i] = prev;if (prev != -1) hen[i].erase(std::find(hen[i].begin(), hen[i].end(), prev));for (auto &j : hen[i]) {dfs0(j, i);if (size[j] > size[hen[i][0]]) std::swap(j, hen[i][0]);size[i] += size[j];}}std::vector<std::vector<std::vector<int> > > kdown;std::vector<int> group, ord_in_hp, kth_in_hp;int group_cnt = 1;std::vector<int> path;std::vector<int> seq, ord;std::vector<int> kdown_head;std::vector<int> in, out;std::vector<std::vector<std::pair<int, int> > > down_range;std::vector<std::vector<int> > down_leftmost;int get_kdown_head(int i) {for (int j = 0; j < k; j++) {if (!hen[i].size()) return -1;i = hen[i][0];}return i;}void dfs1(int i) {path.push_back(i);if (i >= k) kdown[path[path.size() - (k + 1)]].push_back(std::vector<int>(path.end() - (k + 1), path.end()));in[i] = seq.size();kdown_head[i] = get_kdown_head(i);if (kdown_head[i] != -1) seq.push_back(kdown_head[i]);if (!i || i != hen[par[i]][0]) kth_in_hp[i] = kdown_head[i];else kth_in_hp[i] = kth_in_hp[par[i]];for (auto j : hen[i]) {if (j == hen[i][0]) ord_in_hp[j] = ord_in_hp[i] + 1, group[j] = group[i];else ord_in_hp[j] = 0, group[j] = group_cnt++;dfs1(j);}for (auto j : kdown[i]) {if (j.back() == kdown_head[i]) {for (int l = 0; l < k; l++) down_leftmost[j[l]][k - l] = j.back();} else {seq.push_back(j.back());for (int l = 0; l < k; l++) {if (down_range[j[l]][k - l].first == -1) down_range[j[l]][k - l].first = j.back();down_range[j[l]][k - l].second = j.back();}}}out[i] = seq.size();path.pop_back();}void process() {size.resize(n, 1);par.resize(n);dfs0(0, -1);ord_in_hp.resize(n);kth_in_hp.resize(n);kdown.resize(n);kdown_head.resize(n);in.resize(n);out.resize(n);group.resize(n);for (int i = 0; i < k; i++) seq.push_back(i);down_range.resize(n, std::vector<std::pair<int, int> >(k + 1, {-1, -1}));down_leftmost.resize(n, std::vector<int>(k + 1, -1));dfs1(0);assert(seq.size() == n);assert(std::set<int>(seq.begin(), seq.end()).size() == seq.size());ord.resize(n);for (int i = 0; i < n; i++) ord[seq[i]] = i;for (auto &i : down_range) for (auto &j : i) {if (j.first != -1) j.first = ord[j.first];if (j.second != -1) j.second = ord[j.second] + 1;}for (auto &i : down_leftmost) for (auto &j : i) if (j != -1) j = ord[j];for (int i = 0; i < n; i++) down_range[i][0] = {ord[i], ord[i] + 1};/*for (auto i : seq) std::cerr << i - k << " ";std::cerr << std::endl;for (int i = 0; i < n; i++) {std::cerr << i << " : " << std::endl;std::cerr << " g:" << group[i] << " kth:" << kth_in_hp[i] << std::endl;for (int j = 1; j <= k; j++) {std::cerr << " " << j << " : " << down_range[i][j].first << "," << down_range[i][j].second << " lm:" << down_leftmost[i][j] << std::endl;}}*/}std::vector<std::pair<int, int> > get_path(int x, int y) {x += k;y += k;std::vector<std::pair<int, int> > res;auto up_y = [&] () {res.push_back({ord[kth_in_hp[y]], ord[y] + 1});y = par[kth_in_hp[y]];};while (group[x] != group[y]) {if (group[x] > group[y]) std::swap(x, y);if (ord_in_hp[y] >= k) up_y();else {res.push_back({ord[y], ord[y] + 1});y = par[y];}}if (ord_in_hp[x] > ord_in_hp[y]) std::swap(x, y);if (ord_in_hp[y] >= k) {if (ord_in_hp[x] >= k) {res.push_back({ord[x], ord[y] + 1});return res;} else up_y();}while (y != x) {res.push_back({ord[y], ord[y] + 1});y = par[y];}res.push_back({ord[x], ord[x] + 1});return res;}std::vector<std::pair<int, int> > get_subtree(int x) {x += k;std::vector<std::pair<int, int> > res{{in[x], out[x]}, {ord[x], ord[x] + 1}};for (int i = 1; i < k; i++) {if (down_range[x][i].first != -1) res.push_back(down_range[x][i]);if (down_leftmost[x][i] != -1) res.push_back({down_leftmost[x][i], down_leftmost[x][i] + 1});}return res;}std::vector<std::pair<int, int> > get_k_vicinity(int x, int d) {x += k;assert(d <= k);std::vector<std::pair<int, int> > res;int t = x;int depth = d;for (int i = d; i >= -d; i--, depth--) {if (i != d && !((d - i) & 1)) t = par[t], depth++;// std::cerr << " depth " << i << " : " << t << "@" << depth << std::endl;if (down_range[t][depth].first != -1) res.push_back(down_range[t][depth]);if (down_leftmost[t][depth] != -1) res.push_back({down_leftmost[t][depth], down_leftmost[t][depth] + 1});}return res;}int pos(int x) { return ord[x + k]; }};template<class monoid_t> struct dual_segtree {using value_t = decltype(monoid_t::unit());static_assert(std::is_same<decltype(monoid_t::op), value_t(value_t, value_t)>::value ||std::is_same<decltype(monoid_t::op), value_t(const value_t &, const value_t &)>::value, "");value_t unit() { return monoid_t::unit(); }int n_, n;std::vector<value_t> vals;int ceil_power2(int x) { int i = 1; while (i < x) i <<= 1; return i; }dual_segtree (int n_) : n_(n_), n(ceil_power2(n_)), vals(n << 1, unit()) {}template<typename itr_t> dual_segtree (itr_t begin, itr_t end) : dual_segtree(end - begin) {std::copy(begin, end, vals.begin() + n);}template<typename T = value_t> dual_segtree (const std::vector<T> &a) : dual_segtree(a.begin(), a.end()) {}void flush(int i) {vals[i << 1] = monoid_t::op(vals[i << 1], vals[i]);vals[i << 1 | 1] = monoid_t::op(vals[i << 1 | 1], vals[i]);vals[i] = unit();}template<class func_t> void dive_range(int l, int r, int node, int nodel, int noder, const func_t &f) {if (r <= nodel || l >= noder) return;if (l <= nodel && r >= noder) f(node);else {flush(node);int nodem = nodel + ((noder - nodel) >> 1);dive_range(l, r, node << 1, nodel, nodem, f);dive_range(l, r, node << 1 | 1, nodem, noder, f);}}void apply(int l, int r, const value_t &op) {/// std::cerr << l << " " << r << " " << op.first << " " << op.second << std::endl;dive_range(l, r, 1, 0, n, [&] (int node) { vals[node] = monoid_t::op(vals[node], op); });}value_t operator [] (int i) {value_t res;dive_range(i, i + 1, 1, 0, n, [&] (int node) { res = vals[node]; });return res;}};template<int MOD> struct affine_mod {using T = std::pair<int, int>;using u64 = uint64_t;static T unit() { return {1, 0}; }static T op(T lhs, T rhs) { return {(u64) lhs.first * rhs.first % MOD, ((u64) lhs.second * rhs.first + rhs.second) % MOD}; }};#define MOD 998244353int main() {int n = ri();int q = ri();decomp tree(n, 10);for (int i = 1; i < n; i++) {int a = ri() - 1;int b = ri() - 1;tree.add_hen(a, b);}tree.process();std::vector<int> a(n);for (auto &i : a) i = ri();dual_segtree<affine_mod<MOD> > seq(tree.n);for (int i = 0; i < q; i++) {int t = ri();if (t == 4) {int x = ri() - 1;int y = ri() - 1;int c = ri();int d = ri();for (auto j : tree.get_path(x, y)) seq.apply(j.first, j.second, {c, d});} else if (t == 3) {int x = ri() - 1;int c = ri();int d = ri();for (auto j : tree.get_subtree(x)) seq.apply(j.first, j.second, {c, d});} else if (t == 2) {int x = ri() - 1;int k = ri();int c = ri();int d = ri();for (auto j : tree.get_k_vicinity(x, k)) seq.apply(j.first, j.second, {c, d});} else {int x = ri() - 1;auto t = seq[tree.pos(x)];printf("%d\n", (int) (((uint64_t) a[x] * t.first + t.second) % MOD));}}return 0;}