Struct ReRooting

Source

pub struct ReRooting<'a, M: Monoid, F: Fn(&M::T, usize, Option<usize>) -> M::T> {
    graph: &'a UndirectedSparseGraph,
    pub dp: Vec<M::T>,
    pub ep: Vec<M::T>,
    rooting: F,
}

Expand description

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§

§graph: &'a UndirectedSparseGraph§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

§rooting: F

rooting(data, vid, (Optional)eid): add root node(vid), result subtree is edge(eid)

Implementations§

Source §

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

Source

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)

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

Source

fn eidx(&self, u: usize, a: &Adjacency) -> usize

Examples found in repository ?

crates/competitive/src/tree/rerooting.rs (line 61)

59    fn dfs(&mut self, pa: &Adjacency, p: usize) {
60        let u = pa.to;
61        let pi = self.eidx(p, pa);
62        for a in self.graph.adjacencies(u).filter(|a| a.to != p) {
63            let i = self.eidx(u, a);
64            self.dfs(a, u);
65            self.ep[pi] = self.merge(&self.ep[pi], &self.ep[i]);
66        }
67        self.ep[pi] = self.add_subroot(&self.ep[pi], u, pa.id);
68    }
69    fn efs(&mut self, u: usize, p: usize) {
70        let m = self.graph.adjacencies(u).len();
71        let mut left = vec![M::unit(); m + 1];
72        let mut right = vec![M::unit(); m + 1];
73        for (k, a) in self.graph.adjacencies(u).enumerate() {
74            let i = self.eidx(u, a);
75            left[k + 1] = self.merge(&left[k], &self.ep[i]);
76        }
77        for (k, a) in self.graph.adjacencies(u).enumerate().rev() {
78            let i = self.eidx(u, a);
79            right[k] = self.merge(&right[k + 1], &self.ep[i]);
80        }
81        self.dp[u] = self.add_root(&left[m], u);
82        for (k, a) in self.graph.adjacencies(u).enumerate() {
83            if a.to != p {
84                let i = self.reidx(u, a);
85                self.ep[i] = self.merge(&left[k], &right[k + 1]);
86                self.ep[i] = self.add_subroot(&self.ep[i], u, a.id);
87                self.efs(a.to, u);
88            }
89        }
90    }

Source

fn reidx(&self, u: usize, a: &Adjacency) -> usize

Examples found in repository ?

crates/competitive/src/tree/rerooting.rs (line 84)

69    fn efs(&mut self, u: usize, p: usize) {
70        let m = self.graph.adjacencies(u).len();
71        let mut left = vec![M::unit(); m + 1];
72        let mut right = vec![M::unit(); m + 1];
73        for (k, a) in self.graph.adjacencies(u).enumerate() {
74            let i = self.eidx(u, a);
75            left[k + 1] = self.merge(&left[k], &self.ep[i]);
76        }
77        for (k, a) in self.graph.adjacencies(u).enumerate().rev() {
78            let i = self.eidx(u, a);
79            right[k] = self.merge(&right[k + 1], &self.ep[i]);
80        }
81        self.dp[u] = self.add_root(&left[m], u);
82        for (k, a) in self.graph.adjacencies(u).enumerate() {
83            if a.to != p {
84                let i = self.reidx(u, a);
85                self.ep[i] = self.merge(&left[k], &right[k + 1]);
86                self.ep[i] = self.add_subroot(&self.ep[i], u, a.id);
87                self.efs(a.to, u);
88            }
89        }
90    }

Source

fn merge(&self, x: &M::T, y: &M::T) -> M::T

Examples found in repository ?

crates/competitive/src/tree/rerooting.rs (line 65)

59    fn dfs(&mut self, pa: &Adjacency, p: usize) {
60        let u = pa.to;
61        let pi = self.eidx(p, pa);
62        for a in self.graph.adjacencies(u).filter(|a| a.to != p) {
63            let i = self.eidx(u, a);
64            self.dfs(a, u);
65            self.ep[pi] = self.merge(&self.ep[pi], &self.ep[i]);
66        }
67        self.ep[pi] = self.add_subroot(&self.ep[pi], u, pa.id);
68    }
69    fn efs(&mut self, u: usize, p: usize) {
70        let m = self.graph.adjacencies(u).len();
71        let mut left = vec![M::unit(); m + 1];
72        let mut right = vec![M::unit(); m + 1];
73        for (k, a) in self.graph.adjacencies(u).enumerate() {
74            let i = self.eidx(u, a);
75            left[k + 1] = self.merge(&left[k], &self.ep[i]);
76        }
77        for (k, a) in self.graph.adjacencies(u).enumerate().rev() {
78            let i = self.eidx(u, a);
79            right[k] = self.merge(&right[k + 1], &self.ep[i]);
80        }
81        self.dp[u] = self.add_root(&left[m], u);
82        for (k, a) in self.graph.adjacencies(u).enumerate() {
83            if a.to != p {
84                let i = self.reidx(u, a);
85                self.ep[i] = self.merge(&left[k], &right[k + 1]);
86                self.ep[i] = self.add_subroot(&self.ep[i], u, a.id);
87                self.efs(a.to, u);
88            }
89        }
90    }

