Struct ReRooting

pub struct ReRooting<'a, M: Monoid, F: Fn(&M::T, usize, Option<usize>) -> M::T> {
    pub dp: Vec<M::T>,
    pub ep: Vec<M::T>,
    /* private fields */
}

dynamic programming on all-rooted trees

caluculate all subtrees (hanging on the edge) in specific ordering, each subtree calculated in the order of merge and rooting

Fields

dp: Vec<M::T>

dp[v]: result of v-rooted tree

ep: Vec<M::T>

ep[e]: result of e-subtree, if e >= n then reversed-e-subtree

Implementations

impl<'a, M, F> ReRooting<'a, M, F>

where M: Monoid, F: Fn(&M::T, usize, Option<usize>) -> M::T,

pub fn new(graph: &'a UndirectedSparseGraph, rooting: F) -> Self

Examples found in repository

crates/aizu_online_judge/src/grl/grl_5_b.rs (lines 10-12)

pub fn grl_5_b(reader: impl Read, mut writer: impl Write) {
    let s = read_all_unchecked(reader);
    let mut scanner = Scanner::new(&s);
    scan!(scanner, n, (graph, w): @TreeGraphScanner::<usize, u64>::new(n));
    let re = ReRooting::<MaxOperation<u64>, _>::new(&graph, |d, _vid, eid_opt| {
        d + eid_opt.map_or(0, |eid| w[eid])
    });
    iter_print!(writer, @sep '\n', @it re.dp);
}

Trait Implementations

impl<'a, M: Clone + Monoid, F: Clone + Fn(&M::T, usize, Option<usize>) -> M::T> Clone for ReRooting<'a, M, F>

where M::T: Clone,

fn clone(&self) -> ReRooting<'a, M, F>

Returns a duplicate of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl<'a, M: Debug + Monoid, F: Debug + Fn(&M::T, usize, Option<usize>) -> M::T> Debug for ReRooting<'a, M, F>

where M::T: Debug,

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.