結果

問題 No.2342 Triple Tree Query (Hard)
ユーザー SSRS
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

// #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 998244353
int 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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0