Source

fn add_subroot(&self, x: &M::T, vid: usize, eid: usize) -> M::T

Examples found in repository ?

crates/competitive/src/tree/rerooting.rs (line 67)

59    fn dfs(&mut self, pa: &Adjacency, p: usize) {
60        let u = pa.to;
61        let pi = self.eidx(p, pa);
62        for a in self.graph.adjacencies(u).filter(|a| a.to != p) {
63            let i = self.eidx(u, a);
64            self.dfs(a, u);
65            self.ep[pi] = self.merge(&self.ep[pi], &self.ep[i]);
66        }
67        self.ep[pi] = self.add_subroot(&self.ep[pi], u, pa.id);
68    }
69    fn efs(&mut self, u: usize, p: usize) {
70        let m = self.graph.adjacencies(u).len();
71        let mut left = vec![M::unit(); m + 1];
72        let mut right = vec![M::unit(); m + 1];
73        for (k, a) in self.graph.adjacencies(u).enumerate() {
74            let i = self.eidx(u, a);
75            left[k + 1] = self.merge(&left[k], &self.ep[i]);
76        }
77        for (k, a) in self.graph.adjacencies(u).enumerate().rev() {
78            let i = self.eidx(u, a);
79            right[k] = self.merge(&right[k + 1], &self.ep[i]);
80        }
81        self.dp[u] = self.add_root(&left[m], u);
82        for (k, a) in self.graph.adjacencies(u).enumerate() {
83            if a.to != p {
84                let i = self.reidx(u, a);
85                self.ep[i] = self.merge(&left[k], &right[k + 1]);
86                self.ep[i] = self.add_subroot(&self.ep[i], u, a.id);
87                self.efs(a.to, u);
88            }
89        }
90    }

Source

fn add_root(&self, x: &M::T, vid: usize) -> M::T

Examples found in repository ?

crates/competitive/src/tree/rerooting.rs (line 81)

69    fn efs(&mut self, u: usize, p: usize) {
70        let m = self.graph.adjacencies(u).len();
71        let mut left = vec![M::unit(); m + 1];
72        let mut right = vec![M::unit(); m + 1];
73        for (k, a) in self.graph.adjacencies(u).enumerate() {
74            let i = self.eidx(u, a);
75            left[k + 1] = self.merge(&left[k], &self.ep[i]);
76        }
77        for (k, a) in self.graph.adjacencies(u).enumerate().rev() {
78            let i = self.eidx(u, a);
79            right[k] = self.merge(&right[k + 1], &self.ep[i]);
80        }
81        self.dp[u] = self.add_root(&left[m], u);
82        for (k, a) in self.graph.adjacencies(u).enumerate() {
83            if a.to != p {
84                let i = self.reidx(u, a);
85                self.ep[i] = self.merge(&left[k], &right[k + 1]);
86                self.ep[i] = self.add_subroot(&self.ep[i], u, a.id);
87                self.efs(a.to, u);
88            }
89        }
90    }

Source

fn dfs(&mut self, pa: &Adjacency, p: usize)

Examples found in repository ?

crates/competitive/src/tree/rerooting.rs (line 64)

59    fn dfs(&mut self, pa: &Adjacency, p: usize) {
60        let u = pa.to;
61        let pi = self.eidx(p, pa);
62        for a in self.graph.adjacencies(u).filter(|a| a.to != p) {
63            let i = self.eidx(u, a);
64            self.dfs(a, u);
65            self.ep[pi] = self.merge(&self.ep[pi], &self.ep[i]);
66        }
67        self.ep[pi] = self.add_subroot(&self.ep[pi], u, pa.id);
68    }
69    fn efs(&mut self, u: usize, p: usize) {
70        let m = self.graph.adjacencies(u).len();
71        let mut left = vec![M::unit(); m + 1];
72        let mut right = vec![M::unit(); m + 1];
73        for (k, a) in self.graph.adjacencies(u).enumerate() {
74            let i = self.eidx(u, a);
75            left[k + 1] = self.merge(&left[k], &self.ep[i]);
76        }
77        for (k, a) in self.graph.adjacencies(u).enumerate().rev() {
78            let i = self.eidx(u, a);
79            right[k] = self.merge(&right[k + 1], &self.ep[i]);
80        }
81        self.dp[u] = self.add_root(&left[m], u);
82        for (k, a) in self.graph.adjacencies(u).enumerate() {
83            if a.to != p {
84                let i = self.reidx(u, a);
85                self.ep[i] = self.merge(&left[k], &right[k + 1]);
86                self.ep[i] = self.add_subroot(&self.ep[i], u, a.id);
87                self.efs(a.to, u);
88            }
89        }
90    }
91    fn rerooting(&mut self) {
92        for a in self.graph.adjacencies(0) {
93            self.dfs(a, 0);
94        }
95        self.efs(0, usize::MAX);
96    }

