Struct TreeGraphScanner

Source

pub struct TreeGraphScanner<U, T = ()>where
    U: IterScan<Output = usize>,
    T: IterScan,{
    vsize: usize,
    _marker: PhantomData<fn() -> (U, T)>,
}

Fields§

§vsize: usize§_marker: PhantomData<fn() -> (U, T)>

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/library_checker/src/tree/frequency_table_of_tree_distance.rs (line 9)

6pub fn frequency_table_of_tree_distance(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, (g, _): @TreeGraphScanner::<usize>::new(n));
10    let freqs = g.distance_frequencies();
11    iter_print!(writer, @it freqs[1..].iter().map(|&f| f / 2));
12}

More examples

Hide additional examples

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}

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/tree/jump_on_tree.rs (line 9)

6pub fn jump_on_tree(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, q, (g, _): @TreeGraphScanner::<usize>::new(n));
10    let la = g.level_ancestor(0);
11    let lca = g.lca(0);
12    for _ in 0..q {
13        scan!(scanner, s, t, i);
14        let l = lca.lca(s, t);
15        let ds = la.depth(s) - la.depth(l);
16        let dt = la.depth(t) - la.depth(l);
17        let ans = if i <= ds {
18            la.la(s, i)
19        } else if i <= ds + dt {
20            la.la(t, ds + dt - i)
21        } else {
22            None
23        };
24        writeln!(writer, "{}", ans.unwrap_or(!0) as isize).ok();
25    }
26}
27
28#[verify::library_checker("jump_on_tree")]
29pub fn jump_on_tree_batch(reader: impl Read, mut writer: impl Write) {
30    let s = read_all_unchecked(reader);
31    let mut scanner = Scanner::new(&s);
32    scan!(scanner, n, q, (g, _): @TreeGraphScanner::<usize>::new(n), queries: [(usize, usize, usize)]);
33    let lca = g.lca(0);
34    let depth = g.tree_depth(0);
35    let results = g.level_ancestor_batch(
36        0,
37        queries.take(q).map(|(s, t, i)| {
38            let l = lca.lca(s, t);
39            let ds = (depth[s] - depth[l]) as usize;
40            let dt = (depth[t] - depth[l]) as usize;
41            if i <= ds {
42                (s, i)
43            } else if i <= ds + dt {
44                (t, ds + dt - i)
45            } else {
46                (0, n)
47            }
48        }),
49    );
50    iter_print!(writer, @lf @it results.iter().map(|&v| v.unwrap_or(!0) as isize));
51}

crates/library_checker/src/tree/point_set_tree_path_composite_sum_fixed_root.rs (line 114)

106pub fn point_set_tree_path_composite_sum_fixed_root(reader: impl Read, mut writer: impl Write) {
107    let s = read_all_unchecked(reader);
108    let mut scanner = Scanner::new(&s);
109    scan!(
110        scanner,
111        n,
112        q,
113        value: [MInt; n],
114        (graph, edges): @TreeGraphScanner::<usize, (MInt, MInt)>::new(n)
115    );
116
117    let top_tree = graph.static_top_tree(0);
118    let mut dp = top_tree.dp::<Dp>(value, edges);
119
120    for _ in 0..q {
121        scan!(scanner, query: Query);
122        match query {
123            Query::SetVertex { v, x } => {
124                dp.set_vertex(v, x);
125                writeln!(writer, "{}", dp.fold_all().sum).ok();
126            }
127            Query::SetEdge { e, a, b } => {
128                dp.set_edge(e, (a, b));
129                writeln!(writer, "{}", dp.fold_all().sum).ok();
130            }
131        }
132    }
133}

crates/library_checker/src/tree/point_set_tree_path_composite_sum.rs (line 148)

140pub fn point_set_tree_path_composite_sum(reader: impl Read, mut writer: impl Write) {
141    let s = read_all_unchecked(reader);
142    let mut scanner = Scanner::new(&s);
143    scan!(
144        scanner,
145        n,
146        q,
147        value: [MInt; n],
148        (graph, edges): @TreeGraphScanner::<usize, (MInt, MInt)>::new(n)
149    );
150
151    let top_tree = graph.static_top_tree(0);
152    let mut dp = top_tree.dp::<Dp>(value, edges);
153
154    for _ in 0..q {
155        scan!(scanner, query: Query);
156        match query {
157            Query::SetVertex { v, x, r } => {
158                dp.set_vertex(v, x);
159                writeln!(writer, "{}", dp.fold_path(r).reverse.sum).ok();
160            }
161            Query::SetEdge { e, a, b, r } => {
162                dp.set_edge(e, (a, b));
163                writeln!(writer, "{}", dp.fold_path(r).reverse.sum).ok();
164            }
165        }
166    }
167}