(cache)Link-Cut 木 - ei1333の日記

えーむずかしかったのでかきます. まちがってたらごめんね. コードはverifyしたので間違ってないはずです. あとからなんか書き加えたり修正したりするかも.

最初に

このスライドがわかりやすいです(それはそう). ソースコードをほとんどこれ参考にしてるので, こっちも参考にしてね.

プログラミングコンテストでのデータ構造 2　～動的木編～ from Takuya Akiba

www.slideshare.net

HL分解

突然ですが, みなさんはHL分解を知っていますか. 僕は知っています(イキり).

HL分解は木を分解するアルゴリズムの一つです.

次のような木が与えられたとします. 根はどこでもいいんですが, ここでは頂点 $1$ を根とする根付き木として考えます.

f:id:ei1333:20180527135022p:plain — 与えられる木

次に, それぞれの頂点に対して部分木の大きさ(頂点数)を求めます.

f:id:ei1333:20180527135738p:plain — 部分木の大きさを求めた木

最後に, それぞれの頂点に対して, 子の頂点のうち最もその部分木の頂点数が大きい頂点を1つ選択して "Heavy" edge で結びます. 結ばれなかった辺は "Light" edge と呼ぶことにします. この操作を行うことで木をパスの集合で表すことができます.

f:id:ei1333:20180527140647p:plain — HL分解後の木

これをHeavy edgeが隣り合うように一次元配列の形で並べます(Heavy edgeには分岐がないためこのような並べ方は存在します).

f:id:ei1333:20180527142432p:plain

すると, ある頂点からある頂点へのパスが $O (\log N)$ 個の一次元配列の区間で表すことができます. 例えば頂点 $5$ から頂点 $13$ へのパスであれば次の通りです.

f:id:ei1333:20180527143023p:plain

木上のLCAが $O (\log N)$ で求まることが, この図より分かると思います(いい感じの順序で配列の左方向に遡ればよい). ここの配列をセグメント木などを使って例えば距離を入れておくと, 木上の距離クエリや更新クエリみたいなものが $O (\log^{2} N)$ とかで処理できます.

Link-Cut 木

基本的なアイディアはHL分解と同じです.

HL分解はパスの集合のパスを一次元配列の区間とかで静的に管理していましたが, Link-Cut木は親が変わる操作などが可能なので, もともとの木の構造が動的に変化します. そこでそれぞれのパスを平衡二分探索木で管理することにします.

例えば1-2-5-9 のパス(HL分解で示した木参照)であれば, 次のような木になります.

f:id:ei1333:20180527145244p:plain — パスの管理

もともとの木こわれるみたいな気持ちになりますが, これはそれぞれのパスについて左から右方向に木を通りがけ順(post-order)に走査した結果がこの順番になっています. これは例なので, この図の他にも色々な平衡二分探索木の状態がありえます(ただし左から見た時の順番は保持されている).

ここで, Link-Cut 木の核となるアイディア, expose( $x$ ) について説明します. これは頂点 $x$ から根までのパス上の辺をすべて Heavy-edge で繋げる操作です(もともとこのパス上の辺には Light-edge がいくつか存在する可能性があるので, それらを Heavy-edge でつなぎます. またそれに伴って他のHeavy-edge を切る操作が必要になる場合があります.). この操作をすると, このHeavy-edgeのパスは頂点 $x$ から根までのパス上の頂点のみから構成されます. したがって, このパスを表す平衡二分探索木の根を見れば頂点 $x$ と根との間の何か(距離とかパス上のminとか) を求めることができます.

f:id:ei1333:20180527152828p:plain — expose(13)

f:id:ei1333:20180527204312p:plain — expose(5)

実は expose() の計算量は, 平衡二分探索木にSplay木を用いると, ならし $O (\log N)$ となることがわかります. これはつまり, 平衡二分探索木に区間sumなどの色々な機能をもたせれば, 根とある頂点 $x$ 間のいろいろなクエリがならし $O (\log N)$ で実現できることを表しています.

これだと, 根とある頂点間のクエリしかできないやんけみたいな話になりますが, これは後から説明するとして....

Splay 木

えーくわしくはWIkipediaなどをみてください.

スプレー木 - Wikipedia

Splay 木で特徴的なのは, ある頂点 $x$ にアクセスするとき, $x$ を Splay() 操作をして根に移動させるという点がある. 根に移動させる際に闇をすることにより, 平均的に平衡が保たれるという仕組みである.

以下は Splay 木のボトムアップ実装です. 一応半群(?)がのるようになっています. コンストラクタのラムダ式で演算を渡すようにしてください.

template< typename Monoid = int >
struct SplayTree {
  using F = function< Monoid(Monoid, Monoid) >;

