Struct LevelAncestorBatch

Source

struct LevelAncestorBatch<'a> {
    tree: &'a UndirectedSparseGraph,
    path: Vec<usize>,
    start: Vec<usize>,
    queries: Vec<(usize, usize)>,
    results: Vec<Option<usize>>,
}

Fields§

§tree: &'a UndirectedSparseGraph§path: Vec<usize>§start: Vec<usize>§queries: Vec<(usize, usize)>§results: Vec<Option<usize>>

Implementations§

Source §

impl<'a> LevelAncestorBatch<'a>

Source

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

Examples found in repository ?

crates/competitive/src/tree/level_ancestor.rs (line 86)

59    pub fn level_ancestor_batch(
60        &self,
61        root: usize,
62        queries: impl IntoIterator<Item = (usize, usize)>,
63    ) -> Vec<Option<usize>> {
64        let n = self.vertices_size();
65        let mut start = vec![0; n + 1];
66        let queries: Vec<(usize, usize)> = queries.into_iter().collect();
67        for &(u, _) in &queries {
68            start[u] += 1;
69        }
70        for d in 0..n {
71            start[d + 1] += start[d];
72        }
73        let qsize = queries.len();
74        let mut batch = vec![(0, 0); qsize];
75        for (i, &(u, k)) in queries.iter().enumerate() {
76            start[u] -= 1;
77            batch[start[u]] = (k, i);
78        }
79        let mut la = LevelAncestorBatch {
80            tree: self,
81            path: Vec::with_capacity(n),
82            start,
83            queries: batch,
84            results: vec![None; qsize],
85        };
86        la.dfs(root, !0);
87        la.results
88    }
89}
90
91impl LevelAncestor {
92    pub fn la(&self, u: usize, k: usize) -> Option<usize> {
93        if self.depth[u] < k {
94            return None;
95        }
96        let d = self.depth[u] - k;
97        let slice = &self.bucket[self.start[d]..self.start[d + 1]];
98        let idx = slice.partition_point(|&v| v > self.vidx[u]);
99        Some(self.inv_vidx[slice[idx]])
100    }
101
102    pub fn depth(&self, u: usize) -> usize {
103        self.depth[u]
104    }
105}
106
107impl<'a> LevelAncestorBatch<'a> {
108    fn dfs(&mut self, u: usize, p: usize) {
109        self.path.push(u);
110        for &(k, qi) in &self.queries[self.start[u]..self.start[u + 1]] {
111            let depth = self.path.len() - 1;
112            if k <= depth {
113                self.results[qi] = Some(self.path[depth - k]);
114            }
115        }
116        for a in self.tree.adjacencies(u) {
117            if a.to != p {
118                self.dfs(a.to, u);
119            }
120        }
121        self.path.pop();
122    }