Link-Cut-Tree (src/DataStructure/LinkCutTree.hpp)

• View this file on GitHub
• View document part on GitHub
• Last update: 2024-09-01 12:11:12+09:00
• Include: #include "src/DataStructure/LinkCutTree.hpp"
• Link: View error logs on GitHub Actions

概要

Link-Cut Tree は木の集合を管理するデータ構造。以下の操作を効率的に行うことができる。

• link(u, v): ２つの木に属する頂点 u, v を辺で結ぶ。u は v の子となる。
• cut(u, v): 頂点 u, v を結ぶ辺を切り離す。
• evert(u): 頂点 u を全体の根にする。
• パスに対するクエリ: prod(u, v) で u-v パスの集約値、apply(u, v, x) で u-v パスへの作用を適用できる。
• lca(u, v): 最小共通祖先を求める。

テンプレートパラメータ

LinkCutTree<M> のように、作用素モノイド M をテンプレートパラメータとして渡すことで、ノードが持つ値の型や、パスに対する操作をカスタマイズできる。

M は以下のメンバを持つ構造体として定義する。

• using T = ...: ノードが持つ値の型
• using E = ...: パスへの作用素の型
• static T op(const T &l, const T &r): 値のマージ演算。prod で使われる。
• static void mp(T &v, const E &f): 値 v に作用素 f を適用する。apply で使われる。
• static void cp(E &f, const E &g): 作用素 f に作用素 g を合成する。apply で使われる。
• using commute = void: op が可換である場合に定義する。

計算量

各操作のならし計算量は $O(\log n)$ である。

インターフェース

• LinkCutTree(size_t sz): sz 個の頂点を持つ森を構築する。
• LinkCutTree(size_t sz, T val): sz 個の頂点を持つ森を構築し、全頂点の値を val で初期化する。
• evert(int k): 頂点 k を根にする。
• link(int c, int p): c の親が p となるように辺を張る。
• cut(int c, int p): c と親 p を結ぶ辺を削除する。
• root(int x): x が属する木の根を返す。
• parent(int x): x の親を返す。根の場合は -1 を返す。
• lca(int x, int y): x と y の最小共通祖先を返す。同じ木に属さない場合は -1 を返す。
• get(int k) / operator[](int k): 頂点 k の値を取得する。
• set(int k, const T &v): 頂点 k の値を v に設定する。
• prod(int a, int b): パス a-b 上の頂点の値の集約結果（opによる）を返す。
• apply(int a, int b, const E &v): パス a-b 上の各頂点に作用 v を適用する。

使用例

パス上のノードの値（long long）の和を求める例。

#include "src/DataStructure/LinkCutTree.hpp"
#include <iostream>

// モノイドを定義
struct RsumQ {
    using T = long long;
    static T op(const T &l, const T &r) { return l + r; }
    // op は可換
    using commute = void;
};

int main() {
    int N = 5;
    LinkCutTree<RsumQ> lct(N);

    // 初期値を設定
    for (int i = 0; i < N; ++i) {
        lct.set(i, i + 1);
    }

    // 木の構造を定義
    // 1 -- 0 -- 2
    //      |
    //      3 -- 4
    lct.link(1, 0);
    lct.link(2, 0);
    lct.link(3, 0);
    lct.link(4, 3);

    // パス 1-4 の和を計算 (1-0-3-4)
    // 1-0-3-4 の値は 2, 1, 4, 5
    // 2 + 1 + 4 + 5 = 12
    long long sum = lct.prod(1, 4);
    std::cout << "Sum on path 1-4: " << sum << std::endl; // 12

    // 頂点 0 の値を 10 に更新
    lct.set(0, 10);

    // 再度パス 1-4 の和を計算
    // 1-0-3-4 の値は 2, 10, 4, 5
    // 2 + 10 + 4 + 5 = 21
    sum = lct.prod(1, 4);
    std::cout << "Sum on path 1-4 after update: " << sum << std::endl; // 21
}

Depends on

• detection idiom (src/Internal/detection_idiom.hpp)

Verified with

