Link-Cut木と最遠点クエリ

Link Cut Treeを書いたことがない人はこちら！（ステマ）

ei1333.hateblo.jp

beet-aizu.hatenablog.com　を読んでね♡

行間がヤバイので、どうしよう　ごめんね　読者のエスパー力に期待しています

結論から書くと、部分木クエリの応用である頂点から最も遠い頂点までの距離を求めるクエリを、クエリあたり で求めることが可能です。

木があって、ある頂点から最も遠い頂点まで距離を求めるクエリをLink-Cut木で処理することを考えます。このままだとヤバイので、その部分木の頂点のうち最も遠い頂点まで距離を求めるクエリを処理することにします。クエリで求めたい頂点 にevert(根を移動すること)ができれば、部分木で最も遠い頂点までの距離が最遠点までの距離に一致するので、それをすればよいです。

各頂点に、そこから生えるLight-Edgeごとに最遠点までの距離をmultisetで持ちます。で、expose()が来たら、Light-Edgeが貼り替えられる時に適当にinsert/eraseをします（えーこのへんの解説もしたいんですが、面倒くさい（最悪））。

evert()は、もともとの根 と頂点 間のパス上にあるすべての辺の向きを反転させる操作です。つまり expose() して Splay木に 間のパス上の頂点だけを属すようにしたあとに、 Splay木全体を遅延反転させる操作に相当します。

辺の向きが変わると当然部分木の形も変わるので、部分木の最遠点までの距離も変わります。beetしゃんの記事にあった

(2019/06/11 更新) evertすると部分木の再計算がやばいので多分無理です

がそれです。

じゃあ無理なのかというと、実はそうではなくて頑張ればevertできます。

↑の状態だと可換ではないのでexpose()すらできないね　う　結局はなんかいい感じの情報を持ってがんばって可換にしたいイメージ

(2019/06/14 更新) 冷静に考えるとほとんどのlight-edgeはそのままなのでできそう　可換性を仮定しているのでsplay木上の左右の子を入れ替えても影響はないし （よくわからん　間違ってるかも）

