跳转至

Link Cut Tree

簡介

Link/Cut Tree 是一種數據結構，我們用它來解決 動態樹問題。

Link/Cut Tree 又稱 Link-Cut Tree，簡稱 LCT，但它不叫動態樹，動態樹是指一類問題。

Splay Tree 是 LCT 的基礎，但是 LCT 用的 Splay Tree 和普通的 Splay 在細節處不太一樣（進行了一些擴展）。

問題引入

維護一棵樹，支持如下操作：

  • 修改兩點間路徑權值。
  • 查詢兩點間路徑權值和。
  • 修改某點子樹權值。
  • 查詢某點子樹權值和。

這是一道樹剖模版題。

但是再加一個操作：

  • 斷開並連接一些邊，保證仍是一棵樹。

要求在線求出上面的答案。

這就成了動態樹問題，可以使用 LCT 求解。

動態樹問題

維護一個 森林，支持刪除某條邊，加入某條邊，並保證加邊，刪邊之後仍是森林。我們要維護這個森林的一些信息。

一般的操作有兩點連通性，兩點路徑權值和，連接兩點和切斷某條邊、修改信息等。

從 LCT 的角度回顧一下樹鏈剖分

  • 對整棵樹按子樹大小進行剖分，並重新標號。
  • 我們發現重新標號之後，在樹上形成了一些以鏈為單位的連續區間，並且可以用線段樹進行區間操作。

轉向動態樹問題

我們發現我們剛剛講的樹剖是以子樹大小作為劃分條件。那我們能不能重定義一種剖分，使它更適應我們的動態樹問題呢？

考慮動態樹問題需要什麼鏈。

由於動態維護一個森林，顯然我們希望這個鏈是我們指定的鏈，以便利用來求解。

實鏈剖分

對於一個點連向它所有兒子的邊，我們自己選擇一條邊進行剖分，我們稱被選擇的邊為實邊，其他邊則為虛邊。對於實邊，我們稱它所連接的兒子為實兒子。對於一條由實邊組成的鏈，我們同樣稱之為實鏈。請記住我們選擇實鏈剖分的最重要的原因：它是我們選擇的，靈活且可變。正是它的這種靈活可變性，我們採用 Splay Tree 來維護這些實鏈。

LCT

我們可以簡單的把 LCT 理解成用一些 Splay 來維護動態的樹鏈剖分，以期實現動態樹上的區間操作。對於每條實鏈，我們建一個 Splay 來維護整個鏈區間的信息。

輔助樹

我們先來看一看輔助樹的一些性質，再通過一張圖實際瞭解一下輔助樹的具體結構。

在本文裏，你可以認為一些 Splay 構成了一個輔助樹，每棵輔助樹維護的是一棵樹，一些輔助樹構成了 LCT，其維護的是整個森林。

  1. 輔助樹由多棵 Splay 組成，每棵 Splay 維護原樹中的一條路徑，且中序遍歷這棵 Splay 得到的點序列，從前到後對應原樹「從上到下」的一條路徑。
  2. 原樹每個節點與輔助樹的 Splay 節點一一對應。
  3. 輔助樹的各棵 Splay 之間並不是獨立的。每棵 Splay 的根節點的父親節點本應是空，但在 LCT 中每棵 Splay 的根節點的父親節點指向原樹中 這條鏈 的父親節點（即鏈最頂端的點的父親節點）。這類父親鏈接與通常 Splay 的父親鏈接區別在於兒子認父親，而父親不認兒子，對應原樹的一條 虛邊。因此，每個連通塊恰好有一個點的父親節點為空。
  4. 由於輔助樹的以上性質，我們維護任何操作都不需要維護原樹，輔助樹可以在任何情況下拿出一個唯一的原樹，我們只需要維護輔助樹即可。

現在我們有一棵原樹，如圖所示。（加粗邊是實邊，虛線邊是虛邊。）

tree

由剛剛的定義，輔助樹的結構如圖所示。

auxtree

考慮原樹和輔助樹的結構關係

  • 原樹中的實鏈 : 在輔助樹中節點都在一棵 Splay 中。
  • 原樹中的虛鏈 : 在輔助樹中，子節點所在 Splay 的 Father 指向父節點，但是父節點的兩個兒子都不指向子節點。
  • 注意：原樹的根不等於輔助樹的根。
  • 原樹的 Father 指向不等於輔助樹的 Father 指向。
  • 輔助樹是可以在滿足輔助樹、Splay 的性質下任意換根的。
  • 虛實鏈變換可以輕鬆在輔助樹上完成，這也就是實現了動態維護樹鏈剖分。

接下來要用到的變量聲明

  • ch[N][2] 左右兒子
  • f[N] 父親指向
  • sum[N] 路徑權值和
  • val[N] 點權
  • tag[N] 翻轉標記
  • laz[N] 權值標記
  • siz[N] 輔助樹上子樹大小
  • Other_Vars

函數聲明

一般數據結構函數（字面意思）

  1. PushUp(x)
  2. PushDown(x)

Splay 樹的函數

下面是 Splay 樹中用到的函數，具體可以查閲 Splay 樹。

  1. Get(x) 獲取 \(x\) 是父親的哪個兒子。
  2. Splay(x) 通過和 Rotate 操作聯動實現把 \(x\) 旋轉到 當前 Splay 的根。
  3. Rotate(x) 將 \(x\) 向上旋轉一層的操作。

