部分木クエリLink/Cut Tree
(lct/link-cut-tree-subtree.hpp)

• View this file on GitHub
• Last update: 2026-06-08 17:59:24+09:00
• Include: #include "lct/link-cut-tree-subtree.hpp"

Depends on

• Link/Cut Tree(base) (lct/link-cut-base.hpp)
• 反転可能平衡二分木(基底クラス) (lct/reversible-bbst-base.hpp)
• Splay Tree(base) (lct/splay-base.hpp)

Verified with

• verify/verify-yosupo-ds/yosupo-dynamic-tree-vertex-add-subtree-sum.test.cpp
• verify/verify-yosupo-ds/yosupo-offline-dynamic-connectivity.test.cpp

Code

#pragma once

#include "reversible-bbst-base.hpp"
#include "splay-base.hpp"

template <typename T, T (*f)(T, T), T (*finv)(T, T)>
struct LinkCutForSubtreeNode {
  using Node = LinkCutForSubtreeNode;
  using Ptr = LinkCutForSubtreeNode*;
  Ptr l, r, p;
  T key, sum, sub;
  int cnt;
  bool rev;

  LinkCutForSubtreeNode(const T& t = T())
      : l(), r(), p(), key(t), sum(t), sub(T()), cnt(1), rev(false) {}
  void add(Node* other) { sub = f(sub, other->sum); }
  void erase(Node* other) { sub = finv(sub, other->sum); }
  void merge(Node* n1, Node* n2) {
    sum = f(f(n1 ? n1->sum : T(), key), f(sub, n2 ? n2->sum : T()));
  }
};

template <typename T, T (*f)(T, T), T (*finv)(T, T)>
struct SplayTreeForLCSubtree
    : ReversibleBBST<SplayTreeBase<LinkCutForSubtreeNode<T, f, finv>>,
                     LinkCutForSubtreeNode<T, f, finv>, T, nullptr, nullptr> {
  using Node = LinkCutForSubtreeNode<T, f, finv>;
};
//
#include "link-cut-base.hpp"

template <typename T, T (*f)(T, T), T (*finv)(T, T)>
struct LinkCutTreeSubtreeQuery
    : LinkCutBase<SplayTreeForLCSubtree<T, f, finv>> {
  using base = LinkCutBase<SplayTreeForLCSubtree<T, f, finv>>;
  using Node = typename base::Node;
  using Ptr = typename base::Ptr;

  Ptr expose(Ptr t) override {
    Ptr rp = nullptr;
    for (Ptr cur = t; cur; cur = cur->p) {
      this->splay(cur);
      if (cur->r) cur->add(cur->r);
      cur->r = rp;
      if (cur->r) cur->erase(cur->r);
      this->update(cur);
      rp = cur;
    }
    this->splay(t);
    return rp;
  }

  void link(Ptr u, Ptr v) override {
    this->evert(u);
    this->expose(v);
    u->p = v;
    v->add(u);
  }

  void toggle(Ptr t) override {
    if(!t) return;
    swap(t->l, t->r);
    t->rev ^= true;
  }

  Ptr update(Ptr t) override {
    if (!t) return t;
    t->cnt = 1 + this->count(t->l) + this->count(t->r);
    t->merge(t->l, t->r);
    return t;
  }

  void set_key(Ptr t, const T& key) override {
    this->expose(t);
    t->key = key;
    this->update(t);
  }

  T subtree(Ptr t) {
    this->expose(t);
    return f(t->key, t->sub);
  }
};

/**
 * @brief 部分木クエリLink/Cut Tree
 */

#line 2 "lct/link-cut-tree-subtree.hpp"

#line 2 "lct/reversible-bbst-base.hpp"

template <typename Tree, typename Node, typename T, T (*f)(T, T), T (*ts)(T)>
struct ReversibleBBST : Tree {
  using Tree::merge;
  using Tree::split;
  using typename Tree::Ptr;

  ReversibleBBST() = default;

  virtual void toggle(Ptr t) {
    if(!t) return;
    swap(t->l, t->r);
    t->sum = ts(t->sum);
    t->rev ^= true;
  }

  T fold(Ptr &t, int a, int b) {
    auto x = split(t, a);
    auto y = split(x.second, b - a);
    auto ret = sum(y.first);
    t = merge(x.first, merge(y.first, y.second));
    return ret;
  }

  void reverse(Ptr &t, int a, int b) {
    auto x = split(t, a);
    auto y = split(x.second, b - a);
    toggle(y.first);
    t = merge(x.first, merge(y.first, y.second));
  }

