Struct cp_library_rs::graph::dynamic_rerooting::Rerooting

pub struct Rerooting<T, M, FE, FV>where
    T: Clone,
    M: Fn(&T, &T) -> T,
    FE: Fn(&T, usize) -> T,
    FV: Fn(&T, usize) -> T,{
    pub dp: Vec<Vec<T>>,
    pub ans: Vec<T>,
    pub G: Vec<Vec<usize>>,
    pub edge_id: HashMap<(usize, usize), (usize, usize)>,
    /* private fields */
}

全方位木DP

Fields

dp: Vec<Vec<T>>

dpテーブル

ans: Vec<T>

結果を保存する配列

G: Vec<Vec<usize>>

グラフ

edge_id: HashMap<(usize, usize), (usize, usize)>

辺の番号: (u, v) -> (辺番号, G[u].index(v))

Implementations

impl<T, M, FE, FV> Rerooting<T, M, FE, FV>where T: Clone, M: Fn(&T, &T) -> T, FE: Fn(&T, usize) -> T, FV: Fn(&T, usize) -> T,

pub fn new(N: usize, id: T, merge: M, put_edge: FE, put_vertex: FV) -> Self

木を初期化する

• 時間計算量: $O(N)$

引数

• N: 頂点数
• id: 単位元
• merge: 値をマージする関数
• put_edge: 辺を追加する関数
• put_vertex: 頂点を追加する関数

pub fn add_edge(&mut self, u: usize, v: usize)

有向辺 (u,v) を追加する

• 時間計算量: $O(1)$

pub fn add_edge2(&mut self, u: usize, v: usize)

有向辺 (u,v) / (v,u) を追加する

• 時間計算量: $O(1)$

pub fn build(&mut self)

すべての頂点vについて，vを根として集約した値を求める

• 時間計算量: $O(N)$

pub fn aggregate(&mut self, p: usize, u: usize) -> T

頂点uに対して値を集約する

• 時間計算量: $O(N)$

pub fn reroot(&mut self, p: usize, u: usize)

rerootingを行う

• 時間計算量: $O(N)$

引数

• p: 親の頂点
• u: 現在の頂点