Struct LinkCutTree

Source

pub struct LinkCutTree<S>where
    S: LinkCutTreeSpec,{
    nodes: Vec<NonNull<BstNode<LinkCutData<S>, WithParent<LinkCutData<S>>>>>,
    allocator: MemoryPool<BstNode<LinkCutData<S>, WithParent<LinkCutData<S>>>>,
}

Expand description

A link-cut forest with stable insertion-order node identifiers.

Its dynamic-tree operations take amortized O(log n) time when the spec hooks take constant time.

Fields§

§nodes: Vec<NonNull<BstNode<LinkCutData<S>, WithParent<LinkCutData<S>>>>>§allocator: MemoryPool<BstNode<LinkCutData<S>, WithParent<LinkCutData<S>>>>

Implementations§

Source §

impl<S> LinkCutTree<S>
where S: LinkCutTreeSpec,

Source

pub fn with_capacity(capacity: usize) -> Self

Examples found in repository ?

crates/competitive/src/tree/link_cut_tree.rs (line 364)

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    }

Source

pub fn from_edges<T>(values: T, edges: &[(usize, usize)]) -> Self
where T: IntoIterator<Item = S::Value>,

edges must form a tree over the values in iteration order.

Examples found in repository ?

crates/library_checker/src/tree/dynamic_tree_subtree_add_subtree_sum.rs (line 187)

184pub fn dynamic_tree_subtree_add_subtree_sum(reader: impl Read, writer: impl Write) {
185    prepare_io!(reader, writer);
186    sc!(n, q, a: [u64; n], edges: [(usize, usize); n - 1]);
187    let mut tree = LinkCutTree::<SubtreeSum>::from_edges(a, &edges);
188    for _ in 0..q {
189        sc!(query: Query);
190        match query {
191            Query::Relink { u, v, w, x } => {
192                tree.cut(u, v);
193                tree.link(w, x);
194            }
195            Query::Add { v, p, x } => tree.update_subtree(v, p, &x),
196            Query::Sum { v, p } => {
197                pp!(tree.fold_subtree(v, p));
198            }
199        }
200    }
201}

More examples

Hide additional examples

crates/library_checker/src/tree/dynamic_tree_vertex_add_subtree_sum.rs (line 105)

102pub fn dynamic_tree_vertex_add_subtree_sum(reader: impl Read, writer: impl Write) {
103    prepare_io!(reader, writer);
104    sc!(n, q, a: [u64; n], edges: [(usize, usize); n - 1]);
105    let mut tree = LinkCutTree::<SubtreeSum>::from_edges(a, &edges);
106    for _ in 0..q {
107        sc!(query: Query);
108        match query {
109            Query::Relink { u, v, w, x } => {
110                tree.cut(u, v);
111                tree.link(w, x);
112            }
113            Query::Add { p, x } => tree.modify(p, |value| *value + x),
114            Query::Sum { v, p } => {
115                pp!(tree.fold_subtree(v, p));
116            }
117        }
118    }
119}

crates/library_checker/src/tree/dynamic_tree_vertex_add_path_sum.rs (line 49)

46pub fn dynamic_tree_vertex_add_path_sum(reader: impl Read, writer: impl Write) {
47    prepare_io!(reader, writer);
48    sc!(n, q, a: [i64; n], edges: [(usize, usize); n - 1]);
49    let mut tree = PathLinkCutTree::<EmptyActLazy<AdditiveOperation<i64>>>::from_edges(a, &edges);
50    for _ in 0..q {
51        sc!(query: Query);
52        match query {
53            Query::Relink { u, v, w, x } => {
54                tree.cut(u, v);
55                tree.link(w, x);
56            }
57            Query::Add { p, x } => tree.modify(p, |value| *value + x),
58            Query::Sum { u, v } => {
59                pp!(tree.fold_path(u, v));
60            }
61        }
62    }
63}

crates/library_checker/src/tree/dynamic_tree_vertex_set_path_composite.rs (line 93)