  struct Node {
    Node *l, *r, *p;
    int idx;
    Monoid key, sum;
    int sz;

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

    Node(int idx, const Monoid &key) :
        idx(idx), key(key), sum(key), sz(1),
        l(nullptr), r(nullptr), p(nullptr) {}
  };

  const F f;

  SplayTree() : SplayTree([](Monoid a, Monoid b) { return a + b; }, Monoid()) {}

  SplayTree(const F &f, const Monoid &M1) :
      SplayTree(f, M1) {}

  Node *make_node(int idx, const Monoid &v = Monoid()) {
    return new Node(idx, v);
  }

  void update(Node *t) {
    t->sz = 1;
    t->sum = t->key;
    if(t->l) t->sz += t->l->sz, t->sum = f(t->l->sum, t->sum);
    if(t->r) t->sz += t->r->sz, t->sum = f(t->sum, t->r->sum);
  }

  void rotr(Node *t) {
    auto *x = t->p, *y = x->p;
    if((x->l = t->r)) t->r->p = x;
    t->r = 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;
      update(y);
    }
  }

  void rotl(Node *t) {
    auto *x = t->p, *y = x->p;
    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;
      update(y);
    }
  }

  void splay(Node *t) {
    while(!t->is_root()) {
      auto *q = t->p;
      if(q->is_root()) {
        if(q->l == t) rotr(t);
        else rotl(t);
      } else {
        auto *r = q->p;
        if(r->l == q) {
          if(q->l == t) rotr(q), rotr(t);
          else rotl(t), rotr(t);
        } else {
          if(q->r == t) rotl(q), rotl(t);
          else rotr(t), rotl(t);
        }
      }
    }
  }
};

えーブラックボックスとしても扱ってもよいはず.

Link-Cut 木ふたたび

Splay 木が実装できました(やったぜ).

ここで Heavy-edgeのパスと他のHeavy-edgeのパス同士は, 高々1本のLight edgeで結ばれています. 実装をしやすくするために, is_root() を次のように変更しましょう.

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

もともとのSplay木だと, Heavy-edgeのパスの平衡二分探索木上の根はNULLでした. ここに, Light-edge の情報を加え, この根は Light-edge の親を指すようにします(Light-edgeがないやつもあってそれはもともとの木の根をふくむHeavy-edgeのパスなんですが, これは普通にNULLのままでよい).

f:id:ei1333:20180528131538p:plain — Light-edgeのもたせ方

えー, 親のどちらかの子も自分を指していなければ, そこはHeavy-edgeで結ばれていません. すなわち親とは別のHeavy-edgeのパスになって, Splay木の根を指します.

ここまでくればexpose( $x$ ) は次のような実装になります.

Node *expose(Node *t) {
  Node *rp = nullptr;
  for(Node *cur = t; cur; cur = cur->p /* ④ */) {
    splay(cur); /* ① */
    cur->r = rp; /* ② */
    update(cur); /* ③ */
    rp = cur; 
  }
  splay(t);
  return rp;
}

今いる頂点をsplay() して根に移動させる.
根の右側にさっきまでいたパスをくっつける.
今いるパスを保存する.
Light-edgeを通って, 上のHeavy-edgeのパスを表すSplay木に移動する(根の頂点から親方向に生えるパスはLight-edge).

最後にsplay() しています. 頂点 $x$ を根に持ってくると, クエリの値をみるとき楽です(根をわざわざ探さなくてもよくなって, 頂点 $x$ の値を見ればいいので).

なんかsplay()してくっつける操作は次のようなイメージです(えー実際のSplay木の動きと一致しないかもしれないけどイメージなのでゆるちて).

f:id:ei1333:20180528140509p:plain

たとえば頂点 $x$ から根頂点まで移動するときの経路を列挙したいときは, 次のように expose() を利用してDFSすればよいです.

vector< int > getpath(Node *x) {
  vector< int > vs;
  function< void(Node *) > dfs = [&](Node *cur) {
    if(!cur) return;
    dfs(cur->r);
    vs.push_back(cur->idx);
    dfs(cur->l);
  };
  expose(x);
  dfs(x);
  return vs;
}

まず expose( $x$ ) して頂点 $x$ を根に持ってきます. もともとの木の根に近いほどSplay木の左側のノードになることを利用すると, 右部分木をみて自分をみて左部分木をみることで列挙できます. (特に $x$ の右部分木は, $x$ より深い頂点はないので空木です)

次に Link-Cut 木の link() と cut() を見ていきます.

link(child, parent) はchildの親を parrent にする操作です.

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

childを根にもってくる
parentを根にもってくる
childの親をparentにする
parentの右の子をchildにする

