Struct EulerTour

Source

pub struct EulerTour<K>where
    K: EulerTourKind,{
    pub root: usize,
    pub vidx: Vec<[usize; 2]>,
    pub eidx: Vec<[usize; 2]>,
    pub size: usize,
    _marker: PhantomData<fn() -> K>,
}

Fields§

§root: usize§vidx: Vec<[usize; 2]>§eidx: Vec<[usize; 2]>§size: usize§_marker: PhantomData<fn() -> K>

Implementations§

Source §

impl EulerTour<First>

Source

pub fn get<T>(&self, u: usize, f: impl FnMut(usize) -> T) -> T

Source

pub fn update<T>(&self, u: usize, x: T, f: impl FnMut(usize, T))

Examples found in repository ?

crates/library_checker/src/tree/vertex_add_subtree_sum.rs (line 27)

15pub fn vertex_add_subtree_sum(reader: impl Read, mut writer: impl Write) {
16    let s = read_all_unchecked(reader);
17    let mut scanner = Scanner::new(&s);
18    scan!(scanner, n, q, a: [u64; n], p: [usize]);
19    let edges = p.take(n - 1).enumerate().map(|(i, p)| (i + 1, p)).collect();
20    let tree = UndirectedSparseGraph::from_edges(n, edges);
21    let (et, b) = tree.subtree_euler_tour_builder(0).build_with_rearrange(&a);
22    let mut seg = SegmentTree::<AdditiveOperation<_>>::from_vec(b);
23    for _ in 0..q {
24        scan!(scanner, query: Query);
25        match query {
26            Query::Add { u, x } => {
27                et.update(u, x, |k, x| seg.update(k, x));
28            }
29            Query::Sum { u } => {
30                writeln!(writer, "{}", et.fold(u, |r| seg.fold(r))).ok();
31            }
32        }
33    }
34}

Source

pub fn fold<T>(&self, u: usize, f: impl FnMut(Range<usize>) -> T) -> T

Examples found in repository ?

crates/library_checker/src/tree/vertex_add_subtree_sum.rs (line 30)

15pub fn vertex_add_subtree_sum(reader: impl Read, mut writer: impl Write) {
16    let s = read_all_unchecked(reader);
17    let mut scanner = Scanner::new(&s);
18    scan!(scanner, n, q, a: [u64; n], p: [usize]);
19    let edges = p.take(n - 1).enumerate().map(|(i, p)| (i + 1, p)).collect();
20    let tree = UndirectedSparseGraph::from_edges(n, edges);
21    let (et, b) = tree.subtree_euler_tour_builder(0).build_with_rearrange(&a);
22    let mut seg = SegmentTree::<AdditiveOperation<_>>::from_vec(b);
23    for _ in 0..q {
24        scan!(scanner, query: Query);
25        match query {
26            Query::Add { u, x } => {
27                et.update(u, x, |k, x| seg.update(k, x));
28            }
29            Query::Sum { u } => {
30                writeln!(writer, "{}", et.fold(u, |r| seg.fold(r))).ok();
31            }
32        }
33    }
34}

Source

pub fn update<T>(&self, u: usize, x: T, invx: T, f: impl FnMut(usize, T))

Examples found in repository ?

crates/aizu_online_judge/src/grl/grl_5_d.rs (line 34)

16pub fn grl_5_d(reader: impl Read, mut writer: impl Write) {
17    let s = read_all_unchecked(reader);
18    let mut scanner = Scanner::new(&s);
19    scan!(scanner, n, c: [SizedCollect<usize>]);
20    let edges = c
21        .take(n)
22        .enumerate()
23        .flat_map(|(u, it)| it.into_iter().map(move |v| (u, v)))
24        .collect();
25    let graph = UndirectedSparseGraph::from_edges(n, edges);
26    let et = graph.path_euler_tour_builder(0).build();
27    let mut bit = BinaryIndexedTree::<AdditiveOperation<_>>::new(et.size);
28
29    scan!(scanner, q);
30    for _ in 0..q {
31        scan!(scanner, query: Query);
32        match query {
33            Query::Add { v, w } => {
34                et.update(v, w, -w, |k, x| bit.update(k, x));
35            }
36            Query::Get { u } => {
37                let ans = et.fold(u, |k| bit.accumulate(k));
38                writeln!(writer, "{}", ans).ok();
39            }
40        }
41    }
42}

Source

pub fn fold<T>(&self, u: usize, f: impl FnMut(usize) -> T) -> T

Examples found in repository ?

crates/aizu_online_judge/src/grl/grl_5_d.rs (line 37)

16pub fn grl_5_d(reader: impl Read, mut writer: impl Write) {
17    let s = read_all_unchecked(reader);
18    let mut scanner = Scanner::new(&s);
19    scan!(scanner, n, c: [SizedCollect<usize>]);
20    let edges = c
21        .take(n)
22        .enumerate()
23        .flat_map(|(u, it)| it.into_iter().map(move |v| (u, v)))
24        .collect();
25    let graph = UndirectedSparseGraph::from_edges(n, edges);
26    let et = graph.path_euler_tour_builder(0).build();
27    let mut bit = BinaryIndexedTree::<AdditiveOperation<_>>::new(et.size);
28
29    scan!(scanner, q);
30    for _ in 0..q {
31        scan!(scanner, query: Query);
32        match query {
33            Query::Add { v, w } => {
34                et.update(v, w, -w, |k, x| bit.update(k, x));
35            }
36            Query::Get { u } => {
37                let ans = et.fold(u, |k| bit.accumulate(k));
38                writeln!(writer, "{}", ans).ok();
39            }
40        }
41    }
42}