Struct XorEIndexedAccumulator

Source

struct XorEIndexedAccumulator {
    deg: Vec<isize>,
    xor: Vec<usize>,
    edge_xor: Vec<usize>,
}

Fields§

§deg: Vec<isize>§xor: Vec<usize>§edge_xor: Vec<usize>

Implementations§

Source §

impl XorEIndexedAccumulator

Source

fn new(n: usize) -> Self

Examples found in repository ?

crates/competitive/src/tree/xor_linked_tree.rs (line 393)

389    pub fn build<I>(self, root: usize, edges: I) -> XorLinkedRootedTree<P, D, H, PE, EC, X>
390    where
391        I: IntoIterator<Item = (usize, usize)>,
392    {
393        let mut acc = XorEIndexedAccumulator::new(self.n);
394        for (eid, (u, v)) in edges.into_iter().enumerate() {
395            acc.add_edge(eid, u, v);
396        }
397        finish_eindexed_accumulator::<P, D, H, PE, EC, X, B>(self.n, root, acc)
398    }
399}
400
401impl XorLinkedRootedTreeBuilder {
402    pub fn run<I, F>(self, root: usize, edges: I, f: F)
403    where
404        I: IntoIterator<Item = (usize, usize)>,
405        F: FnMut(usize, usize),
406    {
407        let mut acc = XorAccumulator::new(self.n);
408        for (u, v) in edges {
409            acc.add_edge(u, v);
410        }
411        let mut order = ();
412        acc.finish::<NoXorBottomUpOrder, _>(root, &mut order, f);
413    }
414}
415
416impl
417    XorLinkedRootedTreeBuilder<
418        NoParent,
419        NoDfsPreorder,
420        NoDepth,
421        NoParentEdge,
422        NoEdgeChild,
423        NoXorBottomUpOrder,
424        NoXorBottomUpOrder,
425        EIndexed,
426    >
427{
428    pub fn run<I, F>(self, root: usize, edges: I, f: F)
429    where
430        I: IntoIterator<Item = (usize, usize)>,
431        F: FnMut(usize, usize, usize),
432    {
433        let mut acc = XorEIndexedAccumulator::new(self.n);
434        for (eid, (u, v)) in edges.into_iter().enumerate() {
435            acc.add_edge(eid, u, v);
436        }
437        let mut order = ();
438        let mut edge_child = ();
439        acc.finish::<NoXorBottomUpOrder, NoEdgeChild, _>(root, &mut order, &mut edge_child, f);
440    }
441}
442
443impl<P, D, H, PE, EC, O> XorLinkedRootedTree<P, D, H, PE, EC, O>
444where
445    P: ParentComponent,
446    D: DfsPreorderComponent,
447    H: DepthComponent,
448    PE: ParentEdgeComponent,
449    EC: EdgeChildComponent,
450    O: XorBottomUpOrderComponent,
451{
452    pub fn vertices_size(&self) -> usize {
453        self.n
454    }
455    pub fn edges_size(&self) -> usize {
456        self.n.saturating_sub(1)
457    }
458    pub fn root(&self) -> usize {
459        self.root
460    }
461}
462
463impl<D, H, PE, EC, O> XorLinkedRootedTree<RecordParent, D, H, PE, EC, O>
464where
465    D: DfsPreorderComponent,
466    H: DepthComponent,
467    PE: ParentEdgeComponent,
468    EC: EdgeChildComponent,
469    O: XorBottomUpOrderComponent,
470{
471    pub fn parent(&self, v: usize) -> usize {
472        self.parent[v]
473    }
474    pub fn parents(&self) -> &[usize] {
475        &self.parent
476    }
477}
478
479impl<P, D, H, PE, EC> XorLinkedRootedTree<P, D, H, PE, EC, RecordXorBottomUpOrder>
480where
481    P: ParentComponent,
482    D: DfsPreorderComponent,
483    H: DepthComponent,
484    PE: ParentEdgeComponent,
485    EC: EdgeChildComponent,
486{
487    /// Returns the bottom-up XOR order, excluding the root.
488    pub fn xor_bottom_up_order(&self) -> &[usize] {
489        &self.xor_order
490    }
491    /// Returns the top-down XOR order, excluding the root.
492    pub fn xor_top_down_order(
493        &self,
494    ) -> impl DoubleEndedIterator<Item = usize> + ExactSizeIterator + '_ {
495        self.xor_order.iter().rev().copied()
496    }
497}
498
499impl<P, H, PE, EC, O> XorLinkedRootedTree<P, RecordDfsPreorder, H, PE, EC, O>
500where
501    P: ParentComponent,
502    H: DepthComponent,
503    PE: ParentEdgeComponent,
504    EC: EdgeChildComponent,
505    O: XorBottomUpOrderComponent,
506{
507    pub fn dfs_order(&self) -> &[usize] {
508        &self.dfs.order
509    }
510    pub fn dfs_index(&self, v: usize) -> usize {
511        self.dfs.preorder_index[v]
512    }
513    pub fn subtree_size(&self, v: usize) -> usize {
514        self.dfs.subtree_end[v] - self.dfs.preorder_index[v]
515    }
516    pub fn subtree_range(&self, v: usize) -> Range<usize> {
517        self.dfs.preorder_index[v]..self.dfs.subtree_end[v]
518    }
519    pub fn children(&self, v: usize) -> Children<'_> {
520        Children {
521            dfs: &self.dfs,
522            next: self.dfs.preorder_index[v] + 1,
523            end: self.dfs.subtree_end[v],
524        }
525    }
526}
527
528impl<P, D, PE, EC, O> XorLinkedRootedTree<P, D, RecordDepth, PE, EC, O>
529where
530    P: ParentComponent,
531    D: DfsPreorderComponent,
532    PE: ParentEdgeComponent,
533    EC: EdgeChildComponent,
534    O: XorBottomUpOrderComponent,
535{
536    pub fn depth(&self, v: usize) -> usize {
537        self.depth[v]
538    }
539    pub fn depths(&self) -> &[usize] {
540        &self.depth
541    }
542}
543
544impl<P, D, H, EC, O> XorLinkedRootedTree<P, D, H, RecordParentEdge, EC, O>
545where
546    P: ParentComponent,
547    D: DfsPreorderComponent,
548    H: DepthComponent,
549    EC: EdgeChildComponent,
550    O: XorBottomUpOrderComponent,
551{
552    pub fn parent_edge(&self, v: usize) -> usize {
553        self.parent_edge[v]
554    }
555    pub fn parent_edges(&self) -> &[usize] {
556        &self.parent_edge
557    }
558}
559
560impl<P, D, H, PE, O> XorLinkedRootedTree<P, D, H, PE, RecordEdgeChild, O>
561where
562    P: ParentComponent,
563    D: DfsPreorderComponent,
564    H: DepthComponent,
565    PE: ParentEdgeComponent,
566    O: XorBottomUpOrderComponent,
567{
568    pub fn edge_child(&self, eid: usize) -> usize {
569        self.edge_child[eid]
570    }
571    pub fn edge_children(&self) -> &[usize] {
572        &self.edge_child
573    }
574}
575
576pub struct Children<'a> {
577    dfs: &'a DfsPreorder,
578    next: usize,
579    end: usize,
580}
581
582impl Iterator for Children<'_> {
583    type Item = usize;
584    fn next(&mut self) -> Option<usize> {
585        if self.next == self.end {
586            None
587        } else {
588            let v = self.dfs.order[self.next];
589            self.next = self.dfs.subtree_end[v];
590            Some(v)
591        }
592    }
593}
594
595pub struct XorLinkedRootedTreeScanner<
596    U,
597    T = (),
598    P = NoParent,
599    D = NoDfsPreorder,
600    H = NoDepth,
601    PE = NoParentEdge,
602    EC = NoEdgeChild,
603    X = NoXorBottomUpOrder,
604    B = NoXorBottomUpOrder,
605    E = NoEIndexed,
606> where
607    U: Scan<Output = usize>,
608    T: Scan,
609{
610    n: usize,
611    root: usize,
612    _marker: ScannerMarker<U, T, P, D, H, PE, EC, X, B, E>,
613}
614
615impl<U, T> XorLinkedRootedTreeScanner<U, T>
616where
617    U: Scan<Output = usize>,
618    T: Scan,
619{
620    pub fn new(n: usize, root: usize) -> Self {
621        Self {
622            n,
623            root,
624            _marker: PhantomData,
625        }
626    }
627}
628
629impl<U, T, P, D, H, PE, EC, X, B, E> XorLinkedRootedTreeScanner<U, T, P, D, H, PE, EC, X, B, E>
630where
631    U: Scan<Output = usize>,
632    T: Scan,
633{
634    pub fn with_parent(
635        self,
636    ) -> XorLinkedRootedTreeScanner<U, T, RecordParent, D, H, PE, EC, X, B, E> {
637        XorLinkedRootedTreeScanner {
638            n: self.n,
639            root: self.root,
640            _marker: PhantomData,
641        }
642    }
643    pub fn with_dfs_preorder(
644        self,
645    ) -> XorLinkedRootedTreeScanner<
646        U,
647        T,
648        P,
649        RecordDfsPreorder,
650        H,
651        PE,
652        EC,
653        X,
654        RecordXorBottomUpOrder,
655        E,
656    > {
657        XorLinkedRootedTreeScanner {
658            n: self.n,
659            root: self.root,
660            _marker: PhantomData,
661        }
662    }
663    pub fn with_depth(
664        self,
665    ) -> XorLinkedRootedTreeScanner<U, T, P, D, RecordDepth, PE, EC, X, RecordXorBottomUpOrder, E>
666    {
667        XorLinkedRootedTreeScanner {
668            n: self.n,
669            root: self.root,
670            _marker: PhantomData,
671        }
672    }
673    pub fn with_xor_bottom_up_order(
674        self,
675    ) -> XorLinkedRootedTreeScanner<
676        U,
677        T,
678        P,
679        D,
680        H,
681        PE,
682        EC,
683        RecordXorBottomUpOrder,
684        RecordXorBottomUpOrder,
685        E,
686    > {
687        XorLinkedRootedTreeScanner {
688            n: self.n,
689            root: self.root,
690            _marker: PhantomData,
691        }
692    }
693}
694
695impl<U, T, P, D, H, X, B>
696    XorLinkedRootedTreeScanner<U, T, P, D, H, NoParentEdge, NoEdgeChild, X, B, NoEIndexed>
697where
698    U: Scan<Output = usize>,
699    T: Scan,
700{
701    pub fn with_eindexed(
702        self,
703    ) -> XorLinkedRootedTreeScanner<U, T, P, D, H, NoParentEdge, NoEdgeChild, X, B, EIndexed> {
704        XorLinkedRootedTreeScanner {
705            n: self.n,
706            root: self.root,
707            _marker: PhantomData,
708        }
709    }
710}
711
712impl<U, T, P, D, H, PE, EC, X, B> XorLinkedRootedTreeScanner<U, T, P, D, H, PE, EC, X, B, EIndexed>
713where
714    U: Scan<Output = usize>,
715    T: Scan,
716{
717    pub fn with_parent_edge(
718        self,
719    ) -> XorLinkedRootedTreeScanner<U, T, P, D, H, RecordParentEdge, EC, X, B, EIndexed> {
720        XorLinkedRootedTreeScanner {
721            n: self.n,
722            root: self.root,
723            _marker: PhantomData,
724        }
725    }
726    pub fn with_edge_child(
727        self,
728    ) -> XorLinkedRootedTreeScanner<U, T, P, D, H, PE, RecordEdgeChild, X, B, EIndexed> {
729        XorLinkedRootedTreeScanner {
730            n: self.n,
731            root: self.root,
732            _marker: PhantomData,
733        }
734    }
735}
736
737impl<U, T, P, D, H, X, B> MarkedScan
738    for XorLinkedRootedTreeScanner<U, T, P, D, H, NoParentEdge, NoEdgeChild, X, B, NoEIndexed>
739where
740    U: Scan<Output = usize>,
741    T: Scan,
742    P: ParentComponent,
743    D: DfsPreorderComponent,
744    H: DepthComponent,
745    X: BuildXorBottomUpOrder<B>,
746    B: XorBottomUpOrderBuffer,
747{
748    type Output = (
749        XorLinkedRootedTree<P, D, H, NoParentEdge, NoEdgeChild, X>,
750        Vec<<T as Scan>::Output>,
751    );
752
753    fn mscan<I: ScanSource>(self, iter: &mut I) -> Option<Self::Output> {
754        let mut acc = XorAccumulator::new(self.n);
755        let mut weights = Vec::with_capacity(self.n.saturating_sub(1));
756        for _ in 0..self.n.saturating_sub(1) {
757            let u = U::scan(iter)?;
758            let v = U::scan(iter)?;
759            acc.add_edge(u, v);
760            weights.push(T::scan(iter)?);
761        }
762        Some((
763            finish_accumulator::<P, D, H, X, B>(self.n, self.root, acc),
764            weights,
765        ))
766    }
767}
768
769impl<U, T, P, D, H, PE, EC, X, B> MarkedScan
770    for XorLinkedRootedTreeScanner<U, T, P, D, H, PE, EC, X, B, EIndexed>
771where
772    U: Scan<Output = usize>,
773    T: Scan,
774    P: ParentComponent,
775    D: DfsPreorderComponent,
776    H: DepthComponent,
777    PE: ParentEdgeComponent,
778    EC: EdgeChildComponent,
779    X: BuildXorBottomUpOrder<B>,
780    B: XorBottomUpOrderBuffer,
781{
782    type Output = (
783        XorLinkedRootedTree<P, D, H, PE, EC, X>,
784        Vec<<T as Scan>::Output>,
785    );
786
787    fn mscan<I: ScanSource>(self, iter: &mut I) -> Option<Self::Output> {
788        let mut acc = XorEIndexedAccumulator::new(self.n);
789        let mut weights = Vec::with_capacity(self.n.saturating_sub(1));
790        for eid in 0..self.n.saturating_sub(1) {
791            let u = U::scan(iter)?;
792            let v = U::scan(iter)?;
793            acc.add_edge(eid, u, v);
794            weights.push(T::scan(iter)?);
795        }
796        Some((
797            finish_eindexed_accumulator::<P, D, H, PE, EC, X, B>(self.n, self.root, acc),
798            weights,
799        ))
800    }

Source

fn add_edge(&mut self, eid: usize, u: usize, v: usize)

Examples found in repository ?

crates/competitive/src/tree/xor_linked_tree.rs (line 395)

389    pub fn build<I>(self, root: usize, edges: I) -> XorLinkedRootedTree<P, D, H, PE, EC, X>
390    where
391        I: IntoIterator<Item = (usize, usize)>,
392    {
393        let mut acc = XorEIndexedAccumulator::new(self.n);
394        for (eid, (u, v)) in edges.into_iter().enumerate() {
395            acc.add_edge(eid, u, v);
396        }
397        finish_eindexed_accumulator::<P, D, H, PE, EC, X, B>(self.n, root, acc)
398    }
399}
400
401impl XorLinkedRootedTreeBuilder {
402    pub fn run<I, F>(self, root: usize, edges: I, f: F)
403    where
404        I: IntoIterator<Item = (usize, usize)>,
405        F: FnMut(usize, usize),
406    {
407        let mut acc = XorAccumulator::new(self.n);
408        for (u, v) in edges {
409            acc.add_edge(u, v);
410        }
411        let mut order = ();
412        acc.finish::<NoXorBottomUpOrder, _>(root, &mut order, f);
413    }
414}
415
416impl
417    XorLinkedRootedTreeBuilder<
418        NoParent,
419        NoDfsPreorder,
420        NoDepth,
421        NoParentEdge,
422        NoEdgeChild,
423        NoXorBottomUpOrder,
424        NoXorBottomUpOrder,
425        EIndexed,
426    >
427{
428    pub fn run<I, F>(self, root: usize, edges: I, f: F)
429    where
430        I: IntoIterator<Item = (usize, usize)>,
431        F: FnMut(usize, usize, usize),
432    {
433        let mut acc = XorEIndexedAccumulator::new(self.n);
434        for (eid, (u, v)) in edges.into_iter().enumerate() {
435            acc.add_edge(eid, u, v);
436        }
437        let mut order = ();
438        let mut edge_child = ();
439        acc.finish::<NoXorBottomUpOrder, NoEdgeChild, _>(root, &mut order, &mut edge_child, f);
440    }
441}
442
443impl<P, D, H, PE, EC, O> XorLinkedRootedTree<P, D, H, PE, EC, O>
444where
445    P: ParentComponent,
446    D: DfsPreorderComponent,
447    H: DepthComponent,
448    PE: ParentEdgeComponent,
449    EC: EdgeChildComponent,
450    O: XorBottomUpOrderComponent,
451{
452    pub fn vertices_size(&self) -> usize {
453        self.n
454    }
455    pub fn edges_size(&self) -> usize {
456        self.n.saturating_sub(1)
457    }
458    pub fn root(&self) -> usize {
459        self.root
460    }
461}
462
463impl<D, H, PE, EC, O> XorLinkedRootedTree<RecordParent, D, H, PE, EC, O>
464where
465    D: DfsPreorderComponent,
466    H: DepthComponent,
467    PE: ParentEdgeComponent,
468    EC: EdgeChildComponent,
469    O: XorBottomUpOrderComponent,
470{
471    pub fn parent(&self, v: usize) -> usize {
472        self.parent[v]
473    }
474    pub fn parents(&self) -> &[usize] {
475        &self.parent
476    }
477}
478
479impl<P, D, H, PE, EC> XorLinkedRootedTree<P, D, H, PE, EC, RecordXorBottomUpOrder>
480where
481    P: ParentComponent,
482    D: DfsPreorderComponent,
483    H: DepthComponent,
484    PE: ParentEdgeComponent,
485    EC: EdgeChildComponent,
486{
487    /// Returns the bottom-up XOR order, excluding the root.
488    pub fn xor_bottom_up_order(&self) -> &[usize] {
489        &self.xor_order
490    }
491    /// Returns the top-down XOR order, excluding the root.
492    pub fn xor_top_down_order(
493        &self,
494    ) -> impl DoubleEndedIterator<Item = usize> + ExactSizeIterator + '_ {
495        self.xor_order.iter().rev().copied()
496    }
497}
498
499impl<P, H, PE, EC, O> XorLinkedRootedTree<P, RecordDfsPreorder, H, PE, EC, O>
500where
501    P: ParentComponent,
502    H: DepthComponent,
503    PE: ParentEdgeComponent,
504    EC: EdgeChildComponent,
505    O: XorBottomUpOrderComponent,
506{
507    pub fn dfs_order(&self) -> &[usize] {
508        &self.dfs.order
509    }
510    pub fn dfs_index(&self, v: usize) -> usize {
511        self.dfs.preorder_index[v]
512    }
513    pub fn subtree_size(&self, v: usize) -> usize {
514        self.dfs.subtree_end[v] - self.dfs.preorder_index[v]
515    }
516    pub fn subtree_range(&self, v: usize) -> Range<usize> {
517        self.dfs.preorder_index[v]..self.dfs.subtree_end[v]
518    }
519    pub fn children(&self, v: usize) -> Children<'_> {
520        Children {
521            dfs: &self.dfs,
522            next: self.dfs.preorder_index[v] + 1,
523            end: self.dfs.subtree_end[v],
524        }
525    }
526}
527
528impl<P, D, PE, EC, O> XorLinkedRootedTree<P, D, RecordDepth, PE, EC, O>
529where
530    P: ParentComponent,
531    D: DfsPreorderComponent,
532    PE: ParentEdgeComponent,
533    EC: EdgeChildComponent,
534    O: XorBottomUpOrderComponent,
535{
536    pub fn depth(&self, v: usize) -> usize {
537        self.depth[v]
538    }
539    pub fn depths(&self) -> &[usize] {
540        &self.depth
541    }
542}
543
544impl<P, D, H, EC, O> XorLinkedRootedTree<P, D, H, RecordParentEdge, EC, O>
545where
546    P: ParentComponent,
547    D: DfsPreorderComponent,
548    H: DepthComponent,
549    EC: EdgeChildComponent,
550    O: XorBottomUpOrderComponent,
551{
552    pub fn parent_edge(&self, v: usize) -> usize {
553        self.parent_edge[v]
554    }
555    pub fn parent_edges(&self) -> &[usize] {
556        &self.parent_edge
557    }
558}
559
560impl<P, D, H, PE, O> XorLinkedRootedTree<P, D, H, PE, RecordEdgeChild, O>
561where
562    P: ParentComponent,
563    D: DfsPreorderComponent,
564    H: DepthComponent,
565    PE: ParentEdgeComponent,
566    O: XorBottomUpOrderComponent,
567{
568    pub fn edge_child(&self, eid: usize) -> usize {
569        self.edge_child[eid]
570    }
571    pub fn edge_children(&self) -> &[usize] {
572        &self.edge_child
573    }
574}
575
576pub struct Children<'a> {
577    dfs: &'a DfsPreorder,
578    next: usize,
579    end: usize,
580}
581
582impl Iterator for Children<'_> {
583    type Item = usize;
584    fn next(&mut self) -> Option<usize> {
585        if self.next == self.end {
586            None
587        } else {
588            let v = self.dfs.order[self.next];
589            self.next = self.dfs.subtree_end[v];
590            Some(v)
591        }
592    }
593}
594
595pub struct XorLinkedRootedTreeScanner<
596    U,
597    T = (),
598    P = NoParent,
599    D = NoDfsPreorder,
600    H = NoDepth,
601    PE = NoParentEdge,
602    EC = NoEdgeChild,
603    X = NoXorBottomUpOrder,
604    B = NoXorBottomUpOrder,
605    E = NoEIndexed,
606> where
607    U: Scan<Output = usize>,
608    T: Scan,
609{
610    n: usize,
611    root: usize,
612    _marker: ScannerMarker<U, T, P, D, H, PE, EC, X, B, E>,
613}
614
615impl<U, T> XorLinkedRootedTreeScanner<U, T>
616where
617    U: Scan<Output = usize>,
618    T: Scan,
619{
620    pub fn new(n: usize, root: usize) -> Self {
621        Self {
622            n,
623            root,
624            _marker: PhantomData,
625        }
626    }
627}
628
629impl<U, T, P, D, H, PE, EC, X, B, E> XorLinkedRootedTreeScanner<U, T, P, D, H, PE, EC, X, B, E>
630where
631    U: Scan<Output = usize>,
632    T: Scan,
633{
634    pub fn with_parent(
635        self,
636    ) -> XorLinkedRootedTreeScanner<U, T, RecordParent, D, H, PE, EC, X, B, E> {
637        XorLinkedRootedTreeScanner {
638            n: self.n,
639            root: self.root,
640            _marker: PhantomData,
641        }
642    }
643    pub fn with_dfs_preorder(
644        self,
645    ) -> XorLinkedRootedTreeScanner<
646        U,
647        T,
648        P,
649        RecordDfsPreorder,
650        H,
651        PE,
652        EC,
653        X,
654        RecordXorBottomUpOrder,
655        E,
656    > {
657        XorLinkedRootedTreeScanner {
658            n: self.n,
659            root: self.root,
660            _marker: PhantomData,
661        }
662    }
663    pub fn with_depth(
664        self,
665    ) -> XorLinkedRootedTreeScanner<U, T, P, D, RecordDepth, PE, EC, X, RecordXorBottomUpOrder, E>
666    {
667        XorLinkedRootedTreeScanner {
668            n: self.n,
669            root: self.root,
670            _marker: PhantomData,
671        }
672    }
673    pub fn with_xor_bottom_up_order(
674        self,
675    ) -> XorLinkedRootedTreeScanner<
676        U,
677        T,
678        P,
679        D,
680        H,
681        PE,
682        EC,
683        RecordXorBottomUpOrder,
684        RecordXorBottomUpOrder,
685        E,
686    > {
687        XorLinkedRootedTreeScanner {
688            n: self.n,
689            root: self.root,
690            _marker: PhantomData,
691        }
692    }
693}
694
695impl<U, T, P, D, H, X, B>
696    XorLinkedRootedTreeScanner<U, T, P, D, H, NoParentEdge, NoEdgeChild, X, B, NoEIndexed>
697where
698    U: Scan<Output = usize>,
699    T: Scan,
700{
701    pub fn with_eindexed(
702        self,
703    ) -> XorLinkedRootedTreeScanner<U, T, P, D, H, NoParentEdge, NoEdgeChild, X, B, EIndexed> {
704        XorLinkedRootedTreeScanner {
705            n: self.n,
706            root: self.root,
707            _marker: PhantomData,
708        }
709    }
710}
711
712impl<U, T, P, D, H, PE, EC, X, B> XorLinkedRootedTreeScanner<U, T, P, D, H, PE, EC, X, B, EIndexed>
713where
714    U: Scan<Output = usize>,
715    T: Scan,
716{
717    pub fn with_parent_edge(
718        self,
719    ) -> XorLinkedRootedTreeScanner<U, T, P, D, H, RecordParentEdge, EC, X, B, EIndexed> {
720        XorLinkedRootedTreeScanner {
721            n: self.n,
722            root: self.root,
723            _marker: PhantomData,
724        }
725    }
726    pub fn with_edge_child(
727        self,
728    ) -> XorLinkedRootedTreeScanner<U, T, P, D, H, PE, RecordEdgeChild, X, B, EIndexed> {
729        XorLinkedRootedTreeScanner {
730            n: self.n,
731            root: self.root,
732            _marker: PhantomData,
733        }
734    }
735}
736
737impl<U, T, P, D, H, X, B> MarkedScan
738    for XorLinkedRootedTreeScanner<U, T, P, D, H, NoParentEdge, NoEdgeChild, X, B, NoEIndexed>
739where
740    U: Scan<Output = usize>,
741    T: Scan,
742    P: ParentComponent,
743    D: DfsPreorderComponent,
744    H: DepthComponent,
745    X: BuildXorBottomUpOrder<B>,
746    B: XorBottomUpOrderBuffer,
747{
748    type Output = (
749        XorLinkedRootedTree<P, D, H, NoParentEdge, NoEdgeChild, X>,
750        Vec<<T as Scan>::Output>,
751    );
752
753    fn mscan<I: ScanSource>(self, iter: &mut I) -> Option<Self::Output> {
754        let mut acc = XorAccumulator::new(self.n);
755        let mut weights = Vec::with_capacity(self.n.saturating_sub(1));
756        for _ in 0..self.n.saturating_sub(1) {
757            let u = U::scan(iter)?;
758            let v = U::scan(iter)?;
759            acc.add_edge(u, v);
760            weights.push(T::scan(iter)?);
761        }
762        Some((
763            finish_accumulator::<P, D, H, X, B>(self.n, self.root, acc),
764            weights,
765        ))
766    }
767}
768
769impl<U, T, P, D, H, PE, EC, X, B> MarkedScan
770    for XorLinkedRootedTreeScanner<U, T, P, D, H, PE, EC, X, B, EIndexed>
771where
772    U: Scan<Output = usize>,
773    T: Scan,
774    P: ParentComponent,
775    D: DfsPreorderComponent,
776    H: DepthComponent,
777    PE: ParentEdgeComponent,
778    EC: EdgeChildComponent,
779    X: BuildXorBottomUpOrder<B>,
780    B: XorBottomUpOrderBuffer,
781{
782    type Output = (
783        XorLinkedRootedTree<P, D, H, PE, EC, X>,
784        Vec<<T as Scan>::Output>,
785    );
786
787    fn mscan<I: ScanSource>(self, iter: &mut I) -> Option<Self::Output> {
788        let mut acc = XorEIndexedAccumulator::new(self.n);
789        let mut weights = Vec::with_capacity(self.n.saturating_sub(1));
790        for eid in 0..self.n.saturating_sub(1) {
791            let u = U::scan(iter)?;
792            let v = U::scan(iter)?;
793            acc.add_edge(eid, u, v);
794            weights.push(T::scan(iter)?);
795        }
796        Some((
797            finish_eindexed_accumulator::<P, D, H, PE, EC, X, B>(self.n, self.root, acc),
798            weights,
799        ))
800    }

Source

fn finish<O, EC, F>( self, root: usize, xor_order: &mut O::Data, edge_child: &mut EC::Data, f: F, ) -> (Vec<usize>, Vec<usize>)
where O: XorBottomUpOrderBuffer, EC: EdgeChildComponent, F: FnMut(usize, usize, usize),

Examples found in repository ?

crates/competitive/src/tree/xor_linked_tree.rs (line 439)

428    pub fn run<I, F>(self, root: usize, edges: I, f: F)
429    where
430        I: IntoIterator<Item = (usize, usize)>,
431        F: FnMut(usize, usize, usize),
432    {
433        let mut acc = XorEIndexedAccumulator::new(self.n);
434        for (eid, (u, v)) in edges.into_iter().enumerate() {
435            acc.add_edge(eid, u, v);
436        }
437        let mut order = ();
438        let mut edge_child = ();
439        acc.finish::<NoXorBottomUpOrder, NoEdgeChild, _>(root, &mut order, &mut edge_child, f);
440    }
441}
442
443impl<P, D, H, PE, EC, O> XorLinkedRootedTree<P, D, H, PE, EC, O>
444where
445    P: ParentComponent,
446    D: DfsPreorderComponent,
447    H: DepthComponent,
448    PE: ParentEdgeComponent,
449    EC: EdgeChildComponent,
450    O: XorBottomUpOrderComponent,
451{
452    pub fn vertices_size(&self) -> usize {
453        self.n
454    }
455    pub fn edges_size(&self) -> usize {
456        self.n.saturating_sub(1)
457    }
458    pub fn root(&self) -> usize {
459        self.root
460    }
461}
462
463impl<D, H, PE, EC, O> XorLinkedRootedTree<RecordParent, D, H, PE, EC, O>
464where
465    D: DfsPreorderComponent,
466    H: DepthComponent,
467    PE: ParentEdgeComponent,
468    EC: EdgeChildComponent,
469    O: XorBottomUpOrderComponent,
470{
471    pub fn parent(&self, v: usize) -> usize {
472        self.parent[v]
473    }
474    pub fn parents(&self) -> &[usize] {
475        &self.parent
476    }
477}
478
479impl<P, D, H, PE, EC> XorLinkedRootedTree<P, D, H, PE, EC, RecordXorBottomUpOrder>
480where
481    P: ParentComponent,
482    D: DfsPreorderComponent,
483    H: DepthComponent,
484    PE: ParentEdgeComponent,
485    EC: EdgeChildComponent,
486{
487    /// Returns the bottom-up XOR order, excluding the root.
488    pub fn xor_bottom_up_order(&self) -> &[usize] {
489        &self.xor_order
490    }
491    /// Returns the top-down XOR order, excluding the root.
492    pub fn xor_top_down_order(
493        &self,
494    ) -> impl DoubleEndedIterator<Item = usize> + ExactSizeIterator + '_ {
495        self.xor_order.iter().rev().copied()
496    }
497}
498
499impl<P, H, PE, EC, O> XorLinkedRootedTree<P, RecordDfsPreorder, H, PE, EC, O>
500where
501    P: ParentComponent,
502    H: DepthComponent,
503    PE: ParentEdgeComponent,
504    EC: EdgeChildComponent,
505    O: XorBottomUpOrderComponent,
506{
507    pub fn dfs_order(&self) -> &[usize] {
508        &self.dfs.order
509    }
510    pub fn dfs_index(&self, v: usize) -> usize {
511        self.dfs.preorder_index[v]
512    }
513    pub fn subtree_size(&self, v: usize) -> usize {
514        self.dfs.subtree_end[v] - self.dfs.preorder_index[v]
515    }
516    pub fn subtree_range(&self, v: usize) -> Range<usize> {
517        self.dfs.preorder_index[v]..self.dfs.subtree_end[v]
518    }
519    pub fn children(&self, v: usize) -> Children<'_> {
520        Children {
521            dfs: &self.dfs,
522            next: self.dfs.preorder_index[v] + 1,
523            end: self.dfs.subtree_end[v],
524        }
525    }
526}
527
528impl<P, D, PE, EC, O> XorLinkedRootedTree<P, D, RecordDepth, PE, EC, O>
529where
530    P: ParentComponent,
531    D: DfsPreorderComponent,
532    PE: ParentEdgeComponent,
533    EC: EdgeChildComponent,
534    O: XorBottomUpOrderComponent,
535{
536    pub fn depth(&self, v: usize) -> usize {
537        self.depth[v]
538    }
539    pub fn depths(&self) -> &[usize] {
540        &self.depth
541    }
542}
543
544impl<P, D, H, EC, O> XorLinkedRootedTree<P, D, H, RecordParentEdge, EC, O>
545where
546    P: ParentComponent,
547    D: DfsPreorderComponent,
548    H: DepthComponent,
549    EC: EdgeChildComponent,
550    O: XorBottomUpOrderComponent,
551{
552    pub fn parent_edge(&self, v: usize) -> usize {
553        self.parent_edge[v]
554    }
555    pub fn parent_edges(&self) -> &[usize] {
556        &self.parent_edge
557    }
558}
559
560impl<P, D, H, PE, O> XorLinkedRootedTree<P, D, H, PE, RecordEdgeChild, O>
561where
562    P: ParentComponent,
563    D: DfsPreorderComponent,
564    H: DepthComponent,
565    PE: ParentEdgeComponent,
566    O: XorBottomUpOrderComponent,
567{
568    pub fn edge_child(&self, eid: usize) -> usize {
569        self.edge_child[eid]
570    }
571    pub fn edge_children(&self) -> &[usize] {
572        &self.edge_child
573    }
574}
575
576pub struct Children<'a> {
577    dfs: &'a DfsPreorder,
578    next: usize,
579    end: usize,
580}
581
582impl Iterator for Children<'_> {
583    type Item = usize;
584    fn next(&mut self) -> Option<usize> {
585        if self.next == self.end {
586            None
587        } else {
588            let v = self.dfs.order[self.next];
589            self.next = self.dfs.subtree_end[v];
590            Some(v)
591        }
592    }
593}
594
595pub struct XorLinkedRootedTreeScanner<
596    U,
597    T = (),
598    P = NoParent,
599    D = NoDfsPreorder,
600    H = NoDepth,
601    PE = NoParentEdge,
602    EC = NoEdgeChild,
603    X = NoXorBottomUpOrder,
604    B = NoXorBottomUpOrder,
605    E = NoEIndexed,
606> where
607    U: Scan<Output = usize>,
608    T: Scan,
609{
610    n: usize,
611    root: usize,
612    _marker: ScannerMarker<U, T, P, D, H, PE, EC, X, B, E>,
613}
614
615impl<U, T> XorLinkedRootedTreeScanner<U, T>
616where
617    U: Scan<Output = usize>,
618    T: Scan,
619{
620    pub fn new(n: usize, root: usize) -> Self {
621        Self {
622            n,
623            root,
624            _marker: PhantomData,
625        }
626    }
627}
628
629impl<U, T, P, D, H, PE, EC, X, B, E> XorLinkedRootedTreeScanner<U, T, P, D, H, PE, EC, X, B, E>
630where
631    U: Scan<Output = usize>,
632    T: Scan,
633{
634    pub fn with_parent(
635        self,
636    ) -> XorLinkedRootedTreeScanner<U, T, RecordParent, D, H, PE, EC, X, B, E> {
637        XorLinkedRootedTreeScanner {
638            n: self.n,
639            root: self.root,
640            _marker: PhantomData,
641        }
642    }
643    pub fn with_dfs_preorder(
644        self,
645    ) -> XorLinkedRootedTreeScanner<
646        U,
647        T,
648        P,
649        RecordDfsPreorder,
650        H,
651        PE,
652        EC,
653        X,
654        RecordXorBottomUpOrder,
655        E,
656    > {
657        XorLinkedRootedTreeScanner {
658            n: self.n,
659            root: self.root,
660            _marker: PhantomData,
661        }
662    }
663    pub fn with_depth(
664        self,
665    ) -> XorLinkedRootedTreeScanner<U, T, P, D, RecordDepth, PE, EC, X, RecordXorBottomUpOrder, E>
666    {
667        XorLinkedRootedTreeScanner {
668            n: self.n,
669            root: self.root,
670            _marker: PhantomData,
671        }
672    }
673    pub fn with_xor_bottom_up_order(
674        self,
675    ) -> XorLinkedRootedTreeScanner<
676        U,
677        T,
678        P,
679        D,
680        H,
681        PE,
682        EC,
683        RecordXorBottomUpOrder,
684        RecordXorBottomUpOrder,
685        E,
686    > {
687        XorLinkedRootedTreeScanner {
688            n: self.n,
689            root: self.root,
690            _marker: PhantomData,
691        }
692    }
693}
694
695impl<U, T, P, D, H, X, B>
696    XorLinkedRootedTreeScanner<U, T, P, D, H, NoParentEdge, NoEdgeChild, X, B, NoEIndexed>
697where
698    U: Scan<Output = usize>,
699    T: Scan,
700{
701    pub fn with_eindexed(
702        self,
703    ) -> XorLinkedRootedTreeScanner<U, T, P, D, H, NoParentEdge, NoEdgeChild, X, B, EIndexed> {
704        XorLinkedRootedTreeScanner {
705            n: self.n,
706            root: self.root,
707            _marker: PhantomData,
708        }
709    }
710}
711
712impl<U, T, P, D, H, PE, EC, X, B> XorLinkedRootedTreeScanner<U, T, P, D, H, PE, EC, X, B, EIndexed>
713where
714    U: Scan<Output = usize>,
715    T: Scan,
716{
717    pub fn with_parent_edge(
718        self,
719    ) -> XorLinkedRootedTreeScanner<U, T, P, D, H, RecordParentEdge, EC, X, B, EIndexed> {
720        XorLinkedRootedTreeScanner {
721            n: self.n,
722            root: self.root,
723            _marker: PhantomData,
724        }
725    }
726    pub fn with_edge_child(
727        self,
728    ) -> XorLinkedRootedTreeScanner<U, T, P, D, H, PE, RecordEdgeChild, X, B, EIndexed> {
729        XorLinkedRootedTreeScanner {
730            n: self.n,
731            root: self.root,
732            _marker: PhantomData,
733        }
734    }
735}
736
737impl<U, T, P, D, H, X, B> MarkedScan
738    for XorLinkedRootedTreeScanner<U, T, P, D, H, NoParentEdge, NoEdgeChild, X, B, NoEIndexed>
739where
740    U: Scan<Output = usize>,
741    T: Scan,
742    P: ParentComponent,
743    D: DfsPreorderComponent,
744    H: DepthComponent,
745    X: BuildXorBottomUpOrder<B>,
746    B: XorBottomUpOrderBuffer,
747{
748    type Output = (
749        XorLinkedRootedTree<P, D, H, NoParentEdge, NoEdgeChild, X>,
750        Vec<<T as Scan>::Output>,
751    );
752
753    fn mscan<I: ScanSource>(self, iter: &mut I) -> Option<Self::Output> {
754        let mut acc = XorAccumulator::new(self.n);
755        let mut weights = Vec::with_capacity(self.n.saturating_sub(1));
756        for _ in 0..self.n.saturating_sub(1) {
757            let u = U::scan(iter)?;
758            let v = U::scan(iter)?;
759            acc.add_edge(u, v);
760            weights.push(T::scan(iter)?);
761        }
762        Some((
763            finish_accumulator::<P, D, H, X, B>(self.n, self.root, acc),
764            weights,
765        ))
766    }
767}
768
769impl<U, T, P, D, H, PE, EC, X, B> MarkedScan
770    for XorLinkedRootedTreeScanner<U, T, P, D, H, PE, EC, X, B, EIndexed>
771where
772    U: Scan<Output = usize>,
773    T: Scan,
774    P: ParentComponent,
775    D: DfsPreorderComponent,
776    H: DepthComponent,
777    PE: ParentEdgeComponent,
778    EC: EdgeChildComponent,
779    X: BuildXorBottomUpOrder<B>,
780    B: XorBottomUpOrderBuffer,
781{
782    type Output = (
783        XorLinkedRootedTree<P, D, H, PE, EC, X>,
784        Vec<<T as Scan>::Output>,
785    );
786
787    fn mscan<I: ScanSource>(self, iter: &mut I) -> Option<Self::Output> {
788        let mut acc = XorEIndexedAccumulator::new(self.n);
789        let mut weights = Vec::with_capacity(self.n.saturating_sub(1));
790        for eid in 0..self.n.saturating_sub(1) {
791            let u = U::scan(iter)?;
792            let v = U::scan(iter)?;
793            acc.add_edge(eid, u, v);
794            weights.push(T::scan(iter)?);
795        }
796        Some((
797            finish_eindexed_accumulator::<P, D, H, PE, EC, X, B>(self.n, self.root, acc),
798            weights,
799        ))
800    }
801}
802
803fn finish_accumulator<P, D, H, X, B>(
804    n: usize,
805    root: usize,
806    acc: XorAccumulator,
807) -> XorLinkedRootedTree<P, D, H, NoParentEdge, NoEdgeChild, X>
808where
809    P: ParentComponent,
810    D: DfsPreorderComponent,
811    H: DepthComponent,
812    X: BuildXorBottomUpOrder<B>,
813    B: XorBottomUpOrderBuffer,
814{
815    let mut xor_order = B::new(n);
816    let parent = acc.finish::<B, _>(root, &mut xor_order, |_, _| {});
817    finish_rooted_tree::<P, D, H, X, B>(root, parent, xor_order)
818}
819
820fn finish_rooted_tree<P, D, H, X, B>(
821    root: usize,
822    parent: Vec<usize>,
823    xor_order: B::Data,
824) -> XorLinkedRootedTree<P, D, H, NoParentEdge, NoEdgeChild, X>
825where
826    P: ParentComponent,
827    D: DfsPreorderComponent,
828    H: DepthComponent,
829    X: BuildXorBottomUpOrder<B>,
830    B: XorBottomUpOrderBuffer,
831{
832    let n = parent.len();
833    let order = B::as_slice(&xor_order);
834    let dfs = D::build(n, root, &parent, order);
835    let depth = H::build(n, root, &parent, order);
836    XorLinkedRootedTree {
837        n,
838        root,
839        parent: P::build(parent),
840        dfs,
841        depth,
842        parent_edge: (),
843        edge_child: (),
844        xor_order: X::build(xor_order),
845        _marker: PhantomData,
846    }
847}
848
849fn finish_eindexed_accumulator<P, D, H, PE, EC, X, B>(
850    n: usize,
851    root: usize,
852    acc: XorEIndexedAccumulator,
853) -> XorLinkedRootedTree<P, D, H, PE, EC, X>
854where
855    P: ParentComponent,
856    D: DfsPreorderComponent,
857    H: DepthComponent,
858    PE: ParentEdgeComponent,
859    EC: EdgeChildComponent,
860    X: BuildXorBottomUpOrder<B>,
861    B: XorBottomUpOrderBuffer,
862{
863    let mut xor_order = B::new(n);
864    let mut edge_child = EC::new(n.saturating_sub(1));
865    let (parent, parent_edge) =
866        acc.finish::<B, EC, _>(root, &mut xor_order, &mut edge_child, |_, _, _| {});
867    let order = B::as_slice(&xor_order);
868    let dfs = D::build(n, root, &parent, order);
869    let depth = H::build(n, root, &parent, order);
870    XorLinkedRootedTree {
871        n,
872        root,
873        parent: P::build(parent),
874        dfs,
875        depth,
876        parent_edge: PE::build(parent_edge),
877        edge_child,
878        xor_order: X::build(xor_order),
879        _marker: PhantomData,
880    }
881}