90pub fn dynamic_tree_vertex_set_path_composite(reader: impl Read, writer: impl Write) {
91    prepare_io!(reader, writer);
92    sc!(n, q, ab: [Affine; n], edges: [(usize, usize); n - 1]);
93    let mut tree = PathLinkCutTree::<PathComposite>::from_edges(ab, &edges);
94    for _ in 0..q {
95        sc!(query: Query);
96        match query {
97            Query::Relink { u, v, w, x } => {
98                tree.cut(u, v);
99                tree.link(w, x);
100            }
101            Query::Set { p, cd } => tree.set(p, cd),
102            Query::Apply { u, v, x } => {
103                pp!(LinearOperation::apply(&tree.fold_path(u, v).0, &x));
104            }
105        }
106    }
107}

Source

pub fn add_node(&mut self, value: S::Value) -> usize

Examples found in repository ?

crates/competitive/src/tree/link_cut_tree.rs (line 366)

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    }

Source

fn node( &self, index: usize, ) -> NonNull<BstNode<LinkCutData<S>, WithParent<LinkCutData<S>>>>

Examples found in repository ?

crates/competitive/src/tree/link_cut_tree.rs (line 175)

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    }

Source

unsafe fn pull( node: NonNull<BstNode<LinkCutData<S>, WithParent<LinkCutData<S>>>>, )

Examples found in repository ?

crates/competitive/src/tree/link_cut_tree.rs (line 184)

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    }

Source

unsafe fn splay( node: NonNull<BstNode<LinkCutData<S>, WithParent<LinkCutData<S>>>>, )

Examples found in repository ?

crates/competitive/src/tree/link_cut_tree.rs (line 235)

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    }

Source

fn access_node( node: NonNull<BstNode<LinkCutData<S>, WithParent<LinkCutData<S>>>>, )

Examples found in repository ?

crates/competitive/src/tree/link_cut_tree.rs (line 258)

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    }

Source

pub fn get(&mut self, node: usize) -> &S::Value

Source

pub fn set(&mut self, node: usize, value: S::Value)

Examples found in repository ?

crates/library_checker/src/tree/dynamic_tree_vertex_set_path_composite.rs (line 101)

90pub fn dynamic_tree_vertex_set_path_composite(reader: impl Read, writer: impl Write) {
91    prepare_io!(reader, writer);
92    sc!(n, q, ab: [Affine; n], edges: [(usize, usize); n - 1]);
93    let mut tree = PathLinkCutTree::<PathComposite>::from_edges(ab, &edges);
94    for _ in 0..q {
95        sc!(query: Query);
96        match query {
97            Query::Relink { u, v, w, x } => {
98                tree.cut(u, v);
99                tree.link(w, x);
100            }
101            Query::Set { p, cd } => tree.set(p, cd),
102            Query::Apply { u, v, x } => {
103                pp!(LinearOperation::apply(&tree.fold_path(u, v).0, &x));
104            }
105        }
106    }
107}

Source

pub fn modify<F>(&mut self, node: usize, f: F)
where F: FnOnce(&S::Value) -> S::Value,

Examples found in repository ?

crates/competitive/src/tree/link_cut_tree.rs (line 263)

262    pub fn set(&mut self, node: usize, value: S::Value) {
263        self.modify(node, |_| value);
264    }

More examples

Hide additional examples

crates/library_checker/src/tree/dynamic_tree_vertex_add_subtree_sum.rs (line 113)

102pub fn dynamic_tree_vertex_add_subtree_sum(reader: impl Read, writer: impl Write) {
103    prepare_io!(reader, writer);
104    sc!(n, q, a: [u64; n], edges: [(usize, usize); n - 1]);
105    let mut tree = LinkCutTree::<SubtreeSum>::from_edges(a, &edges);
106    for _ in 0..q {
107        sc!(query: Query);
108        match query {
109            Query::Relink { u, v, w, x } => {
110                tree.cut(u, v);
111                tree.link(w, x);
112            }
113            Query::Add { p, x } => tree.modify(p, |value| *value + x),
114            Query::Sum { v, p } => {
115                pp!(tree.fold_subtree(v, p));
116            }
117        }
118    }
119}

crates/library_checker/src/tree/dynamic_tree_vertex_add_path_sum.rs (line 57)