  Ptr update(Ptr t) override {
    if (!t) return t;
    t->cnt = 1;
    t->sum = t->key;
    if (t->l) t->cnt += t->l->cnt, t->sum = f(t->l->sum, t->sum);
    if (t->r) t->cnt += t->r->cnt, t->sum = f(t->sum, t->r->sum);
    return t;
  }

 protected:
  inline T sum(const Ptr t) { return t ? t->sum : T(); }

  void push(Ptr t) override {
    if (!t) return;
    if (t->rev) {
      if (t->l) toggle(t->l);
      if (t->r) toggle(t->r);
      t->rev = false;
    }
  }
};

/**
 * @brief 反転可能平衡二分木(基底クラス)
 */
#line 2 "lct/splay-base.hpp"

template <typename Node>
struct SplayTreeBase {
  using Ptr = Node *;
  template <typename... Args>
  Ptr my_new(const Args &...args) {
    return new Node(args...);
  }
  void my_del(Ptr p) { delete p; }

  bool is_root(Ptr t) { return !(t->p) || (t->p->l != t && t->p->r != t); }

  int size(Ptr t) const { return count(t); }

  virtual void splay(Ptr t) {
    if (!t) return;
    push(t);
    while (!is_root(t)) {
      Ptr q = t->p;
      if (is_root(q)) {
        push(q), push(t);
        rot(t);
      } else {
        Ptr r = q->p;
        push(r), push(q), push(t);
        if (pos(q) == pos(t))
          rot(q), rot(t);
        else
          rot(t), rot(t);
      }
    }
  }

  Ptr get_left(Ptr t) {
    while (t->l) push(t), t = t->l;
    return t;
  }

  Ptr get_right(Ptr t) {
    while (t->r) push(t), t = t->r;
    return t;
  }

  Ptr kth(Ptr t, int k) {
    while (true) {
      push(t);
      int lsz = count(t->l);
      if (k < lsz) {
        t = t->l;
      } else if (k == lsz) {
        splay(t);
        return t;
      } else {
        k -= lsz + 1;
        t = t->r;
      }
    }
  }

  pair<Ptr, Ptr> split(Ptr t, int k) {
    if (!t) return {nullptr, nullptr};
    if (k == 0) return {nullptr, t};
    if (k == count(t)) return {t, nullptr};

    Ptr r = kth(t, k);
    Ptr l = r->l;
    r->l = nullptr;
    if (l) l->p = nullptr;
    update(r);
    return {l, r};
  }

  Ptr merge(Ptr l, Ptr r) {
    if (!l && !r) return nullptr;
    if (!l) return r;
    if (!r) return l;

    l = kth(l, count(l) - 1);
    l->r = r;
    r->p = l;
    update(l);
    return l;
  }

  using Key = decltype(Node::key);
  Ptr build(const vector<Key> &v) { return build(0, v.size(), v); }
  Ptr build(int l, int r, const vector<Key> &v) {
    if (l == r) return nullptr;
    if (l + 1 == r) return my_new(v[l]);
    return merge(build(l, (l + r) >> 1, v), build((l + r) >> 1, r, v));
  }

  template <typename... Args>
  void insert(Ptr &t, int k, const Args &...args) {
    splay(t);
    auto x = split(t, k);
    t = merge(merge(x.first, my_new(args...)), x.second);
  }

  void erase(Ptr &t, int k) {
    splay(t);
    auto x = split(t, k);
    auto y = split(x.second, 1);
    my_del(y.first);
    t = merge(x.first, y.second);
  }

  virtual Ptr update(Ptr t) = 0;

 protected:
  inline int count(Ptr t) const { return t ? t->cnt : 0; }

  virtual void push(Ptr t) = 0;

  Ptr build(const vector<Ptr> &v) { return build(0, v.size(), v); }

  Ptr build(int l, int r, const vector<Ptr> &v) {
    if (l + 1 >= r) return v[l];
    return merge(build(l, (l + r) >> 1, v), build((l + r) >> 1, r, v));
  }

  inline int pos(Ptr t) {
    if (t->p) {
      if (t->p->l == t) return -1;
      if (t->p->r == t) return 1;
    }
    return 0;
  }