新操作

  1. Access(x) 把從根到 \(x\) 的所有點放在一條實鏈裏，使根到 \(x\) 成為一條實路徑，並且在同一棵 Splay 裏。只有此操作是必須實現的，其他操作視題目而實現。
  2. IsRoot(x) 判斷 \(x\) 是否是所在樹的根。
  3. Update(x) 在 Access 操作之後，遞歸地從上到下 PushDown 更新信息。
  4. MakeRoot(x) 使 \(x\) 點成為其所在樹的根。
  5. Link(x, y) 在 \(x, y\) 兩點間連一條邊。
  6. Cut(x, y) 把 \(x, y\) 兩點間邊刪掉。
  7. Find(x) 找到 \(x\) 所在樹的根節點編號。
  8. Fix(x, v) 修改 \(x\) 的點權為 \(v\)。
  9. Split(x, y) 提取出 \(x, y\) 間的路徑，方便做區間操作。

宏定義

  • #define ls ch[p][0]
  • #define rs ch[p][1]

函數講解

PushUp()

1
2
3
4
void PushUp(int p) {
  // maintain other variables
  siz[p] = siz[ls] + siz[rs] + 1;
}

PushDown()

1
2
3
4
5
6
void PushDown(int p) {
  if (tag[p] != std_tag) {
    // pushdown the tag
    tag[p] = std_tag;
  }
}

Splay() && Rotate()

這裏 Splay() 和 Rotate() 與 Splay 樹的實現有些區別。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
#define Get(x) (ch[f[x]][1] == x)

void Rotate(int x) {
  int y = f[x], z = f[y], k = Get(x);
  if (!isRoot(y)) ch[z][ch[z][1] == y] = x;
  // 上面這句一定要寫在前面，普通的 Splay 是不用的，因為 isRoot  (後面會講)
  ch[y][k] = ch[x][!k], f[ch[x][!k]] = y;
  ch[x][!k] = y, f[y] = x, f[x] = z;
  PushUp(y), PushUp(x);
}

void Splay(int x) {
  Update(
      x);  // 馬上就能看到啦。在 Splay 之前要把旋轉會經過的路徑上的點都 PushDown
  for (int fa; fa = f[x], !isRoot(x); Rotate(x)) {
    if (!isRoot(fa)) Rotate(Get(fa) == Get(x) ? fa : x);
  }
}

以上函數可以查閲 Splay 樹。

下面是 LCT 獨有的函數。

isRoot()

1
2
3
// 在前面我們已經説過，LCT 具有 如果一個兒子不是實兒子，他的父親找不到它的性質
// 所以當一個點既不是它父親的左兒子，又不是它父親的右兒子，它就是當前 Splay 的根
#define isRoot(x) (ch[f[x]][0] != x && ch[f[x]][1] != x)

Access()

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
// Access 是 LCT
// 的核心操作，試想我們像求解一條路徑，而這條路徑恰好就是我們當前的一棵 Splay，
// 直接調用其信息即可。先來看一下代碼，再結合圖來看看過程
int Access(int x) {
  int p;
  for (p = 0; x; p = x, x = f[x]) {
    Splay(x), ch[x][1] = p, PushUp(x);
  }
  return p;
}

  • 我們有這樣一棵樹，實線為實邊，虛線為虛邊。

    initial tree

  • 它的輔助樹可能長成這樣（構圖方式不同可能 LCT 的結構也不同）。

    initial auxtree

  • 現在我們要 Access(N)，把 \(A\) 到 \(N\) 路徑上的邊都變為實邊，拉成一棵 Splay。

    access tree

  • 實現的方法是從下到上逐步更新 Splay。

  • 首先我們要把 \(N\) 旋至當前 Splay 的根。

  • 為了保證 AuxTree（輔助樹）的性質，原來 \(N\) 到 \(O\) 的實邊要更改為虛邊。

  • 由於認父不認子的性質，我們可以單方面的把 \(N\) 的兒子改為 NULL。

  • 於是原來的 AuxTree 就從下圖變成了下下圖。

    step 1 auxtree

  • 下一步，我們把 \(N\) 指向的 Father \(I\) 也旋轉到 \(I\) 的 Splay 樹根。

  • 原來的實邊 \(I\)—\(K\) 要去掉，這時候我們把 \(I\) 的右兒子指向 \(N\)，就得到了 \(I\)—\(L\) 這樣一棵 Splay。

    step 2 auxtree

  • 接下來，按照剛剛的操作步驟，由於 \(I\) 的 Father 指向 \(H\)，我們把 \(H\) 旋轉到他所在 Splay Tree 的根，然後把 \(H\) 的 rs 設為 \(I\)。

  • 之後的樹是這樣的。

    step 3 auxtree

  • 同理我們 Splay(A)，並把 \(A\) 的右兒子指向 \(H\)。

  • 於是我們得到了這樣一棵 AuxTree。並且發現 \(A\)—\(N\) 的整個路徑已經在同一棵 Splay 中了。

    step final auxtree

1
2
3
4
5
6
7
8
// 回顧一下代碼
int Access(int x) {
  int p;
  for (p = 0; x; p = x, x = f[x]) {
    Splay(x), ch[x][1] = p, PushUp(x);
  }
  return p;
}

我們發現 Access() 其實很容易，只有如下四步操作：

  1. 把當前節點轉到根。
  2. 把兒子換成之前的節點。
  3. 更新當前點的信息。
  4. 把當前點換成當前點的父親，繼續操作。

這裏提供的 Access 還有一個返回值。這個返回值相當於最後一次虛實鏈變換時虛邊父親節點的編號。該值有兩個含義：

  • 連續兩次 Access 操作時，第二次 Access 操作的返回值等於這兩個節點的 LCA.
  • 表示 \(x\) 到根的鏈所在的 Splay 樹的根。這個節點一定已經被旋轉到了根節點，且父親一定為空。

Update()

1
2
3
4
5
// 從上到下一層一層 pushDown 即可
void Update(int p) {
  if (!isRoot(p)) Update(f[p]);
  pushDown(p);
}

