Struct StaticTopTree

Source

pub struct StaticTopTree {
    root: usize,
    n: usize,
    edge_child: Vec<usize>,
    parent_edge: Vec<usize>,
    compressed: Vec<InnerNode>,
    raked: Vec<InnerNode>,
    vertex_links: Vec<VertexLinks>,
    compress_roots: Vec<Option<Slot>>,
    rake_roots: Vec<Option<Slot>>,
}

Fields§

§root: usize§n: usize§edge_child: Vec<usize>§parent_edge: Vec<usize>§compressed: Vec<InnerNode>§raked: Vec<InnerNode>§vertex_links: Vec<VertexLinks>§compress_roots: Vec<Option<Slot>>§rake_roots: Vec<Option<Slot>>

Implementations§

Source §

impl StaticTopTree

Source

pub fn new(root: usize, graph: &UndirectedSparseGraph) -> Self

Examples found in repository ?

crates/competitive/src/tree/static_top_tree.rs (line 150)

149    pub fn static_top_tree(&self, root: usize) -> StaticTopTree {
150        StaticTopTree::new(root, self)
151    }

Source

pub fn vertices_size(&self) -> usize

Examples found in repository ?

crates/competitive/src/tree/static_top_tree.rs (line 462)

457    pub fn new(
458        tree: &'a StaticTopTree,
459        vertices: Vec<<C as Cluster>::Vertex>,
460        edges: Vec<<C as Cluster>::Edge>,
461    ) -> Self {
462        assert_eq!(vertices.len(), tree.vertices_size());
463        assert_eq!(edges.len(), tree.edges_size());
464
465        let mut data: StaticTopTreeDataBuilder<C> = StaticTopTreeDataBuilder::new(tree);
466        let path = tree.init_compress(
467            &mut data,
468            &vertices,
469            &edges,
470            tree.compress_roots[tree.root].expect("root compress tree must exist"),
471        );
472        let all_point = C::add_edge(&path);
473        Self {
474            tree,
475            vertices,
476            edges,
477            compressed: unsafe { assume_init_vec(data.compressed) },
478            raked: unsafe { assume_init_vec(data.raked) },
479            light_points: data.light_points,
480            all_point,
481        }
482    }

Source

pub fn edges_size(&self) -> usize

Examples found in repository ?

crates/competitive/src/tree/static_top_tree.rs (line 463)

457    pub fn new(
458        tree: &'a StaticTopTree,
459        vertices: Vec<<C as Cluster>::Vertex>,
460        edges: Vec<<C as Cluster>::Edge>,
461    ) -> Self {
462        assert_eq!(vertices.len(), tree.vertices_size());
463        assert_eq!(edges.len(), tree.edges_size());
464
465        let mut data: StaticTopTreeDataBuilder<C> = StaticTopTreeDataBuilder::new(tree);
466        let path = tree.init_compress(
467            &mut data,
468            &vertices,
469            &edges,
470            tree.compress_roots[tree.root].expect("root compress tree must exist"),
471        );
472        let all_point = C::add_edge(&path);
473        Self {
474            tree,
475            vertices,
476            edges,
477            compressed: unsafe { assume_init_vec(data.compressed) },
478            raked: unsafe { assume_init_vec(data.raked) },
479            light_points: data.light_points,
480            all_point,
481        }
482    }

Source

pub fn dp<C>( &self, vertices: Vec<<C as Cluster>::Vertex>, edges: Vec<<C as Cluster>::Edge>, ) -> StaticTopTreeDp<'_, C>
where C: Cluster,

Examples found in repository ?

crates/library_checker/src/tree/point_set_tree_path_composite_sum_fixed_root.rs (line 118)

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 152)

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 build_compress( &mut self, vertex: usize, heavy_child: &[usize], mask: &[u64], ) -> Node

Examples found in repository ?

crates/competitive/src/tree/static_top_tree.rs (line 218)

