Struct TreeGraphScanner 

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

Fields

vsize: usize

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

Implementations

impl<U, T> TreeGraphScanner<U, T>

where U: Scan<Output = usize>, T: Scan,

pub fn new(vsize: usize) -> Self

Examples found in repository

crates/library_checker/src/tree/frequency_table_of_tree_distance.rs (line 7)

pub fn frequency_table_of_tree_distance(reader: impl Read, writer: impl Write) {
    prepare_io!(reader, writer);
    sc!(n, (g, _): @TreeGraphScanner::<usize>::new(n));
    let freqs = g.distance_frequencies();
    pp!(@it freqs[1..].iter().map(|&f| f / 2));
}

crates/library_checker/src/tree/jump_on_tree.rs (line 7)

pub fn jump_on_tree(reader: impl Read, writer: impl Write) {
    prepare_io!(reader, writer);
    sc!(n, q, (g, _): @TreeGraphScanner::<usize>::new(n));
    let hld = g.hld(0);
    for _ in 0..q {
        sc!(s, t, i);
        pp!(hld.jump(s, t, i).unwrap_or(!0) as isize);
    }
}

#[verify::library_checker("jump_on_tree")]
pub fn jump_on_tree_level_ancestor(reader: impl Read, writer: impl Write) {
    prepare_io!(reader, writer);
    sc!(n, q, (g, _): @TreeGraphScanner::<usize>::new(n));
    let la = g.level_ancestor(0);
    let lca = g.lca(0);
    for _ in 0..q {
        sc!(s, t, i);
        let l = lca.lca(s, t);
        let dl = la.depth(l);
        let ds = la.depth(s) - dl;
        let dt = la.depth(t) - dl;
        let ans = if i <= ds {
            la.la(s, i)
        } else if i <= ds + dt {
            la.la(t, ds + dt - i)
        } else {
            None
        };
        pp!(ans.unwrap_or(!0) as isize);
    }
}

#[verify::library_checker("jump_on_tree")]
pub fn jump_on_tree_level_ancestor_batch(reader: impl Read, writer: impl Write) {
    prepare_io!(reader, writer);
    sc!(n, q, (g, _): @TreeGraphScanner::<usize>::new(n), queries: [(usize, usize, usize); iter q]);
    let lca = g.lca(0);
    let results = g.level_ancestor_batch(
        0,
        queries.map(|(s, t, i)| {
            let l = lca.lca(s, t);
            let dl = lca.depth(l);
            let ds = lca.depth(s) - dl;
            let dt = lca.depth(t) - dl;
            if i <= ds {
                (s, i)
            } else if i <= ds + dt {
                (t, ds + dt - i)
            } else {
                (0, n)
            }
        }),
    );
    pp!(@lf @it results.iter().map(|&v| v.unwrap_or(!0) as isize));
}

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

pub fn grl_5_b(reader: impl Read, writer: impl Write) {
    prepare_io!(reader, writer);
    sc!(n, (graph, w): @TreeGraphScanner::<usize, u64>::new(n));
    let re = ReRooting::<MaxOperation<u64>, _>::new(&graph, |d, _vid, eid_opt| {
        d + eid_opt.map_or(0, |eid| w[eid])
    });
    pp!(@lf @it re.dp);
}

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

pub fn grl_5_a(reader: impl Read, writer: impl Write) {
    prepare_io!(reader, writer);
    sc!(n, (graph, w): @TreeGraphScanner::<usize, u64>::new(n));
    let d = graph.weighted_tree_depth::<AdditiveOperation<_>, _>(0, |eid| w[eid]);
    let r = (0..n).max_by_key(|&u| d[u]).unwrap();
    let ans = graph
        .weighted_tree_depth::<AdditiveOperation<_>, _>(r, |eid| w[eid])
        .into_iter()
        .max()
        .unwrap();
    pp!(ans);
}

crates/library_checker/src/tree/vertex_set_path_composite.rs (line 16)

pub fn vertex_set_path_composite(reader: impl Read, writer: impl Write) {
    prepare_io!(reader, writer);
    sc!(n, q, ab: [(M, M); n], (graph, _): @TreeGraphScanner::<usize, ()>::new(n));
    let hld = graph.hld(0);
    let mut fold = hld.build_fold::<LinearOperation<_>>(&ab);
    for _ in 0..q {
        sc!(query: Query);
        match query {
            Query::Set { p, cd } => {
                fold.set(p, cd);
            }
            Query::Apply { u, v, x } => {
                let (a, b) = fold.fold_vertices(u, v);
                pp!(a * x + b);
            }
        }
    }
}

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

pub fn point_set_tree_path_composite_sum_fixed_root(reader: impl Read, writer: impl Write) {
    prepare_io!(reader, writer);
    sc!(n,
        q,
        value: [M; n],
        (graph, edges): @TreeGraphScanner::<usize, (M, M)>::new(n));

    let top_tree = graph.static_top_tree(0);
    let mut dp = top_tree.dp::<Dp>(value, edges);

    for _ in 0..q {
        sc!(query: Query);
        match query {
            Query::SetVertex { v, x } => {
                dp.set_vertex(v, x);
                pp!(dp.fold_all().sum);
            }
            Query::SetEdge { e, a, b } => {
                dp.set_edge(e, (a, b));
                pp!(dp.fold_all().sum);
            }
        }
    }
}

Additional examples can be found in:

• crates/library_checker/src/tree/tree_path_composite_sum.rs
• crates/library_checker/src/tree/point_set_tree_path_composite_sum.rs
• crates/library_checker/src/tree/vertex_get_range_contour_add_on_tree.rs
• crates/library_checker/src/tree/vertex_add_range_contour_sum_on_tree.rs

Trait Implementations

impl<U, T> MarkedScan for TreeGraphScanner<U, T>

where U: Scan<Output = usize>, T: Scan,

type Output = (SparseGraph<UndirectedEdge>, Vec<<T as Scan>::Output>)

fn mscan<I: ScanSource>(self, iter: &mut I) -> Option<Self::Output>