#632900 (C++17) No.399 動的な領主

• 問題: No.399 動的な領主
• ユーザー: lorent_kyopro
• 提出日時: 2021-03-21 23:28:01
• 言語: C++17 (gcc 12.3.0 + boost 1.83.0)
• 結果: AC
• 実行時間: 511 ms / 2,000 ms
• コード長: 6,097 bytes
• コンパイル時間: 3,211 ms
• コンパイル使用メモリ: 223,776 KB
• 実行使用メモリ: 24,832 KB
• 最終ジャッジ日時: 2024-11-22 18:41:44
• 合計ジャッジ時間: 7,416 ms
• ジャッジサーバーID （参考情報）: judge1 / judge5

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	2 ms; 5,248 KB
testcase_01	AC	2 ms; 5,248 KB
testcase_02	AC	2 ms; 5,248 KB
testcase_03	AC	2 ms; 5,248 KB
testcase_04	AC	4 ms; 5,248 KB
testcase_05	AC	29 ms; 5,248 KB
testcase_06	AC	497 ms; 19,712 KB
testcase_07	AC	477 ms; 19,840 KB
testcase_08	AC	477 ms; 19,840 KB
testcase_09	AC	461 ms; 19,968 KB
testcase_10	AC	5 ms; 5,248 KB
testcase_11	AC	25 ms; 5,248 KB
testcase_12	AC	344 ms; 20,224 KB
testcase_13	AC	329 ms; 20,224 KB
testcase_14	AC	84 ms; 24,832 KB
testcase_15	AC	120 ms; 24,832 KB
testcase_16	AC	203 ms; 22,912 KB
testcase_17	AC	484 ms; 19,968 KB
testcase_18	AC	511 ms; 19,968 KB

ソースコード

#include <bits/stdc++.h>
#include <atcoder/lazysegtree>

__attribute__((constructor))
void fast_io() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
}

class heavy_light_decomposition {
public:
    heavy_light_decomposition(size_t n)
        : n(n),
          tree(n),
          subtree_size(n, 1),
          parent(n),
          in(n),
          out(n),
          chain_head(n),
          built(false) {}

    heavy_light_decomposition(const std::vector<std::vector<size_t>>& tree)
        : heavy_light_decomposition(tree, 0) {}

    heavy_light_decomposition(const std::vector<std::vector<size_t>>& tree,
                              size_t root)
        : n(tree.size()),
          tree(tree),
          subtree_size(n, 1),
          parent(n),
          in(n),
          out(n),
          chain_head(n),
          built(false) {
        assert(root < n);
        build(root);
    }

    void add_edge(size_t u, size_t v) {
        assert(u < n && v < n);
        tree[u].push_back(v);
        tree[v].push_back(u);
    }

    void build(size_t root = 0) {
        dfs_for_size(0, n);
        size_t time = 0;
        chain_head[root] = root;
        dfs_for_hld(root, time);
        built = true;
    }

    size_t operator[](size_t u) const {
        assert(built && u < n);
        return in[u];
    }

    size_t lca(size_t u, size_t v) const {
        assert(built && u < n && v < n);
        while (true) {
            if (in[u] > in[v]) std::swap(u, v);
            if (chain_head[u] == chain_head[v]) return u;
            v = parent[chain_head[v]];
        }
    }

    std::pair<size_t, size_t> subtree_query(size_t u) const {
        assert(built && u < n);
        return {in[u], out[u]};
    }
    
    template <typename F> void subtree_query(size_t u, const F& f) const {
        assert(built && u < n);
        f(in[u], out[u]);
    }

    // when operation is noncommutative

    // S resl = e(), resr = e();
    // size_t w = hld.lca(u, v)
    // hld.node_query(u, w, [&](size_t l, size_t r) { resl = op(resl, rseg.prod(l, r)); });
    // hld.edge_query(w, v, [&](size_t l, size_t r) { resr = op(seg.prod(l, r), resr); });
    // S res = op(resl, resr);