155    pub fn new(root: usize, graph: &UndirectedSparseGraph) -> Self {
156        let n = graph.vertices_size();
157        assert!(n > 0);
158        assert!(root < n);
159        assert_eq!(graph.edges_size() + 1, n);
160
161        let RootedInfo {
162            order,
163            children_start,
164            children,
165            edge_child,
166            parent_edge,
167        } = rooted_children(graph, root);
168        let mut this = Self {
169            root,
170            n,
171            edge_child,
172            parent_edge,
173            compressed: Vec::with_capacity(n.saturating_sub(1)),
174            raked: Vec::with_capacity(n.saturating_sub(1)),
175            vertex_links: vec![
176                VertexLinks {
177                    heavy_parent: usize::MAX,
178                    compress_parent: usize::MAX,
179                    rake_parent: usize::MAX,
180                };
181                n
182            ],
183            compress_roots: vec![None; n],
184            rake_roots: vec![None; n],
185        };
186
187        let mut heavy_child = vec![usize::MAX; n];
188        let mut mask = vec![1u64; n];
189        let mut buckets: [Vec<Node>; 64] = std::array::from_fn(|_| Vec::new());
190
191        for &u in order.iter().rev() {
192            let children = &children[children_start[u]..children_start[u + 1]];
193            let mut sum_rake = 0u64;
194            for &v in children {
195                sum_rake += bit_ceil(mask[v]) << 1;
196            }
197            mask[u] = bit_ceil(sum_rake);
198            for &v in children {
199                let child = bit_ceil(mask[v]) << 1;
200                let depth = bit_ceil(sum_rake - child).trailing_zeros() as usize;
201                let step = 1u64 << depth;
202                let cand = ((mask[v] + step - 1) >> depth << depth) + step;
203                if cand <= mask[u] {
204                    mask[u] = cand;
205                    heavy_child[u] = v;
206                }
207            }
208
209            let mut has = 0u64;
210            let mut num_light = 0usize;
211            for &v in children {
212                if v == heavy_child[u] {
213                    continue;
214                }
215                num_light += 1;
216                let child = bit_ceil(mask[v]) << 1;
217                let depth = bit_ceil(sum_rake - child).trailing_zeros() as usize;
218                this.build_compress(v, &heavy_child, &mask);
219                buckets[depth].push(Node {
220                    depth,
221                    slot: Slot::RakeLeaf(v),
222                });
223                has |= 1u64 << depth;
224            }
225            if num_light == 0 {
226                continue;
227            }
228
229            while num_light > 1 {
230                let left = pop_bucket(&mut buckets, &mut has);
231                let right = pop_bucket(&mut buckets, &mut has);
232                let node = this.merge_rake(left, right);
233                let depth = node.depth;
234                buckets[depth].push(node);
235                has |= 1u64 << depth;
236                num_light -= 1;
237            }
238
239            let root = pop_bucket(&mut buckets, &mut has);
240            this.rake_roots[u] = Some(root.slot);
241            for &v0 in children {
242                if v0 == heavy_child[u] {
243                    continue;
244                }
245                let rake_parent = this.vertex_links[v0].rake_parent;
246                let mut v = v0;
247                while v != usize::MAX {
248                    this.vertex_links[v].heavy_parent = u;
249                    this.vertex_links[v].rake_parent = rake_parent;
250                    v = heavy_child[v];
251                }
252            }
253        }
254
255        this.build_compress(root, &heavy_child, &mask);
256        this
257    }

Source

fn merge_compress(&mut self, left: Node, right: Node) -> Node

Examples found in repository ?

crates/competitive/src/tree/static_top_tree.rs (line 295)