46pub fn dynamic_tree_vertex_add_path_sum(reader: impl Read, writer: impl Write) {
47    prepare_io!(reader, writer);
48    sc!(n, q, a: [i64; n], edges: [(usize, usize); n - 1]);
49    let mut tree = PathLinkCutTree::<EmptyActLazy<AdditiveOperation<i64>>>::from_edges(a, &edges);
50    for _ in 0..q {
51        sc!(query: Query);
52        match query {
53            Query::Relink { u, v, w, x } => {
54                tree.cut(u, v);
55                tree.link(w, x);
56            }
57            Query::Add { p, x } => tree.modify(p, |value| *value + x),
58            Query::Sum { u, v } => {
59                pp!(tree.fold_path(u, v));
60            }
61        }
62    }
63}

Source

pub fn reroot(&mut self, node: usize)

Examples found in repository ?

crates/competitive/src/tree/link_cut_tree.rs (line 292)

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    }

Source

pub fn link(&mut self, child: usize, parent: usize)

child and parent must belong to different trees.

Examples found in repository ?

crates/library_checker/src/tree/dynamic_tree_subtree_add_subtree_sum.rs (line 193)

184pub fn dynamic_tree_subtree_add_subtree_sum(reader: impl Read, writer: impl Write) {
185    prepare_io!(reader, writer);
186    sc!(n, q, a: [u64; n], edges: [(usize, usize); n - 1]);
187    let mut tree = LinkCutTree::<SubtreeSum>::from_edges(a, &edges);
188    for _ in 0..q {
189        sc!(query: Query);
190        match query {
191            Query::Relink { u, v, w, x } => {
192                tree.cut(u, v);
193                tree.link(w, x);
194            }
195            Query::Add { v, p, x } => tree.update_subtree(v, p, &x),
196            Query::Sum { v, p } => {
197                pp!(tree.fold_subtree(v, p));
198            }
199        }
200    }
201}

More examples

Hide additional examples

crates/library_checker/src/tree/dynamic_tree_vertex_add_subtree_sum.rs (line 111)

102pub fn dynamic_tree_vertex_add_subtree_sum(reader: impl Read, writer: impl Write) {
103    prepare_io!(reader, writer);
104    sc!(n, q, a: [u64; n], edges: [(usize, usize); n - 1]);
105    let mut tree = LinkCutTree::<SubtreeSum>::from_edges(a, &edges);
106    for _ in 0..q {
107        sc!(query: Query);
108        match query {
109            Query::Relink { u, v, w, x } => {
110                tree.cut(u, v);
111                tree.link(w, x);
112            }
113            Query::Add { p, x } => tree.modify(p, |value| *value + x),
114            Query::Sum { v, p } => {
115                pp!(tree.fold_subtree(v, p));
116            }
117        }
118    }
119}

crates/library_checker/src/tree/dynamic_tree_vertex_add_path_sum.rs (line 55)

46pub fn dynamic_tree_vertex_add_path_sum(reader: impl Read, writer: impl Write) {
47    prepare_io!(reader, writer);
48    sc!(n, q, a: [i64; n], edges: [(usize, usize); n - 1]);
49    let mut tree = PathLinkCutTree::<EmptyActLazy<AdditiveOperation<i64>>>::from_edges(a, &edges);
50    for _ in 0..q {
51        sc!(query: Query);
52        match query {
53            Query::Relink { u, v, w, x } => {
54                tree.cut(u, v);
55                tree.link(w, x);
56            }
57            Query::Add { p, x } => tree.modify(p, |value| *value + x),
58            Query::Sum { u, v } => {
59                pp!(tree.fold_path(u, v));
60            }
61        }
62    }
63}

crates/library_checker/src/tree/dynamic_tree_vertex_set_path_composite.rs (line 99)

90pub fn dynamic_tree_vertex_set_path_composite(reader: impl Read, writer: impl Write) {
91    prepare_io!(reader, writer);
92    sc!(n, q, ab: [Affine; n], edges: [(usize, usize); n - 1]);
93    let mut tree = PathLinkCutTree::<PathComposite>::from_edges(ab, &edges);
94    for _ in 0..q {
95        sc!(query: Query);
96        match query {
97            Query::Relink { u, v, w, x } => {
98                tree.cut(u, v);
99                tree.link(w, x);
100            }
101            Query::Set { p, cd } => tree.set(p, cd),
102            Query::Apply { u, v, x } => {
103                pp!(LinearOperation::apply(&tree.fold_path(u, v).0, &x));
104            }
105        }
106    }
107}

