Struct TreeGraphScanner

Source

pub struct TreeGraphScanner<U, T = ()>where
    U: IterScan<Output = usize>,
    T: IterScan,
{ /* private fields */ }

Implementations§

Source §

impl<U, T> TreeGraphScanner<U, T>
where U: IterScan<Output = usize>, T: IterScan,

Source

pub fn new(vsize: usize) -> Self

Examples found in repository ?

crates/aizu_online_judge/src/grl/grl_5_b.rs (line 9)

6pub fn grl_5_b(reader: impl Read, mut writer: impl Write) {
7    let s = read_all_unchecked(reader);
8    let mut scanner = Scanner::new(&s);
9    scan!(scanner, n, (graph, w): @TreeGraphScanner::<usize, u64>::new(n));
10    let re = ReRooting::<MaxOperation<u64>, _>::new(&graph, |d, _vid, eid_opt| {
11        d + eid_opt.map_or(0, |eid| w[eid])
12    });
13    iter_print!(writer, @sep '\n', @it re.dp);
14}

More examples

Hide additional examples

crates/aizu_online_judge/src/grl/grl_5_a.rs (line 9)

6pub fn grl_5_a(reader: impl Read, mut writer: impl Write) {
7    let s = read_all_unchecked(reader);
8    let mut scanner = Scanner::new(&s);
9    scan!(scanner, n, (graph, w): @TreeGraphScanner::<usize, u64>::new(n));
10    let d = graph.weighted_tree_depth::<AdditiveOperation<_>, _>(0, |eid| w[eid]);
11    let r = (0..n).max_by_key(|&u| d[u]).unwrap();
12    let ans = graph
13        .weighted_tree_depth::<AdditiveOperation<_>, _>(r, |eid| w[eid])
14        .into_iter()
15        .max()
16        .unwrap();
17    writeln!(writer, "{}", ans).ok();
18}

crates/library_checker/src/datastructure/vertex_add_path_sum.rs (line 12)

9pub fn vertex_add_path_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: [i64; n], (mut graph, _): @TreeGraphScanner::<usize, ()>::new(n));
13    let hld = HeavyLightDecomposition::new(0, &mut graph);
14    let mut bit = BinaryIndexedTree::<AdditiveOperation<_>>::new(n);
15    for (i, a) in a.iter().cloned().enumerate() {
16        bit.update(hld.vidx[i], a);
17    }
18    for _ in 0..q {
19        match scanner.scan::<usize>() {
20            0 => {
21                scan!(scanner, p, x: i64);
22                bit.update(hld.vidx[p], x);
23            }
24            1 => {
25                scan!(scanner, u, v);
26                writeln!(
27                    writer,
28                    "{}",
29                    hld.query::<AdditiveOperation<_>, _>(u, v, false, |l, r| bit.fold(l, r))
30                )
31                .ok();
32            }
33            _ => panic!("unknown query"),
34        }
35    }
36}

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

12pub fn vertex_set_path_composite(reader: impl Read, mut writer: impl Write) {
13    let s = read_all_unchecked(reader);
14    let mut scanner = Scanner::new(&s);
15    scan!(scanner, n, q, ab: [(MInt998244353, MInt998244353); n], (mut graph, _): @TreeGraphScanner::<usize, ()>::new(n));
16    let hld = HeavyLightDecomposition::new(0, &mut graph);
17    let mut nab = vec![(MInt998244353::default(), MInt998244353::default()); n];
18    for i in 0..n {
19        nab[hld.vidx[i]] = ab[i];
20    }
21    let mut seg1 = SegmentTree::<LinearOperation<_>>::from_vec(nab.clone());
22    let mut seg2 = SegmentTree::<ReverseOperation<LinearOperation<_>>>::from_vec(nab);
23    for _ in 0..q {
24        match scanner.scan::<usize>() {
25            0 => {
26                scan!(scanner, p, cd: (MInt998244353, MInt998244353));
27                seg1.set(hld.vidx[p], cd);
28                seg2.set(hld.vidx[p], cd);
29            }
30            1 => {
31                scan!(scanner, u, v, x: MInt998244353);
32                let (a, b) = hld.query_noncom::<LinearOperation<_>, _, _>(
33                    u,
34                    v,
35                    false,
36                    |l, r| seg1.fold(l..r),
37                    |l, r| seg2.fold(l..r),
38                );
39                writeln!(writer, "{}", a * x + b).ok();
40            }
41            _ => panic!("unknown query"),
42        }
43    }
44}