Struct EulerTourForEdge

Source

pub struct EulerTourForEdge<'a> {
    graph: &'a UndirectedSparseGraph,
    pub eidx: Vec<(usize, usize)>,
    pub par: Vec<usize>,
    epos: usize,
}

Fields§

§graph: &'a UndirectedSparseGraph§eidx: Vec<(usize, usize)>§par: Vec<usize>§epos: usize

Implementations§

Source §

impl<'a> EulerTourForEdge<'a>

Source

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

Examples found in repository ?

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

9pub fn grl_5_d(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, c: [SizedCollect<usize>]);
13    let edges = c
14        .take(n)
15        .enumerate()
16        .flat_map(|(u, it)| it.into_iter().map(move |v| (u, v)))
17        .collect();
18    let graph = UndirectedSparseGraph::from_edges(n, edges);
19    let et = EulerTourForEdge::new(0, &graph);
20    let mut bit = BinaryIndexedTree::<AdditiveOperation<_>>::new(et.length());
21
22    scan!(scanner, q);
23    for _ in 0..q {
24        match scanner.scan::<usize>() {
25            0 => {
26                scan!(scanner, v, w: i64);
27                let (l, r) = et.eidx[et.par[v]];
28                bit.update(l, w);
29                bit.update(r, -w);
30            }
31            1 => {
32                scan!(scanner, u);
33                let ans = if u > 0 {
34                    bit.accumulate(et.eidx[et.par[u]].0)
35                } else {
36                    0
37                };
38                writeln!(writer, "{}", ans).ok();
39            }
40            _ => unreachable!("unknown query"),
41        }
42    }
43}

Source

pub fn length(&self) -> usize

Examples found in repository ?

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

9pub fn grl_5_d(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, c: [SizedCollect<usize>]);
13    let edges = c
14        .take(n)
15        .enumerate()
16        .flat_map(|(u, it)| it.into_iter().map(move |v| (u, v)))
17        .collect();
18    let graph = UndirectedSparseGraph::from_edges(n, edges);
19    let et = EulerTourForEdge::new(0, &graph);
20    let mut bit = BinaryIndexedTree::<AdditiveOperation<_>>::new(et.length());
21
22    scan!(scanner, q);
23    for _ in 0..q {
24        match scanner.scan::<usize>() {
25            0 => {
26                scan!(scanner, v, w: i64);
27                let (l, r) = et.eidx[et.par[v]];
28                bit.update(l, w);
29                bit.update(r, -w);
30            }
31            1 => {
32                scan!(scanner, u);
33                let ans = if u > 0 {
34                    bit.accumulate(et.eidx[et.par[u]].0)
35                } else {
36                    0
37                };
38                writeln!(writer, "{}", ans).ok();
39            }
40            _ => unreachable!("unknown query"),
41        }
42    }
43}

Source

fn edge_tour(&mut self, u: usize, p: usize)

Examples found in repository ?

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

15    pub fn new(root: usize, graph: &'a UndirectedSparseGraph) -> Self {
16        let mut self_ = Self {
17            graph,
18            eidx: vec![(0, 0); graph.vertices_size() - 1],
19            par: vec![usize::MAX; graph.vertices_size()],
20            epos: 0,
21        };
22        self_.edge_tour(root, usize::MAX);
23        self_
24    }
25    pub fn length(&self) -> usize {
26        self.epos
27    }
28    fn edge_tour(&mut self, u: usize, p: usize) {
29        for a in self.graph.adjacencies(u).filter(|a| a.to != p) {
30            self.par[a.to] = a.id;
31            self.eidx[a.id].0 = self.epos;
32            self.epos += 1;
33            self.edge_tour(a.to, u);
34            self.eidx[a.id].1 = self.epos;
35            self.epos += 1;
36        }
37    }