Source

pub fn cut(&mut self, u: usize, v: usize)

(u, v) must be an edge.

Examples found in repository ?

crates/library_checker/src/tree/dynamic_tree_subtree_add_subtree_sum.rs (line 192)

184pub fn dynamic_tree_subtree_add_subtree_sum(reader: impl Read, writer: impl Write) {
185    prepare_io!(reader, writer);
186    sc!(n, q, a: [u64; n], edges: [(usize, usize); n - 1]);
187    let mut tree = LinkCutTree::<SubtreeSum>::from_edges(a, &edges);
188    for _ in 0..q {
189        sc!(query: Query);
190        match query {
191            Query::Relink { u, v, w, x } => {
192                tree.cut(u, v);
193                tree.link(w, x);
194            }
195            Query::Add { v, p, x } => tree.update_subtree(v, p, &x),
196            Query::Sum { v, p } => {
197                pp!(tree.fold_subtree(v, p));
198            }
199        }
200    }
201}

More examples

Hide additional examples

crates/library_checker/src/tree/dynamic_tree_vertex_add_subtree_sum.rs (line 110)

102pub fn dynamic_tree_vertex_add_subtree_sum(reader: impl Read, writer: impl Write) {
103    prepare_io!(reader, writer);
104    sc!(n, q, a: [u64; n], edges: [(usize, usize); n - 1]);
105    let mut tree = LinkCutTree::<SubtreeSum>::from_edges(a, &edges);
106    for _ in 0..q {
107        sc!(query: Query);
108        match query {
109            Query::Relink { u, v, w, x } => {
110                tree.cut(u, v);
111                tree.link(w, x);
112            }
113            Query::Add { p, x } => tree.modify(p, |value| *value + x),
114            Query::Sum { v, p } => {
115                pp!(tree.fold_subtree(v, p));
116            }
117        }
118    }
119}

crates/library_checker/src/tree/dynamic_tree_vertex_add_path_sum.rs (line 54)

46pub fn dynamic_tree_vertex_add_path_sum(reader: impl Read, writer: impl Write) {
47    prepare_io!(reader, writer);
48    sc!(n, q, a: [i64; n], edges: [(usize, usize); n - 1]);
49    let mut tree = PathLinkCutTree::<EmptyActLazy<AdditiveOperation<i64>>>::from_edges(a, &edges);
50    for _ in 0..q {
51        sc!(query: Query);
52        match query {
53            Query::Relink { u, v, w, x } => {
54                tree.cut(u, v);
55                tree.link(w, x);
56            }
57            Query::Add { p, x } => tree.modify(p, |value| *value + x),
58            Query::Sum { u, v } => {
59                pp!(tree.fold_path(u, v));
60            }
61        }
62    }
63}

crates/library_checker/src/tree/dynamic_tree_vertex_set_path_composite.rs (line 98)

90pub fn dynamic_tree_vertex_set_path_composite(reader: impl Read, writer: impl Write) {
91    prepare_io!(reader, writer);
92    sc!(n, q, ab: [Affine; n], edges: [(usize, usize); n - 1]);
93    let mut tree = PathLinkCutTree::<PathComposite>::from_edges(ab, &edges);
94    for _ in 0..q {
95        sc!(query: Query);
96        match query {
97            Query::Relink { u, v, w, x } => {
98                tree.cut(u, v);
99                tree.link(w, x);
100            }
101            Query::Set { p, cd } => tree.set(p, cd),
102            Query::Apply { u, v, x } => {
103                pp!(LinearOperation::apply(&tree.fold_path(u, v).0, &x));
104            }
105        }
106    }
107}

Source

pub fn root(&mut self, node: usize) -> usize

Examples found in repository ?

crates/competitive/src/tree/link_cut_tree.rs (line 335)

334    pub fn is_connected(&mut self, u: usize, v: usize) -> bool {
335        self.root(u) == self.root(v)
336    }

Source

pub fn is_connected(&mut self, u: usize, v: usize) -> bool

Source

fn detach_left<R>( node: NonNull<BstNode<LinkCutData<S>, WithParent<LinkCutData<S>>>>, f: impl FnOnce(&mut S::Data) -> R, ) -> R

