Struct XorLinkedRootedTree 

pub struct XorLinkedRootedTree<P = NoParent, D = NoDfsPreorder, H = NoDepth, PE = NoParentEdge, EC = NoEdgeChild, X = NoXorBottomUpOrder>
where
    P: ParentComponent,
    D: DfsPreorderComponent,
    H: DepthComponent,
    PE: ParentEdgeComponent,
    EC: EdgeChildComponent,
    X: XorBottomUpOrderComponent,
{
    n: usize,
    root: usize,
    parent: P::Data,
    dfs: D::Data,
    depth: H::Data,
    parent_edge: PE::Data,
    edge_child: EC::Data,
    xor_order: X::Data,
    _marker: PhantomData<fn() -> (P, D, H, PE, EC, X)>,
}

Fields

n: usize

root: usize

parent: P::Data

dfs: D::Data

depth: H::Data

parent_edge: PE::Data

edge_child: EC::Data

xor_order: X::Data

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

Implementations

impl XorLinkedRootedTree

pub fn builder(n: usize) -> XorLinkedRootedTreeBuilder

Examples found in repository

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

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));
            }
        }
    }
}

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, O> XorLinkedRootedTree<P, D, H, PE, EC, O>

where P: ParentComponent, D: DfsPreorderComponent, H: DepthComponent, PE: ParentEdgeComponent, EC: EdgeChildComponent, O: XorBottomUpOrderComponent,

pub fn vertices_size(&self) -> usize

pub fn edges_size(&self) -> usize

pub fn root(&self) -> usize

impl<D, H, PE, EC, O> XorLinkedRootedTree<RecordParent, D, H, PE, EC, O>

where D: DfsPreorderComponent, H: DepthComponent, PE: ParentEdgeComponent, EC: EdgeChildComponent, O: XorBottomUpOrderComponent,

pub fn parent(&self, v: usize) -> usize

pub fn parents(&self) -> &[usize]

Examples found in repository

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

pub fn vertex_add_path_sum(reader: impl Read, writer: impl Write) {
    prepare_io!(reader, writer);
    sc!(n, q, mut a: [i64; n],
        (tree, _): @XorLinkedRootedTreeScanner::<usize, ()>::new(n, 0)
            .with_parent().with_dfs_preorder());
    let lca = LowestCommonAncestor::from_dfs_preorder(tree.parents(), tree.dfs_order());
    let mut values = vec![0; n + 1];
    for (u, &x) in a.iter().enumerate() {
        let range = tree.subtree_range(u);
        values[range.start] += x;
        values[range.end] -= x;
    }
    let mut bit = BinaryIndexedTree::<AdditiveOperation<_>>::from_slice(&values);
    for _ in 0..q {
        sc!(query: Query);
        match query {
            Query::Add { p, x } => {
                a[p] += x;
                let range = tree.subtree_range(p);
                bit.update(range.start, x);
                bit.update(range.end, -x);
            }
            Query::Sum { u, v } => {
                let p = lca.lca(u, v);
                pp!(
                    a[p] + bit.accumulate(tree.dfs_index(u)) + bit.accumulate(tree.dfs_index(v))
                        - 2 * bit.accumulate(tree.dfs_index(p))
                );
            }
        }
    }
}

impl<P, D, H, PE, EC> XorLinkedRootedTree<P, D, H, PE, EC, RecordXorBottomUpOrder>

where P: ParentComponent, D: DfsPreorderComponent, H: DepthComponent, PE: ParentEdgeComponent, EC: EdgeChildComponent,

pub fn xor_bottom_up_order(&self) -> &[usize]

Returns the bottom-up XOR order, excluding the root.

pub fn xor_top_down_order( &self, ) -> impl DoubleEndedIterator<Item = usize> + ExactSizeIterator + '_

Returns the top-down XOR order, excluding the root.

impl<P, H, PE, EC, O> XorLinkedRootedTree<P, RecordDfsPreorder, H, PE, EC, O>

where P: ParentComponent, H: DepthComponent, PE: ParentEdgeComponent, EC: EdgeChildComponent, O: XorBottomUpOrderComponent,

pub fn dfs_order(&self) -> &[usize]

Examples found in repository

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

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));
            }
        }
    }
}

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

pub fn vertex_add_path_sum(reader: impl Read, writer: impl Write) {
    prepare_io!(reader, writer);
    sc!(n, q, mut a: [i64; n],
        (tree, _): @XorLinkedRootedTreeScanner::<usize, ()>::new(n, 0)
            .with_parent().with_dfs_preorder());
    let lca = LowestCommonAncestor::from_dfs_preorder(tree.parents(), tree.dfs_order());
    let mut values = vec![0; n + 1];
    for (u, &x) in a.iter().enumerate() {
        let range = tree.subtree_range(u);
        values[range.start] += x;
        values[range.end] -= x;
    }
    let mut bit = BinaryIndexedTree::<AdditiveOperation<_>>::from_slice(&values);
    for _ in 0..q {
        sc!(query: Query);
        match query {
            Query::Add { p, x } => {
                a[p] += x;
                let range = tree.subtree_range(p);
                bit.update(range.start, x);
                bit.update(range.end, -x);
            }
            Query::Sum { u, v } => {
                let p = lca.lca(u, v);
                pp!(
                    a[p] + bit.accumulate(tree.dfs_index(u)) + bit.accumulate(tree.dfs_index(v))
                        - 2 * bit.accumulate(tree.dfs_index(p))
                );
            }
        }
    }
}