つまりparentとchildをHeavy-edgeで結んでいます.

以下は頂点1の親を頂点9にする例です.

cut(child) は頂点 child を親から切り離す操作です.

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

expose(child)をすると child の左の子が親になるので, それを切ればよいです.

最後の締めは evert(v) です. 頂点 v をもともとの木の根に変更します.

void toggle(Node *t) {
  assert(t);
  swap(t->l, t->r);
  /* note: ここに反転の処理 */
  t->rev ^= true;
}

void evert(Node *t) {
  expose(t); 
  toggle(t); /* 反転 */
  push(t); /* 遅延評価 */
}

頂点 v を中心にすべての辺の向きを反転すれば良いです. そしてSplay木に遅延反転の機能(うく)を実装します. これを実装するとかなりやれることが増えて, 頂点 $s, t$ 間のクエリを処理したいときには evert(t) をして根を t に写してから expose(s) を呼び出したあとに頂点 s の値をみることで処理できるようになります.

えー遅延反転させる関数push()を注意深く追加する必要があります. また演算が可換ではない場合は, toggle() のところでtの値を反転させる処理を書く必要があります.

これをした最終的なコードは次のようになると思います. (えーあと遅延評価ができるように改良してあります. )

template< typename Monoid = int, typename OperatorMonoid = Monoid >
struct LinkCutTree {
  using F = function< Monoid(Monoid, Monoid) >;
  using G = function< Monoid(Monoid, OperatorMonoid, int) >;
  using H = function< OperatorMonoid(OperatorMonoid, OperatorMonoid) >;

  struct Node {
    Node *l, *r, *p;
    int idx;
    Monoid key, sum;
    OperatorMonoid lazy;

    bool rev;
    int sz;

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

    Node(int idx, const Monoid &key, const OperatorMonoid &om) :
        idx(idx), key(key), sum(key), lazy(om), sz(1),
        l(nullptr), r(nullptr), p(nullptr), rev(false) {}
  };

  const Monoid M1;
  const OperatorMonoid OM0;
  const F f;
  const G g;
  const H h;

  LinkCutTree() : LinkCutTree([](Monoid a, Monoid b) { return a + b; }, Monoid()) {}

  LinkCutTree(const F &f, const Monoid &M1) :
      LinkCutTree(f, G(), H(), M1, OperatorMonoid()) {}

  LinkCutTree(const F &f, const G &g, const H &h,
              const Monoid &M1, const OperatorMonoid &OM0) :
      f(f), g(g), h(h), M1(M1), OM0(OM0) {}

  Node *make_node(int idx, const Monoid &v = Monoid()) {
    return new Node(idx, v, OM0);
  }

  void propagate(Node *t, const OperatorMonoid &x) {
    t->lazy = h(t->lazy, x);
    t->key = g(t->key, x, 1);
    t->sum = g(t->sum, x, t->sz);
  }

  void toggle(Node *t) {
    assert(t);
    swap(t->l, t->r);
    /* note: ここに反転の処理 */
    t->rev ^= true;
  }

  void push(Node *t) {
    if(t->lazy != OM0) {
      if(t->l) propagate(t->l, t->lazy);
      if(t->r) propagate(t->r, t->lazy);
      t->lazy = OM0;
    }
    if(t->rev) {
      if(t->l) toggle(t->l);
      if(t->r) toggle(t->r);
      t->rev = false;
    }
  }

  void update(Node *t) {
    t->sz = 1;
    t->sum = t->key;
    if(t->l) t->sz += t->l->sz, t->sum = f(t->l->sum, t->sum);
    if(t->r) t->sz += t->r->sz, t->sum = f(t->sum, t->r->sum);
  }

  void rotr(Node *t) {
    auto *x = t->p, *y = x->p;
    if((x->l = t->r)) t->r->p = x;
    t->r = 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;
      update(y);
    }
  }

  void rotl(Node *t) {
    auto *x = t->p, *y = x->p;
    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;
      update(y);
    }
  }

  void splay(Node *t) {
    push(t);
    while(!t->is_root()) {
      auto *q = t->p;
      if(q->is_root()) {
        push(q), push(t);
        if(q->l == t) rotr(t);
        else rotl(t);
      } else {
        auto *r = q->p;
        push(r), push(q), push(t);
        if(r->l == q) {
          if(q->l == t) rotr(q), rotr(t);
          else rotl(t), rotr(t);
        } else {
          if(q->r == t) rotl(q), rotl(t);
          else rotr(t), rotl(t);
        }
      }
    }
  }

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

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

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

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

  Node *lca(Node *u, Node *v) {
    expose(u);
    return expose(v);
  }

  vector< int > getpath(Node *x) {
    vector< int > vs;
    function< void(Node *) > dfs = [&](Node *cur) {
      if(!cur) return;
      push(cur);
      dfs(cur->r);
      vs.push_back(cur->idx);
      dfs(cur->l);
    };
    expose(x);
    dfs(x);
    return vs;
  }

  void set_propagate(Node *t, const OperatorMonoid &x) {
    expose(t);
    propagate(t, x);
    push(t);
  }
};