Examples found in repository ?

crates/competitive/src/tree/link_cut_tree.rs (line 407)

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    }

Source §

impl<S> LinkCutTree<S>
where S: LinkCutTreePathFold,

Source

pub fn fold_path(&mut self, u: usize, v: usize) -> S::Path

u and v must be connected.

Examples found in repository ?

crates/library_checker/src/tree/dynamic_tree_vertex_add_path_sum.rs (line 59)

46pub fn dynamic_tree_vertex_add_path_sum(reader: impl Read, writer: impl Write) {
47    prepare_io!(reader, writer);
48    sc!(n, q, a: [i64; n], edges: [(usize, usize); n - 1]);
49    let mut tree = PathLinkCutTree::<EmptyActLazy<AdditiveOperation<i64>>>::from_edges(a, &edges);
50    for _ in 0..q {
51        sc!(query: Query);
52        match query {
53            Query::Relink { u, v, w, x } => {
54                tree.cut(u, v);
55                tree.link(w, x);
56            }
57            Query::Add { p, x } => tree.modify(p, |value| *value + x),
58            Query::Sum { u, v } => {
59                pp!(tree.fold_path(u, v));
60            }
61        }
62    }
63}

More examples

Hide additional examples

crates/library_checker/src/tree/dynamic_tree_vertex_set_path_composite.rs (line 103)

90pub fn dynamic_tree_vertex_set_path_composite(reader: impl Read, writer: impl Write) {
91    prepare_io!(reader, writer);
92    sc!(n, q, ab: [Affine; n], edges: [(usize, usize); n - 1]);
93    let mut tree = PathLinkCutTree::<PathComposite>::from_edges(ab, &edges);
94    for _ in 0..q {
95        sc!(query: Query);
96        match query {
97            Query::Relink { u, v, w, x } => {
98                tree.cut(u, v);
99                tree.link(w, x);
100            }
101            Query::Set { p, cd } => tree.set(p, cd),
102            Query::Apply { u, v, x } => {
103                pp!(LinearOperation::apply(&tree.fold_path(u, v).0, &x));
104            }
105        }
106    }
107}

Source §

impl<S> LinkCutTree<S>
where S: LinkCutTreePathUpdate,

Source

pub fn update_path(&mut self, u: usize, v: usize, action: &S::PathAction)

u and v must be connected.

Source §

impl<S> LinkCutTree<S>
where S: LinkCutTreeSubtreeFold,

Source

pub fn fold_subtree(&mut self, node: usize, parent: usize) -> S::Subtree

(node, parent) must be an edge.

Examples found in repository ?

crates/library_checker/src/tree/dynamic_tree_subtree_add_subtree_sum.rs (line 197)

184pub fn dynamic_tree_subtree_add_subtree_sum(reader: impl Read, writer: impl Write) {
185    prepare_io!(reader, writer);
186    sc!(n, q, a: [u64; n], edges: [(usize, usize); n - 1]);
187    let mut tree = LinkCutTree::<SubtreeSum>::from_edges(a, &edges);
188    for _ in 0..q {
189        sc!(query: Query);
190        match query {
191            Query::Relink { u, v, w, x } => {
192                tree.cut(u, v);
193                tree.link(w, x);
194            }
195            Query::Add { v, p, x } => tree.update_subtree(v, p, &x),
196            Query::Sum { v, p } => {
197                pp!(tree.fold_subtree(v, p));
198            }
199        }
200    }
201}

More examples

Hide additional examples

crates/library_checker/src/tree/dynamic_tree_vertex_add_subtree_sum.rs (line 115)

102pub fn dynamic_tree_vertex_add_subtree_sum(reader: impl Read, writer: impl Write) {
103    prepare_io!(reader, writer);
104    sc!(n, q, a: [u64; n], edges: [(usize, usize); n - 1]);
105    let mut tree = LinkCutTree::<SubtreeSum>::from_edges(a, &edges);
106    for _ in 0..q {
107        sc!(query: Query);
108        match query {
109            Query::Relink { u, v, w, x } => {
110                tree.cut(u, v);
111                tree.link(w, x);
112            }
113            Query::Add { p, x } => tree.modify(p, |value| *value + x),
114            Query::Sum { v, p } => {
115                pp!(tree.fold_subtree(v, p));
116            }
117        }
118    }
119}