278    fn build_compress(&mut self, mut vertex: usize, heavy_child: &[usize], mask: &[u64]) -> Node {
279        let start = vertex;
280        let mut stack = Vec::new();
281        while vertex != usize::MAX {
282            stack.push(Node {
283                depth: bit_ceil(mask[vertex]).trailing_zeros() as usize,
284                slot: Slot::CompressLeaf(vertex),
285            });
286            loop {
287                let len = stack.len();
288                if len >= 3
289                    && (stack[len - 3].depth == stack[len - 2].depth
290                        || stack[len - 3].depth <= stack[len - 1].depth)
291                {
292                    let tail = stack.pop().unwrap();
293                    let right = stack.pop().unwrap();
294                    let left = stack.pop().unwrap();
295                    let node = self.merge_compress(left, right);
296                    stack.push(node);
297                    stack.push(tail);
298                } else if len >= 2 && stack[len - 2].depth <= stack[len - 1].depth {
299                    let right = stack.pop().unwrap();
300                    let left = stack.pop().unwrap();
301                    stack.push(self.merge_compress(left, right));
302                } else {
303                    break;
304                }
305            }
306            vertex = heavy_child[vertex];
307        }
308        while stack.len() > 1 {
309            let right = stack.pop().unwrap();
310            let left = stack.pop().unwrap();
311            stack.push(self.merge_compress(left, right));
312        }
313        let root = stack.pop().unwrap();
314        self.compress_roots[start] = Some(root.slot);
315        root
316    }

Source

fn merge_rake(&mut self, left: Node, right: Node) -> Node

Examples found in repository ?

crates/competitive/src/tree/static_top_tree.rs (line 232)

155    pub fn new(root: usize, graph: &UndirectedSparseGraph) -> Self {
156        let n = graph.vertices_size();
157        assert!(n > 0);
158        assert!(root < n);
159        assert_eq!(graph.edges_size() + 1, n);
160
161        let RootedInfo {
162            order,
163            children_start,
164            children,
165            edge_child,
166            parent_edge,
167        } = rooted_children(graph, root);
168        let mut this = Self {
169            root,
170            n,
171            edge_child,
172            parent_edge,
173            compressed: Vec::with_capacity(n.saturating_sub(1)),
174            raked: Vec::with_capacity(n.saturating_sub(1)),
175            vertex_links: vec![
176                VertexLinks {
177                    heavy_parent: usize::MAX,
178                    compress_parent: usize::MAX,
179                    rake_parent: usize::MAX,
180                };
181                n
182            ],
183            compress_roots: vec![None; n],
184            rake_roots: vec![None; n],
185        };
186
187        let mut heavy_child = vec![usize::MAX; n];
188        let mut mask = vec![1u64; n];
189        let mut buckets: [Vec<Node>; 64] = std::array::from_fn(|_| Vec::new());
190
191        for &u in order.iter().rev() {
192            let children = &children[children_start[u]..children_start[u + 1]];
193            let mut sum_rake = 0u64;
194            for &v in children {
195                sum_rake += bit_ceil(mask[v]) << 1;
196            }
197            mask[u] = bit_ceil(sum_rake);
198            for &v in children {
199                let child = bit_ceil(mask[v]) << 1;
200                let depth = bit_ceil(sum_rake - child).trailing_zeros() as usize;
201                let step = 1u64 << depth;
202                let cand = ((mask[v] + step - 1) >> depth << depth) + step;
203                if cand <= mask[u] {
204                    mask[u] = cand;
205                    heavy_child[u] = v;
206                }
207            }
208
209            let mut has = 0u64;
210            let mut num_light = 0usize;
211            for &v in children {
212                if v == heavy_child[u] {
213                    continue;
214                }
215                num_light += 1;
216                let child = bit_ceil(mask[v]) << 1;
217                let depth = bit_ceil(sum_rake - child).trailing_zeros() as usize;
218                this.build_compress(v, &heavy_child, &mask);
219                buckets[depth].push(Node {
220                    depth,
221                    slot: Slot::RakeLeaf(v),
222                });
223                has |= 1u64 << depth;
224            }
225            if num_light == 0 {
226                continue;
227            }
228
229            while num_light > 1 {
230                let left = pop_bucket(&mut buckets, &mut has);
231                let right = pop_bucket(&mut buckets, &mut has);
232                let node = this.merge_rake(left, right);
233                let depth = node.depth;
234                buckets[depth].push(node);
235                has |= 1u64 << depth;
236                num_light -= 1;
237            }
238
239            let root = pop_bucket(&mut buckets, &mut has);
240            this.rake_roots[u] = Some(root.slot);
241            for &v0 in children {
242                if v0 == heavy_child[u] {
243                    continue;
244                }
245                let rake_parent = this.vertex_links[v0].rake_parent;
246                let mut v = v0;
247                while v != usize::MAX {
248                    this.vertex_links[v].heavy_parent = u;
249                    this.vertex_links[v].rake_parent = rake_parent;
250                    v = heavy_child[v];
251                }
252            }
253        }
254
255        this.build_compress(root, &heavy_child, &mask);
256        this
257    }