  virtual void rot(Ptr t) {
    Ptr x = t->p, y = x->p;
    if (pos(t) == -1) {
      if ((x->l = t->r)) t->r->p = x;
      t->r = x, x->p = t;
    } else {
      if ((x->r = t->l)) t->l->p = x;
      t->l = x, x->p = t;
    }
    update(x), update(t);
    if ((t->p = y)) {
      if (y->l == x) y->l = t;
      if (y->r == x) y->r = t;
    }
  }
};

/**
 * @brief Splay Tree(base)
 */
#line 5 "lct/link-cut-tree-subtree.hpp"

template <typename T, T (*f)(T, T), T (*finv)(T, T)>
struct LinkCutForSubtreeNode {
  using Node = LinkCutForSubtreeNode;
  using Ptr = LinkCutForSubtreeNode*;
  Ptr l, r, p;
  T key, sum, sub;
  int cnt;
  bool rev;

  LinkCutForSubtreeNode(const T& t = T())
      : l(), r(), p(), key(t), sum(t), sub(T()), cnt(1), rev(false) {}
  void add(Node* other) { sub = f(sub, other->sum); }
  void erase(Node* other) { sub = finv(sub, other->sum); }
  void merge(Node* n1, Node* n2) {
    sum = f(f(n1 ? n1->sum : T(), key), f(sub, n2 ? n2->sum : T()));
  }
};

template <typename T, T (*f)(T, T), T (*finv)(T, T)>
struct SplayTreeForLCSubtree
    : ReversibleBBST<SplayTreeBase<LinkCutForSubtreeNode<T, f, finv>>,
                     LinkCutForSubtreeNode<T, f, finv>, T, nullptr, nullptr> {
  using Node = LinkCutForSubtreeNode<T, f, finv>;
};
//
#line 2 "lct/link-cut-base.hpp"

template <typename Splay>
struct LinkCutBase : Splay {
  using Node = typename Splay::Node;
  using Ptr = Node*;

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

  virtual void link(Ptr u, Ptr v) {
    evert(u);
    expose(v);
    u->p = v;
  }

  void cut(Ptr u, Ptr v) {
    evert(u);
    expose(v);
    assert(u->p == v);
    v->l = u->p = nullptr;
    this->update(v);
  }

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

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

  Ptr get_kth(Ptr 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;
  }

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

  Ptr get_parent(Ptr x) {
    expose(x);
    Ptr p = x->l;
    if(p == nullptr) return nullptr;
    while (true) {
      this->push(p);
      if (p->r == nullptr) return p;
      p = p->r;
    }
    exit(1);
  }

  virtual void set_key(Ptr t, const decltype(Node::key)& key) {
    this->splay(t);
    t->key = key;
    this->update(t);
  }

  virtual decltype(Node::key) get_key(Ptr t) { return t->key; }

  decltype(Node::key) fold(Ptr u, Ptr v) {
    evert(u);
    expose(v);
    return v->sum;
  }
};

/**
 * @brief Link/Cut Tree(base)
 */
#line 32 "lct/link-cut-tree-subtree.hpp"

template <typename T, T (*f)(T, T), T (*finv)(T, T)>
struct LinkCutTreeSubtreeQuery
    : LinkCutBase<SplayTreeForLCSubtree<T, f, finv>> {
  using base = LinkCutBase<SplayTreeForLCSubtree<T, f, finv>>;
  using Node = typename base::Node;
  using Ptr = typename base::Ptr;

  Ptr expose(Ptr t) override {
    Ptr rp = nullptr;
    for (Ptr cur = t; cur; cur = cur->p) {
      this->splay(cur);
      if (cur->r) cur->add(cur->r);
      cur->r = rp;
      if (cur->r) cur->erase(cur->r);
      this->update(cur);
      rp = cur;
    }
    this->splay(t);
    return rp;
  }

  void link(Ptr u, Ptr v) override {
    this->evert(u);
    this->expose(v);
    u->p = v;
    v->add(u);
  }

  void toggle(Ptr t) override {
    if(!t) return;
    swap(t->l, t->r);
    t->rev ^= true;
  }

  Ptr update(Ptr t) override {
    if (!t) return t;
    t->cnt = 1 + this->count(t->l) + this->count(t->r);
    t->merge(t->l, t->r);
    return t;
  }

  void set_key(Ptr t, const T& key) override {
    this->expose(t);
    t->key = key;
    this->update(t);
  }

  T subtree(Ptr t) {
    this->expose(t);
    return f(t->key, t->sub);
  }
};

/**
 * @brief 部分木クエリLink/Cut Tree
 */

Back to top page