LCT にはつよい LCT とよわい LCT があります

Static Top Tree

Nyaan さんありがとう

Static Top Tree の補足

根付き木を隣接リストで表したものを vector< vector< int > > g とします。

HL 分解を考えます。葉以外の各頂点 ${v}$ について ${(v, g[v][0])}$ が HL 分解の heavy_edge、それ以外が light_edge とします。

このとき、Static Top Tree は以下のコードをうまく平衡二分木で表すことにより更新を効率的にできるようにしたものです。vertex, add_vertex, add_edge, rake, compress の 5 つの演算は解きたい問題に依存します。

Path vertex(int r);
Path add_vertex(Point p, int r);
Point add_edge(Path p);
Point rake(Point l, Point r);
Path compress(Path p, Path c);

Point calc_light(int r) {
  vector< Point > points;
  // g[r][0] は heavy_edge なので skip
  for(int i = 1; i < (int) g[r].size(); i++) {
    Path res = calc_heavy(g[r][i]);
    points.push_back(add_edge(res));
  }
  for(int i = 1; i < (int) points.size(); i++) {
    points[0] = rake(points[0], points[i]);
  }
  return points[0];
}

Path calc_heavy(int r) {
  vector< Path > paths;
  while(not g[r].empty()) {
    if(g[r].size() == 1) {
      // light_edge を持っていない
      paths.push_back(vertex(r));
    } else {
      // light_edge を持っている
      Point res = calc_light(r);
      paths.push_back(add_vertex(res, r));
    }
    r = g[r][0];
  }
  for(int i = 1; i < (int) paths.size(); i++) {
    paths[0] = compress(paths[0], paths[i]);
  }
  return paths[0];
}

// calc_heavy(0)

例えば、ABC351 G - Hash on Tree は次のような演算とすることで解けるはずです。

struct Point { mint v; };
struct Path { mint a, b; };

Path vertex(int u) const { return {1, A[u]}; };
Path add_vertex(Point d, int u) const { return {d.v, A[u]}; };
Point add_edge(Path d) const { return {d.b}; };
Point rake(Point l, Point r) const { return {l.v * r.v}; };
Path compress(Path p, Path c) const { return {p.a * c.a, p.a * c.b + p.b}; };

読んでも読まなくてもいいところ

亜種として、次のように vertex(r) を add_vertex(id, r) で代用したものも考えられます。

top tree やってると point cluster の方に単位元を要求したくなること及び実際自然な単位元があることが多く、その場合 add_vertex(id, v) で vertex(v) を表現できるので関数が減ります。id に押し付けてるだけだけどこれは内部実装の簡略化にもなるのでセーフ (？)
— 熨斗袋 (@noshi91) 2024年4月27日

Point id();
Path add_vertex(Point p, int r);
Point add_edge(Path p);
Point rake(Point l, Point r);
Path compress(Path p, Path c);

Point calc_light(int r) {
  vector< Point > points {id()};
  for(int i = 1; i < (int) g[r].size(); i++) {
    Path res = calc_heavy(g[r][i]);
    points.push_back(add_edge(res));
  }
  for(int i = 1; i < (int) points.size(); i++) {
    points[0] = rake(points[0], points[i]);
  }
  return points[0];
}

Path calc_heavy(int r) {
  vector< Path > paths;
  while(not g[r].empty()) {
    Point res = calc_light(r);
    paths.push_back(add_vertex(res, r));
    r = g[r][0];
  }
  for(int i = 1; i < (int) paths.size(); i++) {
    paths[0] = compress(paths[0], paths[i]);
  }
  return paths[0];
}

// calc_heavy(0)

最初のコードと比較して、light_edge の有無による場合分けが減っているので、これを Static Top Tree にのせたときに実装が簡略化できそうというイメージが湧く人が多いと思います。が、最初の vertex があるバージョンを後述するつよい LCT ですでに実装してしまったため、こちらは読者への課題とします。

よわい LCT

ei1333.hateblo.jp

普通の LCT です

100年前に書いた記事なので、正しいことが書かれているかちょっと不安です

つよい LCT

つよい LCT とは、Static Top Tree を動的にしたものを指します。（Top Tree（狭義）とは異なります）

アイデアとしては、calc_light の次の部分

  for(int i = 1; i < (int) points.size(); i++) {
    points[0] = rake(points[0], points[i]);
  }

calc_heavy の次の部分

  for(int i = 1; i < (int) paths.size(); i++) {
    paths[0] = compress(paths[0], paths[i]);
  }

