Rerooting
クラス · 全方位木dp
template <class M, weighted_graph_type G, class U>
requires rerooting_monoid<M, graph_weight_t<G>, U>
struct Rerooting;
概要
全方位木dp
非連結（森）にも対応する。各連結成分をそれぞれ独立に処理する。 集約型 value_type と確定値型 key_type（省略時 value_type）を区別でき、 operator[] は確定値型を返す。
テンプレートパラメータ
| 名前 | 説明 |
|---|---|
M |
全方位木dp用モノイド（rerooting_monoid） |
G |
重み付きグラフ型（list_graph<T> / csr_graph<T> のいずれでも可） |
U |
頂点データの型 |
計算量
- 構築は $O(V + E)$、結果の参照とイテレータ取得は $O(1)$
構築・破棄
| 名前 | 説明 | 計算量 |
|---|---|---|
(constructor) |
グラフ g と各頂点のデータ v から全ての根に対する DP 値を計算する |
$O(V + E)$ |
メンバ関数
| 名前 | 説明 | 計算量 |
|---|---|---|
begin |
(1) 結果列の先頭を指す読み取り専用イテレータを返す (2) 結果列の先頭を指すイテレータを返す |
$O(1)$ |
end |
(1) 結果列の終端を指す読み取り専用イテレータを返す (2) 結果列の終端を指すイテレータを返す |
$O(1)$ |
演算子
| 名前 | 説明 | 計算量 |
|---|---|---|
operator[] |
(1) 頂点 i を根とした結果を読み取り専用で返す(2) 頂点 i を根とした結果を返す |
$O(1)$ |
メンバの詳細
begin
// (1)
const auto begin() const;
// (2)
auto begin();
(1) 結果列の先頭を指す読み取り専用イテレータを返す
- 計算量: $O(1)$
(2) 結果列の先頭を指すイテレータを返す
- 計算量: $O(1)$
end
// (1)
const auto end() const;
// (2)
auto end();
(1) 結果列の終端を指す読み取り専用イテレータを返す
- 計算量: $O(1)$
(2) 結果列の終端を指すイテレータを返す
- 計算量: $O(1)$
operator[]
// (1)
const auto &operator[](int i) const;
// (2)
auto &operator[](int i);
(1) 頂点 i を根とした結果を読み取り専用で返す
- 計算量: $O(1)$
(2) 頂点 i を根とした結果を返す
- 計算量: $O(1)$
関連項目
rerooting_key— 全方位木dp用モノイドの確定値型（key_type、省略時はvalue_type）rerooting_key_t— 全方位木 DP の確定値型rerooting_monoid— 全方位木dp用モノイドの要件