    std::vector<std::pair<size_t, size_t>> node_query(size_t u, size_t v) const {
        assert(built && u < n && v < n);
        std::vector<std::pair<size_t, size_t>> result;
        while (true) {
            if (in[u] > in[v]) std::swap(u, v);
            if (chain_head[u] != chain_head[v]) {
                result.emplace_back(in[chain_head[v]], in[v] + 1);
                v = parent[chain_head[v]];
            } else {
                result.emplace_back(in[u], in[v] + 1);
                return result;
            }
        }
    }

    template <typename F> void node_query(size_t u, size_t v, const F& f) const {
        assert(built && u < n && v < n);
        while (true) {
            if (in[u] > in[v]) std::swap(u, v);
            if (chain_head[u] != chain_head[v]) {
                f(in[chain_head[v]], in[v] + 1);
                v = parent[chain_head[v]];
            } else {
                f(in[u], in[v] + 1);
                return;
            }
        }
    }

    std::vector<std::pair<size_t, size_t>> edge_query(size_t u, size_t v) const {
        assert(built && u < n && v < n);
        std::vector<std::pair<size_t, size_t>> result;
        while (true) {
            if (in[u] > in[v]) std::swap(u, v);
            if (chain_head[u] != chain_head[v]) {
                result.emplace_back(in[chain_head[v]], in[v] + 1);
                v = parent[chain_head[v]];
            } else {
                if (u != v) result.emplace_back(in[u] + 1, in[v] + 1);
                return result;
            }
        }
    }

    template <typename F> void edge_query(size_t u, size_t v, const F& f) const {
        assert(built && u < n && v < n);
        while (true) {
            if (in[u] > in[v]) std::swap(u, v);
            if (chain_head[u] != chain_head[v]) {
                f(in[chain_head[v]], in[v] + 1);
                v = parent[chain_head[v]];
            } else {
                if (u != v) f(in[u] + 1, in[v] + 1);
                return;
            }
        }
    }

private:
    const size_t n;
    std::vector<std::vector<size_t>> tree;
    std::vector<size_t> subtree_size, parent, in, out, chain_head;
    bool built;

    void dfs_for_size(size_t u, size_t p) {
        parent[u] = p;
        if (!tree[u].empty() && tree[u].front() == p)
            std::swap(tree[u].front(), tree[u].back());
        for (size_t& v : tree[u]) {
            if (v == p) continue;
            dfs_for_size(v, u);
            subtree_size[u] += subtree_size[v];
            if (subtree_size[v] > subtree_size[tree[u].front()]) {
                std::swap(v, tree[u].front());
            }
        }
    }

    void dfs_for_hld(size_t u, size_t& time) {
        in[u] = time++;
        for (size_t& v : tree[u]) {
            if (v == parent[u]) continue;
            chain_head[v] = (v == tree[u].front() ? chain_head[u] : v);
            dfs_for_hld(v, time);
        }
        out[u] = time;
    }
};

using S = std::pair<long long, size_t>;
S op(S a, S b) { return {a.first + b.first, a.second + b.second}; }
S e() { return {0, 0}; }
using F = long long;
S mapping(F f, S x) { return {x.first + f * x.second, x.second}; }
F composition(F f, F g) { return f + g; }
F id() { return 0; }

int main() {
    size_t n;
    std::cin >> n;

    heavy_light_decomposition hld(n);
    for (size_t i = 0; i < n - 1; ++i) {
        size_t u, v;
        std::cin >> u >> v;
        u--; v--;
        hld.add_edge(u, v);
    }
    hld.build();
    atcoder::lazy_segtree<S, op, e, F, mapping, composition, id> seg(std::vector<S>(n, {0, 1}));

    size_t q;
    std::cin >> q;
    long long ans = 0;
    while (q--) {
        size_t a, b;
        std::cin >> a >> b;
        a--; b--;
        hld.node_query(a, b, [&](size_t l, size_t r) {
            seg.apply(l, r, 1);
            ans += seg.prod(l, r).first;
        });
    }
    std::cout << ans << '\n';
}