• test/aoj/2450.LCT.test.cpp
• test/aoj/2559.LCT.test.cpp
• test/yosupo/dynamic_tree_vertex_add_path_sum.LCT.test.cpp
• test/yosupo/dynamic_tree_vertex_set_path_composite.LCT.test.cpp
• test/yosupo/lca.LCT.test.cpp
• test/yosupo/vertex_add_path_sum.LCT.test.cpp
• test/yosupo/vertex_set_path_composite.LCT.test.cpp
• test/yukicoder/235.LCT.test.cpp
• test/yukicoder/529.LCT.test.cpp
• test/yukicoder/650.LCT.test.cpp

Code

#pragma once
#include <algorithm>
#include <vector>
#include <string>
#include <cstddef>
#include <utility>
#include <cassert>
#include "src/Internal/detection_idiom.hpp"
template <class M= void> class LinkCutTree {
 _DETECT_BOOL(semigroup, typename T::T, decltype(&T::op));
 _DETECT_BOOL(dual, typename T::T, typename T::E, decltype(&T::mp), decltype(&T::cp));
 _DETECT_BOOL(commute, typename T::commute);
 _DETECT_TYPE(myself_or_T, typename T::T, T, typename T::T);
 _DETECT_TYPE(nullptr_or_E, typename T::E, std::nullptr_t, typename T::E);
 using T= std::conditional_t<std::is_void_v<M>, std::nullptr_t, typename myself_or_T<M>::type>;
 using E= typename nullptr_or_E<M>::type;
 struct NodeB {
  int ch[2]= {-1, -1}, par= -1;
  bool revf= 0;
 };
 template <class D, class A> struct NodeV: NodeB {
  T val;
 };
 template <class D> struct NodeV<D, void>: NodeB {};
 template <class D, bool du> struct NodeD: NodeV<D, M> {};
 template <class D> struct NodeD<D, 1>: NodeV<D, M> {
  E laz;
  bool lazf= 0;
 };
 template <class D, bool sg, bool com> struct NodeS: NodeD<D, dual_v<M>> {};
 template <class D> struct NodeS<D, 1, 1>: NodeD<D, dual_v<M>> {
  T sum;
 };
 template <class D> struct NodeS<D, 1, 0>: NodeD<D, dual_v<M>> {
  T sum, rsum;
 };
 using Node= NodeS<void, semigroup_v<M>, commute_v<M>>;
 std::vector<Node> n;
 inline void update(int i) {
  n[i].sum= n[i].val;
  if constexpr (!commute_v<M>) n[i].rsum= n[i].val;
  if (int l= n[i].ch[0]; l != -1) {
   n[i].sum= M::op(n[l].sum, n[i].sum);
   if constexpr (!commute_v<M>) n[i].rsum= M::op(n[i].rsum, n[l].rsum);
  }
  if (int r= n[i].ch[1]; r != -1) {
   n[i].sum= M::op(n[i].sum, n[r].sum);
   if constexpr (!commute_v<M>) n[i].rsum= M::op(n[r].rsum, n[i].rsum);
  }
 }
 inline void propagate(int i, const E &x) {
  if (i == -1) return;
  if (n[i].lazf) M::cp(n[i].laz, x);
  else n[i].laz= x;
  if constexpr (semigroup_v<M>) {
   M::mp(n[i].sum, x);
   if constexpr (!commute_v<M>) M::mp(n[i].rsum, x);
  }
  M::mp(n[i].val, x), n[i].lazf= 1;
 }
 inline void toggle(int i) {
  if (i == -1) return;
  std::swap(n[i].ch[0], n[i].ch[1]);
  if constexpr (semigroup_v<M> && !commute_v<M>) std::swap(n[i].sum, n[i].rsum);
  n[i].revf^= 1;
 }
 inline void push(int i) {
  if (n[i].revf) toggle(n[i].ch[0]), toggle(n[i].ch[1]), n[i].revf= 0;
  if constexpr (dual_v<M>)
   if (n[i].lazf) propagate(n[i].ch[0], n[i].laz), propagate(n[i].ch[1], n[i].laz), n[i].lazf= 0;
 }
 inline int dir(int i) {
  if (int p= n[i].par; p != -1) {
   if (n[p].ch[0] == i) return 0;
   if (n[p].ch[1] == i) return 1;
  }
  return 2;
 }
 inline void rot(int i) {
  int p= n[i].par, d= n[p].ch[1] == i;
  if (int c= n[p].ch[d]= std::exchange(n[i].ch[!d], p); c != -1) n[c].par= p;
  if (d= dir(p); d < 2) n[n[p].par].ch[d]= i;
  n[i].par= std::exchange(n[p].par, i);
  if constexpr (semigroup_v<M>) update(p);
 }
 inline void splay(int i) {
  push(i);
  for (int d; d= dir(i), d < 2; rot(i))
   if (int p= n[i].par, c= dir(p), pp= n[p].par; c < 2) push(pp), push(p), push(i), rot(d == c ? p : i);
   else push(p), push(i);
  if constexpr (semigroup_v<M>) update(i);
 }
 inline int expose(int i) {
  int r= -1;
  for (int p= i; p != -1; r= p, p= n[p].par) {
   splay(p), n[p].ch[1]= r;
   if constexpr (semigroup_v<M>) update(p);
  }
  return splay(i), r;
 }
public:
 LinkCutTree(size_t sz): n(sz) {}
 LinkCutTree(size_t sz, T val): n(sz) {
  for (int i= sz; i--;) n[i].val= val;
 }
 void evert(int k) { expose(k), toggle(k), push(k); }
 void link(int c, int p) {
  evert(c), expose(p), assert(n[c].par == -1), n[p].ch[1]= c, n[c].par= p;
  if constexpr (semigroup_v<M>) update(p);
 }
 void cut(int c, int p) {
  evert(p), expose(c), assert(n[c].ch[0] == p), n[c].ch[0]= n[p].par= -1;
  if constexpr (semigroup_v<M>) update(c);
 }
 int root(int x) {
  for (expose(x);; x= n[x].ch[0])
   if (push(x), n[x].ch[0] == -1) return splay(x), x;
 }
 int parent(int x) {
  if (expose(x), x= n[x].ch[0]; x == -1) return -1;
  for (;; x= n[x].ch[1])
   if (push(x), n[x].ch[1] == -1) return splay(x), x;
 }
 int lca(int x, int y) { return x == y ? x : (expose(x), y= expose(y), n[x].par == -1) ? -1 : y; }
 const T &get(int k) {
  static_assert(!std::is_void_v<M>, "\"get\" is not available\n");
  return expose(k), n[k].val;
 }
 T &at(int k) {
  static_assert(!std::is_void_v<M> && !semigroup_v<M>, "\"at\" is not available\n");
  return expose(k), n[k].val;
 }
 template <class L= M> const std::enable_if_t<semigroup_v<L>, T> &operator[](size_t k) { return get(k); }
 template <class L= M> std::enable_if_t<!semigroup_v<L>, T> &operator[](size_t k) { return at(k); }
 void set(int k, const T &v) {
  static_assert(!std::is_void_v<M>, "\"set\" is not available\n");
  expose(k), n[k].val= v;
  if constexpr (semigroup_v<M>) update(k);
 }
 void mul(int k, const T &v) {
  static_assert(semigroup_v<M> && commute_v<M>, "\"mul\" is not available\n");
  expose(k), n[k].val= M::op(n[k].val, v), update(k);
 }
 // [a,b] closed section
 T prod(int a, int b) {
  static_assert(semigroup_v<M>, "\"prod\" is not available\n");
  return a == b ? get(a) : (evert(a), expose(b), assert(n[a].par != -1), n[b].sum);
 }
 // [a,b] closed section
 void apply(int a, int b, const E &v) {
  static_assert(dual_v<M>, "\"apply\" is not available\n");
  evert(a), expose(b), assert(a == b || n[a].par != -1), propagate(b, v), push(b);
 }
 static std::string which_unavailable() {
  std::string ret= "";
  if constexpr (semigroup_v<M>) ret+= "\"at\" ";
  else ret+= "\"prod\" ";
  if constexpr (!semigroup_v<M> || !commute_v<M>) ret+= "\"mul\" ";
  if constexpr (!dual_v<M>) ret+= "\"apply\" ";
  if constexpr (std::is_void_v<M>) ret+= "\"get\" \"set\" ";
  return ret;
 }
};

