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 275)
267    pub fn dp<C>(
268        &self,
269        vertices: Vec<<C as Cluster>::Vertex>,
270        edges: Vec<<C as Cluster>::Edge>,
271    ) -> StaticTopTreeDp<'_, C>
272    where
273        C: Cluster,
274    {
275        StaticTopTreeDp::new(self, vertices, edges)
276    }
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 124)
106pub fn point_set_tree_path_composite_sum_fixed_root(reader: impl Read, mut writer: impl Write) {
107    let s = read_all_unchecked(reader);
108    let mut scanner = Scanner::new(&s);
109    scan!(
110        scanner,
111        n,
112        q,
113        value: [MInt; n],
114        (graph, edges): @TreeGraphScanner::<usize, (MInt, MInt)>::new(n)
115    );
116
117    let top_tree = graph.static_top_tree(0);
118    let mut dp = top_tree.dp::<Dp>(value, edges);
119
120    for _ in 0..q {
121        scan!(scanner, query: Query);
122        match query {
123            Query::SetVertex { v, x } => {
124                dp.set_vertex(v, x);
125                writeln!(writer, "{}", dp.fold_all().sum).ok();
126            }
127            Query::SetEdge { e, a, b } => {
128                dp.set_edge(e, (a, b));
129                writeln!(writer, "{}", dp.fold_all().sum).ok();
130            }
131        }
132    }
133}
More examples
Hide additional examples
crates/library_checker/src/tree/point_set_tree_path_composite_sum.rs (line 158)
140pub fn point_set_tree_path_composite_sum(reader: impl Read, mut writer: impl Write) {
141    let s = read_all_unchecked(reader);
142    let mut scanner = Scanner::new(&s);
143    scan!(
144        scanner,
145        n,
146        q,
147        value: [MInt; n],
148        (graph, edges): @TreeGraphScanner::<usize, (MInt, MInt)>::new(n)
149    );
150
151    let top_tree = graph.static_top_tree(0);
152    let mut dp = top_tree.dp::<Dp>(value, edges);
153
154    for _ in 0..q {
155        scan!(scanner, query: Query);
156        match query {
157            Query::SetVertex { v, x, r } => {
158                dp.set_vertex(v, x);
159                writeln!(writer, "{}", dp.fold_path(r).reverse.sum).ok();
160            }
161            Query::SetEdge { e, a, b, r } => {
162                dp.set_edge(e, (a, b));
163                writeln!(writer, "{}", dp.fold_path(r).reverse.sum).ok();
164            }
165        }
166    }
167}
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 128)
106pub fn point_set_tree_path_composite_sum_fixed_root(reader: impl Read, mut writer: impl Write) {
107    let s = read_all_unchecked(reader);
108    let mut scanner = Scanner::new(&s);
109    scan!(
110        scanner,
111        n,
112        q,
113        value: [MInt; n],
114        (graph, edges): @TreeGraphScanner::<usize, (MInt, MInt)>::new(n)
115    );
116
117    let top_tree = graph.static_top_tree(0);
118    let mut dp = top_tree.dp::<Dp>(value, edges);
119
120    for _ in 0..q {
121        scan!(scanner, query: Query);
122        match query {
123            Query::SetVertex { v, x } => {
124                dp.set_vertex(v, x);
125                writeln!(writer, "{}", dp.fold_all().sum).ok();
126            }
127            Query::SetEdge { e, a, b } => {
128                dp.set_edge(e, (a, b));
129                writeln!(writer, "{}", dp.fold_all().sum).ok();
130            }
131        }
132    }
133}
More examples
Hide additional examples
crates/library_checker/src/tree/point_set_tree_path_composite_sum.rs (line 162)
140pub fn point_set_tree_path_composite_sum(reader: impl Read, mut writer: impl Write) {
141    let s = read_all_unchecked(reader);
142    let mut scanner = Scanner::new(&s);
143    scan!(
144        scanner,
145        n,
146        q,
147        value: [MInt; n],
148        (graph, edges): @TreeGraphScanner::<usize, (MInt, MInt)>::new(n)
149    );
150
151    let top_tree = graph.static_top_tree(0);
152    let mut dp = top_tree.dp::<Dp>(value, edges);
153
154    for _ in 0..q {
155        scan!(scanner, query: Query);
156        match query {
157            Query::SetVertex { v, x, r } => {
158                dp.set_vertex(v, x);
159                writeln!(writer, "{}", dp.fold_path(r).reverse.sum).ok();
160            }
161            Query::SetEdge { e, a, b, r } => {
162                dp.set_edge(e, (a, b));
163                writeln!(writer, "{}", dp.fold_path(r).reverse.sum).ok();
164            }
165        }
166    }
167}
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 125)
106pub fn point_set_tree_path_composite_sum_fixed_root(reader: impl Read, mut writer: impl Write) {
107    let s = read_all_unchecked(reader);
108    let mut scanner = Scanner::new(&s);
109    scan!(
110        scanner,
111        n,
112        q,
113        value: [MInt; n],
114        (graph, edges): @TreeGraphScanner::<usize, (MInt, MInt)>::new(n)
115    );
116
117    let top_tree = graph.static_top_tree(0);
118    let mut dp = top_tree.dp::<Dp>(value, edges);
119
120    for _ in 0..q {
121        scan!(scanner, query: Query);
122        match query {
123            Query::SetVertex { v, x } => {
124                dp.set_vertex(v, x);
125                writeln!(writer, "{}", dp.fold_all().sum).ok();
126            }
127            Query::SetEdge { e, a, b } => {
128                dp.set_edge(e, (a, b));
129                writeln!(writer, "{}", dp.fold_all().sum).ok();
130            }
131        }
132    }
133}
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 159)
140pub fn point_set_tree_path_composite_sum(reader: impl Read, mut writer: impl Write) {
141    let s = read_all_unchecked(reader);
142    let mut scanner = Scanner::new(&s);
143    scan!(
144        scanner,
145        n,
146        q,
147        value: [MInt; n],
148        (graph, edges): @TreeGraphScanner::<usize, (MInt, MInt)>::new(n)
149    );
150
151    let top_tree = graph.static_top_tree(0);
152    let mut dp = top_tree.dp::<Dp>(value, edges);
153
154    for _ in 0..q {
155        scan!(scanner, query: Query);
156        match query {
157            Query::SetVertex { v, x, r } => {
158                dp.set_vertex(v, x);
159                writeln!(writer, "{}", dp.fold_path(r).reverse.sum).ok();
160            }
161            Query::SetEdge { e, a, b, r } => {
162                dp.set_edge(e, (a, b));
163                writeln!(writer, "{}", dp.fold_path(r).reverse.sum).ok();
164            }
165        }
166    }
167}
Source

