data-structure/link-cut-tree/link-cut-tree-base.hpp

View this file on GitHub
Last update: 2024-06-10 16:05:09+07:00
Include: #include "data-structure/link-cut-tree/link-cut-tree-base.hpp"

Required by

Verified with

verify/yosupo/data-structure/range_affine_range_sum_lct.test.cpp

Code

#pragma once

/**
 * Author: Teetat T.
 * Date: 2024-05-19
 * Description: Link Cut Tree Base.
 * Usage:
 *  evert(u): make u be the root of the tree.
 *  link(u,v): attach u to v.
 *  cut(u,v): remove edge between u and v.
 *  get_root(u): get the root of the tree containing u.
 *  lca(u,v): get the lowest common ancestor of u and v.
 *  fold(u,v): get the value of the path from u to v.
 */

template<class Splay>
struct LinkCutTreeBase:Splay{
    using Node = typename Splay::Node;
    using Ptr = Node*;
    using T = typename Node::value_type;
    Ptr expose(Ptr t){
        Ptr pc=nullptr; // preferred child
        for(Ptr cur=t;cur;cur=cur->p){
            this->splay(cur);
            cur->r=pc;
            this->pull(cur);
            pc=cur;
        }
        this->splay(t);
        return pc;
    }
    void evert(Ptr t){ // make t be the root of the tree
        expose(t);
        this->toggle(t);
        this->push(t);
    }
    void link(Ptr u,Ptr v){ // attach u to v
        evert(u);
        expose(v);
        u->p=v;
    }
    void cut(Ptr u,Ptr v){ // cut edge between u and v
        evert(u);
        expose(v);
        assert(u->p==v);
        v->l=u->p=nullptr;
        this->pull(v);
    }
    Ptr get_root(Ptr t){
        expose(t);
        while(t->l)this->push(t),t=t->l;
        this->splay(t);
        return t;
    }
    Ptr lca(Ptr u,Ptr v){
        if(get_root(u)!=get_root(v))return nullptr;
        expose(u);
        return expose(v);
    }
    void set_val(Ptr t,const T &val){
        this->evert(t);
        t->val=val;
        this->pull(t);
    }
    T get_val(Ptr t){
        this->evert(t);
        return t->val;
    }
    T fold(Ptr u,Ptr v){
        evert(u);
        expose(v);
        return v->sum;
    }
};

#line 2 "data-structure/link-cut-tree/link-cut-tree-base.hpp"

/**
 * Author: Teetat T.
 * Date: 2024-05-19
 * Description: Link Cut Tree Base.
 * Usage:
 *  evert(u): make u be the root of the tree.
 *  link(u,v): attach u to v.
 *  cut(u,v): remove edge between u and v.
 *  get_root(u): get the root of the tree containing u.
 *  lca(u,v): get the lowest common ancestor of u and v.
 *  fold(u,v): get the value of the path from u to v.
 */

template<class Splay>
struct LinkCutTreeBase:Splay{
    using Node = typename Splay::Node;
    using Ptr = Node*;
    using T = typename Node::value_type;
    Ptr expose(Ptr t){
        Ptr pc=nullptr; // preferred child
        for(Ptr cur=t;cur;cur=cur->p){
            this->splay(cur);
            cur->r=pc;
            this->pull(cur);
            pc=cur;
        }
        this->splay(t);
        return pc;
    }
    void evert(Ptr t){ // make t be the root of the tree
        expose(t);
        this->toggle(t);
        this->push(t);
    }
    void link(Ptr u,Ptr v){ // attach u to v
        evert(u);
        expose(v);
        u->p=v;
    }
    void cut(Ptr u,Ptr v){ // cut edge between u and v
        evert(u);
        expose(v);
        assert(u->p==v);
        v->l=u->p=nullptr;
        this->pull(v);
    }
    Ptr get_root(Ptr t){
        expose(t);
        while(t->l)this->push(t),t=t->l;
        this->splay(t);
        return t;
    }
    Ptr lca(Ptr u,Ptr v){
        if(get_root(u)!=get_root(v))return nullptr;
        expose(u);
        return expose(v);
    }
    void set_val(Ptr t,const T &val){
        this->evert(t);
        t->val=val;
        this->pull(t);
    }
    T get_val(Ptr t){
        this->evert(t);
        return t->val;
    }
    T fold(Ptr u,Ptr v){
        evert(u);
        expose(v);
        return v->sum;
    }
};