Source

fn set_parent(&mut self, slot: Slot, parent: usize)

Examples found in repository ?

crates/competitive/src/tree/static_top_tree.rs (line 320)

318    fn merge_compress(&mut self, left: Node, right: Node) -> Node {
319        let id = self.compressed.len();
320        self.set_parent(left.slot, id << 1);
321        self.set_parent(right.slot, id << 1 | 1);
322        self.compressed.push(InnerNode {
323            left: left.slot,
324            right: right.slot,
325            parent: usize::MAX,
326        });
327        Node {
328            depth: left.depth.max(right.depth) + 1,
329            slot: Slot::CompressInner(id),
330        }
331    }
332
333    fn merge_rake(&mut self, left: Node, right: Node) -> Node {
334        let id = self.raked.len();
335        self.set_parent(left.slot, id << 1);
336        self.set_parent(right.slot, id << 1 | 1);
337        self.raked.push(InnerNode {
338            left: left.slot,
339            right: right.slot,
340            parent: usize::MAX,
341        });
342        Node {
343            depth: left.depth.max(right.depth) + 1,
344            slot: Slot::RakeInner(id),
345        }
346    }

Source

fn init_compress<C>( &self, data: &mut StaticTopTreeDataBuilder<C>, vertices: &[<C as Cluster>::Vertex], edges: &[<C as Cluster>::Edge], slot: Slot, ) -> <C as Cluster>::Path
where C: Cluster,

Examples found in repository ?

crates/competitive/src/tree/static_top_tree.rs (line 378)