makeRoot()

  • Make_Root() 的重要性絲毫不亞於 Access()。我們在需要維護路徑信息的時候，一定會出現路徑深度無法嚴格遞增的情況，根據 AuxTree 的性質，這種路徑是不能出現在一棵 Splay 中的。
  • 這時候我們需要用到 Make_Root()。
  • Make_Root() 的作用是使指定的點成為原樹的根，考慮如何實現這種操作。
  • 設 Access(x) 的返回值為 \(y\)，則此時 \(x\) 到當前根的路徑恰好構成一個 Splay，且該 Splay 的根為 \(y\).
  • 考慮將樹用有向圖表示出來，給每條邊定一個方向，表示從兒子到父親的方向。容易發現換根相當於將 \(x\) 到根的路徑的所有邊反向（請仔細思考）。
  • 因此將 \(x\) 到當前根的路徑翻轉即可。
  • 由於 \(y\) 是 \(x\) 到當前根的路徑所代表的 Splay 的根，因此將以 \(y\) 為根的 Splay 樹進行區間翻轉即可。
1
2
3
4
5
void makeRoot(int p) {
  p = Access(p);
  swap(ch[p][0], ch[p][1]);
  tag[p] ^= 1;
}
  • Link 兩個點其實很簡單，先 Make_Root(x)，然後把 \(x\) 的父親指向 \(y\) 即可。顯然，這個操作肯定不能發生在同一棵樹內，所以記得先判一下。
1
2
3
4
5
void Link(int x, int p) {
  makeRoot(x);
  splay(x);
  f[x] = p;
}

Split()

  • Split 操作意義很簡單，就是拿出一棵 Splay，維護的是 \(x\) 到 \(y\) 的路徑。
  • 先 MakeRoot(x)，然後 Access(y)。如果要 \(y\) 做根，再 Splay(y)。
  • 另外 Split 這三個操作可以直接把需要的路徑拿出到 \(y\) 的子樹上，可以進行其他操作。

Cut()

  • Cut 有兩種情況，保證合法和不一定保證合法。
  • 如果保證合法，直接 Split(x, y)，這時候 \(y\) 是根，\(x\) 一定是它的兒子，雙向斷開即可。就像這樣：
1
void Cut(int x, int p) { makeRoot(x), Access(p), Splay(p), ls = f[x] = 0; }

如果是不保證合法，我們需要判斷一下是否有，這裏選擇使用 map 存一下，但是這裏有一個利用性質的方法：

想要刪邊，必須要滿足如下三個條件：

  1. \(x,y\) 連通。
  2. \(x,y\) 的路徑上沒有其他的鏈。
  3. \(x\) 沒有右兒子。

總結一下，上面三句話的意思就一個：\(x,y\) 之間有邊。

具體實現就留作一個思考題給大家。判斷連通需要用到後面的 Find，其他兩點稍作思考分析一下結構就知道該怎麼判斷了。

Find()

  • Find() 查找的是 \(x\) 所在的 原樹 的根，請不要把原樹根和輔助樹根弄混。在 Access(p) 後，再 Splay(p)。這樣根就是樹裏深度最小的那個，一直往左兒子走，沿途 PushDown 即可。
  • 一直走到沒有 ls，非常簡單。
  • 注意，每次查詢之後需要把查詢到的答案對應的結點 Splay 上去以保證複雜度。
1
2
3
4
5
6
7
8
int Find(int p) {
  Access(p);
  Splay(p);
  pushDown(p);
  while (ls) p = ls, pushDown(p);
  Splay(p);
  return p;
}

注意事項

  • 操作前一定要想一想需不需要 PushUp 或者 PushDown，LCT 由於特別靈活的原因，少 Pushdown 或者 Pushup 一次就可能把修改改到不該改的點上！
  • LCT 的 Rotate 和 Splay 的不太一樣，if (z) 一定要放在前面。
  • LCT 的 Splay 操作就是旋轉到根，沒有旋轉到誰兒子的操作，因為不需要。

習題

維護樹鏈信息

LCT 通過 Split(x,y) 操作，可以將樹上從點 \(x\) 到點 \(y\) 的路徑提取到以 \(y\) 為根的 Splay 內，樹鏈信息的修改和統計轉化為平衡樹上的操作，這使得 LCT 在維護樹鏈信息上具有優勢。此外，藉助 LCT 實現的在樹鏈上二分比樹鏈剖分少一個 \(O(\log n)\) 的複雜度。

例題 「國家集訓隊」Tree II

給出一棵有 \(n\) 個結點的樹，每個點的初始權值為 \(1\)。\(q\) 次操作，每次操作均為以下四種之一：

  1. - u1 v1 u2 v2：將樹上 \(u_1,v_1\) 兩點之間的邊刪除，連接 \(u_2,v_2\) 兩點，保證操作合法且連邊後仍是一棵樹。
  2. + u v c：將樹上 \(u,v\) 兩點之間的路徑上的點權都增加 \(c\)。
  3. * u v c：將樹上 \(u,v\) 兩點之間的路徑上的點權都乘以 \(c\)。

  4. / u v：輸出樹上 \(u,v\) 兩點之間的路徑上的點權之和對 \(51061\) 取模後的值。

    \(1\le n,q\le 10^5,0\le c\le 10^4\)

    - 操作可以直接 Cut(u1,v1),Link(u2,v2)。

對樹上 \(u,v\) 兩點之間的路徑進行修改時，先 Split(u,v)。

此題要求進行在輔助樹上的子樹加，子樹乘，子樹求和操作，所以我們除了一般 LCT 需要維護的子樹翻轉標記，還要維護子樹加法標記和子樹乘法標記。處理標記的方法和在 Splay 上是一樣的。

在打上和下傳加法標記時，子樹權值和的變化量和子樹中的結點數有關，所以我們還要維護子樹的大小 siz。

在下傳標記時，需要注意順序，先下傳乘法標記再下傳加法標記。子樹翻轉和子樹加乘兩種標記沒有衝突。