fn update_from_vertex(&mut self, vertex: usize)

Examples found in repository?
crates/competitive/src/tree/static_top_tree.rs (line 487)
484    pub fn set_vertex(&mut self, vertex: usize, value: <C as Cluster>::Vertex) {
485        assert!(vertex < self.vertices.len());
486        self.vertices[vertex] = value;
487        self.update_from_vertex(vertex);
488    }
489
490    pub fn set_edge(&mut self, edge: usize, value: <C as Cluster>::Edge) {
491        assert!(edge < self.edges.len());
492        self.edges[edge] = value;
493        self.update_from_vertex(self.tree.edge_child[edge]);
494    }
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 555)
546    fn update_from_vertex(&mut self, mut vertex: usize) {
547        assert!(vertex < self.tree.n);
548        while vertex != usize::MAX {
549            let links = self.tree.vertex_links[vertex];
550            let base = C::add_vertex(
551                &self.light_points[vertex],
552                &self.vertices[vertex],
553                self.tree.parent_edge_ref(&self.edges, vertex),
554            );
555            let path = self.update_compress(links.compress_parent, base);
556            let point = C::add_edge(&path);
557            let point = self.update_rake(links.rake_parent, point);
558            if links.heavy_parent == usize::MAX {
559                self.all_point = point;
560            } else {
561                self.light_points[links.heavy_parent] = point;
562            }
563            vertex = links.heavy_parent;
564        }
565    }
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 557)
546    fn update_from_vertex(&mut self, mut vertex: usize) {
547        assert!(vertex < self.tree.n);
548        while vertex != usize::MAX {
549            let links = self.tree.vertex_links[vertex];
550            let base = C::add_vertex(
551                &self.light_points[vertex],
552                &self.vertices[vertex],
553                self.tree.parent_edge_ref(&self.edges, vertex),
554            );
555            let path = self.update_compress(links.compress_parent, base);
556            let point = C::add_edge(&path);
557            let point = self.update_rake(links.rake_parent, point);
558            if links.heavy_parent == usize::MAX {
559                self.all_point = point;
560            } else {
561                self.light_points[links.heavy_parent] = point;
562            }
563            vertex = links.heavy_parent;
564        }
565    }

Auto Trait Implementations§

§

impl<'a, C> Freeze for StaticTopTreeDp<'a, C>
where <C as Cluster>::Point: Freeze,

§

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

§

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

§

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

§

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

§

impl<'a, C> UnsafeUnpin for StaticTopTreeDp<'a, C>
where <C as Cluster>::Point: UnsafeUnpin,

§

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

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

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

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.