Source

fn efs(&mut self, u: usize, p: usize)

Examples found in repository ?

crates/competitive/src/tree/rerooting.rs (line 87)

69    fn efs(&mut self, u: usize, p: usize) {
70        let m = self.graph.adjacencies(u).len();
71        let mut left = vec![M::unit(); m + 1];
72        let mut right = vec![M::unit(); m + 1];
73        for (k, a) in self.graph.adjacencies(u).enumerate() {
74            let i = self.eidx(u, a);
75            left[k + 1] = self.merge(&left[k], &self.ep[i]);
76        }
77        for (k, a) in self.graph.adjacencies(u).enumerate().rev() {
78            let i = self.eidx(u, a);
79            right[k] = self.merge(&right[k + 1], &self.ep[i]);
80        }
81        self.dp[u] = self.add_root(&left[m], u);
82        for (k, a) in self.graph.adjacencies(u).enumerate() {
83            if a.to != p {
84                let i = self.reidx(u, a);
85                self.ep[i] = self.merge(&left[k], &right[k + 1]);
86                self.ep[i] = self.add_subroot(&self.ep[i], u, a.id);
87                self.efs(a.to, u);
88            }
89        }
90    }
91    fn rerooting(&mut self) {
92        for a in self.graph.adjacencies(0) {
93            self.dfs(a, 0);
94        }
95        self.efs(0, usize::MAX);
96    }

Source

fn rerooting(&mut self)

Examples found in repository ?

crates/competitive/src/tree/rerooting.rs (line 36)

27    pub fn new(graph: &'a UndirectedSparseGraph, rooting: F) -> Self {
28        let dp = vec![M::unit(); graph.vertices_size()];
29        let ep = vec![M::unit(); graph.vertices_size() * 2];
30        let mut self_ = Self {
31            graph,
32            dp,
33            ep,
34            rooting,
35        };
36        self_.rerooting();
37        self_
38    }

Trait Implementations§

Source §

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,

Source §

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

Returns a duplicate of the value. Read more

1.0.0 · Source§

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

Performs copy-assignment from source. Read more

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,

Source §

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

Formats the value using the given formatter. Read more

Auto Trait Implementations§

§

impl<'a, M, F> Freeze for ReRooting<'a, M, F>
where F: Freeze,

§

impl<'a, M, F> RefUnwindSafe for ReRooting<'a, M, F>
where F: RefUnwindSafe, <M as Magma>::T: RefUnwindSafe,

§

impl<'a, M, F> Send for ReRooting<'a, M, F>
where F: Send, <M as Magma>::T: Send,

§

impl<'a, M, F> Sync for ReRooting<'a, M, F>
where F: Sync, <M as Magma>::T: Sync,

§

impl<'a, M, F> Unpin for ReRooting<'a, M, F>
where F: Unpin, <M as Magma>::T: Unpin,

§

impl<'a, M, F> UnwindSafe for ReRooting<'a, M, F>
where F: UnwindSafe, <M as Magma>::T: UnwindSafe,

Blanket Implementations§

Source §

impl<T> Any for T
where T: 'static + ?Sized,

Source §

fn type_id(&self) -> TypeId

Gets the TypeId of self. Read more

Source §

impl<T> Borrow<T> for T
where T: ?Sized,

Source §

fn borrow(&self) -> &T

Immutably borrows from an owned value. Read more

Source §

impl<T> BorrowMut<T> for T
where T: ?Sized,

Source §

fn borrow_mut(&mut self) -> &mut T

Mutably borrows from an owned value. Read more

Source §

impl<T> CloneToUninit for T
where T: Clone,

Source §

unsafe fn clone_to_uninit(&self, dest: *mut u8)

🔬This is a nightly-only experimental API. (clone_to_uninit)

Performs copy-assignment from self to dest. Read more

Source §

impl<T> From<T> for T

Source §

fn from(t: T) -> T

Returns the argument unchanged.

Source §

impl<T, U> Into for T
where U: From<T>,

Source §

fn into(self) -> U

Calls U::from(self).

That is, this conversion is whatever the implementation of From<T> for U chooses to do.

Source §

impl<T> ToOwned for T
where T: Clone,