Source §

impl<S> LinkCutTree<S>
where S: LinkCutTreeSubtreeUpdate,

Source

pub fn update_subtree( &mut self, node: usize, parent: usize, action: &S::SubtreeAction, )

(node, parent) must be an edge.

Examples found in repository ?

crates/library_checker/src/tree/dynamic_tree_subtree_add_subtree_sum.rs (line 195)

184pub fn dynamic_tree_subtree_add_subtree_sum(reader: impl Read, writer: impl Write) {
185    prepare_io!(reader, writer);
186    sc!(n, q, a: [u64; n], edges: [(usize, usize); n - 1]);
187    let mut tree = LinkCutTree::<SubtreeSum>::from_edges(a, &edges);
188    for _ in 0..q {
189        sc!(query: Query);
190        match query {
191            Query::Relink { u, v, w, x } => {
192                tree.cut(u, v);
193                tree.link(w, x);
194            }
195            Query::Add { v, p, x } => tree.update_subtree(v, p, &x),
196            Query::Sum { v, p } => {
197                pp!(tree.fold_subtree(v, p));
198            }
199        }
200    }
201}

Trait Implementations§

Source §

impl<S> FromIterator<<S as LinkCutTreeSpec>::Value> for LinkCutTree<S>
where S: LinkCutTreeSpec,

Source §

fn from_iter<T: IntoIterator<Item = S::Value>>(iter: T) -> Self

Creates a value from an iterator. Read more

Auto Trait Implementations§

§

impl<S> !Send for LinkCutTree<S>

§

impl<S> !Sync for LinkCutTree<S>

§

impl<S> Freeze for LinkCutTree<S>
where Vec<NonNull<BstNode<LinkCutData<S>, WithParent<LinkCutData<S>>>>>: Freeze, MemoryPool<BstNode<LinkCutData<S>, WithParent<LinkCutData<S>>>>: Freeze,

§

impl<S> RefUnwindSafe for LinkCutTree<S>
where Vec<NonNull<BstNode<LinkCutData<S>, WithParent<LinkCutData<S>>>>>: RefUnwindSafe, MemoryPool<BstNode<LinkCutData<S>, WithParent<LinkCutData<S>>>>: RefUnwindSafe,

§

impl<S> Unpin for LinkCutTree<S>
where Vec<NonNull<BstNode<LinkCutData<S>, WithParent<LinkCutData<S>>>>>: Unpin, MemoryPool<BstNode<LinkCutData<S>, WithParent<LinkCutData<S>>>>: Unpin,

§

impl<S> UnsafeUnpin for LinkCutTree<S>
where Vec<NonNull<BstNode<LinkCutData<S>, WithParent<LinkCutData<S>>>>>: UnsafeUnpin, MemoryPool<BstNode<LinkCutData<S>, WithParent<LinkCutData<S>>>>: UnsafeUnpin,

§

impl<S> UnwindSafe for LinkCutTree<S>
where Vec<NonNull<BstNode<LinkCutData<S>, WithParent<LinkCutData<S>>>>>: UnwindSafe, MemoryPool<BstNode<LinkCutData<S>, WithParent<LinkCutData<S>>>>: UnwindSafe,

Blanket Implementations§

Source §

impl<T> Any for T
where T: 'static + ?Sized,

Source §

fn type_id(&self) -> TypeId

Gets the TypeId of self. Read more

Source §

impl<T> Borrow<T> for T
where T: ?Sized,

Source §

fn borrow(&self) -> &T

Immutably borrows from an owned value. Read more

Source §

impl<T> BorrowMut<T> for T
where T: ?Sized,

Source §

fn borrow_mut(&mut self) -> &mut T

Mutably borrows from an owned value. Read more

Source §

impl<T> From<T> for T

Source §

fn from(t: T) -> T

Returns the argument unchanged.

Source §

impl<T, U> Into for T
where U: From<T>,

Source §

fn into(self) -> U

Calls U::from(self).

That is, this conversion is whatever the implementation of From<T> for U chooses to do.

Source §

type Error = !

