fn finish_rooted_tree<P, D, H, X, B>(
root: usize,
parent: Vec<usize>,
xor_order: B::Data,
) -> XorLinkedRootedTree<P, D, H, NoParentEdge, NoEdgeChild, X>where
P: ParentComponent,
D: DfsPreorderComponent,
H: DepthComponent,
X: BuildXorBottomUpOrder<B>,
B: XorBottomUpOrderBuffer,Examples found in repository?
crates/competitive/src/tree/xor_linked_tree.rs (line 360)
346 pub fn build_from_ordered_parents(
347 self,
348 parents: impl IntoIterator<Item = usize>,
349 ) -> XorLinkedRootedTree<P, D, H, NoParentEdge, NoEdgeChild, X> {
350 let mut parent = Vec::with_capacity(self.n);
351 if self.n != 0 {
352 parent.push(usize::MAX);
353 }
354 parent.extend(parents);
355 assert_eq!(parent.len(), self.n);
356 let mut order = B::new(self.n);
357 for v in (1..self.n).rev() {
358 B::push(&mut order, v);
359 }
360 finish_rooted_tree::<P, D, H, X, B>(0, parent, order)
361 }
362
363 pub fn build<I>(
364 self,
365 root: usize,
366 edges: I,
367 ) -> XorLinkedRootedTree<P, D, H, NoParentEdge, NoEdgeChild, X>
368 where
369 I: IntoIterator<Item = (usize, usize)>,
370 {
371 let mut acc = XorAccumulator::new(self.n);
372 for (u, v) in edges {
373 acc.add_edge(u, v);
374 }
375 finish_accumulator::<P, D, H, X, B>(self.n, root, acc)
376 }
377}
378
379impl<P, D, H, PE, EC, X, B> XorLinkedRootedTreeBuilder<P, D, H, PE, EC, X, B, EIndexed>
380where
381 P: ParentComponent,
382 D: DfsPreorderComponent,
383 H: DepthComponent,
384 PE: ParentEdgeComponent,
385 EC: EdgeChildComponent,
386 X: BuildXorBottomUpOrder<B>,
387 B: XorBottomUpOrderBuffer,
388{
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 }
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}