Skip to main content

StaticTopTreeDp

competitive::tree::static_top_tree

Struct StaticTopTreeDp 

Source 
pub struct StaticTopTreeDp<'a, C>
where
    C: Cluster,
{
    tree: &'a StaticTopTree,
    vertices: Vec<<C as Cluster>::Vertex>,
    edges: Vec<<C as Cluster>::Edge>,
    compressed: Vec<InnerValue<<C as Cluster>::Path>>,
    raked: Vec<InnerValue<<C as Cluster>::Point>>,
    light_points: Vec<<C as Cluster>::Point>,
    all_point: <C as Cluster>::Point,
}

Fields§

§tree: &'a StaticTopTree§vertices: Vec<<C as Cluster>::Vertex>§edges: Vec<<C as Cluster>::Edge>§compressed: Vec<InnerValue<<C as Cluster>::Path>>§raked: Vec<InnerValue<<C as Cluster>::Point>>§light_points: Vec<<C as Cluster>::Point>§all_point: <C as Cluster>::Point

Implementations§

Source§

impl<'a, C> StaticTopTreeDp<'a, C>
where C: Cluster,

Source

pub fn new( tree: &'a StaticTopTree, vertices: Vec<<C as Cluster>::Vertex>, edges: Vec<<C as Cluster>::Edge>, ) -> Self

Examples found in repository?
crates/competitive/src/tree/static_top_tree.rs (line 276)
268    pub fn dp<C>(
269        &self,
270        vertices: Vec<<C as Cluster>::Vertex>,
271        edges: Vec<<C as Cluster>::Edge>,
272    ) -> StaticTopTreeDp<'_, C>
273    where
274        C: Cluster,
275    {
276        StaticTopTreeDp::new(self, vertices, edges)
277    }
Source

pub fn get_vertex(&self, vertex: usize) -> &<C as Cluster>::Vertex

Source

pub fn apply_vertex<F>(&mut self, vertex: usize, f: F)
where F: FnOnce(&mut <C as Cluster>::Vertex),

Examples found in repository?
crates/competitive/src/tree/static_top_tree.rs (line 591)
590    pub fn set_vertex(&mut self, vertex: usize, value: <C as Cluster>::Vertex) {
591        self.apply_vertex(vertex, |x| *x = value);
592    }
Source

pub fn set_vertex(&mut self, vertex: usize, value: <C as Cluster>::Vertex)

Examples found in repository?
crates/library_checker/src/tree/point_set_tree_path_composite_sum_fixed_root.rs (line 117)
103pub fn point_set_tree_path_composite_sum_fixed_root(reader: impl Read, writer: impl Write) {
104    prepare_io!(reader, writer);
105    sc!(n,
106        q,
107        value: [M; n],
108        (graph, edges): @TreeGraphScanner::<usize, (M, M)>::new(n));
109
110    let top_tree = graph.static_top_tree(0);
111    let mut dp = top_tree.dp::<Dp>(value, edges);
112
113    for _ in 0..q {
114        sc!(query: Query);
115        match query {
116            Query::SetVertex { v, x } => {
117                dp.set_vertex(v, x);
118                pp!(dp.fold_all().sum);
119            }
120            Query::SetEdge { e, a, b } => {
121                dp.set_edge(e, (a, b));
122                pp!(dp.fold_all().sum);
123            }
124        }
125    }
126}
More examples
Hide additional examples
crates/library_checker/src/tree/point_set_tree_path_composite_sum.rs (line 151)
137pub fn point_set_tree_path_composite_sum(reader: impl Read, writer: impl Write) {
138    prepare_io!(reader, writer);
139    sc!(n,
140        q,
141        value: [M; n],
142        (graph, edges): @TreeGraphScanner::<usize, (M, M)>::new(n));
143
144    let top_tree = graph.static_top_tree(0);
145    let mut dp = top_tree.dp::<Dp>(value, edges);
146
147    for _ in 0..q {
148        sc!(query: Query);
149        match query {
150            Query::SetVertex { v, x, r } => {
151                dp.set_vertex(v, x);
152                pp!(dp.fold_path(r).reverse.sum);
153            }
154            Query::SetEdge { e, a, b, r } => {
155                dp.set_edge(e, (a, b));
156                pp!(dp.fold_path(r).reverse.sum);
157            }
158        }
159    }
160}
Source

pub fn get_edge(&self, edge: usize) -> &<C as Cluster>::Edge

Source

pub fn apply_edge<F>(&mut self, edge: usize, f: F)
where F: FnOnce(&mut <C as Cluster>::Edge),

Examples found in repository?
crates/competitive/src/tree/static_top_tree.rs (line 608)
607    pub fn set_edge(&mut self, edge: usize, value: <C as Cluster>::Edge) {
608        self.apply_edge(edge, |x| *x = value);
609    }
Source

pub fn set_edge(&mut self, edge: usize, value: <C as Cluster>::Edge)

Examples found in repository?
crates/library_checker/src/tree/point_set_tree_path_composite_sum_fixed_root.rs (line 121)
103pub fn point_set_tree_path_composite_sum_fixed_root(reader: impl Read, writer: impl Write) {
104    prepare_io!(reader, writer);
105    sc!(n,
106        q,
107        value: [M; n],
108        (graph, edges): @TreeGraphScanner::<usize, (M, M)>::new(n));
109
110    let top_tree = graph.static_top_tree(0);
111    let mut dp = top_tree.dp::<Dp>(value, edges);
112
113    for _ in 0..q {
114        sc!(query: Query);
115        match query {
116            Query::SetVertex { v, x } => {
117                dp.set_vertex(v, x);
118                pp!(dp.fold_all().sum);
119            }
120            Query::SetEdge { e, a, b } => {
121                dp.set_edge(e, (a, b));
122                pp!(dp.fold_all().sum);
123            }
124        }
125    }
126}
More examples
Hide additional examples
crates/library_checker/src/tree/point_set_tree_path_composite_sum.rs (line 155)
137pub fn point_set_tree_path_composite_sum(reader: impl Read, writer: impl Write) {
138    prepare_io!(reader, writer);
139    sc!(n,
140        q,
141        value: [M; n],
142        (graph, edges): @TreeGraphScanner::<usize, (M, M)>::new(n));
143
144    let top_tree = graph.static_top_tree(0);
145    let mut dp = top_tree.dp::<Dp>(value, edges);
146
147    for _ in 0..q {
148        sc!(query: Query);
149        match query {
150            Query::SetVertex { v, x, r } => {
151                dp.set_vertex(v, x);
152                pp!(dp.fold_path(r).reverse.sum);
153            }
154            Query::SetEdge { e, a, b, r } => {
155                dp.set_edge(e, (a, b));
156                pp!(dp.fold_path(r).reverse.sum);
157            }
158        }
159    }
160}
Source

pub fn fold_all(&self) -> &<C as Cluster>::Point

Examples found in repository?
crates/library_checker/src/tree/point_set_tree_path_composite_sum_fixed_root.rs (line 118)
103pub fn point_set_tree_path_composite_sum_fixed_root(reader: impl Read, writer: impl Write) {
104    prepare_io!(reader, writer);
105    sc!(n,
106        q,
107        value: [M; n],
108        (graph, edges): @TreeGraphScanner::<usize, (M, M)>::new(n));
109
110    let top_tree = graph.static_top_tree(0);
111    let mut dp = top_tree.dp::<Dp>(value, edges);
112
113    for _ in 0..q {
114        sc!(query: Query);
115        match query {
116            Query::SetVertex { v, x } => {
117                dp.set_vertex(v, x);
118                pp!(dp.fold_all().sum);
119            }
120            Query::SetEdge { e, a, b } => {
121                dp.set_edge(e, (a, b));
122                pp!(dp.fold_all().sum);
123            }
124        }
125    }
126}
Source

pub fn fold_path(&self, vertex: usize) -> <C as Cluster>::Path

Examples found in repository?
crates/library_checker/src/tree/point_set_tree_path_composite_sum.rs (line 152)
137pub fn point_set_tree_path_composite_sum(reader: impl Read, writer: impl Write) {
138    prepare_io!(reader, writer);
139    sc!(n,
140        q,
141        value: [M; n],
142        (graph, edges): @TreeGraphScanner::<usize, (M, M)>::new(n));
143
144    let top_tree = graph.static_top_tree(0);
145    let mut dp = top_tree.dp::<Dp>(value, edges);
146
147    for _ in 0..q {
148        sc!(query: Query);
149        match query {
150            Query::SetVertex { v, x, r } => {
151                dp.set_vertex(v, x);
152                pp!(dp.fold_path(r).reverse.sum);
153            }
154            Query::SetEdge { e, a, b, r } => {
155                dp.set_edge(e, (a, b));
156                pp!(dp.fold_path(r).reverse.sum);
157            }
158        }
159    }
160}
Source

fn update_from_vertex(&mut self, vertex: usize)

Examples found in repository?
crates/competitive/src/tree/static_top_tree.rs (line 587)
581    pub fn apply_vertex<F>(&mut self, vertex: usize, f: F)
582    where
583        F: FnOnce(&mut <C as Cluster>::Vertex),
584    {
585        assert!(vertex < self.vertices.len());
586        f(&mut self.vertices[vertex]);
587        self.update_from_vertex(vertex);
588    }
589
590    pub fn set_vertex(&mut self, vertex: usize, value: <C as Cluster>::Vertex) {
591        self.apply_vertex(vertex, |x| *x = value);
592    }
593
594    pub fn get_edge(&self, edge: usize) -> &<C as Cluster>::Edge {
595        &self.edges[edge]
596    }
597
598    pub fn apply_edge<F>(&mut self, edge: usize, f: F)
599    where
600        F: FnOnce(&mut <C as Cluster>::Edge),
601    {
602        assert!(edge < self.edges.len());
603        f(&mut self.edges[edge]);
604        self.update_from_vertex(self.tree.edge_child[edge]);
605    }
Source

fn update_compress( &mut self, id: usize, path: <C as Cluster>::Path, ) -> <C as Cluster>::Path

Examples found in repository?
crates/competitive/src/tree/static_top_tree.rs (line 671)
662    fn update_from_vertex(&mut self, mut vertex: usize) {
663        assert!(vertex < self.tree.n);
664        while vertex != usize::MAX {
665            let links = self.tree.vertex_links[vertex];
666            let base = C::add_vertex(
667                &self.light_points[vertex],
668                &self.vertices[vertex],
669                self.tree.parent_edge_ref(&self.edges, vertex),
670            );
671            let path = self.update_compress(links.compress_parent, base);
672            let point = C::add_edge(&path);
673            let point = self.update_rake(links.rake_parent, point);
674            if links.heavy_parent == usize::MAX {
675                self.all_point = point;
676            } else {
677                self.light_points[links.heavy_parent] = point;
678            }
679            vertex = links.heavy_parent;
680        }
681    }
Source

fn update_rake( &mut self, id: usize, point: <C as Cluster>::Point, ) -> <C as Cluster>::Point

Examples found in repository?
crates/competitive/src/tree/static_top_tree.rs (line 673)
662    fn update_from_vertex(&mut self, mut vertex: usize) {
663        assert!(vertex < self.tree.n);
664        while vertex != usize::MAX {
665            let links = self.tree.vertex_links[vertex];
666            let base = C::add_vertex(
667                &self.light_points[vertex],
668                &self.vertices[vertex],
669                self.tree.parent_edge_ref(&self.edges, vertex),
670            );
671            let path = self.update_compress(links.compress_parent, base);
672            let point = C::add_edge(&path);
673            let point = self.update_rake(links.rake_parent, point);
674            if links.heavy_parent == usize::MAX {
675                self.all_point = point;
676            } else {
677                self.light_points[links.heavy_parent] = point;
678            }
679            vertex = links.heavy_parent;
680        }
681    }

Auto Trait Implementations§

§

impl<'a, C> Freeze for StaticTopTreeDp<'a, C>
where Vec<<C as Cluster>::Vertex>: Freeze, Vec<<C as Cluster>::Edge>: Freeze, Vec<InnerValue<<C as Cluster>::Path>>: Freeze, Vec<InnerValue<<C as Cluster>::Point>>: Freeze, Vec<<C as Cluster>::Point>: Freeze, <C as Cluster>::Point: Freeze,

§

impl<'a, C> RefUnwindSafe for StaticTopTreeDp<'a, C>
where Vec<<C as Cluster>::Vertex>: RefUnwindSafe, Vec<<C as Cluster>::Edge>: RefUnwindSafe, Vec<InnerValue<<C as Cluster>::Path>>: RefUnwindSafe, Vec<InnerValue<<C as Cluster>::Point>>: RefUnwindSafe, Vec<<C as Cluster>::Point>: RefUnwindSafe, <C as Cluster>::Point: RefUnwindSafe,

§

impl<'a, C> Send for StaticTopTreeDp<'a, C>
where Vec<<C as Cluster>::Vertex>: Send, Vec<<C as Cluster>::Edge>: Send, Vec<InnerValue<<C as Cluster>::Path>>: Send, Vec<InnerValue<<C as Cluster>::Point>>: Send, Vec<<C as Cluster>::Point>: Send, <C as Cluster>::Point: Send,

§

impl<'a, C> Sync for StaticTopTreeDp<'a, C>
where Vec<<C as Cluster>::Vertex>: Sync, Vec<<C as Cluster>::Edge>: Sync, Vec<InnerValue<<C as Cluster>::Path>>: Sync, Vec<InnerValue<<C as Cluster>::Point>>: Sync, Vec<<C as Cluster>::Point>: Sync, <C as Cluster>::Point: Sync,

§

impl<'a, C> Unpin for StaticTopTreeDp<'a, C>
where Vec<<C as Cluster>::Vertex>: Unpin, Vec<<C as Cluster>::Edge>: Unpin, Vec<InnerValue<<C as Cluster>::Path>>: Unpin, Vec<InnerValue<<C as Cluster>::Point>>: Unpin, Vec<<C as Cluster>::Point>: Unpin, <C as Cluster>::Point: Unpin,

§

impl<'a, C> UnsafeUnpin for StaticTopTreeDp<'a, C>
where Vec<<C as Cluster>::Vertex>: UnsafeUnpin, Vec<<C as Cluster>::Edge>: UnsafeUnpin, Vec<InnerValue<<C as Cluster>::Path>>: UnsafeUnpin, Vec<InnerValue<<C as Cluster>::Point>>: UnsafeUnpin, Vec<<C as Cluster>::Point>: UnsafeUnpin, <C as Cluster>::Point: UnsafeUnpin,

§

impl<'a, C> UnwindSafe for StaticTopTreeDp<'a, C>
where Vec<<C as Cluster>::Vertex>: UnwindSafe, Vec<<C as Cluster>::Edge>: UnwindSafe, Vec<InnerValue<<C as Cluster>::Path>>: UnwindSafe, Vec<InnerValue<<C as Cluster>::Point>>: UnwindSafe, Vec<<C as Cluster>::Point>: UnwindSafe, <C as Cluster>::Point: 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> From<T> for T

Source§

fn from(t: T) -> T

Returns the argument unchanged.

Source§

impl<T, U> Into<U> 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> ToArrayVecScalar for T

Source§

fn to_array_vec_scalar(self) -> ArrayVecScalar<T>

Source§

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

Source§

type Error = !

The type returned in the event of a conversion error.
Source§

fn try_from(value: U) -> Result<T, !>

Performs the conversion.
Source§

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

Source§

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

The type returned in the event of a conversion error.
Source§

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

Performs the conversion.