參考代碼 
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;
#define int long long
const int maxn = 100010;
const int mod = 51061;
int n, q, u, v, c;
char op;

struct Splay {
  int ch[maxn][2], fa[maxn], siz[maxn], val[maxn], sum[maxn], rev[maxn],
      add[maxn], mul[maxn];

  void clear(int x) {
    ch[x][0] = ch[x][1] = fa[x] = siz[x] = val[x] = sum[x] = rev[x] = add[x] =
        0;
    mul[x] = 1;
  }

  int getch(int x) { return (ch[fa[x]][1] == x); }

  int isroot(int x) {
    clear(0);
    return ch[fa[x]][0] != x && ch[fa[x]][1] != x;
  }

  void maintain(int x) {
    clear(0);
    siz[x] = (siz[ch[x][0]] + 1 + siz[ch[x][1]]) % mod;
    sum[x] = (sum[ch[x][0]] + val[x] + sum[ch[x][1]]) % mod;
  }

  void pushdown(int x) {
    clear(0);
    if (mul[x] != 1) {
      if (ch[x][0])
        mul[ch[x][0]] = (mul[x] * mul[ch[x][0]]) % mod,
        val[ch[x][0]] = (val[ch[x][0]] * mul[x]) % mod,
        sum[ch[x][0]] = (sum[ch[x][0]] * mul[x]) % mod,
        add[ch[x][0]] = (add[ch[x][0]] * mul[x]) % mod;
      if (ch[x][1])
        mul[ch[x][1]] = (mul[x] * mul[ch[x][1]]) % mod,
        val[ch[x][1]] = (val[ch[x][1]] * mul[x]) % mod,
        sum[ch[x][1]] = (sum[ch[x][1]] * mul[x]) % mod,
        add[ch[x][1]] = (add[ch[x][1]] * mul[x]) % mod;
      mul[x] = 1;
    }
    if (add[x]) {
      if (ch[x][0])
        add[ch[x][0]] = (add[ch[x][0]] + add[x]) % mod,
        val[ch[x][0]] = (val[ch[x][0]] + add[x]) % mod,
        sum[ch[x][0]] = (sum[ch[x][0]] + add[x] * siz[ch[x][0]] % mod) % mod;
      if (ch[x][1])
        add[ch[x][1]] = (add[ch[x][1]] + add[x]) % mod,
        val[ch[x][1]] = (val[ch[x][1]] + add[x]) % mod,
        sum[ch[x][1]] = (sum[ch[x][1]] + add[x] * siz[ch[x][1]] % mod) % mod;
      add[x] = 0;
    }
    if (rev[x]) {
      if (ch[x][0]) rev[ch[x][0]] ^= 1, swap(ch[ch[x][0]][0], ch[ch[x][0]][1]);
      if (ch[x][1]) rev[ch[x][1]] ^= 1, swap(ch[ch[x][1]][0], ch[ch[x][1]][1]);
      rev[x] = 0;
    }
  }

  void update(int x) {
    if (!isroot(x)) update(fa[x]);
    pushdown(x);
  }

  void print(int x) {
    if (!x) return;
    pushdown(x);
    print(ch[x][0]);
    printf("%lld ", x);
    print(ch[x][1]);
  }

  void rotate(int x) {
    int y = fa[x], z = fa[y], chx = getch(x), chy = getch(y);
    fa[x] = z;
    if (!isroot(y)) ch[z][chy] = x;
    ch[y][chx] = ch[x][chx ^ 1];
    fa[ch[x][chx ^ 1]] = y;
    ch[x][chx ^ 1] = y;
    fa[y] = x;
    maintain(y);
    maintain(x);
    maintain(z);
  }

  void splay(int x) {
    update(x);
    for (int f = fa[x]; f = fa[x], !isroot(x); rotate(x))
      if (!isroot(f)) rotate(getch(x) == getch(f) ? f : x);
  }

  void access(int x) {
    for (int f = 0; x; f = x, x = fa[x]) splay(x), ch[x][1] = f, maintain(x);
  }

  void makeroot(int x) {
    access(x);
    splay(x);
    swap(ch[x][0], ch[x][1]);
    rev[x] ^= 1;
  }

  int find(int x) {
    access(x);
    splay(x);
    while (ch[x][0]) x = ch[x][0];
    splay(x);
    return x;
  }
} st;

main() {
  scanf("%lld%lld", &n, &q);
  for (int i = 1; i <= n; i++) st.val[i] = 1, st.maintain(i);
  for (int i = 1; i < n; i++) {
    scanf("%lld%lld", &u, &v);
    if (st.find(u) != st.find(v)) st.makeroot(u), st.fa[u] = v;
  }
  while (q--) {
    scanf(" %c%lld%lld", &op, &u, &v);
    if (op == '+') {
      scanf("%lld", &c);
      st.makeroot(u), st.access(v), st.splay(v);
      st.val[v] = (st.val[v] + c) % mod;
      st.sum[v] = (st.sum[v] + st.siz[v] * c % mod) % mod;
      st.add[v] = (st.add[v] + c) % mod;
    }
    if (op == '-') {
      st.makeroot(u);
      st.access(v);
      st.splay(v);
      if (st.ch[v][0] == u && !st.ch[u][1]) st.ch[v][0] = st.fa[u] = 0;
      scanf("%lld%lld", &u, &v);
      if (st.find(u) != st.find(v)) st.makeroot(u), st.fa[u] = v;
    }
    if (op == '*') {
      scanf("%lld", &c);
      st.makeroot(u), st.access(v), st.splay(v);
      st.val[v] = st.val[v] * c % mod;
      st.sum[v] = st.sum[v] * c % mod;
      st.mul[v] = st.mul[v] * c % mod;
    }
    if (op == '/')
      st.makeroot(u), st.access(v), st.splay(v), printf("%lld\n", st.sum[v]);
  }
  return 0;
}

