Sack
(Src/Graph/Tree/Sack.hpp)

View this file on GitHub
Last update: 2024-02-11 01:31:44+09:00
Include: #include "Src/Graph/Tree/Sack.hpp"

概要

根付き木に対して、「各頂点を根とした部分木を考慮した場合のOOを求めよ」みたいな状況で汎用的に（？）使えるアルゴリズム。

使い方

コンストラクタ

(1) Sack() = default
(2) Sack(usize n)

(1) 特に使用を想定していない

(2) 頂点集合を $\{ 0, 1, 2, \dots, n - 1 \}$ で初期化する。

$n$ は正整数でないといけない

addEdge

void addEdge(u32 u, u32 v)

辺 $\{ u, v \}$ を追加する。

operator[]

const std::vector<u32>& operator[](u32 v) const noexcept

頂点 $v$ と隣接する頂点のリストを返す。

execute

template <class ADD, class DEL, class QUERY, class RESET>
u32 execute(u32 root, const ADD& add, const DEL& del, const QUERY& query, const RESET& reset)

頂点 root を根とした根付き木として、Sackを実行する。addEdgeによって追加された辺から構成されるグラフが木や森でない場合、正常に動作しない可能性がある。

add

void add(u32 v)

頂点 $v$ を引数に取る関数オブジェクトである必要がある。頂点 $v$ の情報を反映する。

del

void del(u32 v)

頂点 $v$ を引数に取る関数オブジェクトである必要がある。頂点 $v$ の情報を削除する。

それ以前にadd(v)が呼ばれていることが保証されるので、それを打ち消す操作を入れる

query

void query(u32 v)

頂点 $v$ を引数に取る関数オブジェクトである必要がある。頂点 $v$ を根とした部分木に対するクエリを処理する。

この関数が呼ばれる時、 $v$ を根とした部分木に属する頂点 $x$ のみにadd(x)が呼ばれた状態であることが保証される。

正確には、del(x)によって打ち消されていないadd(x)が丁度一回ある。
この部分木に含まれていない頂点は add(x)とdel(x)の呼ばれた回数が同じであり、完全に打ち消されている。

reset

void reset()

delによって打ち消せないものがある時、resetで処理する。

rootを根とした根付き木の頂点数を返り値として返す。

Sackを使える問題に木では無く森の場合を要求するものがあったため、本当に $n$ 要素に対して実行を行ったか確認できるようにする意図がある。

計算量解析

一般性を失わず、連結グラフの場合を記す。

add を $O(n\log n)$ 回呼び出す
del を $O(n\log n)$ 回呼び出す
query を丁度 $n$ 回呼び出す
reset を $O(n)$ 回呼び出す

参考

Depends on

標準データ型のエイリアス (Src/Template/TypeAlias.hpp)

Verified with

Code

#pragma once

#include "../../Template/TypeAlias.hpp"

#include <cassert>
#include <utility>
#include <vector>

namespace zawa {

class Sack {
private:    
    static constexpr u32 INVALID{static_cast<u32>(-1)};
    usize n_{};
    std::vector<std::vector<u32>> g_;
    std::vector<u32> sz_, euler_, L_, R_;

    u32 dfsHLD(u32 v, u32 p) {
        sz_[v] = 1;
        usize m{g_[v].size()};
        usize max{};
        if (m > 1u and g_[v][0] == p) std::swap(g_[v][0], g_[v][1]);
        for (u32 i{} ; i < m ; i++) if (g_[v][i] != p) {
            sz_[v] += dfsHLD(g_[v][i], v);
            if (max < sz_[g_[v][i]]) {
                max = sz_[g_[v][i]];
                if (i) std::swap(g_[v][0], g_[v][i]);
            }
        }
        return sz_[v];
    }

    void dfsEuler(u32 v, u32 p, u32& t) {
        euler_[t] = v;
        L_[v] = t++;
        for (auto x : g_[v]) if (x != p) {
            dfsEuler(x, v, t);
        }
        R_[v] = t;
    }

public:
    constexpr usize size() const noexcept {
        return n_;
    }

    Sack() = default;
    Sack(u32 n) 
        : n_{n}, g_(n), sz_(n), euler_(n), L_(n), R_(n) {
        assert(n);
        g_.shrink_to_fit();
        sz_.shrink_to_fit();
        euler_.shrink_to_fit();
        L_.shrink_to_fit();
        R_.shrink_to_fit();
    }
    void addEdge(u32 u, u32 v) {
        assert(u < size());
        assert(v < size());
        g_[u].emplace_back(v);
        g_[v].emplace_back(u);
    }

    const std::vector<u32>& operator[](u32 v) const noexcept {
        assert(v < size());
        return g_[v];
    }

