了解Link-Cut樹

Link-Cut樹是一種基於Splay樹的動態樹數據結構，可用於解決樹形問題的一類動態問題。Link-Cut樹的主要優勢是可以在$O(logn)$的複雜度內處理樹的剖分和重構，被廣泛應用於網路流、最近公共祖先、點分治、虛樹等演算法中的實現，也可以用於樹形可持久化數據結構和虛數對複雜度的分析。

一、Link-Cut樹的簡單介紹

Link-Cut樹是由Daniel Sleator和Robert Tarjan在1983年提出的，是一種基於Splay樹的可動態維護的樹結構。Splay樹是一棵維護序列的平衡樹，具有以下特點：

1. 可以將一個節點旋轉到根節點，以便於對這個節點的操作；
2. 可以在任意兩個節點之間構造查詢路徑，並將查詢路徑上的節點旋轉到根節點；
3. 可以實現節點的分割和合併操作。

Link-Cut樹繼承了Splay樹的所有功能，同時在動態保持樹形約束的同時，支持節點間的重構，並且具有線性時間演算法。

二、Link-Cut樹的基本操作

Link-Cut樹對外提供的操作包括：

1. link(u, v)：將節點u和節點v之間連一條無向邊；
2. cut(u, v)：將節點u和節點v之間的邊斷開，將節點u和v分別成為兩棵獨立的樹；
3. access(u)：將節點u到根節點的路徑形成一條重鏈，並且將u變為這條重鏈的根節點；
4. lca(u, v)：求出節點u和節點v在樹上的最近公共祖先。

下面是基本操作的代碼實現：

struct Node {
  Node *ch[2], *fa;
  bool rev;
  ... // 其他節點屬性和方法
};

void pushdown(Node *u) { // 下傳標記，以便於維護鏈的重構和reverse操作
  if (u->rev) {
    u->rev = false;
    swap(u->ch[0], u->ch[1]);
    if (u->ch[0]) u->ch[0]->rev ^= 1;
    if (u->ch[1]) u->ch[1]->rev ^= 1;
  }
}

bool isroot(Node *u) { // 判斷u是否為重鏈的根節點
  return !u->fa || (u->fa->ch[0] != u && u->fa->ch[1] != u);
}

void rotate(Node *u) { // 旋轉操作
  Node *fa = u->fa, *gfa = fa->fa, *heading;
  if (!isroot(fa))
    heading = (gfa->ch[0] == fa ? gfa->ch[0] : gfa->ch[1]);
  else
    heading = fa;
  int dir = (fa->ch[1] == u);
  if (!isroot(u)) u->fa = gfa;
  fa->ch[dir] = u->ch[dir ^ 1];
  if (u->ch[dir ^ 1]) u->ch[dir ^ 1]->fa = fa;
  u->ch[dir ^ 1] = fa;
  fa->fa = u;
  if (!isroot(fa)) heading->ch[fa->fa->ch[1] == fa] = u;
}

void splay(Node *u) { // Splay操作
  static Node *stk[MAXN];
  int top = 0;
  for (Node *v = u; !isroot(v); v = v->fa) stk[top++] = v;
  stk[top++] = u;
  while (top) pushdown(stk[--top]);
  while (!isroot(u)) {
    Node *fa = u->fa, *gfa = fa->fa;
    if (!isroot(fa)) {
      int d1 = (gfa->ch[1] == fa);
      int d2 = (fa->ch[1] == u);
      if (d1 == d2)
        rotate(fa);
      else
        rotate(u);
    }
    rotate(u);
  }
}

void access(Node *u) { // access操作
  for (Node *v = NULL; u; v = u, u = u->fa) {
    splay(u);
    u->ch[1] = v;
  }
}

void makeroot(Node *u) { // 將u變為所在重鏈的根
  access(u);
  splay(u);
  u->rev ^= 1;
}

void split(Node *u, Node *v) { // 將u到v的連續邊切斷
  makeroot(u);
  access(v);
  splay(v);
  if (!v->ch[0]) return;
  v->ch[0]->fa = NULL;
  v->ch[0] = NULL;
}

void link(Node *u, Node *v) { // 連邊操作
  makeroot(u);
  u->fa = v;
}

void cut(Node *u, Node *v) { // 斷邊操作
  split(u, v);
  v->fa = NULL;
}

Node *lca(Node *u, Node *v) { // LCA操作
  access(u);
  splay(u);
  Node *last = u, *res = NULL;
  for (Node *p = v; p; last = p, p = p->fa) {
    splay(p);
    if (p->fa == NULL) {
      res = last;
      break;
    }
    p->ch[1] = last;
    last->fa = p;
  }
  return res;
}

三、Link-Cut樹的應用

Link-Cut樹作為一種簡單易用的動態維護樹結構的工具，被廣泛應用於各種樹形問題中，下面列舉一些經典的應用場景：

1. 網路流中的建圖技巧：Link-Cut樹可以用於維護一些必要的切割邊，簡化網路流的邊的建圖過程；
2. 最近公共祖先問題：Link-Cut樹可以快速求出任意兩個節點在一棵樹上的最近公共祖先；
3. 點分治問題：Link-Cut樹可以用於實現高效的點分治演算法，通過將子樹分解為鏈來快速處理點分治中的輕重鏈剖分問題；
4. 虛樹問題：Link-Cut樹可以用於維護一棵樹的虛樹，避免重複計算，並且可以用於樹上區間加減和；
5. 樹形可持久化數據結構問題：Link-Cut樹可以用於構造樹形可持久化數據結構，簡化一些操作的實現；
6. 虛數對複雜度問題：Link-Cut樹可以用於分析虛數對複雜度問題，給出複雜度優秀的演算法實現。

結語

本文詳細介紹了Link-Cut樹的基礎知識、基本操作和應用場景，可以幫助讀者了解這個經典數據結構的優點和使用方法。同時鑒於篇幅有限，文章中所涉及的問題只是冰山一角，讀者可以進一步查閱相關文獻，深入研究Link-Cut樹的更多細節和應用技巧。