haar_lib/tree/
euler_tour.rs

1//! Euler tour
2//!
3//! # Problems
4//! - <https://judge.yosupo.jp/problem/vertex_add_subtree_sum>
5
6use crate::tree::*;
7
8/// Euler tour
9pub struct EulerTour {
10    begin: Vec<usize>,
11    end: Vec<usize>,
12}
13
14impl EulerTour {
15    /// `root`を根として[`EulerTour`]を構築する。
16    pub fn new<E: TreeEdgeTrait>(tree: &Tree<E>, root: usize) -> Self {
17        let n = tree.len();
18        let mut this = Self {
19            begin: vec![0; n],
20            end: vec![0; n],
21        };
22        this.dfs(tree, root, None, &mut 0);
23        this
24    }
25
26    fn dfs<E: TreeEdgeTrait>(
27        &mut self,
28        tree: &Tree<E>,
29        cur: usize,
30        par: Option<usize>,
31        pos: &mut usize,
32    ) {
33        self.begin[cur] = *pos;
34        *pos += 1;
35
36        for e in tree.nodes[cur].neighbors() {
37            if par.is_none_or(|p| p != e.to()) {
38                self.dfs(tree, e.to(), Some(cur), pos);
39            }
40        }
41
42        self.end[cur] = *pos;
43    }
44
45    /// 頂点`i`の部分木に対応する範囲を返す。
46    pub fn subtree_query(&self, i: usize) -> (usize, usize) {
47        (self.begin[i], self.end[i])
48    }
49
50    /// 頂点`i`に対応する番号を返す。
51    pub fn point_query(&self, i: usize) -> usize {
52        self.begin[i]
53    }
54}
haar_lib/tree/euler_tour.rs

haar_lib/tree/
euler_tour.rs
