Struct EulerTourForRichVertex

Source

pub struct EulerTourForRichVertex<'a> {
    pub root: usize,
    pub vidx: Vec<(usize, usize)>,
    /* private fields */
}

Fields§

§root: usize§vidx: Vec<(usize, usize)>

Implementations§

Source §

impl<'a> EulerTourForRichVertex<'a>

Source

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

Examples found in repository ?

crates/library_checker/src/graph/lca.rs (line 15)

9pub fn lca_euler_tour(reader: impl Read, mut writer: impl Write) {
10    let s = read_all_unchecked(reader);
11    let mut scanner = Scanner::new(&s);
12    scan!(scanner, n, q, p: [usize]);
13    let edges = p.take(n - 1).enumerate().map(|(i, p)| (i + 1, p)).collect();
14    let graph = UndirectedSparseGraph::from_edges(n, edges);
15    let euler = EulerTourForRichVertex::new(0, &graph);
16    let lca = euler.gen_lca::<LcaMonoidDefaultId>();
17    for (u, v) in scanner.iter::<(usize, usize)>().take(q) {
18        writeln!(writer, "{}", lca.lca(u, v)).ok();
19    }
20}

More examples

Hide additional examples

crates/aizu_online_judge/src/grl/grl_5_c.rs (line 20)

10pub fn grl_5_c(reader: impl Read, mut writer: impl Write) {
11    let s = read_all_unchecked(reader);
12    let mut scanner = Scanner::new(&s);
13    scan!(scanner, n, c: [SizedCollect<usize>]);
14    let edges = c
15        .take(n)
16        .enumerate()
17        .flat_map(|(u, it)| it.into_iter().map(move |v| (u, v)))
18        .collect();
19    let graph = UndirectedSparseGraph::from_edges(n, edges);
20    let et = EulerTourForRichVertex::new(0, &graph);
21    let lca = et.gen_lca::<LcaMonoidDefaultId>();
22    scan!(scanner, q, uv: [(usize, usize)]);
23    for (u, v) in uv.take(q) {
24        writeln!(writer, "{}", lca.lca(u, v)).ok();
25    }
26}

Source

pub fn length(&self) -> usize

Source

pub fn query<T, F: FnMut(usize, usize) -> T>( &self, u: usize, v: usize, f: F, ) -> T

Examples found in repository ?

crates/competitive/src/tree/euler_tour.rs (line 165)

164    pub fn lca(&self, u: usize, v: usize) -> usize {
165        self.euler.query(u, v, |l, r| self.dst.fold(l, r))
166    }

Source §

impl<'a> EulerTourForRichVertex<'a>

Source

pub fn gen_lca<D: LcaMonoidDispatch>(&'a self) -> LowestCommonAncestor<'a, D>

Examples found in repository ?

crates/library_checker/src/graph/lca.rs (line 16)

9pub fn lca_euler_tour(reader: impl Read, mut writer: impl Write) {
10    let s = read_all_unchecked(reader);
11    let mut scanner = Scanner::new(&s);
12    scan!(scanner, n, q, p: [usize]);
13    let edges = p.take(n - 1).enumerate().map(|(i, p)| (i + 1, p)).collect();
14    let graph = UndirectedSparseGraph::from_edges(n, edges);
15    let euler = EulerTourForRichVertex::new(0, &graph);
16    let lca = euler.gen_lca::<LcaMonoidDefaultId>();
17    for (u, v) in scanner.iter::<(usize, usize)>().take(q) {
18        writeln!(writer, "{}", lca.lca(u, v)).ok();
19    }
20}

More examples

Hide additional examples

crates/aizu_online_judge/src/grl/grl_5_c.rs (line 21)

10pub fn grl_5_c(reader: impl Read, mut writer: impl Write) {
11    let s = read_all_unchecked(reader);
12    let mut scanner = Scanner::new(&s);
13    scan!(scanner, n, c: [SizedCollect<usize>]);
14    let edges = c
15        .take(n)
16        .enumerate()
17        .flat_map(|(u, it)| it.into_iter().map(move |v| (u, v)))
18        .collect();
19    let graph = UndirectedSparseGraph::from_edges(n, edges);
20    let et = EulerTourForRichVertex::new(0, &graph);
21    let lca = et.gen_lca::<LcaMonoidDefaultId>();
22    scan!(scanner, q, uv: [(usize, usize)]);
23    for (u, v) in uv.take(q) {
24        writeln!(writer, "{}", lca.lca(u, v)).ok();
25    }
26}