#784691 (C++17) No.1038 TreeAddQuery

提出ソース

結果

問題	No.1038 TreeAddQuery
ユーザー	suisen
提出日時	2022-08-05 20:52:11
言語	C++17 (gcc 13.2.0 + boost 1.83.0)
結果	AC
実行時間	613 ms / 4,000 ms
コード長	10,782 bytes
コンパイル時間	1,851 ms
コンパイル使用メモリ	114,852 KB
実行使用メモリ	66,464 KB
最終ジャッジ日時	2023-10-13 20:59:54
合計ジャッジ時間	13,820 ms
ジャッジサーバーID （参考情報）	judge13 / judge12

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 4,348 KB
testcase_01	AC	2 ms 4,348 KB
testcase_02	AC	2 ms 4,348 KB
testcase_03	AC	7 ms 4,352 KB
testcase_04	AC	7 ms 4,348 KB
testcase_05	AC	7 ms 4,608 KB
testcase_06	AC	6 ms 4,352 KB
testcase_07	AC	7 ms 4,348 KB
testcase_08	AC	431 ms 53,076 KB
testcase_09	AC	450 ms 53,764 KB
testcase_10	AC	456 ms 54,088 KB
testcase_11	AC	448 ms 53,148 KB
testcase_12	AC	484 ms 53,972 KB
testcase_13	AC	595 ms 66,464 KB
testcase_14	AC	554 ms 59,092 KB
testcase_15	AC	528 ms 57,184 KB
testcase_16	AC	503 ms 54,856 KB
testcase_17	AC	513 ms 54,504 KB
testcase_18	AC	448 ms 61,972 KB
testcase_19	AC	383 ms 60,812 KB
testcase_20	AC	342 ms 60,816 KB
testcase_21	AC	331 ms 60,500 KB
testcase_22	AC	331 ms 58,036 KB
testcase_23	AC	333 ms 58,452 KB
testcase_24	AC	350 ms 54,748 KB
testcase_25	AC	613 ms 66,180 KB
testcase_26	AC	531 ms 63,828 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#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_operator
    namespace 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 suisen

namespace 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 suisen

int 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;
}

yukicoder

結果

テストケース

ソースコード