competitive/tree/
link_cut_tree.rs

1use super::{
2    Allocator, LazyMapMonoid, MemoryPool,
3    binary_search_tree::{
4        BstDataMutRef, BstNode, BstRoot, BstSeeker, BstSpec, EqualSide, data::LazyMapElement,
5        node::WithParent,
6    },
7    splay_operations,
8};
9use std::{marker::PhantomData, mem::replace, ptr::NonNull};
10
11pub trait LinkCutTreeSpec: Sized {
12    type Value;
13    type Data;
14
15    /// Whether splay must propagate from the auxiliary root before rotations.
16    const ROOT_TO_NODE_TOP_DOWN: bool = true;
17    /// Whether `modify` must expose the node to update virtual subtree state.
18    const MODIFY_REQUIRES_ACCESS: bool = true;
19
20    fn new(value: Self::Value) -> Self::Data;
21    fn value(data: &Self::Data) -> &Self::Value;
22    fn value_mut(data: &mut Self::Data) -> &mut Self::Value;
23    fn top_down(_data: &mut Self::Data, _children: [Option<&mut Self::Data>; 2]) {}
24    fn bottom_up(data: &mut Self::Data, children: [Option<&Self::Data>; 2]);
25    fn reverse(data: &mut Self::Data);
26    fn attach_virtual(_parent: &mut Self::Data, _child: &mut Self::Data) {}
27    fn detach_virtual(_parent: &mut Self::Data, _child: &mut Self::Data) {}
28    /// Moves state associated with the same path-parent edge after a splay.
29    fn transfer_path_parent(_old_root: &mut Self::Data, _new_root: &mut Self::Data) {}
30}
31
32pub trait LinkCutTreePathFold: LinkCutTreeSpec {
33    type Path;
34    fn fold_path(data: &Self::Data) -> Self::Path;
35}
36
37pub trait LinkCutTreePathUpdate: LinkCutTreeSpec {
38    type PathAction;
39    fn update_path(data: &mut Self::Data, action: &Self::PathAction);
40}
41
42pub trait LinkCutTreeSubtreeFold: LinkCutTreeSpec {
43    type Subtree;
44    fn fold_subtree(data: &Self::Data) -> Self::Subtree;
45}
46
47/// Pending updates must be propagated through `top_down`, `attach_virtual`,
48/// `detach_virtual`, and `transfer_path_parent`.
49pub trait LinkCutTreeSubtreeUpdate: LinkCutTreeSpec {
50    type SubtreeAction;
51    fn update_subtree(data: &mut Self::Data, action: &Self::SubtreeAction);
52}
53
54struct LinkCutData<S>
55where
56    S: LinkCutTreeSpec,
57{
58    inner: S::Data,
59    index_and_reverse: usize,
60}
61
62struct LinkCutBstSpec<S>(PhantomData<fn() -> S>);
63
64type LinkCutNode<S> = BstNode<LinkCutData<S>, WithParent<LinkCutData<S>>>;
65type LinkCutPtr<S> = NonNull<LinkCutNode<S>>;
66
67impl<S> LinkCutBstSpec<S>
68where
69    S: LinkCutTreeSpec,
70{
71    #[inline]
72    unsafe fn toggle(mut node: LinkCutPtr<S>) {
73        unsafe { node.as_mut().child.swap(0, 1) };
74        let data = unsafe { &mut node.as_mut().data };
75        data.index_and_reverse ^= 1;
76        S::reverse(&mut data.inner);
77    }
78
79    #[inline]
80    unsafe fn with_two_inner_mut<R>(
81        mut left: LinkCutPtr<S>,
82        mut right: LinkCutPtr<S>,
83        f: impl FnOnce(&mut S::Data, &mut S::Data) -> R,
84    ) -> R {
85        let left = unsafe { &mut left.as_mut().data.inner };
86        let right = unsafe { &mut right.as_mut().data.inner };
87        f(left, right)
88    }
89}
90
91impl<S> BstSpec for LinkCutBstSpec<S>
92where
93    S: LinkCutTreeSpec,
94{
95    type Parent = WithParent<Self::Data>;
96    type Data = LinkCutData<S>;
97
98    #[inline]
99    fn top_down(mut node: BstDataMutRef<'_, Self>) {
100        let pointer = node.node;
101        if node.reborrow().into_data().index_and_reverse & 1 != 0 {
102            node.data_mut().index_and_reverse &= !1;
103            let children = unsafe { pointer.as_ref().child };
104            for child in children.into_iter().flatten() {
105                unsafe { Self::toggle(child) };
106            }
107        }
108        let children = unsafe { pointer.as_ref().child };
109        let data = unsafe { &mut (*pointer.as_ptr()).data.inner };
110        let children =
111            children.map(|child| child.map(|child| unsafe { &mut (*child.as_ptr()).data.inner }));
112        S::top_down(data, children);
113    }
114
115    #[inline]
116    fn bottom_up(node: BstDataMutRef<'_, Self>) {
117        let pointer = node.node;
118        let children = unsafe { pointer.as_ref().child };
119        let data = unsafe { &mut (*pointer.as_ptr()).data.inner };
120        let children =
121            children.map(|child| child.map(|child| unsafe { &(*child.as_ptr()).data.inner }));
122        S::bottom_up(data, children);
123    }
124
125    fn merge(_left: Option<BstRoot<Self>>, _right: Option<BstRoot<Self>>) -> Option<BstRoot<Self>> {
126        unreachable!("link-cut trees do not merge auxiliary trees through BstSpec")
127    }
128
129    fn split<Seeker>(
130        _node: Option<BstRoot<Self>>,
131        _seeker: Seeker,
132        _equal_side: EqualSide,
133    ) -> (Option<BstRoot<Self>>, Option<BstRoot<Self>>)
134    where
135        Seeker: BstSeeker<Spec = Self>,
136    {
137        unreachable!("link-cut trees do not split auxiliary trees through BstSpec")
138    }
139}
140
141/// A link-cut forest with stable insertion-order node identifiers.
142///
143/// Its dynamic-tree operations take amortized `O(log n)` time when the spec
144/// hooks take constant time.
145pub struct LinkCutTree<S>
146where
147    S: LinkCutTreeSpec,
148{
149    nodes: Vec<LinkCutPtr<S>>,
150    allocator: MemoryPool<LinkCutNode<S>>,
151}
152
153impl<S> LinkCutTree<S>
154where
155    S: LinkCutTreeSpec,
156{
157    pub fn with_capacity(capacity: usize) -> Self {
158        Self {
159            nodes: Vec::with_capacity(capacity),
160            allocator: MemoryPool::with_capacity(capacity),
161        }
162    }
163
164    /// `edges` must form a tree over the values in iteration order.
165    pub fn from_edges<T>(values: T, edges: &[(usize, usize)]) -> Self
166    where
167        T: IntoIterator<Item = S::Value>,
168    {
169        let tree: Self = values.into_iter().collect();
170        for (child, parent, preferred) in
171            splay_operations::rooted_heavy_order(tree.nodes.len(), edges)
172                .into_iter()
173                .rev()
174        {
175            let child = tree.node(child);
176            let mut parent = tree.node(parent);
177            unsafe {
178                (*child.as_ptr()).parent.parent = Some(parent);
179                if preferred {
180                    parent.as_mut().child[1] = Some(child);
181                } else {
182                    LinkCutBstSpec::<S>::with_two_inner_mut(parent, child, S::attach_virtual);
183                }
184                Self::pull(parent);
185            }
186        }
187        tree
188    }
189
190    pub fn add_node(&mut self, value: S::Value) -> usize {
191        let index = self.nodes.len();
192        let node = self.allocator.allocate(BstNode::new(LinkCutData {
193            inner: S::new(value),
194            index_and_reverse: index << 1,
195        }));
196        self.nodes.push(node);
197        index
198    }
199
200    #[inline]
201    fn node(&self, index: usize) -> LinkCutPtr<S> {
202        self.nodes[index]
203    }
204
205    #[inline]
206    unsafe fn pull(node: LinkCutPtr<S>) {
207        unsafe {
208            LinkCutBstSpec::<S>::bottom_up(BstDataMutRef::new_unchecked(node));
209        }
210    }
211
212    #[inline]
213    unsafe fn splay(node: LinkCutPtr<S>) {
214        let root = if S::ROOT_TO_NODE_TOP_DOWN {
215            unsafe {
216                splay_operations::with_parent::splay::<LinkCutBstSpec<S>, LinkCutData<S>>(node)
217            }
218        } else {
219            unsafe {
220                splay_operations::with_parent::splay_with_local_top_down::<
221                    LinkCutBstSpec<S>,
222                    LinkCutData<S>,
223                >(node)
224            }
225        };
226        if root != node {
227            unsafe {
228                LinkCutBstSpec::<S>::with_two_inner_mut(root, node, S::transfer_path_parent);
229            }
230        }
231    }
232
233    fn access_node(mut node: LinkCutPtr<S>) {
234        unsafe {
235            Self::splay(node);
236            if let Some(right) = node.as_mut().child[1].take() {
237                LinkCutBstSpec::<S>::with_two_inner_mut(node, right, S::attach_virtual);
238            }
239            Self::pull(node);
240            while let Some(mut parent) = node.as_ref().parent.parent {
241                Self::splay(parent);
242                if let Some(right) = parent.as_mut().child[1].take() {
243                    LinkCutBstSpec::<S>::with_two_inner_mut(parent, right, S::attach_virtual);
244                }
245                LinkCutBstSpec::<S>::with_two_inner_mut(parent, node, S::detach_virtual);
246                parent.as_mut().child[1] = Some(node);
247                node.as_mut().parent.parent = Some(parent);
248                LinkCutBstSpec::<S>::top_down(BstDataMutRef::new_unchecked(node));
249                splay_operations::with_parent::rotate::<LinkCutBstSpec<S>, LinkCutData<S>>(node);
250                Self::pull(node);
251                LinkCutBstSpec::<S>::with_two_inner_mut(parent, node, S::transfer_path_parent);
252            }
253        }
254    }
255
256    pub fn get(&mut self, node: usize) -> &S::Value {
257        let node = self.node(node);
258        Self::access_node(node);
259        unsafe { S::value(&node.as_ref().data.inner) }
260    }
261
262    pub fn set(&mut self, node: usize, value: S::Value) {
263        self.modify(node, |_| value);
264    }
265
266    pub fn modify<F>(&mut self, node: usize, f: F)
267    where
268        F: FnOnce(&S::Value) -> S::Value,
269    {
270        let node = self.node(node);
271        if S::MODIFY_REQUIRES_ACCESS {
272            Self::access_node(node);
273        } else {
274            unsafe { Self::splay(node) };
275        }
276        unsafe {
277            let data = &mut (*node.as_ptr()).data.inner;
278            *S::value_mut(data) = f(S::value(data));
279            Self::pull(node);
280        }
281    }
282
283    pub fn reroot(&mut self, node: usize) {
284        let node = self.node(node);
285        Self::access_node(node);
286        unsafe { LinkCutBstSpec::<S>::toggle(node) };
287    }
288
289    /// `child` and `parent` must belong to different trees.
290    pub fn link(&mut self, child: usize, parent: usize) {
291        assert_ne!(child, parent);
292        self.reroot(child);
293        let child = self.node(child);
294        let parent = self.node(parent);
295        Self::access_node(parent);
296        unsafe {
297            (*child.as_ptr()).parent.parent = Some(parent);
298            LinkCutBstSpec::<S>::with_two_inner_mut(parent, child, S::attach_virtual);
299            Self::pull(parent);
300        }
301    }
302
303    /// `(u, v)` must be an edge.
304    pub fn cut(&mut self, u: usize, v: usize) {
305        assert_ne!(u, v);
306        self.reroot(u);
307        let mut v = self.node(v);
308        Self::access_node(v);
309        unsafe {
310            let mut left = v.as_mut().child[0]
311                .take()
312                .expect("the specified edge must exist");
313            left.as_mut().parent.parent = None;
314            Self::pull(v);
315        }
316    }
317
318    pub fn root(&mut self, node: usize) -> usize {
319        let mut root = self.node(node);
320        Self::access_node(root);
321        unsafe {
322            loop {
323                LinkCutBstSpec::<S>::top_down(BstDataMutRef::new_unchecked(root));
324                match root.as_ref().child[0] {
325                    Some(left) => root = left,
326                    None => break,
327                }
328            }
329            Self::splay(root);
330            root.as_ref().data.index_and_reverse >> 1
331        }
332    }
333
334    pub fn is_connected(&mut self, u: usize, v: usize) -> bool {
335        self.root(u) == self.root(v)
336    }
337
338    fn detach_left<R>(node: LinkCutPtr<S>, f: impl FnOnce(&mut S::Data) -> R) -> R {
339        unsafe {
340            let left = (*node.as_ptr()).child[0].take();
341            if let Some(mut left) = left {
342                left.as_mut().parent.parent = None;
343            }
344            Self::pull(node);
345            let result = f(&mut (*node.as_ptr()).data.inner);
346            LinkCutBstSpec::<S>::top_down(BstDataMutRef::new_unchecked(node));
347            (*node.as_ptr()).child[0] = left;
348            if let Some(mut left) = left {
349                left.as_mut().parent.parent = Some(node);
350            }
351            Self::pull(node);
352            result
353        }
354    }
355}
356
357impl<S> FromIterator<S::Value> for LinkCutTree<S>
358where
359    S: LinkCutTreeSpec,
360{
361    fn from_iter<T: IntoIterator<Item = S::Value>>(iter: T) -> Self {
362        let iter = iter.into_iter();
363        let (lower, _) = iter.size_hint();
364        let mut tree = Self::with_capacity(lower);
365        for value in iter {
366            tree.add_node(value);
367        }
368        tree
369    }
370}
371
372impl<S> LinkCutTree<S>
373where
374    S: LinkCutTreePathFold,
375{
376    /// `u` and `v` must be connected.
377    pub fn fold_path(&mut self, u: usize, v: usize) -> S::Path {
378        self.reroot(u);
379        let v = self.node(v);
380        Self::access_node(v);
381        unsafe { S::fold_path(&v.as_ref().data.inner) }
382    }
383}
384
385impl<S> LinkCutTree<S>
386where
387    S: LinkCutTreePathUpdate,
388{
389    /// `u` and `v` must be connected.
390    pub fn update_path(&mut self, u: usize, v: usize, action: &S::PathAction) {
391        self.reroot(u);
392        let v = self.node(v);
393        Self::access_node(v);
394        unsafe { S::update_path(&mut (*v.as_ptr()).data.inner, action) };
395    }
396}
397
398impl<S> LinkCutTree<S>
399where
400    S: LinkCutTreeSubtreeFold,
401{
402    /// `(node, parent)` must be an edge.
403    pub fn fold_subtree(&mut self, node: usize, parent: usize) -> S::Subtree {
404        self.reroot(parent);
405        let node = self.node(node);
406        Self::access_node(node);
407        Self::detach_left(node, |data| S::fold_subtree(data))
408    }
409}
410
411impl<S> LinkCutTree<S>
412where
413    S: LinkCutTreeSubtreeUpdate,
414{
415    /// `(node, parent)` must be an edge.
416    pub fn update_subtree(&mut self, node: usize, parent: usize, action: &S::SubtreeAction) {
417        self.reroot(parent);
418        let node = self.node(node);
419        Self::access_node(node);
420        Self::detach_left(node, |data| S::update_subtree(data, action));
421    }
422}
423
424pub struct PathLinkCutTreeData<L>
425where
426    L: LazyMapMonoid,
427{
428    value: LazyMapElement<L>,
429}
430
431pub struct PathLinkCutTreeSpec<L>(PhantomData<fn() -> L>);
432
433impl<L> PathLinkCutTreeSpec<L>
434where
435    L: LazyMapMonoid,
436{
437    #[inline]
438    fn apply_non_unit(data: &mut PathLinkCutTreeData<L>, action: &L::Act) {
439        L::act_operate_assign(&mut data.value.act, action);
440        data.value.key = L::act_key(&data.value.key, action);
441        data.value.agg = L::act_agg(&data.value.agg, action)
442            .expect("a path link-cut tree action must update aggregates lazily");
443    }
444}
445
446impl<L> LinkCutTreeSpec for PathLinkCutTreeSpec<L>
447where
448    L: LazyMapMonoid,
449{
450    type Value = L::Key;
451    type Data = PathLinkCutTreeData<L>;
452
453    const ROOT_TO_NODE_TOP_DOWN: bool = false;
454    const MODIFY_REQUIRES_ACCESS: bool = false;
455
456    fn new(value: Self::Value) -> Self::Data {
457        Self::Data {
458            value: LazyMapElement::from_key(value),
459        }
460    }
461
462    fn value(data: &Self::Data) -> &Self::Value {
463        &data.value.key
464    }
465
466    fn value_mut(data: &mut Self::Data) -> &mut Self::Value {
467        &mut data.value.key
468    }
469
470    fn top_down(data: &mut Self::Data, children: [Option<&mut Self::Data>; 2]) {
471        if L::is_act_unit(&data.value.act) {
472            return;
473        }
474        let action = replace(&mut data.value.act, L::act_unit());
475        for child in children.into_iter().flatten() {
476            Self::apply_non_unit(child, &action);
477        }
478    }
479
480    fn bottom_up(data: &mut Self::Data, children: [Option<&Self::Data>; 2]) {
481        let mut aggregate = L::single_agg(&data.value.key);
482        if let Some(left) = children[0] {
483            aggregate = L::agg_operate(&left.value.agg, &aggregate);
484        }
485        if let Some(right) = children[1] {
486            aggregate = L::agg_operate(&aggregate, &right.value.agg);
487        }
488        data.value.agg = aggregate;
489    }
490
491    fn reverse(data: &mut Self::Data) {
492        L::toggle(&mut data.value.agg);
493    }
494}
495
496impl<L> LinkCutTreePathFold for PathLinkCutTreeSpec<L>
497where
498    L: LazyMapMonoid,
499{
500    type Path = L::Agg;
501
502    fn fold_path(data: &Self::Data) -> Self::Path {
503        data.value.agg.clone()
504    }
505}
506
507impl<L> LinkCutTreePathUpdate for PathLinkCutTreeSpec<L>
508where
509    L: LazyMapMonoid,
510{
511    type PathAction = L::Act;
512
513    fn update_path(data: &mut Self::Data, action: &Self::PathAction) {
514        if !L::is_act_unit(action) {
515            Self::apply_non_unit(data, action);
516        }
517    }
518}
519
520/// `L::act_agg` must return `Some` for every action.
521pub type PathLinkCutTree<L> = LinkCutTree<PathLinkCutTreeSpec<L>>;
522
523#[cfg(test)]
524mod tests {
525    use super::*;
526    use crate::{
527        algebra::{Associative, EmptyAct, Magma, RangeSumRangeLinear, Unital},
528        graph::{Graph, UndirectedSparseGraph},
529        tools::Xorshift,
530        tree::{MixedTree, PathTree, StarTree},
531    };
532
533    fn adjacency(graph: &UndirectedSparseGraph) -> Vec<Vec<usize>> {
534        graph
535            .vertices()
536            .map(|u| graph.neighbors(u).map(|a| a.to).collect())
537            .collect()
538    }
539
540    fn naive_path(adjacency: &[Vec<usize>], start: usize, goal: usize) -> Vec<usize> {
541        let mut parent = vec![usize::MAX; adjacency.len()];
542        let mut stack = vec![start];
543        while let Some(u) = stack.pop() {
544            for &v in &adjacency[u] {
545                if v != parent[u] {
546                    parent[v] = u;
547                    stack.push(v);
548                }
549            }
550        }
551        let mut current = goal;
552        let mut path = Vec::new();
553        loop {
554            path.push(current);
555            if current == start {
556                break;
557            }
558            current = parent[current];
559        }
560        path.reverse();
561        path
562    }
563
564    fn naive_subtree(adjacency: &[Vec<usize>], root: usize, parent: usize) -> Vec<usize> {
565        let mut subtree = Vec::new();
566        let mut stack = vec![(root, parent)];
567        while let Some((u, parent)) = stack.pop() {
568            subtree.push(u);
569            stack.extend(
570                adjacency[u]
571                    .iter()
572                    .filter(|&&v| v != parent)
573                    .map(|&v| (v, u)),
574            );
575        }
576        subtree
577    }
578
579    fn rewire(
580        adjacency: &mut [Vec<usize>],
581        edges: &mut [(usize, usize)],
582        rng: &mut Xorshift,
583    ) -> (usize, usize, usize, usize) {
584        let edge = rng.random(0..edges.len());
585        let (u, v) = edges[edge];
586        adjacency[u].retain(|&to| to != v);
587        adjacency[v].retain(|&to| to != u);
588
589        let mut component = vec![false; adjacency.len()];
590        let mut stack = vec![u];
591        component[u] = true;
592        while let Some(x) = stack.pop() {
593            for &to in &adjacency[x] {
594                if !component[to] {
595                    component[to] = true;
596                    stack.push(to);
597                }
598            }
599        }
600        let left = (0..adjacency.len())
601            .filter(|&x| component[x])
602            .collect::<Vec<_>>();
603        let right = (0..adjacency.len())
604            .filter(|&x| !component[x])
605            .collect::<Vec<_>>();
606        let a = left[rng.random(0..left.len())];
607        let b = right[rng.random(0..right.len())];
608
609        adjacency[a].push(b);
610        adjacency[b].push(a);
611        edges[edge] = (a, b);
612        (u, v, a, b)
613    }
614
615    struct SubtreeSum;
616
617    struct SubtreeSumData {
618        value: i64,
619        virtual_sum: i64,
620        virtual_size: i64,
621        sum: i64,
622        size: i64,
623        lazy: i64,
624        virtual_lazy: i64,
625        path_parent_lazy: i64,
626    }
627
628    impl SubtreeSum {
629        fn apply(data: &mut SubtreeSumData, action: i64) {
630            data.value += action;
631            data.virtual_sum += data.virtual_size * action;
632            data.sum += data.size * action;
633            data.lazy += action;
634            data.virtual_lazy += action;
635        }
636    }
637
638    impl LinkCutTreeSpec for SubtreeSum {
639        type Value = i64;
640        type Data = SubtreeSumData;
641
642        fn new(value: Self::Value) -> Self::Data {
643            SubtreeSumData {
644                value,
645                virtual_sum: 0,
646                virtual_size: 0,
647                sum: value,
648                size: 1,
649                lazy: 0,
650                virtual_lazy: 0,
651                path_parent_lazy: 0,
652            }
653        }
654
655        fn value(data: &Self::Data) -> &Self::Value {
656            &data.value
657        }
658
659        fn value_mut(data: &mut Self::Data) -> &mut Self::Value {
660            &mut data.value
661        }
662
663        fn top_down(data: &mut Self::Data, children: [Option<&mut Self::Data>; 2]) {
664            let action = replace(&mut data.lazy, 0);
665            for child in children.into_iter().flatten() {
666                Self::apply(child, action);
667            }
668        }
669
670        fn bottom_up(data: &mut Self::Data, children: [Option<&Self::Data>; 2]) {
671            data.sum = data.value
672                + data.virtual_sum
673                + children
674                    .into_iter()
675                    .flatten()
676                    .map(|child| child.sum)
677                    .sum::<i64>();
678            data.size = 1
679                + data.virtual_size
680                + children
681                    .into_iter()
682                    .flatten()
683                    .map(|child| child.size)
684                    .sum::<i64>();
685        }
686
687        fn reverse(_data: &mut Self::Data) {}
688
689        fn attach_virtual(parent: &mut Self::Data, child: &mut Self::Data) {
690            child.path_parent_lazy = parent.virtual_lazy;
691            parent.virtual_sum += child.sum;
692            parent.virtual_size += child.size;
693        }
694
695        fn detach_virtual(parent: &mut Self::Data, child: &mut Self::Data) {
696            Self::apply(child, parent.virtual_lazy - child.path_parent_lazy);
697            parent.virtual_sum -= child.sum;
698            parent.virtual_size -= child.size;
699        }
700
701        fn transfer_path_parent(old_root: &mut Self::Data, new_root: &mut Self::Data) {
702            new_root.path_parent_lazy = replace(&mut old_root.path_parent_lazy, 0);
703        }
704    }
705
706    impl LinkCutTreeSubtreeFold for SubtreeSum {
707        type Subtree = i64;
708
709        fn fold_subtree(data: &Self::Data) -> Self::Subtree {
710            data.sum
711        }
712    }
713
714    impl LinkCutTreeSubtreeUpdate for SubtreeSum {
715        type SubtreeAction = i64;
716
717        fn update_subtree(data: &mut Self::Data, action: &Self::SubtreeAction) {
718            Self::apply(data, *action);
719        }
720    }
721
722    struct BidirectionalString;
723
724    impl Magma for BidirectionalString {
725        type T = (String, String);
726
727        fn operate(left: &Self::T, right: &Self::T) -> Self::T {
728            (left.0.clone() + &right.0, right.1.clone() + &left.1)
729        }
730    }
731
732    impl Unital for BidirectionalString {
733        fn unit() -> Self::T {
734            (String::new(), String::new())
735        }
736    }
737
738    impl Associative for BidirectionalString {}
739
740    struct StringPath;
741
742    impl LazyMapMonoid for StringPath {
743        type Key = char;
744        type Agg = (String, String);
745        type Act = ();
746        type AggMonoid = BidirectionalString;
747        type ActMonoid = ();
748        type KeyAct = EmptyAct<char>;
749
750        fn single_agg(key: &Self::Key) -> Self::Agg {
751            (key.to_string(), key.to_string())
752        }
753
754        fn toggle(value: &mut Self::Agg) {
755            std::mem::swap(&mut value.0, &mut value.1);
756        }
757
758        fn act_agg(value: &Self::Agg, _action: &Self::Act) -> Option<Self::Agg> {
759            Some(value.clone())
760        }
761    }
762
763    fn run_path_case(graph: &UndirectedSparseGraph, rounds: usize, rng: &mut Xorshift) {
764        let n = graph.vertices_size();
765        let mut adjacency = adjacency(graph);
766        let mut edges = graph.edges.clone();
767        let mut values = (0..n).map(|_| rng.random(-20i64..=20)).collect::<Vec<_>>();
768        let mut tree =
769            PathLinkCutTree::<RangeSumRangeLinear<i64>>::from_edges(values.iter().copied(), &edges);
770        let root = rng.random(0..n);
771        tree.reroot(root);
772        for u in 0..n {
773            assert_eq!(tree.root(u), root);
774        }
775
776        for _ in 0..rounds {
777            match rng.random(0..if edges.is_empty() { 2 } else { 3 }) {
778                0 => {
779                    let u = rng.random(0..n);
780                    if rng.random(0..2) == 0 {
781                        values[u] = rng.random(-20i64..=20);
782                        tree.set(u, values[u]);
783                    } else {
784                        let action = rng.random(-20i64..=20);
785                        values[u] += action;
786                        tree.modify(u, |value| *value + action);
787                    }
788                }
789                1 => {
790                    let u = rng.random(0..n);
791                    let v = rng.random(0..n);
792                    let action = (rng.random(0i64..=1), rng.random(-20i64..=20));
793                    let path = naive_path(&adjacency, u, v);
794                    for &x in &path {
795                        values[x] = action.0 * values[x] + action.1;
796                    }
797                    tree.update_path(u, v, &action);
798                }
799                _ => {
800                    let (u, v, a, b) = rewire(&mut adjacency, &mut edges, rng);
801                    tree.cut(u, v);
802                    assert!(!tree.is_connected(u, v));
803                    tree.link(a, b);
804                    assert!(tree.is_connected(u, v));
805                }
806            }
807
808            let u = rng.random(0..n);
809            let v = rng.random(0..n);
810            let path = naive_path(&adjacency, u, v);
811            assert_eq!(
812                tree.fold_path(u, v),
813                (path.iter().map(|&x| values[x]).sum(), path.len() as i64)
814            );
815            let u = rng.random(0..n);
816            assert_eq!(*tree.get(u), values[u]);
817        }
818    }
819
820    fn run_ordered_path_case(graph: &UndirectedSparseGraph, rounds: usize, rng: &mut Xorshift) {
821        let n = graph.vertices_size();
822        let mut adjacency = adjacency(graph);
823        let mut edges = graph.edges.clone();
824        let mut values = (0..n)
825            .map(|_| rng.random(b'a'..=b'z') as char)
826            .collect::<Vec<_>>();
827        let mut tree = PathLinkCutTree::<StringPath>::from_edges(values.iter().copied(), &edges);
828
829        for _ in 0..rounds {
830            match rng.random(0..if edges.is_empty() { 2 } else { 3 }) {
831                0 => {
832                    let u = rng.random(0..n);
833                    values[u] = rng.random(b'a'..=b'z') as char;
834                    if rng.random(0..2) == 0 {
835                        tree.set(u, values[u]);
836                    } else {
837                        tree.modify(u, |_| values[u]);
838                    }
839                }
840                1 => {
841                    let u = rng.random(0..n);
842                    tree.reroot(u);
843                    tree.reroot(u);
844                }
845                _ => {
846                    let (u, v, a, b) = rewire(&mut adjacency, &mut edges, rng);
847                    tree.cut(u, v);
848                    tree.link(a, b);
849                }
850            }
851
852            let u = rng.random(0..n);
853            let v = rng.random(0..n);
854            assert_eq!(
855                tree.fold_path(u, v).0,
856                naive_path(&adjacency, u, v)
857                    .into_iter()
858                    .map(|u| values[u])
859                    .collect::<String>()
860            );
861        }
862    }
863
864    fn run_subtree_case(graph: &UndirectedSparseGraph, rounds: usize, rng: &mut Xorshift) {
865        let n = graph.vertices_size();
866        let mut adjacency = adjacency(graph);
867        let mut edges = graph.edges.clone();
868        let mut values = (0..n).map(|_| rng.random(-20i64..=20)).collect::<Vec<_>>();
869        let mut tree = LinkCutTree::<SubtreeSum>::from_edges(values.iter().copied(), &edges);
870
871        for _ in 0..rounds {
872            match rng.random(0..3) {
873                0 => {
874                    let (u, v, a, b) = rewire(&mut adjacency, &mut edges, rng);
875                    tree.cut(u, v);
876                    tree.link(a, b);
877                }
878                1 => {
879                    let u = rng.random(0..n);
880                    if rng.random(0..2) == 0 {
881                        values[u] = rng.random(-20i64..=20);
882                        tree.set(u, values[u]);
883                    } else {
884                        let action = rng.random(-20i64..=20);
885                        values[u] += action;
886                        tree.modify(u, |value| *value + action);
887                    }
888                }
889                _ => {
890                    let &(u, v) = &edges[rng.random(0..edges.len())];
891                    let (node, parent) = if rng.random(0..2) == 0 {
892                        (u, v)
893                    } else {
894                        (v, u)
895                    };
896                    let subtree = naive_subtree(&adjacency, node, parent);
897                    let action = rng.random(-20i64..=20);
898                    for &x in &subtree {
899                        values[x] += action;
900                    }
901                    tree.update_subtree(node, parent, &action);
902                }
903            }
904
905            let &(u, v) = &edges[rng.random(0..edges.len())];
906            for (node, parent) in [(u, v), (v, u)] {
907                let subtree = naive_subtree(&adjacency, node, parent);
908                assert_eq!(
909                    tree.fold_subtree(node, parent),
910                    subtree.iter().map(|&x| values[x]).sum()
911                );
912            }
913            let u = rng.random(0..n);
914            assert_eq!(*tree.get(u), values[u]);
915        }
916    }
917
918    #[test]
919    fn path_link_cut_tree() {
920        let mut rng = Xorshift::default();
921        for n in 1..=14 {
922            for graph in [rng.random(PathTree(n)), rng.random(StarTree(n))] {
923                run_path_case(&graph, 300, &mut rng);
924                run_ordered_path_case(&graph, 300, &mut rng);
925            }
926        }
927        for _ in 0..20 {
928            let graph = rng.random(MixedTree(1..=14usize));
929            run_path_case(&graph, 300, &mut rng);
930            run_ordered_path_case(&graph, 300, &mut rng);
931        }
932    }
933
934    #[test]
935    fn link_cut_tree_subtree() {
936        let mut rng = Xorshift::default();
937        for n in 2..=14 {
938            for graph in [rng.random(PathTree(n)), rng.random(StarTree(n))] {
939                run_subtree_case(&graph, 300, &mut rng);
940            }
941        }
942        for _ in 0..20 {
943            let graph = rng.random(MixedTree(2..=14usize));
944            run_subtree_case(&graph, 300, &mut rng);
945        }
946    }
947}
competitive/tree/link_cut_tree.rs

competitive/tree/
link_cut_tree.rs