習題

維護連通性質

判斷是否連通

藉助 LCT 的 Find() 函數，可以判斷動態森林上的兩點是否連通。如果有 Find(x)==Find(y)，則説明 \(x,y\) 兩點在一棵樹上，相互連通。

例題 「SDOI2008」洞穴勘測

一開始有 \(n\) 個獨立的點，\(m\) 次操作。每次操作為以下之一：

  1. Connect u v：在 \(u,v\) 兩點之間連接一條邊。
  2. Destroy u v：刪除在 \(u,v\) 兩點之間的邊，保證之前存在這樣的一條邊。
  3. Query u v：詢問 \(u,v\) 兩點是否連通。

保證在任何時刻圖的形態都是一個森林。

\(n\le 10^4, m\le 2\times 10^5\)

參考代碼 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;
const int maxn = 10010;

struct Splay {
  int ch[maxn][2], fa[maxn], tag[maxn];

  void clear(int x) { ch[x][0] = ch[x][1] = fa[x] = tag[x] = 0; }

  int getch(int x) { return ch[fa[x]][1] == x; }

  int isroot(int x) { return ch[fa[x]][0] != x && ch[fa[x]][1] != x; }

  void pushdown(int x) {
    if (tag[x]) {
      if (ch[x][0]) swap(ch[ch[x][0]][0], ch[ch[x][0]][1]), tag[ch[x][0]] ^= 1;
      if (ch[x][1]) swap(ch[ch[x][1]][0], ch[ch[x][1]][1]), tag[ch[x][1]] ^= 1;
      tag[x] = 0;
    }
  }

  void update(int x) {
    if (!isroot(x)) update(fa[x]);
    pushdown(x);
  }

  void rotate(int x) {
    int y = fa[x], z = fa[y], chx = getch(x), chy = getch(y);
    fa[x] = z;
    if (!isroot(y)) ch[z][chy] = x;
    ch[y][chx] = ch[x][chx ^ 1];
    fa[ch[x][chx ^ 1]] = y;
    ch[x][chx ^ 1] = y;
    fa[y] = x;
  }

  void splay(int x) {
    update(x);
    for (int f = fa[x]; f = fa[x], !isroot(x); rotate(x))
      if (!isroot(f)) rotate(getch(x) == getch(f) ? f : x);
  }

  void access(int x) {
    for (int f = 0; x; f = x, x = fa[x]) splay(x), ch[x][1] = f;
  }

  void makeroot(int x) {
    access(x);
    splay(x);
    swap(ch[x][0], ch[x][1]);
    tag[x] ^= 1;
  }

  int find(int x) {
    access(x);
    splay(x);
    while (ch[x][0]) x = ch[x][0];
    splay(x);
    return x;
  }
} st;

int n, q, x, y;
char op[maxn];

int main() {
  scanf("%d%d", &n, &q);
  while (q--) {
    scanf("%s%d%d", op, &x, &y);
    if (op[0] == 'Q') {
      if (st.find(x) == st.find(y))
        printf("Yes\n");
      else
        printf("No\n");
    }
    if (op[0] == 'C')
      if (st.find(x) != st.find(y)) st.makeroot(x), st.fa[x] = y;
    if (op[0] == 'D') {
      st.makeroot(x);
      st.access(y);
      st.splay(y);
      if (st.ch[y][0] == x && !st.ch[x][1]) st.ch[y][0] = st.fa[x] = 0;
    }
  }
  return 0;
}

維護邊雙連通分量

如果要求將邊雙連通分量縮成點，每次添加一條邊，所連接的樹上的兩點如果相互連通，那麼這條路徑上的所有點都會被縮成一個點。

例題 「AHOI2005」航線規劃

給出 \(n\) 個點，初始時有 \(m\) 條無向邊，\(q\) 次操作，每次操作為以下之一：

  1. 0 u v：刪除 \(u,v\) 之間的連邊，保證此時存在這樣的一條邊。
  2. 1 u v：查詢此時 \(u,v\) 兩點之間可能的所有路徑必須經過的邊的數量。

保證圖在任意時刻都連通。

\(1<n<3\times 10^4,1<m<10^5,0\le q\le 4\times 10^4\)

可以發現，\(u,v\) 兩點之間的所有可能路徑必須經過的邊的數量為將所有邊雙連通分量縮成點之後 \(u\) 所在點和 \(v\) 所在點之間的路徑上的結點數 \(-1\)。

由於題目中的刪邊操作不好進行，我們考慮離線逆向進行操作，改刪邊為加邊。

加入一條邊時，如果兩點原來不連通，則在 LCT 上連接兩點；否則提取出加這條邊之前 LCT 上這兩點之間的路徑，遍歷輔助樹上的這個子樹，相當於遍歷了這條路徑，將這些點合併，利用並查集維護合併的信息。

用合併後並查集的代表元素代替原來樹上的路徑。注意之後的每次操作都要找到操作點在並查集上的代表元素進行操作。

參考代碼 
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <map>
using namespace std;
const int maxn = 200010;
int f[maxn];

int findp(int x) { return f[x] ? f[x] = findp(f[x]) : x; }

void merge(int x, int y) {
  x = findp(x);
  y = findp(y);
  if (x != y) f[x] = y;
}

struct Splay {
  int ch[maxn][2], fa[maxn], tag[maxn], siz[maxn];

  void clear(int x) { ch[x][0] = ch[x][1] = fa[x] = tag[x] = siz[x] = 0; }

  int getch(int x) { return ch[findp(fa[x])][1] == x; }

  int isroot(int x) {
    return ch[findp(fa[x])][0] != x && ch[findp(fa[x])][1] != x;
  }