The type returned in the event of a conversion error.

Source §

fn try_from(value: U) -> Result<T, !>

Performs the conversion.

Source §

impl<T, U> TryInto for T
where U: TryFrom<T>,

Source §

type Error = >::Error

The type returned in the event of a conversion error.

Source §

fn try_into(self) -> Result<U, >::Error>

Performs the conversion.

Struct LinkCutTree Copy item path

Fields§

Implementations§

impl<S> LinkCutTree<S>where S: LinkCutTreeSpec,

pub fn with_capacity(capacity: usize) -> Self

pub fn from_edges<T>(values: T, edges: &[(usize, usize)]) -> Selfwhere T: IntoIterator<Item = S::Value>,

pub fn add_node(&mut self, value: S::Value) -> usize

fn node( &self, index: usize, ) -> NonNull<BstNode<LinkCutData<S>, WithParent<LinkCutData<S>>>>

unsafe fn pull( node: NonNull<BstNode<LinkCutData<S>, WithParent<LinkCutData<S>>>>, )

unsafe fn splay( node: NonNull<BstNode<LinkCutData<S>, WithParent<LinkCutData<S>>>>, )

fn access_node( node: NonNull<BstNode<LinkCutData<S>, WithParent<LinkCutData<S>>>>, )

pub fn get(&mut self, node: usize) -> &S::Value

pub fn set(&mut self, node: usize, value: S::Value)

pub fn modify<F>(&mut self, node: usize, f: F)where F: FnOnce(&S::Value) -> S::Value,

pub fn reroot(&mut self, node: usize)

pub fn link(&mut self, child: usize, parent: usize)

pub fn cut(&mut self, u: usize, v: usize)

pub fn root(&mut self, node: usize) -> usize

pub fn is_connected(&mut self, u: usize, v: usize) -> bool

fn detach_left<R>( node: NonNull<BstNode<LinkCutData<S>, WithParent<LinkCutData<S>>>>, f: impl FnOnce(&mut S::Data) -> R, ) -> R

impl<S> LinkCutTree<S>where S: LinkCutTreePathFold,

pub fn fold_path(&mut self, u: usize, v: usize) -> S::Path

impl<S> LinkCutTree<S>where S: LinkCutTreePathUpdate,

pub fn update_path(&mut self, u: usize, v: usize, action: &S::PathAction)

impl<S> LinkCutTree<S>where S: LinkCutTreeSubtreeFold,

pub fn fold_subtree(&mut self, node: usize, parent: usize) -> S::Subtree

impl<S> LinkCutTree<S>where S: LinkCutTreeSubtreeUpdate,

pub fn update_subtree( &mut self, node: usize, parent: usize, action: &S::SubtreeAction, )

Trait Implementations§

impl<S> FromIterator<<S as LinkCutTreeSpec>::Value> for LinkCutTree<S>where S: LinkCutTreeSpec,

fn from_iter<T: IntoIterator<Item = S::Value>>(iter: T) -> Self

Auto Trait Implementations§

impl<S> !Send for LinkCutTree<S>

impl<S> !Sync for LinkCutTree<S>

impl<S> Freeze for LinkCutTree<S>where Vec<NonNull<BstNode<LinkCutData<S>, WithParent<LinkCutData<S>>>>>: Freeze, MemoryPool<BstNode<LinkCutData<S>, WithParent<LinkCutData<S>>>>: Freeze,

impl<S> RefUnwindSafe for LinkCutTree<S>where Vec<NonNull<BstNode<LinkCutData<S>, WithParent<LinkCutData<S>>>>>: RefUnwindSafe, MemoryPool<BstNode<LinkCutData<S>, WithParent<LinkCutData<S>>>>: RefUnwindSafe,

impl<S> Unpin for LinkCutTree<S>where Vec<NonNull<BstNode<LinkCutData<S>, WithParent<LinkCutData<S>>>>>: Unpin, MemoryPool<BstNode<LinkCutData<S>, WithParent<LinkCutData<S>>>>: Unpin,

impl<S> UnsafeUnpin for LinkCutTree<S>where Vec<NonNull<BstNode<LinkCutData<S>, WithParent<LinkCutData<S>>>>>: UnsafeUnpin, MemoryPool<BstNode<LinkCutData<S>, WithParent<LinkCutData<S>>>>: UnsafeUnpin,