pub fn dfs_index(&self, v: usize) -> usize

Examples found in repository

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

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));
            }
        }
    }
}

crates/library_checker/src/tree/vertex_add_path_sum.rs (line 41)

pub fn vertex_add_path_sum(reader: impl Read, writer: impl Write) {
    prepare_io!(reader, writer);
    sc!(n, q, mut a: [i64; n],
        (tree, _): @XorLinkedRootedTreeScanner::<usize, ()>::new(n, 0)
            .with_parent().with_dfs_preorder());
    let lca = LowestCommonAncestor::from_dfs_preorder(tree.parents(), tree.dfs_order());
    let mut values = vec![0; n + 1];
    for (u, &x) in a.iter().enumerate() {
        let range = tree.subtree_range(u);
        values[range.start] += x;
        values[range.end] -= x;
    }
    let mut bit = BinaryIndexedTree::<AdditiveOperation<_>>::from_slice(&values);
    for _ in 0..q {
        sc!(query: Query);
        match query {
            Query::Add { p, x } => {
                a[p] += x;
                let range = tree.subtree_range(p);
                bit.update(range.start, x);
                bit.update(range.end, -x);
            }
            Query::Sum { u, v } => {
                let p = lca.lca(u, v);
                pp!(
                    a[p] + bit.accumulate(tree.dfs_index(u)) + bit.accumulate(tree.dfs_index(v))
                        - 2 * bit.accumulate(tree.dfs_index(p))
                );
            }
        }
    }
}

pub fn subtree_size(&self, v: usize) -> usize

pub fn subtree_range(&self, v: usize) -> Range<usize>

Examples found in repository

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

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));
            }
        }
    }
}

crates/library_checker/src/tree/vertex_add_path_sum.rs (line 24)

pub fn vertex_add_path_sum(reader: impl Read, writer: impl Write) {
    prepare_io!(reader, writer);
    sc!(n, q, mut a: [i64; n],
        (tree, _): @XorLinkedRootedTreeScanner::<usize, ()>::new(n, 0)
            .with_parent().with_dfs_preorder());
    let lca = LowestCommonAncestor::from_dfs_preorder(tree.parents(), tree.dfs_order());
    let mut values = vec![0; n + 1];
    for (u, &x) in a.iter().enumerate() {
        let range = tree.subtree_range(u);
        values[range.start] += x;
        values[range.end] -= x;
    }
    let mut bit = BinaryIndexedTree::<AdditiveOperation<_>>::from_slice(&values);
    for _ in 0..q {
        sc!(query: Query);
        match query {
            Query::Add { p, x } => {
                a[p] += x;
                let range = tree.subtree_range(p);
                bit.update(range.start, x);
                bit.update(range.end, -x);
            }
            Query::Sum { u, v } => {
                let p = lca.lca(u, v);
                pp!(
                    a[p] + bit.accumulate(tree.dfs_index(u)) + bit.accumulate(tree.dfs_index(v))
                        - 2 * bit.accumulate(tree.dfs_index(p))
                );
            }
        }
    }
}

pub fn children(&self, v: usize) -> Children<'_>

impl<P, D, PE, EC, O> XorLinkedRootedTree<P, D, RecordDepth, PE, EC, O>

where P: ParentComponent, D: DfsPreorderComponent, PE: ParentEdgeComponent, EC: EdgeChildComponent, O: XorBottomUpOrderComponent,

pub fn depth(&self, v: usize) -> usize

pub fn depths(&self) -> &[usize]

impl<P, D, H, EC, O> XorLinkedRootedTree<P, D, H, RecordParentEdge, EC, O>

where P: ParentComponent, D: DfsPreorderComponent, H: DepthComponent, EC: EdgeChildComponent, O: XorBottomUpOrderComponent,

pub fn parent_edge(&self, v: usize) -> usize

pub fn parent_edges(&self) -> &[usize]

impl<P, D, H, PE, O> XorLinkedRootedTree<P, D, H, PE, RecordEdgeChild, O>

where P: ParentComponent, D: DfsPreorderComponent, H: DepthComponent, PE: ParentEdgeComponent, O: XorBottomUpOrderComponent,

pub fn edge_child(&self, eid: usize) -> usize

pub fn edge_children(&self) -> &[usize]