  void maintain(int x) {
    clear(0);
    if (x) siz[x] = siz[ch[x][0]] + 1 + siz[ch[x][1]];
  }

  void pushdown(int x) {
    if (tag[x]) {
      if (ch[x][0]) tag[ch[x][0]] ^= 1, swap(ch[ch[x][0]][0], ch[ch[x][0]][1]);
      if (ch[x][1]) tag[ch[x][1]] ^= 1, swap(ch[ch[x][1]][0], ch[ch[x][1]][1]);
      tag[x] = 0;
    }
  }

  void print(int x) {
    if (!x) return;
    pushdown(x);
    print(ch[x][0]);
    printf("%d ", x);
    print(ch[x][1]);
  }

  void update(int x) {
    if (!isroot(x)) update(findp(fa[x]));
    pushdown(x);
  }

  void rotate(int x) {
    x = findp(x);
    int y = findp(fa[x]), z = findp(fa[y]), chx = getch(x), chy = getch(y);
    fa[x] = z;
    if (!isroot(y)) ch[z][chy] = x;
    ch[y][chx] = ch[x][chx ^ 1];
    fa[ch[x][chx ^ 1]] = y;
    ch[x][chx ^ 1] = y;
    fa[y] = x;
    maintain(y);
    maintain(x);
    if (z) maintain(z);
  }

  void splay(int x) {
    x = findp(x);
    update(x);
    for (int f = findp(fa[x]); f = findp(fa[x]), !isroot(x); rotate(x))
      if (!isroot(f)) rotate(getch(x) == getch(f) ? f : x);
  }

  void access(int x) {
    for (int f = 0; x; f = x, x = findp(fa[x]))
      splay(x), ch[x][1] = f, maintain(x);
  }

  void makeroot(int x) {
    x = findp(x);
    access(x);
    splay(x);
    tag[x] ^= 1;
    swap(ch[x][0], ch[x][1]);
  }

  int find(int x) {
    x = findp(x);
    access(x);
    splay(x);
    while (ch[x][0]) x = ch[x][0];
    splay(x);
    return x;
  }

  void dfs(int x) {
    pushdown(x);
    if (ch[x][0]) dfs(ch[x][0]), merge(ch[x][0], x);
    if (ch[x][1]) dfs(ch[x][1]), merge(ch[x][1], x);
  }
} st;

int n, m, q, x, y, cur, ans[maxn];

struct oper {
  int op, a, b;
} s[maxn];

map<pair<int, int>, int> mp;

int main() {
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; i++) st.maintain(i);
  for (int i = 1; i <= m; i++)
    scanf("%d%d", &x, &y), mp[{x, y}] = mp[{y, x}] = 1;
  while (scanf("%d", &s[++q].op)) {
    if (s[q].op == -1) {
      q--;
      break;
    }
    scanf("%d%d", &s[q].a, &s[q].b);
    if (!s[q].op) mp[{s[q].a, s[q].b}] = mp[{s[q].b, s[q].a}] = 0;
  }
  reverse(s + 1, s + q + 1);
  for (map<pair<int, int>, int>::iterator it = mp.begin(); it != mp.end(); it++)
    if (it->second) {
      mp[{it->first.second, it->first.first}] = 0;
      x = findp(it->first.first);
      y = findp(it->first.second);
      if (st.find(x) != st.find(y))
        st.makeroot(x), st.fa[x] = y;
      else {
        if (x == y) continue;
        st.makeroot(x);
        st.access(y);
        st.splay(y);
        st.dfs(y);
        int t = findp(y);
        st.fa[t] = findp(st.fa[y]);
        st.ch[t][0] = st.ch[t][1] = 0;
        st.maintain(t);
      }
    }
  for (int i = 1; i <= q; i++) {
    if (s[i].op == 0) {
      x = findp(s[i].a);
      y = findp(s[i].b);
      st.makeroot(x);
      st.access(y);
      st.splay(y);
      st.dfs(y);
      int t = findp(y);
      st.fa[t] = st.fa[y];
      st.ch[t][0] = st.ch[t][1] = 0;
      st.maintain(t);
    }
    if (s[i].op == 1) {
      x = findp(s[i].a);
      y = findp(s[i].b);
      st.makeroot(x);
      st.access(y);
      st.splay(y);
      ans[++cur] = st.siz[y] - 1;
    }
  }
  for (int i = cur; i >= 1; i--) printf("%d\n", ans[i]);
  return 0;
}

習題

維護邊權

LCT 並不能直接處理邊權，此時需要對每條邊建立一個對應點，方便查詢鏈上的邊信息。利用這一技巧可以動態維護生成樹。

例題 luogu P4234 最小差值生成樹

給定一個 \(n\) 個點，\(m\) 條邊的帶權無向圖，求其邊權最大值和邊權最小值的差值最小的生成樹，輸出這個差值。

數據保證至少存在一棵生成樹。

\(1\le n\le 5\times 10^4,1\le m\le 2\times 10^5,1\le w_i\le 10^4\)

將邊按照邊權從小到大排序，枚舉選擇的最右邊的一條邊，要得到最優解，需要使邊權最小邊的邊權最大。

每次按照順序添加邊，如果將要連接的這兩個點已經連通，則刪除這兩點之間邊權最小的一條邊。如果整個圖已經連通成了一棵樹，則用當前邊權減去最小邊權更新答案。最小邊權可用雙指針法更新。

LCT 上沒有固定的父子關係，所以不能將邊權記錄在點權中。

記錄樹鏈上的邊的信息，可以使用 拆邊。對每條邊建立一個對應的點，從這條邊向其兩個端點連接一條邊，原先的連邊與刪邊操作都變成兩次操作。

參考代碼 
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <set>
using namespace std;
const int maxn = 5000010;

struct Splay {
  int ch[maxn][2], fa[maxn], tag[maxn], val[maxn], minn[maxn];