impl<S> UnwindSafe for LinkCutTree<S>where Vec<NonNull<BstNode<LinkCutData<S>, WithParent<LinkCutData<S>>>>>: UnwindSafe, MemoryPool<BstNode<LinkCutData<S>, WithParent<LinkCutData<S>>>>: UnwindSafe,

Blanket Implementations§

impl<T> Any for Twhere T: 'static + ?Sized,

fn type_id(&self) -> TypeId

impl<T> Borrow<T> for Twhere T: ?Sized,

fn borrow(&self) -> &T

impl<T> BorrowMut<T> for Twhere T: ?Sized,

fn borrow_mut(&mut self) -> &mut T

impl<T> From<T> for T

fn from(t: T) -> T

impl<T, U> Into<U> for Twhere U: From<T>,

fn into(self) -> U

impl<T> ToArrayVecScalar for T

fn to_array_vec_scalar(self) -> ArrayVecScalar<T>

impl<T, U> TryFrom<U> for Twhere U: Into<T>,

type Error = !

fn try_from(value: U) -> Result<T, !>

impl<T, U> TryInto<U> for Twhere U: TryFrom<T>,

type Error = <U as TryFrom<T>>::Error

fn try_into(self) -> Result<U, <U as TryFrom<T>>::Error>

Struct LinkCutTree

impl<S> LinkCutTree<S>
where S: LinkCutTreeSpec,

pub fn from_edges<T>(values: T, edges: &[(usize, usize)]) -> Self
where T: IntoIterator<Item = S::Value>,

pub fn modify<F>(&mut self, node: usize, f: F)
where F: FnOnce(&S::Value) -> S::Value,

impl<S> LinkCutTree<S>
where S: LinkCutTreePathFold,

impl<S> LinkCutTree<S>
where S: LinkCutTreePathUpdate,

impl<S> LinkCutTree<S>
where S: LinkCutTreeSubtreeFold,

impl<S> LinkCutTree<S>
where S: LinkCutTreeSubtreeUpdate,

impl<S> FromIterator<<S as LinkCutTreeSpec>::Value> for LinkCutTree<S>
where S: LinkCutTreeSpec,

impl<S> Freeze for LinkCutTree<S>
where Vec<NonNull<BstNode<LinkCutData<S>, WithParent<LinkCutData<S>>>>>: Freeze, MemoryPool<BstNode<LinkCutData<S>, WithParent<LinkCutData<S>>>>: Freeze,

impl<S> RefUnwindSafe for LinkCutTree<S>
where Vec<NonNull<BstNode<LinkCutData<S>, WithParent<LinkCutData<S>>>>>: RefUnwindSafe, MemoryPool<BstNode<LinkCutData<S>, WithParent<LinkCutData<S>>>>: RefUnwindSafe,

impl<S> Unpin for LinkCutTree<S>
where Vec<NonNull<BstNode<LinkCutData<S>, WithParent<LinkCutData<S>>>>>: Unpin, MemoryPool<BstNode<LinkCutData<S>, WithParent<LinkCutData<S>>>>: Unpin,

impl<S> UnsafeUnpin for LinkCutTree<S>
where Vec<NonNull<BstNode<LinkCutData<S>, WithParent<LinkCutData<S>>>>>: UnsafeUnpin, MemoryPool<BstNode<LinkCutData<S>, WithParent<LinkCutData<S>>>>: UnsafeUnpin,

impl<S> UnwindSafe for LinkCutTree<S>
where Vec<NonNull<BstNode<LinkCutData<S>, WithParent<LinkCutData<S>>>>>: UnwindSafe, MemoryPool<BstNode<LinkCutData<S>, WithParent<LinkCutData<S>>>>: UnwindSafe,

impl<T> Any for T
where T: 'static + ?Sized,

impl<T> Borrow<T> for T
where T: ?Sized,

impl<T> BorrowMut<T> for T
where T: ?Sized,

impl<T, U> Into<U> for T
where U: From<T>,

impl<T, U> TryFrom<U> for T
where U: Into<T>,

impl<T, U> TryInto<U> for T
where U: TryFrom<T>,