#line 2 "src/DataStructure/LinkCutTree.hpp"
#include <algorithm>
#include <vector>
#include <string>
#include <cstddef>
#include <utility>
#include <cassert>
#line 2 "src/Internal/detection_idiom.hpp"
#include <type_traits>
#define _DETECT_BOOL(name, ...) \
 template <class, class= void> struct name: std::false_type {}; \
 template <class T> struct name<T, std::void_t<__VA_ARGS__>>: std::true_type {}; \
 template <class T> static constexpr bool name##_v= name<T>::value
#define _DETECT_TYPE(name, type1, type2, ...) \
 template <class T, class= void> struct name { \
  using type= type2; \
 }; \
 template <class T> struct name<T, std::void_t<__VA_ARGS__>> { \
  using type= type1; \
 }
#line 9 "src/DataStructure/LinkCutTree.hpp"
template <class M= void> class LinkCutTree {
 _DETECT_BOOL(semigroup, typename T::T, decltype(&T::op));
 _DETECT_BOOL(dual, typename T::T, typename T::E, decltype(&T::mp), decltype(&T::cp));
 _DETECT_BOOL(commute, typename T::commute);
 _DETECT_TYPE(myself_or_T, typename T::T, T, typename T::T);
 _DETECT_TYPE(nullptr_or_E, typename T::E, std::nullptr_t, typename T::E);
 using T= std::conditional_t<std::is_void_v<M>, std::nullptr_t, typename myself_or_T<M>::type>;
 using E= typename nullptr_or_E<M>::type;
 struct NodeB {
  int ch[2]= {-1, -1}, par= -1;
  bool revf= 0;
 };
 template <class D, class A> struct NodeV: NodeB {
  T val;
 };
 template <class D> struct NodeV<D, void>: NodeB {};
 template <class D, bool du> struct NodeD: NodeV<D, M> {};
 template <class D> struct NodeD<D, 1>: NodeV<D, M> {
  E laz;
  bool lazf= 0;
 };
 template <class D, bool sg, bool com> struct NodeS: NodeD<D, dual_v<M>> {};
 template <class D> struct NodeS<D, 1, 1>: NodeD<D, dual_v<M>> {
  T sum;
 };
 template <class D> struct NodeS<D, 1, 0>: NodeD<D, dual_v<M>> {
  T sum, rsum;
 };
 using Node= NodeS<void, semigroup_v<M>, commute_v<M>>;
 std::vector<Node> n;
 inline void update(int i) {
  n[i].sum= n[i].val;
  if constexpr (!commute_v<M>) n[i].rsum= n[i].val;
  if (int l= n[i].ch[0]; l != -1) {
   n[i].sum= M::op(n[l].sum, n[i].sum);
   if constexpr (!commute_v<M>) n[i].rsum= M::op(n[i].rsum, n[l].rsum);
  }
  if (int r= n[i].ch[1]; r != -1) {
   n[i].sum= M::op(n[i].sum, n[r].sum);
   if constexpr (!commute_v<M>) n[i].rsum= M::op(n[r].rsum, n[i].rsum);
  }
 }
 inline void propagate(int i, const E &x) {
  if (i == -1) return;
  if (n[i].lazf) M::cp(n[i].laz, x);
  else n[i].laz= x;
  if constexpr (semigroup_v<M>) {
   M::mp(n[i].sum, x);
   if constexpr (!commute_v<M>) M::mp(n[i].rsum, x);
  }
  M::mp(n[i].val, x), n[i].lazf= 1;
 }
 inline void toggle(int i) {
  if (i == -1) return;
  std::swap(n[i].ch[0], n[i].ch[1]);
  if constexpr (semigroup_v<M> && !commute_v<M>) std::swap(n[i].sum, n[i].rsum);
  n[i].revf^= 1;
 }
 inline void push(int i) {
  if (n[i].revf) toggle(n[i].ch[0]), toggle(n[i].ch[1]), n[i].revf= 0;
  if constexpr (dual_v<M>)
   if (n[i].lazf) propagate(n[i].ch[0], n[i].laz), propagate(n[i].ch[1], n[i].laz), n[i].lazf= 0;
 }
 inline int dir(int i) {
  if (int p= n[i].par; p != -1) {
   if (n[p].ch[0] == i) return 0;
   if (n[p].ch[1] == i) return 1;
  }
  return 2;
 }
 inline void rot(int i) {
  int p= n[i].par, d= n[p].ch[1] == i;
  if (int c= n[p].ch[d]= std::exchange(n[i].ch[!d], p); c != -1) n[c].par= p;
  if (d= dir(p); d < 2) n[n[p].par].ch[d]= i;
  n[i].par= std::exchange(n[p].par, i);
  if constexpr (semigroup_v<M>) update(p);
 }
 inline void splay(int i) {
  push(i);
  for (int d; d= dir(i), d < 2; rot(i))
   if (int p= n[i].par, c= dir(p), pp= n[p].par; c < 2) push(pp), push(p), push(i), rot(d == c ? p : i);
   else push(p), push(i);
  if constexpr (semigroup_v<M>) update(i);
 }
 inline int expose(int i) {
  int r= -1;
  for (int p= i; p != -1; r= p, p= n[p].par) {
   splay(p), n[p].ch[1]= r;
   if constexpr (semigroup_v<M>) update(p);
  }
  return splay(i), r;
 }
public:
 LinkCutTree(size_t sz): n(sz) {}
 LinkCutTree(size_t sz, T val): n(sz) {
  for (int i= sz; i--;) n[i].val= val;
 }
 void evert(int k) { expose(k), toggle(k), push(k); }
 void link(int c, int p) {
  evert(c), expose(p), assert(n[c].par == -1), n[p].ch[1]= c, n[c].par= p;
  if constexpr (semigroup_v<M>) update(p);
 }
 void cut(int c, int p) {
  evert(p), expose(c), assert(n[c].ch[0] == p), n[c].ch[0]= n[p].par= -1;
  if constexpr (semigroup_v<M>) update(c);
 }
 int root(int x) {
  for (expose(x);; x= n[x].ch[0])
   if (push(x), n[x].ch[0] == -1) return splay(x), x;
 }
 int parent(int x) {
  if (expose(x), x= n[x].ch[0]; x == -1) return -1;
  for (;; x= n[x].ch[1])
   if (push(x), n[x].ch[1] == -1) return splay(x), x;
 }
 int lca(int x, int y) { return x == y ? x : (expose(x), y= expose(y), n[x].par == -1) ? -1 : y; }
 const T &get(int k) {
  static_assert(!std::is_void_v<M>, "\"get\" is not available\n");
  return expose(k), n[k].val;
 }
 T &at(int k) {
  static_assert(!std::is_void_v<M> && !semigroup_v<M>, "\"at\" is not available\n");
  return expose(k), n[k].val;
 }
 template <class L= M> const std::enable_if_t<semigroup_v<L>, T> &operator[](size_t k) { return get(k); }
 template <class L= M> std::enable_if_t<!semigroup_v<L>, T> &operator[](size_t k) { return at(k); }
 void set(int k, const T &v) {
  static_assert(!std::is_void_v<M>, "\"set\" is not available\n");
  expose(k), n[k].val= v;
  if constexpr (semigroup_v<M>) update(k);
 }
 void mul(int k, const T &v) {
  static_assert(semigroup_v<M> && commute_v<M>, "\"mul\" is not available\n");
  expose(k), n[k].val= M::op(n[k].val, v), update(k);
 }
 // [a,b] closed section
 T prod(int a, int b) {
  static_assert(semigroup_v<M>, "\"prod\" is not available\n");
  return a == b ? get(a) : (evert(a), expose(b), assert(n[a].par != -1), n[b].sum);
 }
 // [a,b] closed section
 void apply(int a, int b, const E &v) {
  static_assert(dual_v<M>, "\"apply\" is not available\n");
  evert(a), expose(b), assert(a == b || n[a].par != -1), propagate(b, v), push(b);
 }
 static std::string which_unavailable() {
  std::string ret= "";
  if constexpr (semigroup_v<M>) ret+= "\"at\" ";
  else ret+= "\"prod\" ";
  if constexpr (!semigroup_v<M> || !commute_v<M>) ret+= "\"mul\" ";
  if constexpr (!dual_v<M>) ret+= "\"apply\" ";
  if constexpr (std::is_void_v<M>) ret+= "\"get\" \"set\" ";
  return ret;
 }
};

Back to top page