次のようなSplay木があって、7でevert()した状況を考えましょう。ひとまず、Splay木の遅延反転を忘れて、愚直に更新することにします。また、各頂点には部分木のみの頂点への距離(ここでいう部分木はSplay木の部分木はなくて、入力された木の部分木）のmaxを持つことにします。

ここで頂点 に着目します。最初、持っている情報は頂点 {3,4,5,6,7} へのパスのうちの最大値です（部分木のみを考えるので）。evert()すると持つべき情報は頂点 {3,2,1} からの情報に変化します。

つまり各頂点に自分の頂点より小さい頂点たちからの情報と、大きい頂点たちからの情報を持つようにして、反転が来たらswapすればよいです。

しかし遅延伝搬させたいので、これらは上手くは行きません。そこで妥協(というかこう定義すると上手くいく)して、各頂点には、Splay木の部分木内の頂点内の移動だけで完結するもののみを考えます。木DP的に計算していき、Splay木の根だけが完全な情報を持っていることになります。

ひとまず、頂点 を使う移動を考えることにします。これは左部分木のある頂点を 、右部分木のある頂点を とすると、max( 間のパスの長さ + 間のパスの長さ + から生えるLight-Edgeでつながる木のmax) が解になります。

で 間のパスの長さのmaxは、Splay木の最も左の子までの距離と一致します（左の部分木内の辺の長さの総和と一致）。なので、部分木全体の辺の長さの和(smd)を持っておきます。

( 間のパスの長さ + から生えるLight-Edgeでつながる木のmax) をldとします。また の右の子を とします。 ld は smd + + max( 間のパスの長さ + から生えるLight-Edgeでつながる木のmax) なので、max( 間のパスの長さ + から生えるLight-Edgeでつながる木のmax) は の ld です(完）

すると、更新は以下の様にすればよいです。①は左部分木内だけで終わる移動、②は頂点 で終わる移動です。③は上で説明したやつです。(右部分木内だけで終わる移動はやってもいいんですが、これは③より大きくならないので)

ld = 0;
int64 lld = l ? l->ld : 0;
int64 lsmd = l ? l->smd : 0;
ld = max(ld, lld);  // ①
ld = max(ld, lsmd + key + *td.rbegin()); // ②
if(r) ld = max(ld, lsmd + key + r->ld); // ③

以下のように逆方向にも持てば、遅延反転ができます。反転が来たときに、ldとrdをswapすればよいです。

rd = 0;
int64 rrd = r ? r->rd : 0;
int64 rsmd = r ? r->smd : 0;
rd = max(rd, rrd);
rd = max(rd, rsmd + key + *td.rbegin());
if(l) rd = max(rd, rsmd + key + l->rd);

multisetにerase/insertされる回数がクエリあたり 回なので、全体の計算量は です。

一般的に何がLink-Cut木にのるんでつかね　なにもわからねえ　抽象化芸人のみなさん、抽象化をお願いします

atcoder.jp

#include <bits/stdc++.h>

using namespace std;

using int64 = long long;

struct LinkCutTree {
  using LCT = LinkCutTree;

  LCT *l, *r, *p;
  int idx;
  int64 ld, rd, key, smd;
  multiset< int64 > td;
  bool rev;
  int sz;

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

  LinkCutTree() {}

  LinkCutTree(int k, const int64 &v) { init(k, v); }

  void init(int k, const int64 &v) {
    idx = k;
    key = ld = rd = smd = v;
    sz = 1;
    l = r = p = nullptr;
    rev = false;
    td.clear();
    td.emplace(0);
  }

  void toggle() {
    swap(l, r);
    swap(ld, rd);
    rev ^= true;
  }

  void push() {
    if(rev) {
      if(l) l->toggle();
      if(r) r->toggle();
      rev = false;
    }
  }

  void update() {
    sz = 1;
    smd = key;

    if(l) {
      sz += l->sz;
      smd += l->smd;
    }

    if(r) {
      sz += r->sz;
      smd += r->smd;
    }

    ld = rd = 0;
    int64 lld = l ? l->ld : 0;
    int64 lsmd = l ? l->smd : 0;
    ld = max(ld, lld);
    ld = max(ld, lsmd + key + *td.rbegin());
    if(r) ld = max(ld, lsmd + key + r->ld);


    int64 rrd = r ? r->rd : 0;
    int64 rsmd = r ? r->smd : 0;
    rd = max(rd, rrd);
    rd = max(rd, rsmd + key + *td.rbegin());
    if(l) rd = max(rd, rsmd + key + l->rd);
  }


  void rotr() {
    auto *x = p, *y = x->p;
    if((x->l = r)) r->p = x;
    r = x, x->p = this;
    x->update(), update();
    if((p = y)) {
      if(y->l == x) y->l = this;
      if(y->r == x) y->r = this;
      y->update();
    }
  }

  void rotl() {
    auto *x = p, *y = x->p;
    if((x->r = l)) l->p = x;
    l = x, x->p = this;
    x->update(), update();
    if((p = y)) {
      if(y->l == x) y->l = this;
      if(y->r == x) y->r = this;
      y->update();
    }
  }

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

  LCT *expose() {
    LCT *rp = nullptr;
    for(auto *cur = this; cur; cur = cur->p) {
      cur->splay();
      if(cur->r) cur->td.emplace(cur->r->ld);
      cur->r = rp;
      if(cur->r) cur->td.erase(cur->td.find(cur->r->ld));
      cur->update();
      rp = cur;
    }
    splay();
    return rp;
  }

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

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

  void evert() {
    expose();
    toggle();
    push();
  }

  LCT *lca(LCT *v) {
    expose();
    return v->expose();
  }
};

int main() {
  int Q;
  cin >> Q;

  using LCT=LinkCutTree;
  vector< LinkCutTree > ev(500001), ee(500001);
  ev[0].init(0, 0);

  int num = 1;
  for(int i = 0; i < Q; i++) {
    int t, a, b;
    cin >> t >> a >> b;
    if(t == 1) {
      ev[num].init(num, 0);
      ee[num].init(num, b);
      ee[num].link(&ev[a]);
      ev[num].link(&ee[num]);
      ++num;
    } else if(t == 2) {
      ee[a].expose();
      ee[a].key = b;
      ee[a].update();
    } else {
      ev[a].evert();
      cout << ev[a].ld << endl;
    }
  }
}

まちがってるところあったらおしえてね