Struct EulerTourForEdge

Source

pub struct EulerTourForEdge<'a> {
    pub eidx: Vec<(usize, usize)>,
    pub par: Vec<usize>,
    /* private fields */
}

Fields§

§eidx: Vec<(usize, usize)>§par: Vec<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            _ => panic!("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            _ => panic!("unknown query"),
41        }
42    }
43}