Link-Cut-Tree (structure/develop/link-cut-tree.hpp)

• View this file on GitHub
• Last update: 2024-04-27 01:27:28+09:00
• Include: #include "structure/develop/link-cut-tree.hpp"

Verified with

• test/verify/aoj-2450-3.test.cpp
• test/verify/yosupo-dynamic-tree-vertex-add-path-sum-2.test.cpp
• test/verify/yosupo-dynamic-tree-vertex-set-path-composite-2.test.cpp

Code

/**
 * @brief Link-Cut-Tree
 */
template <typename STp>
struct LinkCutTree : STp {
  using ST = STp;
  using ST::ST;
  using Node = typename ST::Node;

  Node *expose(Node *t) {
    Node *rp = nullptr;
    for (Node *cur = t; cur; cur = cur->p) {
      this->splay(cur);
      cur->r = rp;
      this->update(cur);
      rp = cur;
    }
    this->splay(t);
    return rp;
  }

  void link(Node *child, Node *parent) {
    expose(child);
    expose(parent);
    child->p = parent;
    parent->r = child;
    this->update(parent);
  }

  void cut(Node *child) {
    expose(child);
    auto *parent = child->l;
    child->l = nullptr;
    parent->p = nullptr;
    this->update(child);
  }

  void evert(Node *t) {
    expose(t);
    this->toggle(t);
    this->push(t);
  }

  Node *lca(Node *u, Node *v) {
    if (get_root(u) != get_root(v)) return nullptr;
    expose(u);
    return expose(v);
  }

  Node *get_kth(Node *x, int k) {
    expose(x);
    while (x) {
      this->push(x);
      if (x->r && x->r->sz > k) {
        x = x->r;
      } else {
        if (x->r) k -= x->r->sz;
        if (k == 0) return x;
        k -= 1;
        x = x->l;
      }
    }
    return nullptr;
  }

  Node *get_root(Node *x) {
    expose(x);
    while (x->l) {
      this->push(x);
      x = x->l;
    }
    return x;
  }
};

#line 1 "structure/develop/link-cut-tree.hpp"
/**
 * @brief Link-Cut-Tree
 */
template <typename STp>
struct LinkCutTree : STp {
  using ST = STp;
  using ST::ST;
  using Node = typename ST::Node;

  Node *expose(Node *t) {
    Node *rp = nullptr;
    for (Node *cur = t; cur; cur = cur->p) {
      this->splay(cur);
      cur->r = rp;
      this->update(cur);
      rp = cur;
    }
    this->splay(t);
    return rp;
  }

  void link(Node *child, Node *parent) {
    expose(child);
    expose(parent);
    child->p = parent;
    parent->r = child;
    this->update(parent);
  }

  void cut(Node *child) {
    expose(child);
    auto *parent = child->l;
    child->l = nullptr;
    parent->p = nullptr;
    this->update(child);
  }

  void evert(Node *t) {
    expose(t);
    this->toggle(t);
    this->push(t);
  }

  Node *lca(Node *u, Node *v) {
    if (get_root(u) != get_root(v)) return nullptr;
    expose(u);
    return expose(v);
  }

  Node *get_kth(Node *x, int k) {
    expose(x);
    while (x) {
      this->push(x);
      if (x->r && x->r->sz > k) {
        x = x->r;
      } else {
        if (x->r) k -= x->r->sz;
        if (k == 0) return x;
        k -= 1;
        x = x->l;
      }
    }
    return nullptr;
  }

  Node *get_root(Node *x) {
    expose(x);
    while (x->l) {
      this->push(x);
      x = x->l;
    }
    return x;
  }
};

Back to top page