をそれぞれの Splay Tree で持ちます。rake と compress は二項演算なので全体の結果を Splay Tree 上で簡単に計算可能です。

`rake` をのせる Splay Tree

rake の方は簡単で Splay Tree t に Point v を持つノードを追加する insert(t, v)、ノード t を削除する erase(t) を実装するだけです。

insert、erase はそれぞれ Splay Tree 内のノード全体を rake した値を返すようにしておくと便利です。

template <typename TreeDPInfo>
struct SplayTree {
  using Point = typename TreeDPInfo::Point;
  struct Node {
    Node *l, *r, *p;
    Point key, sum;

    explicit Node(const Point &key)
        : key(key),
          sum(key),
          l(nullptr),
          r(nullptr),
          p(nullptr) {}
  };

  SplayTree() = default;

  using NP = Node *;

  void rotr(NP t) const {
    NP 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;
    }
  }

  void rotl(NP t) const {
    NP 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;
    }
  }

  void update(NP t) const {
    t->sum = t->key;
    if(t->l) t->sum = TreeDPInfo::rake(t->sum, t->l->sum);
    if(t->r) t->sum = TreeDPInfo::rake(t->sum, t->r->sum);
  }

  NP get_right(NP t) const {
    while (t->r) t = t->r;
    return t;
  }

  NP alloc(const Point &v) const {
    auto t = new Node(v);
    update(t);
    return t;
  }

  void splay(NP t) const {
    while (t->p) {
      NP q = t->p;
      if (!q->p) {
        if (q->l == t) rotr(t);
        else rotl(t);
      } else {
        NP 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);
        }
      }
    }
  }

  NP insert(NP t, const Point &v) const {
    if (not t) {
      t = alloc(v);
      return t;
    } else {
      NP cur = get_right(t), z = alloc(v);
      splay(cur);
      z->p = cur;
      cur->r = z;
      update(cur);
      splay(z);
      return z;
    }
  }

  NP erase(NP t) const {
    splay(t);
    NP x = t->l, y = t->r;
    delete t;
    if (not x) {
      t = y;
      if (t) t->p = nullptr;
    } else if (not y) {
      t = x;
      t->p = nullptr;
    } else {
      x->p = nullptr;
      t = get_right(x);
      splay(t);
      t->r = y;
      y->p = t;
      update(t);
    }
    return t;
  }
};

Splay Tree じゃなくてもいいかもしれないですが、rake を計算する平衡二分木に Splay Tree を使うことで (例の Link Cut Tree の解析により) ならし ${O(\log N)}$ になっていてくれという期待があります。（証明できたら教えてください。実用的には高速に動作しています

→ hotman さん　ありがとう・・・　 qiita.com

Link Cut Tree に各操作をのせる

compress を説明する前に、よわい Link Cut Tree を改造して rake を計算する Splay Tree を一緒に保持することを考えます。

Link-Cut 木 - ei1333の日記にあるように、Link Cut Tree の expose(t) は次のように実装できます。

NP expose(NP t) {
  NP rp = nullptr;
  for (NP cur = t; cur; cur = cur->p /* 4 */) {
    splay(cur); /* 1 */ 
    if (cur->r) {
      cur->light = splay_tree.insert(cur->light, TreeDPInfo::add_edge(cur->r->sum));
      cur->r->belong = cur->light;
    }
    cur->r = rp; /* 2 */
    if (cur->r) {
      cur->light = splay_tree.erase(cur->r->belong);
    }
    update(cur);
    rp = cur; /* 3 */
  }
  splay(t);
  return rp;
}

今いる頂点 cur を splay() して根に移動させる。
根の右側に直前のパス rp をくっつける。
直前のパス rp に現在のパス cur を代入する。
Light-edgeを遡って、親の Splay Tree cur->p に移動する(Splay Tree の根から親方向 p に生えるパスはLight-edge)。

つよい LCT では、Light-edge の Splay Tree も同時に更新します。

NP expose(NP t) {
  NP rp = nullptr;
  for (NP cur = t; cur; cur = cur->p /* 4 */) {
    splay(cur); /* 1 */ 
    if (cur->r) {
      cur->light = splay_tree.insert(cur->light, TreeDPInfo::add_edge(cur->r->sum)); /* 1 (a) */
      cur->r->belong = cur->light; /* 1 (b) */
    }
    cur->r = rp; /* 2 */
    if (cur->r) {
      cur->light = splay_tree.erase(cur->r->belong); /* 2(a) */
    }
    update(cur);
    rp = cur; /* 3 */
  }
  splay(t);
  return rp;
}

