Struct EulerTourBuilder 

pub struct EulerTourBuilder<'a, K>
where
    K: EulerTourKind,
{
    tree: &'a UndirectedSparseGraph,
    root: usize,
    vidx: Vec<[usize; 2]>,
    eidx: Vec<[usize; 2]>,
    pos: usize,
    _marker: PhantomData<fn() -> K>,
}

Fields

tree: &'a UndirectedSparseGraph

root: usize

vidx: Vec<[usize; 2]>

eidx: Vec<[usize; 2]>

pos: usize

_marker: PhantomData<fn() -> K>

Implementations

impl<'a, K> EulerTourBuilder<'a, K>

where K: EulerTourKind,

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

Examples found in repository

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

    pub fn subtree_euler_tour_builder<'a>(
        &'a self,
        root: usize,
    ) -> EulerTourBuilder<'a, marker::First> {
        EulerTourBuilder::new(self, root)
    }

    pub fn path_euler_tour_builder<'a>(
        &'a self,
        root: usize,
    ) -> EulerTourBuilder<'a, marker::FirstLast> {
        EulerTourBuilder::new(self, root)
    }

    pub fn full_euler_tour_builder<'a>(
        &'a self,
        root: usize,
    ) -> EulerTourBuilder<'a, marker::Visit> {
        EulerTourBuilder::new(self, root)
    }

pub fn build_with_trace(self, trace: impl FnMut(usize)) -> EulerTour<K>

Examples found in repository

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

    pub fn build(self) -> EulerTour<K> {
        self.build_with_trace(|_u| {})
    }

    fn dfs(&mut self, u: usize, parent: usize, trace: &mut impl FnMut(usize)) {
        self.vidx[u][0] = self.pos;
        trace(u);
        self.pos += 1;
        for a in self.tree.neighbors(u) {
            if a.to != parent {
                self.eidx[a.label][0] = self.pos;
                self.dfs(a.to, u, trace);
                self.eidx[a.label][1] = self.pos;
                if K::USE_VISIT {
                    trace(u);
                    self.pos += 1;
                }
            }
        }
        self.vidx[u][1] = self.pos;
        if K::USE_LAST {
            trace(u);
            self.pos += 1;
        }
    }
}

impl EulerTourBuilder<'_, marker::First> {
    pub fn build_with_rearrange<T>(self, s: &[T]) -> (EulerTour<marker::First>, Vec<T>)
    where
        T: Clone,
    {
        assert_eq!(s.len(), self.tree.vertices_size());
        let mut trace = Vec::with_capacity(marker::First::size(s.len()));
        let tour = self.build_with_trace(|u| {
            trace.push(s[u].clone());
        });
        (tour, trace)
    }
}

impl EulerTourBuilder<'_, marker::FirstLast> {
    pub fn build_with_rearrange<T>(
        self,
        s: &[T],
        mut inverse: impl FnMut(T) -> T,
    ) -> (EulerTour<marker::FirstLast>, Vec<T>)
    where
        T: Clone,
    {
        assert_eq!(s.len(), self.tree.vertices_size());
        let mut visited = vec![false; s.len()];
        let mut trace = Vec::with_capacity(marker::FirstLast::size(s.len()));
        let tour = self.build_with_trace(|u| {
            if !visited[u] {
                trace.push(s[u].clone());
                visited[u] = true;
            } else {
                trace.push(inverse(s[u].clone()));
            }
        });
        (tour, trace)
    }
}

impl EulerTourBuilder<'_, marker::Visit> {
    pub fn build_with_rearrange<T>(self, s: &[T]) -> (EulerTour<marker::Visit>, Vec<T>)
    where
        T: Clone,
    {
        assert_eq!(s.len(), self.tree.vertices_size());
        let mut trace = Vec::with_capacity(marker::Visit::size(s.len()));
        let tour = self.build_with_trace(|u| {
            trace.push(s[u].clone());
        });
        (tour, trace)
    }

pub fn build(self) -> EulerTour<K>

Examples found in repository

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

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);
            }
        }
    }
}

fn dfs(&mut self, u: usize, parent: usize, trace: &mut impl FnMut(usize))

Examples found in repository

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

    pub fn build_with_trace(mut self, mut trace: impl FnMut(usize)) -> EulerTour<K> {
        self.dfs(self.root, !0, &mut trace);
        EulerTour {
            root: self.root,
            vidx: self.vidx,
            eidx: self.eidx,
            size: self.pos,
            _marker: PhantomData,
        }
    }

    pub fn build(self) -> EulerTour<K> {
        self.build_with_trace(|_u| {})
    }

    fn dfs(&mut self, u: usize, parent: usize, trace: &mut impl FnMut(usize)) {
        self.vidx[u][0] = self.pos;
        trace(u);
        self.pos += 1;
        for a in self.tree.neighbors(u) {
            if a.to != parent {
                self.eidx[a.label][0] = self.pos;
                self.dfs(a.to, u, trace);
                self.eidx[a.label][1] = self.pos;
                if K::USE_VISIT {
                    trace(u);
                    self.pos += 1;
                }
            }
        }
        self.vidx[u][1] = self.pos;
        if K::USE_LAST {
            trace(u);
            self.pos += 1;
        }
    }

impl EulerTourBuilder<'_, First>

pub fn build_with_rearrange<T>(self, s: &[T]) -> (EulerTour<First>, Vec<T>)

where T: Clone,

impl EulerTourBuilder<'_, FirstLast>

pub fn build_with_rearrange<T>( self, s: &[T], inverse: impl FnMut(T) -> T, ) -> (EulerTour<FirstLast>, Vec<T>)

where T: Clone,

impl EulerTourBuilder<'_, Visit>

pub fn build_with_rearrange<T>(self, s: &[T]) -> (EulerTour<Visit>, Vec<T>)

where T: Clone,

Trait Implementations

impl<'a, K> Debug for EulerTourBuilder<'a, K>

where K: EulerTourKind + Debug,

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

Formats the value using the given formatter.