357    fn init_compress<C>(
358        &self,
359        data: &mut StaticTopTreeDataBuilder<C>,
360        vertices: &[<C as Cluster>::Vertex],
361        edges: &[<C as Cluster>::Edge],
362        slot: Slot,
363    ) -> <C as Cluster>::Path
364    where
365        C: Cluster,
366    {
367        match slot {
368            Slot::CompressLeaf(vertex) => {
369                let point = self.init_point(data, vertices, edges, vertex);
370                C::add_vertex(
371                    &point,
372                    &vertices[vertex],
373                    self.parent_edge_ref(edges, vertex),
374                )
375            }
376            Slot::CompressInner(id) => {
377                let node = &self.compressed[id];
378                let left = self.init_compress(data, vertices, edges, node.left);
379                let right = self.init_compress(data, vertices, edges, node.right);
380                data.compressed[id].write(InnerValue {
381                    left: left.clone(),
382                    right: right.clone(),
383                });
384                C::compress(&left, &right)
385            }
386            Slot::RakeLeaf(_) | Slot::RakeInner(_) => unreachable!(),
387        }
388    }
389
390    fn init_point<C>(
391        &self,
392        data: &mut StaticTopTreeDataBuilder<C>,
393        vertices: &[<C as Cluster>::Vertex],
394        edges: &[<C as Cluster>::Edge],
395        vertex: usize,
396    ) -> <C as Cluster>::Point
397    where
398        C: Cluster,
399    {
400        let point = if let Some(slot) = self.rake_roots[vertex] {
401            self.init_rake(data, vertices, edges, slot)
402        } else {
403            C::unit_point()
404        };
405        data.light_points[vertex] = point.clone();
406        point
407    }
408
409    fn init_rake<C>(
410        &self,
411        data: &mut StaticTopTreeDataBuilder<C>,
412        vertices: &[<C as Cluster>::Vertex],
413        edges: &[<C as Cluster>::Edge],
414        slot: Slot,
415    ) -> <C as Cluster>::Point
416    where
417        C: Cluster,
418    {
419        match slot {
420            Slot::RakeLeaf(vertex) => {
421                let path = self.init_compress(
422                    data,
423                    vertices,
424                    edges,
425                    self.compress_roots[vertex].expect("light child path must exist"),
426                );
427                C::add_edge(&path)
428            }
429            Slot::RakeInner(id) => {
430                let node = &self.raked[id];
431                let left = self.init_rake(data, vertices, edges, node.left);
432                let right = self.init_rake(data, vertices, edges, node.right);
433                data.raked[id].write(InnerValue {
434                    left: left.clone(),
435                    right: right.clone(),
436                });
437                C::rake(&left, &right)
438            }
439            Slot::CompressLeaf(_) | Slot::CompressInner(_) => unreachable!(),
440        }
441    }
442
443    fn parent_edge_ref<'a, T>(&self, edges: &'a [T], vertex: usize) -> Option<&'a T> {
444        let edge = self.parent_edge[vertex];
445        if edge == usize::MAX {
446            None
447        } else {
448            Some(&edges[edge])
449        }
450    }
451}
452
453impl<'a, C> StaticTopTreeDp<'a, C>
454where
455    C: Cluster,
456{
457    pub fn new(
458        tree: &'a StaticTopTree,
459        vertices: Vec<<C as Cluster>::Vertex>,
460        edges: Vec<<C as Cluster>::Edge>,
461    ) -> Self {
462        assert_eq!(vertices.len(), tree.vertices_size());
463        assert_eq!(edges.len(), tree.edges_size());
464
465        let mut data: StaticTopTreeDataBuilder<C> = StaticTopTreeDataBuilder::new(tree);
466        let path = tree.init_compress(
467            &mut data,
468            &vertices,
469            &edges,
470            tree.compress_roots[tree.root].expect("root compress tree must exist"),
471        );
472        let all_point = C::add_edge(&path);
473        Self {
474            tree,
475            vertices,
476            edges,
477            compressed: unsafe { assume_init_vec(data.compressed) },
478            raked: unsafe { assume_init_vec(data.raked) },
479            light_points: data.light_points,
480            all_point,
481        }
482    }

Source

fn init_point<C>( &self, data: &mut StaticTopTreeDataBuilder<C>, vertices: &[<C as Cluster>::Vertex], edges: &[<C as Cluster>::Edge], vertex: usize, ) -> <C as Cluster>::Point
where C: Cluster,

Examples found in repository ?

crates/competitive/src/tree/static_top_tree.rs (line 369)

357    fn init_compress<C>(
358        &self,
359        data: &mut StaticTopTreeDataBuilder<C>,
360        vertices: &[<C as Cluster>::Vertex],
361        edges: &[<C as Cluster>::Edge],
362        slot: Slot,
363    ) -> <C as Cluster>::Path
364    where
365        C: Cluster,
366    {
367        match slot {
368            Slot::CompressLeaf(vertex) => {
369                let point = self.init_point(data, vertices, edges, vertex);
370                C::add_vertex(
371                    &point,
372                    &vertices[vertex],
373                    self.parent_edge_ref(edges, vertex),
374                )
375            }
376            Slot::CompressInner(id) => {
377                let node = &self.compressed[id];
378                let left = self.init_compress(data, vertices, edges, node.left);
379                let right = self.init_compress(data, vertices, edges, node.right);
380                data.compressed[id].write(InnerValue {
381                    left: left.clone(),
382                    right: right.clone(),
383                });
384                C::compress(&left, &right)
385            }
386            Slot::RakeLeaf(_) | Slot::RakeInner(_) => unreachable!(),
387        }
388    }

Source

fn init_rake<C>( &self, data: &mut StaticTopTreeDataBuilder<C>, vertices: &[<C as Cluster>::Vertex], edges: &[<C as Cluster>::Edge], slot: Slot, ) -> <C as Cluster>::Point
where C: Cluster,

Examples found in repository ?

crates/competitive/src/tree/static_top_tree.rs (line 401)

390    fn init_point<C>(
391        &self,
392        data: &mut StaticTopTreeDataBuilder<C>,
393        vertices: &[<C as Cluster>::Vertex],
394        edges: &[<C as Cluster>::Edge],
395        vertex: usize,
396    ) -> <C as Cluster>::Point
397    where
398        C: Cluster,
399    {
400        let point = if let Some(slot) = self.rake_roots[vertex] {
401            self.init_rake(data, vertices, edges, slot)
402        } else {
403            C::unit_point()
404        };
405        data.light_points[vertex] = point.clone();
406        point
407    }
408
409    fn init_rake<C>(
410        &self,
411        data: &mut StaticTopTreeDataBuilder<C>,
412        vertices: &[<C as Cluster>::Vertex],
413        edges: &[<C as Cluster>::Edge],
414        slot: Slot,
415    ) -> <C as Cluster>::Point
416    where
417        C: Cluster,
418    {
419        match slot {
420            Slot::RakeLeaf(vertex) => {
421                let path = self.init_compress(
422                    data,
423                    vertices,
424                    edges,
425                    self.compress_roots[vertex].expect("light child path must exist"),
426                );
427                C::add_edge(&path)
428            }
429            Slot::RakeInner(id) => {
430                let node = &self.raked[id];
431                let left = self.init_rake(data, vertices, edges, node.left);
432                let right = self.init_rake(data, vertices, edges, node.right);
433                data.raked[id].write(InnerValue {
434                    left: left.clone(),
435                    right: right.clone(),
436                });
437                C::rake(&left, &right)
438            }
439            Slot::CompressLeaf(_) | Slot::CompressInner(_) => unreachable!(),
440        }
441    }

Source

fn parent_edge_ref<'a, T>(&self, edges: &'a [T], vertex: usize) -> Option<&'a T>

