結果
問題 | No.1038 TreeAddQuery |
ユーザー |
|
提出日時 | 2022-08-05 20:53:50 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 444 ms / 4,000 ms |
コード長 | 10,782 bytes |
コンパイル時間 | 2,039 ms |
コンパイル使用メモリ | 117,988 KB |
最終ジャッジ日時 | 2025-01-30 17:28:57 |
ジャッジサーバーID (参考情報) |
judge3 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 24 |
ソースコード
#include <iostream>#include <chrono>#include <algorithm>#include <array>#include <cassert>#include <deque>#include <iostream>#include <queue>#include <utility>#include <vector>namespace suisen {namespace default_operator {template <typename T>auto zero() -> decltype(T { 0 }) { return T { 0 }; }template <typename T>auto one() -> decltype(T { 1 }) { return T { 1 }; }template <typename T>auto add(const T &x, const T &y) -> decltype(x + y) { return x + y; }template <typename T>auto sub(const T &x, const T &y) -> decltype(x - y) { return x - y; }template <typename T>auto mul(const T &x, const T &y) -> decltype(x * y) { return x * y; }template <typename T>auto div(const T &x, const T &y) -> decltype(x / y) { return x / y; }template <typename T>auto mod(const T &x, const T &y) -> decltype(x % y) { return x % y; }template <typename T>auto neg(const T &x) -> decltype(-x) { return -x; }template <typename T>auto inv(const T &x) -> decltype(one<T>() / x) { return one<T>() / x; }} // default_operatornamespace default_operator_noref {template <typename T>auto zero() -> decltype(T { 0 }) { return T { 0 }; }template <typename T>auto one() -> decltype(T { 1 }) { return T { 1 }; }template <typename T>auto add(T x, T y) -> decltype(x + y) { return x + y; }template <typename T>auto sub(T x, T y) -> decltype(x - y) { return x - y; }template <typename T>auto mul(T x, T y) -> decltype(x * y) { return x * y; }template <typename T>auto div(T x, T y) -> decltype(x / y) { return x / y; }template <typename T>auto mod(T x, T y) -> decltype(x % y) { return x % y; }template <typename T>auto neg(T x) -> decltype(-x) { return -x; }template <typename T>auto inv(T x) -> decltype(one<T>() / x) { return one<T>() / x; }} // default_operator} // namespace suisennamespace suisen {template <typename T, T(*_add)(T, T) = default_operator_noref::add<T>, T(*_zero)() = default_operator_noref::zero<T>, T(*_neg)(T) =default_operator_noref::neg<T>>struct PointGetRangeContourAddOnTree {using value_type = T;private:struct InternalFenwickTree {InternalFenwickTree() = default;InternalFenwickTree(int n) : _n(n), _dat(_n + 1, _zero()) {}value_type get(int i) const {value_type res = _zero();for (++i; i; i -= i & -i) res = _add(res, _dat[i]);return res;}void add(int l, int r, const value_type& val) {l = std::max(0, l), r = std::min(r, _n);if (l < r) add(l, val), add(r, _neg(val));}private:int _n;std::vector<value_type> _dat;void add(int r, const value_type& val) {for (++r; r <= _n; r += r & -r) _dat[r] = _add(_dat[r], val);}};using sequence_type = InternalFenwickTree;struct AuxInfo {int8_t child_index;int dist;};struct TreeNode {std::vector<int> adj;typename std::array<AuxInfo, 30>::iterator info_it;};public:PointGetRangeContourAddOnTree(int n = 0, const value_type& fill_value = _zero()) : PointGetRangeContourAddOnTree(std::vector<value_type>(n,fill_value)) {}PointGetRangeContourAddOnTree(const std::vector<value_type>& dat) : _n(dat.size()), _dat(dat), _nodes(_n), _par(_n, -1), _info(_n),_subtrees(_n) {_par.reserve(2 * _n);_subtrees.reserve(2 * _n);for (int i = 0; i < _n; ++i) {_nodes[i].info_it = _info[i].begin();}}void add_edge(int u, int v) {_nodes[u].adj.push_back(v);_nodes[v].adj.push_back(u);}void build() {std::vector<int> sub_size(_n, 0);std::vector<int> ctr(_n, -1);sub_size.reserve(2 * _n);ctr.reserve(2 * _n);std::vector<std::vector<int>> ch(_n);ch.reserve(2 * _n);auto merge = [&](std::vector<int>&& l, std::vector<int>&& r) -> std::vector<int>&& {if (l.size() > r.size()) std::swap(l, r);for (int v : l) r.push_back(v);return std::move(r);};auto rec = [&](auto rec, int r, int siz) -> int {int c = -1;auto get_centroid = [&](auto get_centroid, int u, int p) -> void {sub_size[u] = 1;for (int v : _nodes[u].adj) if (v != p) {get_centroid(get_centroid, v, u);if (v == c) {sub_size[u] = siz - sub_size[c];break;}sub_size[u] += sub_size[v];}if (c < 0 and sub_size[u] * 2 > siz) c = u;};get_centroid(get_centroid, r, -1);for (int v : _nodes[c].adj) {const int comp_size = sub_size[v];_nodes[v].adj.erase(std::find(_nodes[v].adj.begin(), _nodes[v].adj.end(), c));ctr[v] = rec(rec, v, comp_size);sub_size[v] = comp_size;}auto comp = [&](int i, int j) { return sub_size[i] > sub_size[j]; };std::priority_queue<int, std::vector<int>, decltype(comp)> pq{ comp };for (int v : _nodes[c].adj) {ch[v] = { v };pq.push(v);}auto build_sequence = [this](const std::vector<int>& roots, const bool child_index) {std::deque<std::pair<int, int>> dq;for (int r : roots) dq.emplace_back(r, -1);int dist = -1, nxt = roots.front();while (dq.size()) {const auto [u, pu] = dq.front();dq.pop_front();if (u == nxt) ++dist, nxt = -1;auto& node = _nodes[u];*node.info_it++ = { child_index, dist };for (int v : node.adj) if (v != pu) {dq.emplace_back(v, u);if (nxt < 0) nxt = v;}}return sequence_type(dist + 1);};while (pq.size() >= 2) {const int u = pq.top(); pq.pop();const int v = pq.top(); pq.pop();if (pq.empty()) {_par[ctr[u]] = _par[ctr[v]] = c;_subtrees[c][0] = build_sequence(ch[u], 0);_subtrees[c][1] = build_sequence(ch[v], 1);break;}const int new_node = sub_size.size();sub_size.push_back(sub_size[u] + sub_size[v]);ctr.push_back(new_node);_par.push_back(-1);_par[ctr[u]] = _par[ctr[v]] = new_node;_subtrees.emplace_back();_subtrees[new_node][0] = build_sequence(ch[u], 0);_subtrees[new_node][1] = build_sequence(ch[v], 1);ch.push_back(merge(std::move(ch[u]), std::move(ch[v])));ch[u].clear(), ch[u].shrink_to_fit();ch[v].clear(), ch[v].shrink_to_fit();pq.push(new_node);}if (pq.size()) {int u = pq.top(); pq.pop();_par[ctr[u]] = c;_subtrees[c][0] = build_sequence(ch[u], 0);}for (int v : _nodes[c].adj) _nodes[v].adj.push_back(c);return c;};rec(rec, 0, _n);}value_type get(int u) const {value_type res = _dat[u];int v = _par[u];const auto it_end = _nodes[u].info_it;for (auto it = _info[u].begin(); it != it_end; ++it) {res = _add(res, _subtrees[std::exchange(v, _par[v])][it->child_index].get(it->dist));}return res;}void set(int u, const value_type& new_val) {add(u, _add(new_val, _neg(get(u))));}void add(int u, const value_type &val) {_nodes[u].dat = _add(_dat[u], val);}void add(int u, int dl, int dr, const value_type &val) {if (dl <= 0 and 0 < dr) _dat[u] = _add(_dat[u], val);_subtrees[u][0].add(dl - 1, dr - 1, val);_subtrees[u][1].add(dl - 1, dr - 1, val);int v = _par[u];const auto it_end = _nodes[u].info_it;for (auto it = _info[u].begin(); it != it_end; ++it) {int ql = dl - it->dist - 2, qr = dr - it->dist - 2;if (v < _n and ql <= -1 and -1 < qr) _dat[v] = _add(_dat[v], val);_subtrees[std::exchange(v, _par[v])][it->child_index ^ 1].add(ql, qr, val);}}private:int _n;std::vector<value_type> _dat;std::vector<TreeNode> _nodes;std::vector<int> _par;std::vector<std::array<AuxInfo, 30>> _info;std::vector<std::array<sequence_type, 2>> _subtrees;};} // namespace suisenint main() {auto beg_time = std::chrono::system_clock::now();std::ios::sync_with_stdio(false);std::cin.tie(nullptr);int n, q;std::cin >> n >> q;suisen::PointGetRangeContourAddOnTree<long long> g(n);for (int i = 0; i < n - 1; ++i) {int u, v;std::cin >> u >> v;--u, --v;g.add_edge(u, v);}g.build();auto mid_time = std::chrono::system_clock::now();std::cerr << "build time : " << std::chrono::duration_cast<std::chrono::milliseconds>(mid_time - beg_time).count() << std::endl;for (int i = 0; i < q; ++i) {int x, y, z;std::cin >> x >> y >> z;--x, ++y;std::cout << g.get(x) << '\n';g.add(x, 0, y, z);}auto end_time = std::chrono::system_clock::now();std::cerr << "query time : " << std::chrono::duration_cast<std::chrono::milliseconds>(end_time - mid_time).count() << std::endl;return 0;}