えーそれぞれの関数の機能について一応書いておきます. ここで触れてない関数は内部関数で, 基本的には触る必要がないかと思います(toggle は触ることがあるかも).

make_node(idx, v) : ID が idx, 値に v を入れたノードを新しく生成する.
expose(t) : t と根との間を Heavy-edge でつなげて, t を Heavy-edge の Splay 木の根にする.
link(child, parent) : child の親を parent にする(もともと parent の連結成分に child がつながってたらこわれます)
cut(child) : child の親と child を切り離す
evert(t) : t をもともとの木の根にする
lca(u, v) : u と v のLCAを返す(えーこれ説明してなかった気がするんですが, 察してください(うく))
get_path(t) : t から根までのパスに出現する頂点をvectorで返す
set_propagate(t, x) : 根からノード t までのパスに x を加算する(正確には作用素がもにょもにょ).

上の実装は古いので　https://ei1333.github.io/luzhiled/snippets/structure/link-cut-tree.html を参考にしたほうがいいきもする(反転をラムダ式で与えられるようになっていたり、パス上のk番目のノードを求められるようになっていたりします)

えー一応コードの断片も貼っておきます.

LCA https://onlinejudge.u-aizu.ac.jp/#/problems/GRL_5_C

int main() {
  int N;
  scanf("%d", &N);
  LinkCutTree<> lctree;
  vector< LinkCutTree<>::Node * > uku(N);
  for(int i = 0; i < N; i++) {
    uku[i] = lctree.make_node(i);
  }
  for(int i = 0; i < N; i++) {
    int K;
    scanf("%d", &K);
    while(K--) {
      int T;
      scanf("%d", &T);
      lctree.link(uku[T], uku[i]);
    }
  }
  int Q;
  scanf("%d", &Q);
  while(Q--) {
    int U, V;
    scanf("%d %d", &U, &V);
    printf("%d\n", lctree.lca(uku[V], uku[U])->idx);
  }
}

Range Query on a Tree I https://onlinejudge.u-aizu.ac.jp/#/problems/GRL_5_E

int main() {
  int N;
  scanf("%d", &N);
  LinkCutTree<> lctree;
  vector< LinkCutTree<>::Node * > uku(N);
  for(int i = 0; i < N; i++) {
    uku[i] = lctree.make_node(i);
  }
  for(int i = 0; i < N; i++) {
    int K;
    scanf("%d", &K);
    while(K--) {
      int T;
      scanf("%d", &T);
      lctree.link(uku[T], uku[i]);
    }
  }
  int Q;
  scanf("%d", &Q);
  while(Q--) {
    int T;
    scanf("%d", &T);
    if(T == 0) {
      int V, W;
      scanf("%d %d", &V, &W);
      lctree.expose(uku[V]);
      uku[V]->key += W;
    } else {
      int U;
      scanf("%d", &U);
      lctree.expose(uku[U]);
      printf("%d\n", uku[U]->sum);
    }
  }
}

Range Query on a Tree II https://onlinejudge.u-aizu.ac.jp/#/problems/GRL_5_E

using int64 = long long;

int main() {
  int N;
  scanf("%d", &N);
  auto f = [&](int64 x, int64 y) { return x + y; };
  auto g = [&](int64 x, int64 y, int64 z) { return x + y * z; };
  LinkCutTree< int64 > lctree(f, g, f, 0, 0);
  vector< LinkCutTree< int64 >::Node * > uku(N);
  for(int i = 0; i < N; i++) {
    uku[i] = lctree.make_node(i);
  }
  for(int i = 0; i < N; i++) {
    int K;
    scanf("%d", &K);
    while(K--) {
      int T;
      scanf("%d", &T);
      lctree.link(uku[T], uku[i]);
    }
  }
  int Q;
  scanf("%d", &Q);
  int64 all = 0;
  while(Q--) {
    int T;
    scanf("%d", &T);
    if(T == 0) {
      int V, W;
      scanf("%d %d", &V, &W);
      lctree.set_propagate(uku[V], W);
      all += W;
    } else {
      int U;
      scanf("%d", &U);
      lctree.expose(uku[U]);
      printf("%lld\n", uku[U]->sum - all);
    }
  }
}

さいごに

たぷりすたべる