Examples found in repository ?

crates/competitive/src/tree/static_top_tree.rs (line 373)

357    fn init_compress<C>(
358        &self,
359        data: &mut StaticTopTreeDataBuilder<C>,
360        vertices: &[<C as Cluster>::Vertex],
361        edges: &[<C as Cluster>::Edge],
362        slot: Slot,
363    ) -> <C as Cluster>::Path
364    where
365        C: Cluster,
366    {
367        match slot {
368            Slot::CompressLeaf(vertex) => {
369                let point = self.init_point(data, vertices, edges, vertex);
370                C::add_vertex(
371                    &point,
372                    &vertices[vertex],
373                    self.parent_edge_ref(edges, vertex),
374                )
375            }
376            Slot::CompressInner(id) => {
377                let node = &self.compressed[id];
378                let left = self.init_compress(data, vertices, edges, node.left);
379                let right = self.init_compress(data, vertices, edges, node.right);
380                data.compressed[id].write(InnerValue {
381                    left: left.clone(),
382                    right: right.clone(),
383                });
384                C::compress(&left, &right)
385            }
386            Slot::RakeLeaf(_) | Slot::RakeInner(_) => unreachable!(),
387        }
388    }
389
390    fn init_point<C>(
391        &self,
392        data: &mut StaticTopTreeDataBuilder<C>,
393        vertices: &[<C as Cluster>::Vertex],
394        edges: &[<C as Cluster>::Edge],
395        vertex: usize,
396    ) -> <C as Cluster>::Point
397    where
398        C: Cluster,
399    {
400        let point = if let Some(slot) = self.rake_roots[vertex] {
401            self.init_rake(data, vertices, edges, slot)
402        } else {
403            C::unit_point()
404        };
405        data.light_points[vertex] = point.clone();
406        point
407    }
408
409    fn init_rake<C>(
410        &self,
411        data: &mut StaticTopTreeDataBuilder<C>,
412        vertices: &[<C as Cluster>::Vertex],
413        edges: &[<C as Cluster>::Edge],
414        slot: Slot,
415    ) -> <C as Cluster>::Point
416    where
417        C: Cluster,
418    {
419        match slot {
420            Slot::RakeLeaf(vertex) => {
421                let path = self.init_compress(
422                    data,
423                    vertices,
424                    edges,
425                    self.compress_roots[vertex].expect("light child path must exist"),
426                );
427                C::add_edge(&path)
428            }
429            Slot::RakeInner(id) => {
430                let node = &self.raked[id];
431                let left = self.init_rake(data, vertices, edges, node.left);
432                let right = self.init_rake(data, vertices, edges, node.right);
433                data.raked[id].write(InnerValue {
434                    left: left.clone(),
435                    right: right.clone(),
436                });
437                C::rake(&left, &right)
438            }
439            Slot::CompressLeaf(_) | Slot::CompressInner(_) => unreachable!(),
440        }
441    }
442
443    fn parent_edge_ref<'a, T>(&self, edges: &'a [T], vertex: usize) -> Option<&'a T> {
444        let edge = self.parent_edge[vertex];
445        if edge == usize::MAX {
446            None
447        } else {
448            Some(&edges[edge])
449        }
450    }
451}
452
453impl<'a, C> StaticTopTreeDp<'a, C>
454where
455    C: Cluster,
456{
457    pub fn new(
458        tree: &'a StaticTopTree,
459        vertices: Vec<<C as Cluster>::Vertex>,
460        edges: Vec<<C as Cluster>::Edge>,
461    ) -> Self {
462        assert_eq!(vertices.len(), tree.vertices_size());
463        assert_eq!(edges.len(), tree.edges_size());
464
465        let mut data: StaticTopTreeDataBuilder<C> = StaticTopTreeDataBuilder::new(tree);
466        let path = tree.init_compress(
467            &mut data,
468            &vertices,
469            &edges,
470            tree.compress_roots[tree.root].expect("root compress tree must exist"),
471        );
472        let all_point = C::add_edge(&path);
473        Self {
474            tree,
475            vertices,
476            edges,
477            compressed: unsafe { assume_init_vec(data.compressed) },
478            raked: unsafe { assume_init_vec(data.raked) },
479            light_points: data.light_points,
480            all_point,
481        }
482    }
483
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    }
495
496    pub fn fold_all(&self) -> &<C as Cluster>::Point {
497        &self.all_point
498    }
499
500    pub fn fold_path(&self, mut vertex: usize) -> <C as Cluster>::Path {
501        assert!(vertex < self.tree.n);
502        let mut path = C::unit_path();
503        let mut point = self.light_points[vertex].clone();
504        loop {
505            let links = self.tree.vertex_links[vertex];
506            let mut left = C::unit_path();
507            let mut right = C::unit_path();
508            let mut compress_parent = links.compress_parent;
509            while compress_parent != usize::MAX {
510                let inner = &self.compressed[compress_parent / 2];
511                if compress_parent & 1 == 0 {
512                    right = C::compress(&right, &inner.right);
513                } else {
514                    left = C::compress(&inner.left, &left);
515                }
516                compress_parent = self.tree.compressed[compress_parent / 2].parent;
517            }
518            let right_point = C::add_edge(&right);
519            point = C::rake(&point, &right_point);
520            let mid = C::add_vertex(
521                &point,
522                &self.vertices[vertex],
523                self.tree.parent_edge_ref(&self.edges, vertex),
524            );
525            let mid = C::compress(&mid, &path);
526            path = C::compress(&left, &mid);
527            if links.heavy_parent == usize::MAX {
528                return path;
529            }
530
531            point = C::unit_point();
532            let mut rake_parent = links.rake_parent;
533            while rake_parent != usize::MAX {
534                let inner = &self.raked[rake_parent / 2];
535                if rake_parent & 1 == 0 {
536                    point = C::rake(&point, &inner.right);
537                } else {
538                    point = C::rake(&inner.left, &point);
539                }
540                rake_parent = self.tree.raked[rake_parent / 2].parent;
541            }
542            vertex = links.heavy_parent;
543        }
544    }
545
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    }