Source §

type Owned = T

The resulting type after obtaining ownership.

Source §

fn to_owned(&self) -> T

Creates owned data from borrowed data, usually by cloning. Read more

Source §

fn clone_into(&self, target: &mut T)

Uses borrowed data to replace owned data, usually by cloning. Read more

Source §

impl<T, U> TryFrom for T
where U: Into<T>,

Source §

type Error = Infallible

The type returned in the event of a conversion error.

Source §

fn try_from(value: U) -> Result<T, <T as TryFrom>::Error>

Performs the conversion.

Source §

impl<T, U> TryInto for T
where U: TryFrom<T>,

Source §

type Error = >::Error

The type returned in the event of a conversion error.

Source §

fn try_into(self) -> Result<U, >::Error>

Performs the conversion.

Struct ReRooting Copy item path

Fields§

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

fn eidx(&self, u: usize, a: &Adjacency) -> usize

fn reidx(&self, u: usize, a: &Adjacency) -> usize

fn merge(&self, x: &M::T, y: &M::T) -> M::T

fn add_subroot(&self, x: &M::T, vid: usize, eid: usize) -> M::T

fn add_root(&self, x: &M::T, vid: usize) -> M::T

fn dfs(&mut self, pa: &Adjacency, p: usize)

fn efs(&mut self, u: usize, p: usize)

fn rerooting(&mut self)

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>

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

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

Auto Trait Implementations§

impl<'a, M, F> Freeze for ReRooting<'a, M, F>where F: Freeze,

impl<'a, M, F> RefUnwindSafe for ReRooting<'a, M, F>where F: RefUnwindSafe, <M as Magma>::T: RefUnwindSafe,

impl<'a, M, F> Send for ReRooting<'a, M, F>where F: Send, <M as Magma>::T: Send,

impl<'a, M, F> Sync for ReRooting<'a, M, F>where F: Sync, <M as Magma>::T: Sync,

impl<'a, M, F> Unpin for ReRooting<'a, M, F>where F: Unpin, <M as Magma>::T: Unpin,

impl<'a, M, F> UnwindSafe for ReRooting<'a, M, F>where F: UnwindSafe, <M as Magma>::T: UnwindSafe,

Blanket Implementations§

impl<T> Any for Twhere T: 'static + ?Sized,

fn type_id(&self) -> TypeId

impl<T> Borrow<T> for Twhere T: ?Sized,

fn borrow(&self) -> &T

impl<T> BorrowMut<T> for Twhere T: ?Sized,

fn borrow_mut(&mut self) -> &mut T

impl<T> CloneToUninit for Twhere T: Clone,

unsafe fn clone_to_uninit(&self, dest: *mut u8)

impl<T> From<T> for T

fn from(t: T) -> T

impl<T, U> Into<U> for Twhere U: From<T>,

fn into(self) -> U

impl<T> ToOwned for Twhere T: Clone,

type Owned = T

fn to_owned(&self) -> T

fn clone_into(&self, target: &mut T)

impl<T, U> TryFrom<U> for Twhere U: Into<T>,

type Error = Infallible

fn try_from(value: U) -> Result<T, <T as TryFrom<U>>::Error>

impl<T, U> TryInto<U> for Twhere U: TryFrom<T>,

type Error = <U as TryFrom<T>>::Error

fn try_into(self) -> Result<U, <U as TryFrom<T>>::Error>

Struct ReRooting

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

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,

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,

impl<'a, M, F> Freeze for ReRooting<'a, M, F>
where F: Freeze,

impl<'a, M, F> RefUnwindSafe for ReRooting<'a, M, F>
where F: RefUnwindSafe, <M as Magma>::T: RefUnwindSafe,

impl<'a, M, F> Send for ReRooting<'a, M, F>
where F: Send, <M as Magma>::T: Send,

impl<'a, M, F> Sync for ReRooting<'a, M, F>
where F: Sync, <M as Magma>::T: Sync,

impl<'a, M, F> Unpin for ReRooting<'a, M, F>
where F: Unpin, <M as Magma>::T: Unpin,

impl<'a, M, F> UnwindSafe for ReRooting<'a, M, F>
where F: UnwindSafe, <M as Magma>::T: UnwindSafe,

impl<T> Any for T
where T: 'static + ?Sized,

impl<T> Borrow<T> for T
where T: ?Sized,

impl<T> BorrowMut<T> for T
where T: ?Sized,

impl<T> CloneToUninit for T
where T: Clone,

impl<T, U> Into<U> for T
where U: From<T>,

impl<T> ToOwned for T
where T: Clone,

impl<T, U> TryFrom<U> for T
where U: Into<T>,

impl<T, U> TryInto<U> for T
where U: TryFrom<T>,