Struct cp_library_rs::graph::rerooting::Rerooting

pub struct Rerooting<M: TreeMonoid> {
    pub dp: Vec<Vec<M::T>>,
    pub ans: Vec<M::T>,
    pub G: Graph<M::W>,
}

全方位木DP

Fields

dp: Vec<Vec<M::T>>

dpテーブル

ans: Vec<M::T>

結果を保存する配列

G: Graph<M::W>

グラフ

Implementations

impl<M: TreeMonoid> Rerooting<M>

pub fn new(N: usize) -> Self

木を初期化する

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

重みwの有向辺 (u,v) を追加する

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

重みwの有向辺 (u,v) / (v,u) を追加する

pub fn build(&mut self)

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

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

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

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

rerootingを行う （実際にはdfsで処理）