  void clear(int x) {
    ch[x][0] = ch[x][1] = fa[x] = tag[x] = val[x] = minn[x] = 0;
  }

  int getch(int x) { return ch[fa[x]][1] == x; }

  int isroot(int x) { return ch[fa[x]][0] != x && ch[fa[x]][1] != x; }

  void maintain(int x) {
    if (!x) return;
    minn[x] = x;
    if (ch[x][0]) {
      if (val[minn[ch[x][0]]] < val[minn[x]]) minn[x] = minn[ch[x][0]];
    }
    if (ch[x][1]) {
      if (val[minn[ch[x][1]]] < val[minn[x]]) minn[x] = minn[ch[x][1]];
    }
  }

  void pushdown(int x) {
    if (tag[x]) {
      if (ch[x][0]) tag[ch[x][0]] ^= 1, swap(ch[ch[x][0]][0], ch[ch[x][0]][1]);
      if (ch[x][1]) tag[ch[x][1]] ^= 1, swap(ch[ch[x][1]][0], ch[ch[x][1]][1]);
      tag[x] = 0;
    }
  }

  void update(int x) {
    if (!isroot(x)) update(fa[x]);
    pushdown(x);
  }

  void print(int x) {
    if (!x) return;
    pushdown(x);
    print(ch[x][0]);
    printf("%d ", x);
    print(ch[x][1]);
  }

  void rotate(int x) {
    int y = fa[x], z = fa[y], chx = getch(x), chy = getch(y);
    fa[x] = z;
    if (!isroot(y)) ch[z][chy] = x;
    ch[y][chx] = ch[x][chx ^ 1];
    fa[ch[x][chx ^ 1]] = y;
    ch[x][chx ^ 1] = y;
    fa[y] = x;
    maintain(y);
    maintain(x);
    if (z) maintain(z);
  }

  void splay(int x) {
    update(x);
    for (int f = fa[x]; f = fa[x], !isroot(x); rotate(x))
      if (!isroot(f)) rotate(getch(x) == getch(f) ? f : x);
  }

  void access(int x) {
    for (int f = 0; x; f = x, x = fa[x]) splay(x), ch[x][1] = f, maintain(x);
  }

  void makeroot(int x) {
    access(x);
    splay(x);
    tag[x] ^= 1;
    swap(ch[x][0], ch[x][1]);
  }

  int find(int x) {
    access(x);
    splay(x);
    while (ch[x][0]) x = ch[x][0];
    splay(x);
    return x;
  }

  void link(int x, int y) {
    makeroot(x);
    fa[x] = y;
  }

  void cut(int x, int y) {
    makeroot(x);
    access(y);
    splay(y);
    ch[y][0] = fa[x] = 0;
    maintain(y);
  }
} st;

const int inf = 2e9 + 1;
int n, m, ans, nww, x, y;

struct Edge {
  int u, v, w;

  bool operator<(Edge x) const { return w < x.w; };
} s[maxn];

multiset<int> mp;

int main() {
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; i++) st.val[i] = inf, st.maintain(i);
  for (int i = 1; i <= m; i++) scanf("%d%d%d", &s[i].u, &s[i].v, &s[i].w);
  sort(s + 1, s + m + 1);
  for (int i = 1; i <= m; i++) st.val[n + i] = s[i].w, st.maintain(n + i);
  for (int i = 1; i <= m; i++) {
    x = s[i].u;
    y = s[i].v;
    if (x == y) continue;
    if (st.find(x) != st.find(y)) {
      nww++;
      st.link(x, n + i);
      st.link(n + i, y);
      mp.insert(s[i].w);
      if (nww == n - 1) ans = s[i].w - (*(mp.begin()++));
    } else {
      st.makeroot(x);
      st.access(y);
      st.splay(y);
      int t = st.minn[y] - n;
      st.cut(s[t].u, t + n);
      st.cut(t + n, s[t].v);
      mp.erase(mp.find(s[t].w));
      st.link(x, n + i);
      st.link(n + i, y);
      mp.insert(s[i].w);
      if (nww == n - 1) ans = min(ans, s[i].w - (*(mp.begin()++)));
    }
  }
  printf("%d\n", ans);
  return 0;
}

習題

維護子樹信息

LCT 不擅長維護子樹信息。統計一個結點所有虛子樹的信息，就可以求得整棵樹的信息。

例題 「BJOI2014」大融合

給定 \(n\) 個結點和 \(q\) 次操作，每個操作為如下形式：

  1. A x y 在結點 \(x\) 和 \(y\) 之間連接一條邊。
  2. Q x y 給定一條已經存在的邊 \((x,y)\)，求有多少條簡單路徑，其中包含邊 \((x,y)\)。

保證在任意時刻，圖的形態都是一棵森林。

\(1\le n,q,x,y\le 10^5\)

為詢問 Q 考慮另一種表述，我們發現答案等於邊 \((x,y)\) 在 \(x\) 側的結點數與 \(y\) 側的結點數的乘積，即將邊 \((x,y)\) 斷開後分別包含 \(x\) 和 \(y\) 的樹的結點數。為了消除斷邊的影響，在詢問後我們再次連接邊 \((x,y)\)。

題目中的操作既有連邊，又有刪邊，還保證在任意時刻都是一棵森林，我們不由得想到用 LCT 來維護。但是這題中 LCT 維護的是子樹的大小，不像我們印象中的維護一條鏈的信息，而 LCT 的構造 認父不認子，不方便我們直接進行子樹的統計。怎麼辦呢？

方法是統計一個結點 \(x\) 所有虛兒子（即父親為 \(x\)，但 \(x\) 在 Splay 中的左右兒子並不包含它）所代表的子樹的貢獻。

