ダブリング (Tree/doubling.hpp)

ダブリング

Functional Graph上で各頂点から $k$ 回後の状態や遷移先を高速に求めます。

コンストラクタ

template <typename T>
Doubling(int N, unsigned long long max_k)

遷移元のサイズ N と、必要な最大遷移回数 max_k を与えて初期化します。 T はコストの型です。

add_edge

void add_edge(int from, int to, T cost)

遷移元の頂点 from に対し、遷移先 to とコスト cost を設定します。

制約

各頂点からの遷移は 1 度だけ設定可能。

計算量

$O(1)$

init

void init()

すべての頂点に対して $2^i$ 回の遷移先とその累積コストを前計算します。

計算量

$O(N \log k)$

step_forward

pair<int, T> step_forward(int v, unsigned long long k)

頂点 v を始点として、$k$ 回遷移した後の頂点とその間の累積コストを返します。

計算量

$O(\log k)$

step_forwards

vector<pair<int, T>> step_forwards(const vector<int> &indices, unsigned long long k)

複数の始点 indices に対して、それぞれ $k$ 回遷移した後の頂点と累積コストをまとめて返します。各始点について step_forward を同時に実行するイメージです。

計算量

$O( \text{indices} \cdot \log k)$

vector<pair<int, T>> step_forwards(unsigned long long k)

すべての頂点 0 から N-1 を始点として、それぞれ $k$ 回遷移させた後の頂点と累積コストを返します。

計算量

$O(N \log k)$

Required by

Tree/lowest_common_ancestor.hpp

Verified with

Code

#include <bits/stdc++.h>
using namespace std;

template <typename T = long long>
class Doubling
{
    int N, L;

    vector<pair<int, T>> nexts;
    vector<vector<pair<int, T>>> parents;
    bool done_initialized = false;

public:
    Doubling() {};

    Doubling(int N, unsigned long long max_k) : N(N)
    {
        L = max<int>(bit_width(max_k), 1);
        nexts = vector<pair<int, T>>(N, {-1, 0});
        parents = vector<vector<pair<int, T>>>(N + 1, vector<pair<int, T>>(L, {-1, 0}));
    }

    void add_edge(int from, int to, T cost)
    {
        if (nexts[from].first != -1)
        {
            assert(false);
        }

        nexts[from] = pair(to, cost);
    }

    void init()
    {
        for (int i = 0; i < N; i++)
        {
            parents[i][0] = nexts[i];
        }

        for (int i = 0; i < L - 1; i++)
        {
            for (int v = 0; v < N; v++)
            {
                auto p1 = parents[v][i];
                auto p2 = parents[p1.first][i];
                parents[v][i + 1] = pair(p2.first, p1.second + p2.second);
            }
        }

        done_initialized = true;
    }

    // vを始点にK回移動した先のノードを返します
    pair<int, T> step_forward(int v, unsigned long long k)
    {
        if (!done_initialized)
        {
            init();
        }

        T sum_cost = 0;
        while (k != 0)
        {
            int bit_i = countr_zero(k);
            sum_cost += parents[v][bit_i].second, v = parents[v][bit_i].first;
            k ^= 1ll << bit_i;
        }

        return pair(v, sum_cost);
    }

    vector<pair<int, T>> step_forwards(const vector<int> &indeces, unsigned long long k)
    {
        if (!done_initialized)
        {
            init();
        }

        vector<pair<int, T>> result(indeces.size());
        for (int i = 0; i < indeces.size(); i++)
        {
            result[i].first = indeces[i];
        }

        T sum_cost = 0;
        while (k != 0)
        {
            int bit_i = countr_zero(k);
            for (pair<int, T> &p : result)
            {
                p.second += parents[p.first][bit_i].second, p.first = parents[p.first][bit_i].first;
            }
            k ^= 1ll << bit_i;
        }

        return result;
    }

    vector<pair<int, T>> step_forwards(unsigned long long k)
    {
        vector<int> indeces;
        for (int i = 0; i < N; i++)
        {
            indeces.push_back(i);
        }

        return step_forwards(indeces, k);
    }
};

#line 1 "Tree/doubling.hpp"
#include <bits/stdc++.h>
using namespace std;

template <typename T = long long>
class Doubling
{
    int N, L;

    vector<pair<int, T>> nexts;
    vector<vector<pair<int, T>>> parents;
    bool done_initialized = false;

public:
    Doubling() {};

    Doubling(int N, unsigned long long max_k) : N(N)
    {
        L = max<int>(bit_width(max_k), 1);
        nexts = vector<pair<int, T>>(N, {-1, 0});
        parents = vector<vector<pair<int, T>>>(N + 1, vector<pair<int, T>>(L, {-1, 0}));
    }

    void add_edge(int from, int to, T cost)
    {
        if (nexts[from].first != -1)
        {
            assert(false);
        }

        nexts[from] = pair(to, cost);
    }

    void init()
    {
        for (int i = 0; i < N; i++)
        {
            parents[i][0] = nexts[i];
        }

        for (int i = 0; i < L - 1; i++)
        {
            for (int v = 0; v < N; v++)
            {
                auto p1 = parents[v][i];
                auto p2 = parents[p1.first][i];
                parents[v][i + 1] = pair(p2.first, p1.second + p2.second);
            }
        }

        done_initialized = true;
    }

    // vを始点にK回移動した先のノードを返します
    pair<int, T> step_forward(int v, unsigned long long k)
    {
        if (!done_initialized)
        {
            init();
        }

        T sum_cost = 0;
        while (k != 0)
        {
            int bit_i = countr_zero(k);
            sum_cost += parents[v][bit_i].second, v = parents[v][bit_i].first;
            k ^= 1ll << bit_i;
        }

        return pair(v, sum_cost);
    }

    vector<pair<int, T>> step_forwards(const vector<int> &indeces, unsigned long long k)
    {
        if (!done_initialized)
        {
            init();
        }

        vector<pair<int, T>> result(indeces.size());
        for (int i = 0; i < indeces.size(); i++)
        {
            result[i].first = indeces[i];
        }

        T sum_cost = 0;
        while (k != 0)
        {
            int bit_i = countr_zero(k);
            for (pair<int, T> &p : result)
            {
                p.second += parents[p.first][bit_i].second, p.first = parents[p.first][bit_i].first;
            }
            k ^= 1ll << bit_i;
        }

        return result;
    }

    vector<pair<int, T>> step_forwards(unsigned long long k)
    {
        vector<int> indeces;
        for (int i = 0; i < N; i++)
        {
            indeces.push_back(i);
        }

        return step_forwards(indeces, k);
    }
};