Struct EulerTourForVertex

Source

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

Fields§

§vidx: Vec<(usize, usize)>

Implementations§

Source §

impl<'a> EulerTourForVertex<'a>

Source

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

Examples found in repository ?

crates/library_checker/src/datastructure/vertex_add_subtree_sum.rs (line 15)

9pub fn vertex_add_subtree_sum(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, a: [u64; n], 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 mut et = EulerTourForVertex::new(&graph);
16    et.subtree_vertex_tour(0, n);
17    let mut b = vec![0; n];
18    for i in 0..n {
19        b[et.vidx[i].0] = a[i];
20    }
21    let mut seg = SegmentTree::<AdditiveOperation<_>>::from_vec(b);
22    for _ in 0..q {
23        match scanner.scan::<usize>() {
24            0 => {
25                scan!(scanner, u, x: u64);
26                et.subtree_update(u, x, |k, x| seg.update(k, x));
27            }
28            1 => {
29                scan!(scanner, u);
30                writeln!(writer, "{}", et.subtree_query(u, |l, r| seg.fold(l..r))).ok();
31            }
32            _ => panic!("unknown query"),
33        }
34    }
35}

Source

pub fn length(&self) -> usize

Source

pub fn subtree_vertex_tour(&mut self, u: usize, p: usize)

Examples found in repository ?

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

59    pub fn subtree_vertex_tour(&mut self, u: usize, p: usize) {
60        self.vidx[u].0 = self.vpos;
61        self.vpos += 1;
62        for a in self.graph.adjacencies(u).filter(|a| a.to != p) {
63            self.subtree_vertex_tour(a.to, u);
64        }
65        self.vidx[u].1 = self.vpos;
66    }

More examples

Hide additional examples

crates/library_checker/src/datastructure/vertex_add_subtree_sum.rs (line 16)

9pub fn vertex_add_subtree_sum(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, a: [u64; n], 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 mut et = EulerTourForVertex::new(&graph);
16    et.subtree_vertex_tour(0, n);
17    let mut b = vec![0; n];
18    for i in 0..n {
19        b[et.vidx[i].0] = a[i];
20    }
21    let mut seg = SegmentTree::<AdditiveOperation<_>>::from_vec(b);
22    for _ in 0..q {
23        match scanner.scan::<usize>() {
24            0 => {
25                scan!(scanner, u, x: u64);
26                et.subtree_update(u, x, |k, x| seg.update(k, x));
27            }
28            1 => {
29                scan!(scanner, u);
30                writeln!(writer, "{}", et.subtree_query(u, |l, r| seg.fold(l..r))).ok();
31            }
32            _ => panic!("unknown query"),
33        }
34    }
35}

Source

pub fn path_vertex_tour(&mut self, u: usize, p: usize)

Examples found in repository ?

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

67    pub fn path_vertex_tour(&mut self, u: usize, p: usize) {
68        self.vidx[u].0 = self.vpos;
69        self.vpos += 1;
70        for a in self.graph.adjacencies(u).filter(|a| a.to != p) {
71            self.path_vertex_tour(a.to, u);
72        }
73        self.vidx[u].1 = self.vpos;
74        self.vpos += 1;
75    }

Source

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

Examples found in repository ?

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

9pub fn vertex_add_subtree_sum(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, a: [u64; n], 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 mut et = EulerTourForVertex::new(&graph);
16    et.subtree_vertex_tour(0, n);
17    let mut b = vec![0; n];
18    for i in 0..n {
19        b[et.vidx[i].0] = a[i];
20    }
21    let mut seg = SegmentTree::<AdditiveOperation<_>>::from_vec(b);
22    for _ in 0..q {
23        match scanner.scan::<usize>() {
24            0 => {
25                scan!(scanner, u, x: u64);
26                et.subtree_update(u, x, |k, x| seg.update(k, x));
27            }
28            1 => {
29                scan!(scanner, u);
30                writeln!(writer, "{}", et.subtree_query(u, |l, r| seg.fold(l..r))).ok();
31            }
32            _ => panic!("unknown query"),
33        }
34    }
35}

Source

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

Examples found in repository ?

crates/library_checker/src/datastructure/vertex_add_subtree_sum.rs (line 26)

9pub fn vertex_add_subtree_sum(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, a: [u64; n], 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 mut et = EulerTourForVertex::new(&graph);
16    et.subtree_vertex_tour(0, n);
17    let mut b = vec![0; n];
18    for i in 0..n {
19        b[et.vidx[i].0] = a[i];
20    }
21    let mut seg = SegmentTree::<AdditiveOperation<_>>::from_vec(b);
22    for _ in 0..q {
23        match scanner.scan::<usize>() {
24            0 => {
25                scan!(scanner, u, x: u64);
26                et.subtree_update(u, x, |k, x| seg.update(k, x));
27            }
28            1 => {
29                scan!(scanner, u);
30                writeln!(writer, "{}", et.subtree_query(u, |l, r| seg.fold(l..r))).ok();
31            }
32            _ => panic!("unknown query"),
33        }
34    }
35}