1: 今いる頂点 cur を splay() して根に移動させる。
1 (a): 2. での代入 cur->r = rp により、現在の cur->r は Heavy-edge から Light-edge に変更される。これに伴って、頂点 cur を端点とする Light-edge を管理する Splay Tree cur->light に、add_edge(cur->r->sum) を insert する。 1(b): cur->r->belong に、1 (a) で insert した頂点 cur->r の Light-edge に対応するノード cur->light へのポインタを保存する。
2: 根の右側に直前のパス rp をくっつける。
2 (a): 2. での代入 cur->r = rp により、rp を Light-edge から Heavy-edge に変更した。これに伴って、頂点 cur を端点とする Light-edge を管理する Spaly Tree cur->light から、頂点 rp(cur->r) の Light-edge に対応するノード cur->r->belong を削除する。
3: 直前のパス rp に現在のパス cur を代入する。
4: Light-edgeを遡って、親の Splay Tree cur->p に移動する(Splay Tree の根から親方向 p に生えるパスはLight-edge)。

Link Cut Tree の Heavy-edge に含まれる頂点が更新された時に呼び出す update は以下のように実装できます。

void update(NP t) {
  Path key = t->light ? TreeDPInfo::add_vertex(t->light->sum, t->vertex_idx) : TreeDPInfo::vertex(t->vertex_idx);
  t->sum = key;
  if(t->l) {
    t->sum = TreeDPInfo::compress(t->l->sum, t->sum);
  }
  if(t->r) {
    t->sum = TreeDPInfo::compress(t->sum, t->r->sum);
  }
}

t->light->sum には Light-edge の Splay Tree で全体を rake した値が計算されているので、それを参照すれば良いです。Light-edge が存在しない場合、t->light は null です。

これで終わりか？　簡単じゃんと思いきや、このままだとバグります（苦い思い出）

expose では Light-edge に対応する belong は、original の木の頂点に対応するノードではなく、Splay Tree の根に保存しました。splay(t) を呼び出すことで、t が根に変わるので、Splay Tree の belong を、t にコピーする必要があります。具体的には以下のコードを参照してください。

void splay(NP t) {
  { // 根（root）の belong を t にコピーする
    NP root = t;
    while (not root->is_root()) root = rot->p;
    t->belong = root->belong;
    if (t != root) root->belong = nullptr;
  }
  while (not t->is_root()) {
    NP q = t->p;
    if (q->is_root()) {
      if (q->l == t) rotr(t);
      else rotl(t);
    } else {
      NP 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);
      }
    }
  }
}

evert をしたい場合は、逆方向の sum も持って、toggle 時に交換します。

void toggle(NP t) {
  swap(t->l, t->r);
  swap(t->sum, t->mus);
  t->rev ^= true;
}

void update(NP t) {
  Path key = t->light ? TreeDPInfo::add_vertex(t->light->sum, t->info) : TreeDPInfo::vertex(t->info);
  t->sum = key;
  t->mus = key; // 逆方向の sum
  // mus は t->r->mus, t->mus, t->l->mus の順で compress する
  if(t->l) {
    t->sum = TreeDPInfo::compress(t->l->sum, t->sum);
    t->mus = TreeDPInfo::compress(t->mus, t->l->mus);
  }
  if(t->r) {
    t->sum = TreeDPInfo::compress(t->sum, t->r->sum);
    t->mus = TreeDPInfo::compress(t->r->mus, t->mus);
  }
}

全体の実装は https://judge.yosupo.jp/submission/205578 を参照してください。

遅延伝播

Light-edge を保持する Splay Tree や Heavy-edge を保持する Splay Tree に遅延伝播を実装することで、例えば部分木全体に何かを加えるみたいな操作ができるようになります。具体的には・・・と思ったんですが、飽きたのでやめておきます。（https://judge.yosupo.jp/submission/205648 が参考になるかも）

ちょっとつよい LCT（追記）

この記事を公開してから 1 週間くらい経って、Point に単位元と逆元がある場合は Light-edge 用の Splay Tree は不要なことに気づきました。

Light-edge すべてを Splay Tree で管理するのではなく、Light-edge 全体を rake した値を 1 つの変数で管理すれば良いです。Light-edge を追加するときはこの変数と rake して、消すときは逆元を rake すればよいです。

全体の最大/最小は逆元がないので終わりですが、sum は逆元があるのでこちらの実装で十分です。

https://judge.yosupo.jp/submission/207559

おしまい

うしー