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

提出ソース

結果

問題	No.399 動的な領主
ユーザー	lorent_kyopro
提出日時	2021-03-21 23:35:32
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	188 ms / 2,000 ms
コード長	6,096 bytes
コンパイル時間	2,337 ms
コンパイル使用メモリ	215,068 KB
実行使用メモリ	19,712 KB
最終ジャッジ日時	2024-11-22 18:48:13
合計ジャッジ時間	4,964 ms
ジャッジサーバーID （参考情報）	judge3 / judge2

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
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	3 ms 5,248 KB
testcase_05	AC	13 ms 5,248 KB
testcase_06	AC	183 ms 14,720 KB
testcase_07	AC	177 ms 14,720 KB
testcase_08	AC	184 ms 14,848 KB
testcase_09	AC	188 ms 14,848 KB
testcase_10	AC	3 ms 5,248 KB
testcase_11	AC	11 ms 5,248 KB
testcase_12	AC	142 ms 15,232 KB
testcase_13	AC	133 ms 15,232 KB
testcase_14	AC	66 ms 19,712 KB
testcase_15	AC	68 ms 19,712 KB
testcase_16	AC	88 ms 17,920 KB
testcase_17	AC	188 ms 14,720 KB
testcase_18	AC	184 ms 14,848 KB

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

ソースコード

raw source code

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

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

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::fenwick_tree<long long> fw0(n + 1), fw1(n + 1);
    auto apply = [&](size_t l, size_t r, long long x) {
        fw0.add(l, -x * l);
        fw1.add(l, x);
        fw0.add(r, x * r);
        fw1.add(r, -x);
    };
    auto sum = [&](size_t r) {
        return fw0.sum(0, r) + fw1.sum(0, r) * r;
    };
    auto prod = [&](size_t l, size_t r) {
        return sum(r) - sum(l);
    };

    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) {
            apply(l, r, 1);
            ans += prod(l, r);
        });
    }
    std::cout << ans << '\n';
}

yukicoder

結果

テストケース

ソースコード