Struct EulerTour 

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

impl EulerTour<First>

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

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

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

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

impl EulerTour<FirstLast>

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

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

pub fn grl_5_d(reader: impl Read, writer: impl Write) {
    prepare_io!(reader, writer);
    sc!(n, c: [SizedCollect<usize>; iter n]);
    let edges = c
        .enumerate()
        .flat_map(|(u, it)| it.into_iter().map(move |v| (u, v)))
        .collect();
    let graph = UndirectedSparseGraph::from_edges(n, edges);
    let et = graph.path_euler_tour_builder(0).build();
    let mut bit = BinaryIndexedTree::<AdditiveOperation<_>>::new(et.size);

    sc!(q);
    for _ in 0..q {
        sc!(query: Query);
        match query {
            Query::Add { v, w } => {
                et.update(v, w, -w, |k, x| bit.update(k, x));
            }
            Query::Get { u } => {
                let ans = et.fold(u, |k| bit.accumulate(k));
                pp!(ans);
            }
        }
    }
}

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

pub fn grl_5_d(reader: impl Read, writer: impl Write) {
    prepare_io!(reader, writer);
    sc!(n, c: [SizedCollect<usize>; iter n]);
    let edges = c
        .enumerate()
        .flat_map(|(u, it)| it.into_iter().map(move |v| (u, v)))
        .collect();
    let graph = UndirectedSparseGraph::from_edges(n, edges);
    let et = graph.path_euler_tour_builder(0).build();
    let mut bit = BinaryIndexedTree::<AdditiveOperation<_>>::new(et.size);

    sc!(q);
    for _ in 0..q {
        sc!(query: Query);
        match query {
            Query::Add { v, w } => {
                et.update(v, w, -w, |k, x| bit.update(k, x));
            }
            Query::Get { u } => {
                let ans = et.fold(u, |k| bit.accumulate(k));
                pp!(ans);
            }
        }
    }
}

Trait Implementations

impl<K> Clone for EulerTour<K>

where K: EulerTourKind + Clone,

fn clone(&self) -> Self

Returns a duplicate of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl<K> Debug for EulerTour<K>

where K: EulerTourKind + Debug,

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.