Struct XorLinkedRootedTreeBuilder 

pub struct XorLinkedRootedTreeBuilder<P = NoParent, D = NoDfsPreorder, H = NoDepth, PE = NoParentEdge, EC = NoEdgeChild, X = NoXorBottomUpOrder, B = NoXorBottomUpOrder, E = NoEIndexed> {
    n: usize,
    _marker: PhantomData<fn() -> ((P, D, H), (PE, EC), (X, B, E))>,
}

Fields

n: usize

_marker: PhantomData<fn() -> ((P, D, H), (PE, EC), (X, B, E))>

Implementations

impl<P, D, H, PE, EC, X, B, E> XorLinkedRootedTreeBuilder<P, D, H, PE, EC, X, B, E>

pub fn with_parent( self, ) -> XorLinkedRootedTreeBuilder<RecordParent, D, H, PE, EC, X, B, E>

pub fn with_dfs_preorder( self, ) -> XorLinkedRootedTreeBuilder<P, RecordDfsPreorder, H, PE, EC, X, RecordXorBottomUpOrder, E>

Examples found in repository

crates/library_checker/src/tree/vertex_add_subtree_sum.rs (line 21)

pub fn vertex_add_subtree_sum(reader: impl Read, writer: impl Write) {
    prepare_io!(reader, writer);
    sc!(n, q, a: [u64; n], p: [usize; iter n - 1]);
    let tree = XorLinkedRootedTree::builder(n)
        .with_dfs_preorder()
        .build_from_ordered_parents(p);
    let b: Vec<_> = tree.dfs_order().iter().map(|&v| a[v]).collect();
    let mut seg = DaryPrefixSumTreeU64::from_slice(&b);
    for _ in 0..q {
        sc!(query: Query);
        match query {
            Query::Add { u, x } => seg.update(tree.dfs_index(u), x),
            Query::Sum { u } => {
                let range = tree.subtree_range(u);
                pp!(seg.fold(range.start, range.end));
            }
        }
    }
}

pub fn with_depth( self, ) -> XorLinkedRootedTreeBuilder<P, D, RecordDepth, PE, EC, X, RecordXorBottomUpOrder, E>

pub fn with_xor_bottom_up_order( self, ) -> XorLinkedRootedTreeBuilder<P, D, H, PE, EC, RecordXorBottomUpOrder, RecordXorBottomUpOrder, E>

impl<P, D, H, X, B> XorLinkedRootedTreeBuilder<P, D, H, NoParentEdge, NoEdgeChild, X, B, NoEIndexed>

pub fn with_eindexed( self, ) -> XorLinkedRootedTreeBuilder<P, D, H, NoParentEdge, NoEdgeChild, X, B, EIndexed>

Examples found in repository

crates/library_checker/src/tree/tree_diameter.rs (line 11)

pub fn tree_diameter(reader: impl Read, writer: impl Write) {
    prepare_io!(reader, writer);
    sc!(n, edges: [(u32, u32, u64); n - 1]);
    let mut parent = vec![n as u32; n];
    let mut farthest: Vec<_> = (0..n).map(|u| (0, u)).collect();
    let (mut diameter, mut left, mut right, mut center) = (0, 0, 0, 0);
    XorLinkedRootedTree::builder(n).with_eindexed().run(
        0,
        edges.iter().map(|&(u, v, _)| (u as usize, v as usize)),
        |u, p, e| {
            parent[u] = p as u32;
            let distance = farthest[u].0 + edges[e].2;
            if diameter < distance + farthest[p].0 {
                diameter = distance + farthest[p].0;
                left = farthest[u].1;
                right = farthest[p].1;
                center = p;
            }
            if farthest[p].0 < distance {
                farthest[p] = (distance, farthest[u].1);
            }
        },
    );
    let mut path = Vec::new();
    while left != center {
        path.push(left);
        left = parent[left] as usize;
    }
    path.push(center);
    let middle = path.len();
    while right != center {
        path.push(right);
        right = parent[right] as usize;
    }
    path[middle..].reverse();
    pp!(diameter, path.len(); @it path);
}

impl<P, D, H, PE, EC, X, B> XorLinkedRootedTreeBuilder<P, D, H, PE, EC, X, B, EIndexed>

pub fn with_parent_edge( self, ) -> XorLinkedRootedTreeBuilder<P, D, H, RecordParentEdge, EC, X, B, EIndexed>