定義 \(siz2[x]\) 為結點 \(x\) 的所有虛兒子代表的子樹的結點數，\(siz[x]\) 為 結點 \(x\) 子樹中的結點數。

不同於以往我們維護 Splay 中子樹結點個數的方法，我們在計算結點 \(x\) 子樹中的結點數時，還要加上 \(siz2[x]\)，即

1
2
3
4
void maintain(int x) {
  clear(0);
  if (x) siz[x] = siz[ch[x][0]] + 1 + siz[ch[x][1]] + siz2[x];
}

而且在我們 改變 Splay 的形態（即改變一個結點在 Splay 上的左右兒子指向時），需要及時修改 \(siz2[x]\) 的值。

在 Rotate(),Splay() 操作中，我們都只是改變了 Splay 中結點的相對位置，沒有改變任意一條邊的虛實情況，所以不對 \(siz2[x]\) 進行任何修改。

在 access 操作中，在每次 splay 完後，都會改變剛剛 splay 完的結點的右兒子，即該結點與其原右兒子的連邊和該節點和新右兒子的連邊的虛實情況發生了變化，我們需要加上新變成虛邊所連的子樹的貢獻，減去剛剛變成實邊所連的子樹的貢獻。代碼如下：

1
2
3
4
void access(int x) {
  for (int f = 0; x; f = x, x = fa[x])
    splay(x), siz2[x] += siz[ch[x][1]] - siz[f], ch[x][1] = f, maintain(x);
}

在 MakeRoot(),Find() 操作中，我們都只是調用了之前的函數或者在 Splay 上條邊，並不用做任何修改。

在連接兩點時，我們修改了一個結點的父親。我們需要在父親結點的 \(siz2\) 值中加上新子結點的子樹大小貢獻。

1
2
3
4
st.makeroot(x);
st.makeroot(y);
st.fa[x] = y;
st.siz2[y] += st.siz[x];

在斷開一條邊時，我們只是刪除了 Splay 上的一條實邊，Maintain 操作會維護這些信息，不需要做任何修改。

以上是代碼修改的細節，最後總結一下 LCT 維護子樹信息的要求與方法：

  1. 維護的信息要有 可減性，如子樹結點數，子樹權值和，但不能直接維護子樹最大最小值，因為在將一條虛邊變成實邊時要排除原先虛邊的貢獻。
  2. 新建一個附加值存儲虛子樹的貢獻，在統計時將其加入本結點答案，在改變邊的虛實時及時維護。
  3. 其餘部分同普通 LCT，在統計子樹信息時一定將其作為根節點。
  4. 如果維護的信息沒有可減性，如維護區間最值，可以對每個結點開一個平衡樹維護結點的虛子樹中的最值。
參考代碼 
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;
const int maxn = 100010;
typedef long long ll;

struct Splay {
  int ch[maxn][2], fa[maxn], siz[maxn], siz2[maxn], tag[maxn];

  void clear(int x) {
    ch[x][0] = ch[x][1] = fa[x] = siz[x] = siz2[x] = tag[x] = 0;
  }

  int getch(int x) { return ch[fa[x]][1] == x; }

  int isroot(int x) { return ch[fa[x]][0] != x && ch[fa[x]][1] != x; }

  void maintain(int x) {
    clear(0);
    if (x) siz[x] = siz[ch[x][0]] + 1 + siz[ch[x][1]] + siz2[x];
  }

  void pushdown(int x) {
    if (tag[x]) {
      if (ch[x][0]) swap(ch[ch[x][0]][0], ch[ch[x][0]][1]), tag[ch[x][0]] ^= 1;
      if (ch[x][1]) swap(ch[ch[x][1]][0], ch[ch[x][1]][1]), tag[ch[x][1]] ^= 1;
      tag[x] = 0;
    }
  }

  void update(int x) {
    if (!isroot(x)) update(fa[x]);
    pushdown(x);
  }

  void rotate(int x) {
    int y = fa[x], z = fa[y], chx = getch(x), chy = getch(y);
    fa[x] = z;
    if (!isroot(y)) ch[z][chy] = x;
    ch[y][chx] = ch[x][chx ^ 1];
    fa[ch[x][chx ^ 1]] = y;
    ch[x][chx ^ 1] = y;
    fa[y] = x;
    maintain(y);
    maintain(x);
    maintain(z);
  }

  void splay(int x) {
    update(x);
    for (int f = fa[x]; f = fa[x], !isroot(x); rotate(x))
      if (!isroot(f)) rotate(getch(x) == getch(f) ? f : x);
  }

  void access(int x) {
    for (int f = 0; x; f = x, x = fa[x])
      splay(x), siz2[x] += siz[ch[x][1]] - siz[f], ch[x][1] = f, maintain(x);
  }

  void makeroot(int x) {
    access(x);
    splay(x);
    swap(ch[x][0], ch[x][1]);
    tag[x] ^= 1;
  }

  int find(int x) {
    access(x);
    splay(x);
    while (ch[x][0]) x = ch[x][0];
    splay(x);
    return x;
  }
} st;

int n, q, x, y;
char op;

int main() {
  scanf("%d%d", &n, &q);
  while (q--) {
    scanf(" %c%d%d", &op, &x, &y);
    if (op == 'A') {
      st.makeroot(x);
      st.makeroot(y);
      st.fa[x] = y;
      st.siz2[y] += st.siz[x];
    }
    if (op == 'Q') {
      st.makeroot(x);
      st.access(y);
      st.splay(y);
      st.ch[y][0] = st.fa[x] = 0;
      st.maintain(x);
      st.makeroot(x);
      st.makeroot(y);
      printf("%lld\n", (ll)(st.siz[x] * st.siz[y]));
      st.makeroot(x);
      st.makeroot(y);
      st.fa[x] = y;
      st.siz2[y] += st.siz[x];
    }
  }
  return 0;
}

習題

本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用