mo/mo_tree.hpp

• View this file on GitHub
• Last update: 2026-02-27 15:20:30+09:00
• Include: #include "mo/mo_tree.hpp"

Depends on

• mo/hilbert_mo.hpp

Verified with

• test/mo/aoj0489.test.cpp
• test/mo/aoj2270.test.cpp

Code

#ifndef MO_TREE_HPP
#define MO_TREE_HPP

#include "mo/hilbert_mo.hpp"
#include <algorithm>
#include <cassert>
#include <utility>
#include <vector>

struct MoTree {
    explicit MoTree(const std::vector<std::vector<int>> &adj)
        : n_(int(adj.size())), in_(n_), tour_(2 * n_), top_(n_), parent_(n_), mo_(2 * n_) {
        auto timer = 0;
        std::vector<int> size(n_, 1), heavy(n_, -1);
        auto dfs = [&](auto &&self, int u) -> void {
            for (auto v : adj[u]) {
                if (v != parent_[u]) {
                    parent_[v] = u;
                    self(self, v);
                    size[u] += size[v];
                    if (heavy[u] == -1 || size[heavy[u]] < size[v]) {
                        heavy[u] = v;
                    }
                }
            }
        };
        auto hld = [&](auto &&self, int u) -> void {
            in_[u] = timer;
            tour_[timer++] = u;
            for (auto v : adj[u]) {
                if (v != parent_[u]) {
                    top_[v] = (v == heavy[u]) ? top_[u] : v;
                    self(self, v);
                }
            }
            tour_[timer++] = u;
        };
        dfs(dfs, 0);
        hld(hld, 0);
    }
    int lca(int u, int v) const {
        assert(0 <= u && u < n_ && 0 <= v && v <= n_);
        while (top_[u] != top_[v]) {
            if (in_[top_[u]] < in_[top_[v]]) {
                std::swap(u, v);
            }
            u = parent_[top_[u]];
        }
        return (in_[u] < in_[v]) ? u : v;
    }
    void add(int u, int v) {
        assert(0 <= u && u < n_ && 0 <= v && v <= n_);
        lca_.push_back(lca(u, v));
        auto [l, r] = std::minmax(in_[u], in_[v]);
        mo_.add(l + 1, r + 1);
    }
    void solve(auto add, auto remove, auto eval) {
        std::vector<bool> contains(n_);
        auto toggle = [&](int i) {
            auto u = tour_[i];
            if (contains[u]) {
                remove(u);
            } else {
                add(u);
            }
            contains[u].flip();
        };
        auto eval_lca = [&](int i) {
            toggle(in_[lca_[i]]);
            eval(i);
            toggle(in_[lca_[i]]);
        };
        mo_.solve(toggle, toggle, eval_lca);
    }

private:
    int n_;
    std::vector<int> in_, tour_, top_, parent_, lca_;
    HilbertMo mo_;
};

#endif // MO_TREE_HPP

#line 1 "mo/mo_tree.hpp"



#line 1 "mo/hilbert_mo.hpp"



#include <algorithm>
#include <array>
#include <cassert>
#include <vector>

struct HilbertMo {
    HilbertMo(int n) : n_(n), log_(std::bit_width(unsigned(n))) {}
    void add(int l, int r) {
        assert(0 <= l && l <= r && r <= n_);
        auto index = int(queries_.size());
        auto order = hilbert_order(l, r);
        queries_.push_back({l, r, index, order});
    }
    void solve(auto add, auto remove, auto eval) { solve(add, add, remove, remove, eval); }
    void solve(auto add_left, auto add_right, auto remove_left, auto remove_right, auto eval) {
        sort(queries_.begin(), queries_.end());
        auto l = 0, r = 0;
        for (auto [left, right, index, order] : queries_) {
            while (left < l) {
                add_left(--l);
            }
            while (r < right) {
                add_right(r++);
            }
            while (l < left) {
                remove_left(l++);
            }
            while (right < r) {
                remove_right(--r);
            }
            eval(index);
        }
    }

private:
    struct query {
        int left, right, index;
        long long order;
        bool operator<(const query &other) const { return order < other.order; }
    };
    long long hilbert_order(int x, int y) const {
        auto d = 0LL;
        for (auto s = 1 << log_; s > 0; s >>= 1) {
            bool rx = x & s, ry = y & s;
            d = (d << 2) | ((rx * 3) ^ ry);
            if (!ry) {
                if (rx) {
                    x = ~x;
                    y = ~y;
                }
                std::swap(x, y);
            }
        }
        return d;
    }
    std::vector<query> queries_;
    const int n_, log_;
};


#line 7 "mo/mo_tree.hpp"
#include <utility>
#line 9 "mo/mo_tree.hpp"

struct MoTree {
    explicit MoTree(const std::vector<std::vector<int>> &adj)
        : n_(int(adj.size())), in_(n_), tour_(2 * n_), top_(n_), parent_(n_), mo_(2 * n_) {
        auto timer = 0;
        std::vector<int> size(n_, 1), heavy(n_, -1);
        auto dfs = [&](auto &&self, int u) -> void {
            for (auto v : adj[u]) {
                if (v != parent_[u]) {
                    parent_[v] = u;
                    self(self, v);
                    size[u] += size[v];
                    if (heavy[u] == -1 || size[heavy[u]] < size[v]) {
                        heavy[u] = v;
                    }
                }
            }
        };
        auto hld = [&](auto &&self, int u) -> void {
            in_[u] = timer;
            tour_[timer++] = u;
            for (auto v : adj[u]) {
                if (v != parent_[u]) {
                    top_[v] = (v == heavy[u]) ? top_[u] : v;
                    self(self, v);
                }
            }
            tour_[timer++] = u;
        };
        dfs(dfs, 0);
        hld(hld, 0);
    }
    int lca(int u, int v) const {
        assert(0 <= u && u < n_ && 0 <= v && v <= n_);
        while (top_[u] != top_[v]) {
            if (in_[top_[u]] < in_[top_[v]]) {
                std::swap(u, v);
            }
            u = parent_[top_[u]];
        }
        return (in_[u] < in_[v]) ? u : v;
    }
    void add(int u, int v) {
        assert(0 <= u && u < n_ && 0 <= v && v <= n_);
        lca_.push_back(lca(u, v));
        auto [l, r] = std::minmax(in_[u], in_[v]);
        mo_.add(l + 1, r + 1);
    }
    void solve(auto add, auto remove, auto eval) {
        std::vector<bool> contains(n_);
        auto toggle = [&](int i) {
            auto u = tour_[i];
            if (contains[u]) {
                remove(u);
            } else {
                add(u);
            }
            contains[u].flip();
        };
        auto eval_lca = [&](int i) {
            toggle(in_[lca_[i]]);
            eval(i);
            toggle(in_[lca_[i]]);
        };
        mo_.solve(toggle, toggle, eval_lca);
    }

private:
    int n_;
    std::vector<int> in_, tour_, top_, parent_, lca_;
    HilbertMo mo_;
};

Back to top page