pub fn with_edge_child( self, ) -> XorLinkedRootedTreeBuilder<P, D, H, PE, RecordEdgeChild, X, B, EIndexed>

impl<P, D, H, X, B> XorLinkedRootedTreeBuilder<P, D, H, NoParentEdge, NoEdgeChild, X, B, NoEIndexed>

where P: ParentComponent, D: DfsPreorderComponent, H: DepthComponent, X: BuildXorBottomUpOrder<B>, B: XorBottomUpOrderBuffer,

pub fn build_from_ordered_parents( self, parents: impl IntoIterator<Item = usize>, ) -> XorLinkedRootedTree<P, D, H, NoParentEdge, NoEdgeChild, X>

Builds a tree rooted at 0. The n - 1 parents are in vertex order, and the parent of vertex v must be less than v.

Examples found in repository

crates/library_checker/src/tree/vertex_add_subtree_sum.rs (line 22)

pub fn vertex_add_subtree_sum(reader: impl Read, writer: impl Write) {
    prepare_io!(reader, writer);
    sc!(n, q, a: [u64; n], p: [usize; iter n - 1]);
    let tree = XorLinkedRootedTree::builder(n)
        .with_dfs_preorder()
        .build_from_ordered_parents(p);
    let b: Vec<_> = tree.dfs_order().iter().map(|&v| a[v]).collect();
    let mut seg = DaryPrefixSumTreeU64::from_slice(&b);
    for _ in 0..q {
        sc!(query: Query);
        match query {
            Query::Add { u, x } => seg.update(tree.dfs_index(u), x),
            Query::Sum { u } => {
                let range = tree.subtree_range(u);
                pp!(seg.fold(range.start, range.end));
            }
        }
    }
}

pub fn build<I>( self, root: usize, edges: I, ) -> XorLinkedRootedTree<P, D, H, NoParentEdge, NoEdgeChild, X>

where I: IntoIterator<Item = (usize, usize)>,

impl<P, D, H, PE, EC, X, B> XorLinkedRootedTreeBuilder<P, D, H, PE, EC, X, B, EIndexed>

where P: ParentComponent, D: DfsPreorderComponent, H: DepthComponent, PE: ParentEdgeComponent, EC: EdgeChildComponent, X: BuildXorBottomUpOrder<B>, B: XorBottomUpOrderBuffer,

pub fn build<I>( self, root: usize, edges: I, ) -> XorLinkedRootedTree<P, D, H, PE, EC, X>

where I: IntoIterator<Item = (usize, usize)>,

impl XorLinkedRootedTreeBuilder

pub fn run<I, F>(self, root: usize, edges: I, f: F)

where I: IntoIterator<Item = (usize, usize)>, F: FnMut(usize, usize),

impl XorLinkedRootedTreeBuilder<NoParent, NoDfsPreorder, NoDepth, NoParentEdge, NoEdgeChild, NoXorBottomUpOrder, NoXorBottomUpOrder, EIndexed>

pub fn run<I, F>(self, root: usize, edges: I, f: F)

where I: IntoIterator<Item = (usize, usize)>, F: FnMut(usize, usize, usize),

Examples found in repository

crates/library_checker/src/tree/tree_diameter.rs (lines 11-27)

pub fn tree_diameter(reader: impl Read, writer: impl Write) {
    prepare_io!(reader, writer);
    sc!(n, edges: [(u32, u32, u64); n - 1]);
    let mut parent = vec![n as u32; n];
    let mut farthest: Vec<_> = (0..n).map(|u| (0, u)).collect();
    let (mut diameter, mut left, mut right, mut center) = (0, 0, 0, 0);
    XorLinkedRootedTree::builder(n).with_eindexed().run(
        0,
        edges.iter().map(|&(u, v, _)| (u as usize, v as usize)),
        |u, p, e| {
            parent[u] = p as u32;
            let distance = farthest[u].0 + edges[e].2;
            if diameter < distance + farthest[p].0 {
                diameter = distance + farthest[p].0;
                left = farthest[u].1;
                right = farthest[p].1;
                center = p;
            }
            if farthest[p].0 < distance {
                farthest[p] = (distance, farthest[u].1);
            }
        },
    );
    let mut path = Vec::new();
    while left != center {
        path.push(left);
        left = parent[left] as usize;
    }
    path.push(center);
    let middle = path.len();
    while right != center {
        path.push(right);
        right = parent[right] as usize;
    }
    path[middle..].reverse();
    pp!(diameter, path.len(); @it path);
}