    template <class ADD, class DEL, class QUERY, class RESET>
    u32 execute(u32 root, const ADD& add, const DEL& del, const QUERY& query, const RESET& reset) {
        dfsHLD(root, INVALID);
        u32 t{};
        dfsEuler(root, INVALID, t);
        
        auto sack{[&](auto dfs, u32 v, u32 p, bool keep) -> void {
            usize m{g_[v].size()};
            for (u32 i{1} ; i < m ; i++) if (g_[v][i] != p) {
                dfs(dfs, g_[v][i], v, false);
            }
            if (sz_[v] > 1u) dfs(dfs, g_[v][0], v, true);
            if (sz_[v] > 1u) {
                for (u32 i{R_[g_[v][0]]} ; i < R_[v] ; i++) {
                    add(euler_[i]);
                }
            }
            add(v);
            query(v);
            if (!keep) {
                for (u32 i{L_[v]} ; i < R_[v] ; i++) {
                    del(euler_[i]);
                }
                reset();
            }
        }};
        sack(sack, root, INVALID, false);

        return sz_[root];
    }
};

} // namespace zawa

#line 2 "Src/Graph/Tree/Sack.hpp"

#line 2 "Src/Template/TypeAlias.hpp"

#include <cstdint>
#include <cstddef>

namespace zawa {

using i16 = std::int16_t;
using i32 = std::int32_t;
using i64 = std::int64_t;
using i128 = __int128_t;

using u8 = std::uint8_t;
using u16 = std::uint16_t;
using u32 = std::uint32_t;
using u64 = std::uint64_t;

using usize = std::size_t;

} // namespace zawa
#line 4 "Src/Graph/Tree/Sack.hpp"

#include <cassert>
#include <utility>
#include <vector>

namespace zawa {

class Sack {
private:    
    static constexpr u32 INVALID{static_cast<u32>(-1)};
    usize n_{};
    std::vector<std::vector<u32>> g_;
    std::vector<u32> sz_, euler_, L_, R_;

    u32 dfsHLD(u32 v, u32 p) {
        sz_[v] = 1;
        usize m{g_[v].size()};
        usize max{};
        if (m > 1u and g_[v][0] == p) std::swap(g_[v][0], g_[v][1]);
        for (u32 i{} ; i < m ; i++) if (g_[v][i] != p) {
            sz_[v] += dfsHLD(g_[v][i], v);
            if (max < sz_[g_[v][i]]) {
                max = sz_[g_[v][i]];
                if (i) std::swap(g_[v][0], g_[v][i]);
            }
        }
        return sz_[v];
    }

    void dfsEuler(u32 v, u32 p, u32& t) {
        euler_[t] = v;
        L_[v] = t++;
        for (auto x : g_[v]) if (x != p) {
            dfsEuler(x, v, t);
        }
        R_[v] = t;
    }

public:
    constexpr usize size() const noexcept {
        return n_;
    }

    Sack() = default;
    Sack(u32 n) 
        : n_{n}, g_(n), sz_(n), euler_(n), L_(n), R_(n) {
        assert(n);
        g_.shrink_to_fit();
        sz_.shrink_to_fit();
        euler_.shrink_to_fit();
        L_.shrink_to_fit();
        R_.shrink_to_fit();
    }
    void addEdge(u32 u, u32 v) {
        assert(u < size());
        assert(v < size());
        g_[u].emplace_back(v);
        g_[v].emplace_back(u);
    }

    const std::vector<u32>& operator[](u32 v) const noexcept {
        assert(v < size());
        return g_[v];
    }

    template <class ADD, class DEL, class QUERY, class RESET>
    u32 execute(u32 root, const ADD& add, const DEL& del, const QUERY& query, const RESET& reset) {
        dfsHLD(root, INVALID);
        u32 t{};
        dfsEuler(root, INVALID, t);
        
        auto sack{[&](auto dfs, u32 v, u32 p, bool keep) -> void {
            usize m{g_[v].size()};
            for (u32 i{1} ; i < m ; i++) if (g_[v][i] != p) {
                dfs(dfs, g_[v][i], v, false);
            }
            if (sz_[v] > 1u) dfs(dfs, g_[v][0], v, true);
            if (sz_[v] > 1u) {
                for (u32 i{R_[g_[v][0]]} ; i < R_[v] ; i++) {
                    add(euler_[i]);
                }
            }
            add(v);
            query(v);
            if (!keep) {
                for (u32 i{L_[v]} ; i < R_[v] ; i++) {
                    del(euler_[i]);
                }
                reset();
            }
        }};
        sack(sack, root, INVALID, false);

        return sz_[root];
    }
};

} // namespace zawa

Sack (Src/Graph/Tree/Sack.hpp)

概要

使い方