跳转至

Top Tree

Self-Adjusting Top Tree

簡介

Self-Adjusting Top Tree，是 2005 年 Tarjan 和 Werneck 在他們的論文《Self-Adjusting Top Trees》中提出的一種基於 Top Tree 理論的維護完全動態森林的數據結構，簡稱為 SATT。

Self-Adjusting Top Tree 可以實現森林中任一棵樹的鏈修改/查詢、子樹修改/查詢以及非局部搜索等操作。

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

問題引入

維護一個森林，支持如下操作：

  • 刪除，添加一條邊，保證操作前後仍是一個森林。

  • 修改某棵樹上某條簡單路徑的權值。

  • 修改以某個點為根的子樹權值。

  • 查詢某棵樹上的某條簡單路徑權值和。

  • 查詢以某個點為根的子樹權值和。

樹收縮

對於任意一棵樹，我們都可以運用 樹收縮 理論來將它收縮為一條邊。

具體地，樹收縮有兩個基本操作：Compress 和 Rake，Compress 操作指定一個度數為二的點 \(x\)，與點 \(x\) 相鄰的那兩個點記為 \(y\)、\(z\)，我們連一條新邊 \(yz\)；將點 \(x\)、邊 \(xz\)、邊 \(xy\) 的信息放到 \(yz\) 中儲存，並刪去它們。如圖所示。

Rake 操作指定一個度為一的點 \(x\)，而且與點 \(x\) 相鄰的點 \(y\) 的度數需大於一，設點 \(y\) 的另一個鄰點為 \(z\)，我們將點 \(x\)、邊 \(xy\) 的信息放入 邊 \(yz\) 中儲存，並刪去它們。如圖所示。

不難證明，任何一棵樹都可以只用 Compress 操作 和 Rake 操作來將它收縮為一條邊，如圖所示。

簇

為了表達方便，我們記在進行任何操作之前的原樹為 \(T\)。在對 \(T\) 進行某些樹收縮操作（可以不做任何操作）之後的樹記為 \(T_x\)。

我們研究 某個 \(T_x\) 中某一條邊所包含的信息情況。

這條邊除了帶有它本身的信息（當然，如果這條邊在 \(T\) 中不存在，這條邊就沒有本身的信息）之外，還可能包含其它通過 Compress/Rake 操作合併到它上面的點、邊的信息。我們不妨先從下圖中的樹收縮過程中選取一條邊，看看它所包含的信息在 \(T\) 中代表哪些點、邊。

如圖，選取的邊和對應的圖已用紅線圈出。

可以看出，這條邊所包含的信息在 \(T\) 中代表的點、邊是連通的。我們可以推及，對於任一 \(T_x\) 中的任一條邊儲存的信息在 \(T\) 中總體現為一個連通子圖。我們將這樣的連通子圖稱為 簇（Cluster）。

然而，簇是 不完整的子圖，它包含的某些邊的端點不被簇它自己包含。於是我們將這些端點稱作簇的 端點（Endpoint），將它包含的那些連通子圖的點稱作 內點（Internal Node），連通子圖的邊稱作 內邊（Internal Edge）。

對於任意一個簇，都有以下性質：

  1. 簇只存儲和維護內點和內邊的信息。

  2. 簇有兩個端點。這兩個端點即為 \(T_x\) 中代表那個簇的邊相連的那兩個點。兩個端點之間的路徑我們稱之為 簇路徑（Cluster Path）；記一個簇的兩個端點分別為 \(x\)、\(y\)，我們下面用 \(C(x,y)\) 來表示這個簇。

  3. 內點僅與端點或內點相連。

特別地，對於 \(T\) 中的每條邊，都各自獨立為一個簇（僅包含邊自己的信息），這種簇我們稱之為 基簇（Base Cluster）。對於由 \(T\) 收縮到只有一條邊的最終的 \(T_x\)，那條邊代表的簇包含除了兩個端點之外的整棵 \(T\) 的信息，這個簇我們稱之為 根簇（Root Cluster）。

如圖，上文提到的基簇已用紅線圈出。

從簇的視角來看 Compress/Rake 操作，我們發現這兩個操作會將兩個簇“合二為一”，剩下一個新簇，所以樹收縮的過程也是所有的基簇合併為一個簇的過程。

所以我們也可以得到下圖，是對一系列樹收縮操作的另一表示。

Top Tree

我們現在想表示某一棵樹進行樹收縮的全過程。

我們可以用上文的兩種方法來表示這一過程，但這樣十分麻煩，如果樹收縮進行了 \(n\) 步，我們就要用 \(n\) 棵樹來表示整個樹收縮。

考慮一個對某棵樹進行某一樹收縮的更簡便表示，我們引入 Top Tree。

如圖，是以上文的收縮方法和原樹為基礎的一棵 Top Tree。

Top Tree 有以下性質；

  1. 一棵 Top Tree 對應一棵原樹和一種對其進行樹收縮的方法，Top Tree 的每個節點都表示在某個 \(T_x\) 中的某一條邊，也就是樹收縮過程中形成的某一個簇。圖中的形如 \(N_x\) 的點表示 compress(x) 這一操作形成的簇。

  2. Top Tree 中的一個節點有兩個兒子（都分別代表一個簇），這個節點代表的簇是這兩個簇通過 Compress 或 Rake 操作合併得到的新簇。

  3. Top Tree 的葉子節點是基簇，其根節點是根簇。因此我們按一棵 Top Tree 的拓撲序分層，它的每一層就代表了一棵 \(T_x\)。

用三度化 Self-Adjusting Top Tree 實現信息維護

原理

Top Tree 對樹收縮過程的極大簡化 使我們看到通過維護樹收縮過程來維護樹上信息的可能性，SATT 即是通過這一原理來維護樹上信息的。

注意到樹收縮的過程也是樹上信息不斷加入的過程，我們執行一次 compress(x)，\(x\) 點的信息從此刻起就開始在某個簇中出現，影響着我們的統計結果。

假如我們現在用 Top Tree 來維護某棵樹 \(T\)，樹上的每個點，邊都有權值，我們要維護的是 \(T\) 的權值和。

現在我們在維護時要對 \(T\) 中某個點 \(x\) 的權值進行修改，很明顯，我們就需要更改 Top Tree 中所有簇信息包含 \(x\) 的節點信息，這樣做單次時間複雜度會是 \(O(n)\) 級別的。

然而，如果我們選的點它在 Top Tree 中簇信息包含 \(x\) 的節點個數很少，也就是説使它的信息儘可能晚地加入簇中，我們單次操作的時間複雜度就會有一個很大的提升。如圖。

SATT 就是通過修改 某個點/某條路徑 在樹收縮過程中信息被加入簇中的先後順序（以降低其在被修改時的單次時間複雜度）來維護樹上信息的。

實際結構

我們先將一棵原樹 \(T\) 分層定根，然後我們考慮對某種樹收縮順序的 Top Tree 的 根簇，它有兩個端點，我們令這其中一個端點就是原樹的根，另一個端點任選。

如圖，給根簇選出一組端點，這裏標註簇時將端點也圈進去了。

由樹收縮的基本操作可知，簇路徑上的點、邊 \((j,h,c,jh,hc)\) 的信息最後是通過 Compress 操作才加入 \(C(k,g)\) 的，而的非簇路徑點 \((a,b,i,f,g,e,ig,\cdots)\) 是通過 Rake 操作才加入 \(C(k,g)\) 的。

我們將簇路徑單獨拿出來，這是一條形態特殊（為鏈）的樹，我們為這棵樹建出一棵 top tree（其代表的樹收縮順序任意）。

我們將這一結構稱之為 Compress Tree，因為在這棵 Top Tree 中任一個點的兩個兒子之間是通過 Compress 操作來合併成它們的父親。

Compress Tree 裏的節點稱為 Compress Node。只考慮當前這條簇路徑，一個 非葉子的 Compress Node 就代表一次 compress 過程，表示將左兒子和右兒子信息合併起來，再將這個 \(compress(x)\) 本身存儲的點 \(x\) 信息加入。這棵 Compress Tree 就維護了 \(C(k,g)\) 簇路徑的信息。

另外，在 Compress Tree 中，我們實際上還對使用的 Top Tree 做了一些限制。注意到 compress tree 維護的是一個 \(T\) 中點的深度兩兩不同的鏈，我們規定在 Compress Tree 中基簇的中序遍歷順序與對應的 \(T\) 中邊的深度是一致的，且中序遍歷越小深度越淺。同樣，對於每個點 \(x\) 對應的 \(compress(x)\) 的關係 也是如此。

現在來維護那些非簇路徑的信息，我們假設這些 非簇路徑上的點、邊已經形成了一個個極大簇，而這些極大簇是由這些用藍線圈出的更小簇之間互相 Rake 形成的，對由一些更小簇合並形成一個極大簇的過程，我們用一個三叉樹來表示，類似地，我們稱這一結構為 Rake Tree，對應地 Rake Tree 裏的點就是 Rake Node。每個 Rake Node 都代表一個簇，是由其左兒子和右兒子 Rake 到其 中兒子代表的更小簇上形成的。具體可見下圖，可知 Rake Tree 中的每個點都代表了 \(T\) 中具有相同端點的更小簇。

如圖，藍線圈出的是一個個極大簇，黃線圈出的是一個個更小簇。

對於那些更小簇，我們對它們進行相同處理，給它們選擇簇路徑、建出 Compress Tree \(\cdots\) 如此遞歸下去，就建出了許多表示樹收縮過程的 Compress Tree，Rake Tree。

如圖 2-4，為原樹的 Rake-Compress Tree（因為每個 Rake Node 都連着一棵 Compress Tree，所以表現為一棵 Rake Tree 連着許多 Compress Tree 的形態）和代表根簇路徑的 Compress Tree。

考慮將這些樹以某種方式拼接在一起，使它們形成一個有序的整體。記一個 Rake Tree 代表的最小簇的集合的公共端點是 點 \(x\)。我們給這些 rake node 的中兒子（一個 compress tree 集合）都加入非 \(x\) 的另一端點，但仍保持其中序遍歷和 top tree 的基本性質，如圖。

這一步相當於是讓 Rake 操作加入某個 \(T\) 中點的操作直接發生在 Compress Tree 中，這不僅使我們能 正確維護 Rake Node 的信息（只需將三個兒子信息合併即可），還使我們 Compress Tree 的結構更完整。下一步，我們將 Compress Tree 改為三叉樹，若某個 Rake Tree 的公共端點是 點 \(x\)，我們就將 Rake Tree 掛在 \(compress(x)\) 的中兒子處，如圖。

此時經過三叉化的 \(compress(x)\) 點，它的意義就變成先將其中兒子 Rake 到簇路徑上，再統計左右兒子 和點 \(x\) 的信息。

最後，我們再處理一下根簇路徑的那棵 Compress Tree：與其它所有 Compress Tree 一致地，按中序遍歷加入它的兩個端點，使得 它的根儲存整棵 \(T\) 的信息。

於是我們就實現了用三度化 Self-Adjusting Top Tree 實現一棵樹的信息維護。

總結一下，SATT 有以下性質：

  1. SATT 由 Compress Tree 和 Rake Tree 組成，Compress Tree 是一棵特殊的 Top Tree；Rake Tree 是一個三叉樹，它們都對應一棵樹進行樹收縮的過程。

  2. Compress Tree 裏的點最多有三個兒子。Compress Tree 可以做類似於 Splay 樹的旋轉操作（只需保證其中序遍歷不變即可，旋轉一個點時保持其中兒子不動）。

  3. Rake Tree 裏的點一定有一箇中兒子。Rake Tree 可以做類似於 Splay 樹的旋轉操作（只需保證其中序遍歷不變即可，旋轉一個點時保持其中兒子不動）。

  4. SATT 的拓撲序反映了原樹 \(T\) 的樹收縮順序。

我們在上文中提到的「修改 某個點/某條路徑 在樹收縮過程中信息被加入簇中的先後順序」SATT 是否能實現呢，答案是肯定的。

在 SATT 中，有一個 access(x) 的操作，它的作用是使某點 \(x\) 成為根簇的非根端點，同時在 SATT 中使 \(compress(x)\) 成為 SATT 的根。

我們可以通過 access(x) 操作以均攤 \(O(\log n)\) 的複雜度使 SATT 中代表 \(compress(x)\) 的點旋到整棵 SATT 的樹根，根據 SATT 的第四個性質，我們改變了 \(compress(x)\) 的操作順序，使得它最晚執行，\(x\) 點的信息也就被最晚加入；這樣當我們要修改 \(x\) 點的信息時，就只需要更新 \(compress(x)\)。

代碼實現

Push 類函數

Pushup(x)

在考慮對 SATT 的某個節點維護信息時，首先分這個點在 Compress Tree 還是在 Rake Tree 進行討論，原因可見上文，不再贅述，下面以維護某個點的子樹大小為例

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
// ls(x) x的左兒子
// rs(x) x的右兒子
// ms(x) x的中兒子
// type==0 是 compress node
// type==1 是 rake node
void pushup(int x, int type) {
  if (type == 0)
    size[x] = size[rs(x)] + size[ms(x)] + 1;
  else
    size[x] = size[rs(x)] + size[ms(x)] + size[ls(x)];
  return;
}

查詢點 \(x\) 的子樹大小，就將其 Access 到 SATT 根，答案是其中兒子的 size \(+1\)；因為根據上文，在 Access 之後，其中兒子才是它的真子樹。

Pushdown(x)

我們如果要對原樹中的某個子樹做整體修改，一個很自然的想法是：將這個節點直接 Access 到 SATT 根節點，給它的中兒子打上一個標記即可。同理，查詢子樹就直接 Access 後查詢中兒子。

我們如果要對原樹中的某條路徑做整體修改，我們就 \(expose\) 路徑的兩個端點，其中 \(expose(x,y)\) 是使 點 \(x\) 成為了 \(T\) 的根節點，使點 \(y\) 成為根簇的另一個端點。對應在 SATT 上，此時根簇 的 compress tree 就是 \(x\) 到 \(y\) 的路徑。於是直接給根簇的 Compress Tree 打上一個標記即可。同理查詢鏈 \(expose\) 後查詢根節點即可。

於是我們就知道問題引入的問題怎麼做了。

 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
void pushdown(int x, int type) {
  if (type == 0) {
    // 處理鏈
    chain[ls(x)] += chain[x] chain[rs(x)] += chain[x];
    val[ls(x)] += chain[x];
    val[rs(x)] += chain[x];
    // 處理子樹
    subtree[ls(x)] += subtree[x];
    subtree[rs(x)] += subtree[x];
    subtree[ms(x)] += subtree[x];
    val[ls(x)] += subtree[x];
    val[rs(x)] += subtree[x];
    val[ms(x)] += subtree[x];
    subtree[x] = 0;
  } else {
    subtree[ls(x)] += subtree[x];
    subtree[rs(x)] += subtree[x];
    subtree[ms(x)] += subtree[x];
    val[ls(x)] += subtree[x];
    val[rs(x)] += subtree[x];
    val[ms(x)] += subtree[x];
    subtree[x] = 0;
  }
  return;
}

// 下傳標記
void pushall(int x, int type) {
  if (!isroot(x)) pushall(father[x], type);
  pushdown(x, type);
  return;
}

Splay 類函數

我們知道 SATT 中的 Rake Tree 和 Compress Tree 都是可以旋轉的，也就是説它們可以用 Splay 來維護。因此我們可以寫出以下代碼：

 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
// ls 一個SATT節點的左兒子
// rs 一個SATT節點的右兒子
// ms 一個SATT節點的中兒子
// type==1 在rake tree中
// type==0 在compress tree中
bool isroot(int x) {
  return rs(father[x]) != x && ls(father[x]) != x;
}  // 是一個節點的中兒子或無父親

bool direction(int x) { return rs(father[x]) == x; }

void rotate(int x, int type) {
  int y = father[x], z = father[y], d = direction(x), w = son[x][d ^ 1];
  if (z) son[z][ms(z) == y ? 2 : direction(y)] = x;
  son[x][d ^ 1] = y;
  son[y][d] = w;
  if (w) father[w] = y;
  father[y] = x;
  father[x] = z;
  pushup(y, type);
  pushup(x, type);
  return;
}

void splay(int x, int type, int goal = 0) {
  pushall(x, ty); /*下傳標記*/
  for (int y; y = father[x], (!isroot(x)) && y != goal; rotate(x, ty)) {
    if (father[y] != goal && (!isroot(y))) {
      rotate(direction(x) ^ diretion(y) ? x : y, type);
    }
  }
  return;
}

值得注意的是，函數 direction 和 isroot 與普通 Splay 的不同。

因為無論你把這個點怎麼轉，這個點的中兒子是不會變的。

Access 類函數

access(x) 的意義是：將點 \(x\) 旋轉到整個 SATT 的根處，使點 \(x\) 成為根簇的兩個端點之一（另一端點即為 \(T\) 的根節點），同時不能改變原樹的結構和原樹的根。

為了實現 access(x)，我們先將其旋轉到其所在 Compress Tree 的樹根，再把點 \(x\) 的右兒子去掉，使點 \(x\) 成為其所在 compress tree 對應簇的端點。

1
2
3
4
5
6
7
8
9
if (rs(x)) {
  int y = new_node();
  setfather(ms(x), y, 0);
  setfather(rs(x), y, 2);
  rs(x) = 0;
  setfather(y, x, 2);
  pushup(y, 1);
  pushup(x, 0);
}

如果這時點 \(x\) 已經到了根部，則退出；若沒有，則執行以下步驟，以讓它跨過它上面的 Rake Tree：

  1. 將其父親節點（一定是一個 Rake Node），splay 到其 Rake Tree 的樹根；

  2. 將 \(x\) 的爺節點（一定是一個 Compress Node）splay 到其 Compress Tree 根部。

  3. 若 \(x\) 的爺節點有一個右兒子，則將點 x 和爺節點的右兒子互換，更新信息，然後退出。

  4. 若爺節點沒有右兒子，則先讓點 \(x\) 成為爺節點的右兒子，此時點 \(x\) 原來的父節點沒有中兒子，根據上文 Rake Node 的性質，它不能存在。於是調用 Delete 函數，將其刪除，然後退出。

1，2 兩個步驟合稱為 Local Splay。3，4 兩個步驟合稱為 Splice。但我們方便起見，將它們都寫在 Splice(x) 函數里。

上文提到的 Delete(x) 函數是這樣的：

  1. 檢視將要刪除的點 \(x\) 有沒有左兒子，若有，則將左兒子的子樹後繼續旋轉到點 \(x\) 下方（成為新的左兒子），然後將右兒子（若有）變成左兒子的右兒子，此時點 \(x\) 的左兒子就代替了點 \(x\)。（這相當於 Splay 的合併操作）

  2. 若沒有左兒子，則直接讓其右兒子代替點 \(x\)。

不難發現，Splice(x) 改變了原樹的一些簇的端點選取。一次 splice 完了之後，我們將 點 \(x\) 的父親節點當作新的 點 \(x\)，進行下一次 splice。

最終我們會發現 我們最開始要操作的點 \(x\) 一定在 根簇的 compress tree 最右端。我們只需最後做一次 Global Splay，將其旋至 SATT 根部即可。

 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
// ls 一個SATT節點的左兒子
// rs 一個SATT節點的右兒子
// ms 一個SATT節點的中兒子
// son[x][0] ls
// son[x][1] rs
// son[x][2] ms
// type==1 在rake tree中
// type==0 在compress tree中
int new_node() {
  if (top) {
    top--;
    return Stack[top + 1];
  } else
    return ++tot;
}

void setfather(int x, int fa, int type) {
  if (x) father[x] = fa;
  son[fa][type] = x;
  return;
}

void Delete(int x) {
  setfather(ms(x), father[x], 1);
  if (ls(x)) {
    int p = ls(x);
    pushdown(p, 1);
    while (rs(p)) p = rs(p), pushdown(p, 1);
    splay(p, 1, x);
    setfather(rs(x), p, 1);
    setfather(p, father[x], 2);
    pushup(p, 1);
    pushup(father[x], 0);
  } else
    setfather(rs(x), father[x], 2);
  Clear(x);
}

void splice(int x) {
  /*  local splay */
  splay(x, 1);
  int y = father[x];
  splay(y, 0);
  pushdown(x, 1);
  /*  splice  */
  if (rs(y)) {
    swap(father[ms(x)], father[rs(y)]);
    swap(ms(x), rs(y));
  } else
    Delete(x);
  pushup(x, 1);
  pushup(y, 0);
  return;
}

void access(int x) {
  splay(x, 0);
  if (rs(x)) {
    int y = new_node();
    setfather(ms(x), y, 0);
    setfather(rs(x), y, 2);
    rs(x) = 0;
    setfather(y, x, 2);
    pushup(y, 1);
    pushup(x, 0);
  }
  while (father[x]) {
    splice(father[x]);
    x = father[x];
    pushup(x, 0);
  }
  splay(x, 0) /*global splay*/
      return;
}

關於 makeroot(x):

若要讓一個點成為原樹的根，那麼我們就將點 \(x\) Access 到 SATT 的根節點，可知此時點 \(x\) 已經是最終狀態的簇一個端點。由 Compress Tree 的中序遍歷性質可知，將點 \(x\) 所在的 Compress Tree 左右顛倒（所有點的左右兒子互換），就使點 \(x\) 成為原樹的根。在具體實現中，我們通過給點 \(x\) 打上一個翻轉標記，之後下傳來進行這一過程。

1
2
3
4
5
void makeroot(int x) {
  access(x);
  push_rev(x);
  return;
}

於是 expose(x,y) 就呼之欲出：

1
2
3
4
5
void expose(int x,int y){
    makeroot(x);
    access(y);
    return;
}

Link & Cut

現在我們要將原樹中兩個不連通的點之間連一條邊，則我們先將其中的一個點 \(x\) \(makeroot\)，再將另一個點 \(y\) \(access\) 到根，可知此時應該使點 \(y\) 成為點 \(x\) 的右兒子，並在點 \(y\) 的右兒子上掛上這一條邊（在只需維護點的 SATT 中，這一步可省）。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
void Link(int x, int y, int z) {
  /*z代表連接x,y的邊*/
  access(x);
  makeroot(y);
  setfather(y, x, 1);
  setfather(z, y, 0);
  pushup(x, 0);
  pushup(y, 0);
  return;
}

Cut 跟 link 原理差不多……

1
2
3
4
5
6
void cut(int x, int y) {
  expose(x, y);
  clear(rs(x)); /*刪掉xy這一基簇。*/
  father[x] = ls(y) = rs(x);
  pushup(y, 0);
}

完整代碼（Luogu P3690【模板】動態樹）

示例代碼 
  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
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
#include <bits/stdc++.h>
#define ls(x) T[x][0]
#define rs(x) T[x][1]
#define ms(x) T[x][2]
#define maxn 1000005
using namespace std;

int read() {
  int s = 0;
  char a = getchar();
  while (!isdigit(a)) a = getchar();
  while (isdigit(a)) {
    s = (s << 1) + (s << 3);
    s += a ^ 48;
    a = getchar();
  }
  return s;
}

int T[maxn][3], s[maxn][2], tot, v[maxn], n, m, r[maxn], top, st[maxn], f[maxn];

int nnd() {
  if (top) {
    top--;
    return st[top + 1];
  } else
    return ++tot;
}

bool isr(int x) { return rs(f[x]) != x && ls(f[x]) != x; }

bool dir(int x) { return rs(f[x]) == x; }

void psu(int x, int ty) {
  if (ty) {
    s[x][1] = s[ls(x)][1] ^ s[rs(x)][1] ^ s[ms(x)][1];
    return;
  }
  s[x][0] = s[ls(x)][0] ^ v[x] ^ s[rs(x)][0];
  s[x][1] = s[ls(x)][1] ^ s[ms(x)][1] ^ s[rs(x)][1] ^ v[x];
}

void psr(int x) {
  if (!x) return;
  r[x] ^= 1;
  swap(ls(x), rs(x));
}

void psd(int x, int ty) {
  if (ty) return;
  if (r[x]) {
    psr(ls(x));
    psr(rs(x));
    r[x] = 0;
    return;
  }
}

void upd(int x, int ty) {
  if (!isr(x)) upd(f[x], ty);
  psd(x, ty);
}

void stf(int x, int fa, int ty) {
  if (x) f[x] = fa;
  T[fa][ty] = x;
  return;
}

void rtt(int x, int ty) {
  int y = f[x], z = f[y], d = dir(x), w = T[x][d ^ 1];
  if (z) T[z][ms(z) == y ? 2 : dir(y)] = x;
  T[x][d ^ 1] = y;
  T[y][d] = w;
  if (w) f[w] = y;
  f[y] = x;
  f[x] = z;
  psu(y, ty);
  psu(x, ty);
}

void spy(int x, int ty, int gl = 0) {
  upd(x, ty);
  for (int y; y = f[x], (!isr(x)) && y != gl; rtt(x, ty)) {
    if (f[y] != gl && (!isr(y))) rtt(dir(x) ^ dir(y) ? x : y, ty);
  }
}

void cle(int x) {
  ls(x) = ms(x) = rs(x) = s[x][0] = s[x][1] = r[x] = v[x] = 0;
  st[++top] = x;
}

void del(int x) {
  stf(ms(x), f[x], 1);
  if (ls(x)) {
    int p = ls(x);
    psd(p, 1);
    while (rs(p)) p = rs(p), psd(p, 1);
    spy(p, 1, x);
    stf(rs(x), p, 1);
    stf(p, f[x], 2);
    psu(p, 1);
    psu(f[x], 0);
  } else
    stf(rs(x), f[x], 2);
  cle(x);
}

void spl(int x) {
  spy(x, 1);
  int y = f[x];
  spy(y, 0);
  psd(x, 1);
  if (rs(y)) {
    swap(f[ms(x)], f[rs(y)]);
    swap(ms(x), rs(y));
    psu(x, 1);
  } else
    del(x);
  psu(rs(y), 0);
  psu(y, 0);
}

void acs(int x) {
  spy(x, 0);
  int ys = x;
  if (rs(x)) {
    int y = nnd();
    stf(ms(x), y, 0);
    stf(rs(x), y, 2);
    rs(x) = 0;
    stf(y, x, 2);
    psu(y, 1);
    psu(x, 0);
  }
  while (f[x]) {
    spl(f[x]);
    x = f[x];
  }
  spy(ys, 0);
}

int fdr(int x) {
  acs(x);
  psd(x, 0);
  while (ls(x)) x = ls(x), psd(x, 0);
  spy(x, 0);
  return x;
}

void mkr(int x) {
  acs(x);
  psr(x);
}

void epo(int x, int y) {
  mkr(x);
  acs(y);
}

void lnk(int x, int y) {
  if (fdr(x) == fdr(y)) return;
  acs(x);
  mkr(y);
  stf(y, x, 1);
  psu(x, 0);
  psu(y, 0);
}

void cu(int x, int y) {
  epo(x, y);
  if (ls(y) != x || rs(x)) return;
  f[x] = ls(y) = 0;
  psu(y, 0);
}

int main() {
  int i, j, op, U, V, n = read(), m = read();
  tot = n;
  for (i = 1; i <= n; i++) v[i] = read(), psu(i, 0);
  for (i = 1; i <= m; i++) {
    op = read();
    U = read();
    V = read();
    if (op == 0) {
      epo(U, V);
      cout << s[V][0] << '\n';
    }
    if (op == 1) lnk(U, V);
    if (op == 2) cu(U, V);
    if (op == 3) {
      acs(U);
      v[U] = V;
      psu(U, 0);
    }
  }
  return 0;
}

SATT 的時間複雜度證明

設在一棵 SATT（點數為 \(n\)）中，其當前狀態 \(x\) 的勢能函數為

\(\varphi(x)= \sum_{i=1}^{n} r(i)\)

其中 \(r(i) = \lceil \log_2 (\text{以 } i \text{ 為根的子樹大小} ) \rceil\)。

則 SATT 的 splay 的均攤複雜度顯然仍是 \(3n\log n + 1\)，即使 SATT 是一個三叉樹。

因此對於 SATT , 我們只要證得 Access 函數複雜度正確，就能證得 SATT 的時間複雜度。

我們逐步分析 Accese 的均攤複雜度。

我們先要將點 \(x\) 旋至 其所在 Compress Tree 的根，則這一步的均攤複雜度

\(a \leq 3\log n +1\)

接着我們要使點 \(x\) 無右兒子，則這一步的均攤複雜度

\(a = 1 + r'(\gamma)- 0 \leq \log n +1\)

如圖，為去掉點 \(x\) 的右兒子過程。

然後是 Local Splay，Splice 交替進行的過程，經過若干次 Splice，點 \(x\) 被旋至 SATT 的根。我們對其中一組 Local Splay，Splice 進行分析：

如圖，體現了對點 \(x\) 做一次 Splice 的過程，不包括最後左旋點 \(x\) 的部分。

為表達方便，設 \(r_x(i)\) 為點 \(i\) 在狀態 \(x\) 時的 \(r\) 值。

由圖，易知由狀態 1 到狀態 2 的操作（將點 \(x\) 的父親旋至其 Rake Tree 的根部的 Local Splay 操作）的均攤複雜度

\(a \leq 3(r_2(\gamma)- r_1(\gamma))+1\)

由圖，易知由狀態 2 到狀態 3 的操作（將點 \(x\) 的爺節點旋至其 Compress Tree 的根部的 Local Splay 操作）的均攤複雜度

\(a \leq 3(r_3(B)- r_2(B))+1\)

重點分析由狀態 3 到狀態 4 的操作（Splice )

\(a = r_4(\gamma) -r_3(\gamma) +1\)

不難發現 \(r_4(\gamma) \leq r_3(B)\)

故這一次操作的均攤複雜度為

\[a \leq r_3(B)- r_3(\gamma)+1 \leq 3(r_3(B)- r_3(\gamma))+1 \]

綜合上述過程，一次 Splice 的複雜度為

\(a\leq 3r_3(B)+3r_3(B)+3r_2(\gamma)-3r_3(\gamma)-3r_2(B)-3r_1(\gamma)+3\)

記下一次 Splice 的點 \(X\)（即狀態 4 中的點 \(B\)）的 \(r\) 值為 \(r'(X)\)，並注意到

\(r_3(\gamma),r_1(\gamma) \ge r_1(X)\)

\(r_3(B),r_2(\gamma) \leq r'(X)\text{ 且 } r_3(B)=r_2(B)\)

所以

\(a\leq 9(r'(X)-r(X))+3\)

除了上面這個複雜度以外，在 Splice 中可能還會有因 delete(x) 產生的額外均攤複雜度，記這一部分為 \(a' \leq 3\log n +1\)。

先不管 \(a'\) 部分，每次 Splice 的 \(r'(X)\) 等於下一次的 \(r(X)\)，且第一次 Splice 的 \(r(X)\) 等於我們一開始旋轉點 \(x\) 到其 Compress Tree 樹根時的 \(r(X)\)，則對於不計'delete(x)' 的 一次'access(x)' 複雜度，我們有：

\(a \leq 9(r'(x)-r(x))+ 3k + 1\)

其中 \(k\) 為 Splice 次數。

看樣子 \(a\) 會帶一個 \(3k+1\) 導致均攤複雜度無法分析，但我們有辦法來對付它，注意到 zig-zig\zig-zag 的旋轉可以這麼均攤

\[a \leq 3(r'(X)-r(X)) + q \leq 3(q-1)(r'(X)-r(X)) \]

如果我們能找到足夠多的 zig-zig，zig-zag 操作，我們就可以將這 \(3k+1\) 平攤到 這些 操作上去，從而消掉 這個 \(3k+1\)。

我們發現 Globel Splay 裏面就有這麼多的 zig-zig，zag-zig 來給我們使用，因為 Globel Splay 裏面點的個數一定大於 \(k\)，而從點 \(x\) 到 Globel Splay 根部路徑的點數一定不少於 \(k\)，也就是説一次 access(x) 中一定會至少有 \(\dfrac k2\) 個 zig-zag 操作，算上 Globel Splay 的均攤複雜度 \(a \leq 3\log n +1\)，一次 access(x) 不記 delete(x) 的均攤複雜度為

\(a \leq 9(r'(X)-r(X)) + 3k + 1 + 18(r''(X)-r'(X)) -S+1 +3 \log n +1,S \ge 3k\)

\(a\leq 18(r''(X)-r(X)) +2 +3\log n+1\)

\(a\leq 21(r''(X)-r(X)) +3\)

現在算上 \(a'\)，列出進行 \(m\) 次 access(x) 操作的總式子。

\(\sum_{i=1}^m a_i' + \sum_{i=1}^m a_i = \sum_{i=1}^m c_i + \varphi(x_n) -\varphi(x_0)\)

我們要求的是實際複雜度

\(\sum_{i=1}^m c_i = \sum_{i=1}^m a_i +\sum_{i=1}^m a_i' - \varphi(x_n) +\varphi(x_0)\)

\(\sum_{i=1}^m c_i \leq \sum_{i=1}^m a_i' + 21m\log n +n\log n +3m\)

注意到 delete(x) 操作的本質是刪掉一個 Rake Node，但我們在 \(m\) 次操作中最多隻會添加 \(m\) 個 Rake Node，由 Rake Node 的定義，我們初始時最多有 \(n\) 個 Rake Node，也就是説 我們總共只會做 \(m+n\) 次 delete(x) 操作，由 \(a' \leq 3\log n +1\) 可知

\(\sum_{i=1}^m c_i \leq 3(m+n)\log n + 21m\log n +n\log n +4m +n\)

所以我們就證明了 Access 的複雜度，而其他函數要麼基於 Access 要麼單次時間複雜度為常數，所以我們就證明了 SATT 的複雜度。

順便一提，如果像 LCT 一樣省略 Global Splay 的過程，改為在每次 Splice 時直接將要 Access 的點旋轉一下，這樣做時間複雜度也是對的（實測省略 Global Splay 的版本要快很多，能與 LCT 在 Luogu P3690 跑得不分上下）。

例題

CF1192B Dynamic Diameter

維護動態直徑，建出 SATT 後，我們只需要在 Pushup(x) 裏面維護每個點的答案，最後查詢根節點的答案（即整棵樹的直徑）就可以了。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
void pushup(int x, int op) {
  if (op == 0) {
    /*是compress node*/
    len[x] = len[ls(x)] + len[rs(x)];
    diam[x] = maxs[ls(x)][1] + maxs[rs(x)][0];
    diam[x] =
        max(diam[x], max(maxs[ls(x)][1], maxs[rs(x)][0]) + maxs[ms(x)][0]);
    diam[x] = max(diam[x], max(max(diam[ls(x)], diam[rs(x)]), diam[ms(x)]));
    maxs[x][0] =
        max(maxs[ls(x)][0], len[ls(x)] + max(maxs[ms(x)][0], maxs[rs(x)][0]));
    maxs[x][1] =
        max(maxs[rs(x)][1], len[rs(x)] + max(maxs[ms(x)][0], maxs[ls(x)][1]));
  } else {
    /*是rake node*/
    diam[x] = maxs[ls(x)][0] + maxs[rs(x)][0];
    diam[x] =
        max(diam[x], maxs[ms(x)][0] + max(maxs[ls(x)][0], maxs[rs(x)][0]));
    diam[x] = max(max(diam[x], diam[ms(x)]), max(diam[ls(x)], diam[rs(x)]));
    maxs[x][0] = max(maxs[ms(x)][0], max(maxs[ls(x)][0], maxs[rs(x)][0]));
  }
  return;
}

其中 \(diam\) 是當前點的答案（這個點代表的簇的直徑）。\(len\) 表示當前 Compress Node 所在簇路徑的長度，\(maxs_{0/1}\) 表示 compress node 到簇內點和端點的不選簇路徑兒子/不選父親的最大距離（如果是 Rake Node 則只存儲選取當前簇的上端點到簇內點和端點的最大距離 \(maxs_0\)）。每次查詢 SATT 根節點的 diam 即可，正確性顯然。

注意對 Pushrev(x) 做一些改動。

1
2
3
4
5
6
7
void pushrev(int x) {
  if (!x) return;
  r[x] ^= 1;
  swap(ls(x), rs(x));
  swap(maxs[x][0], maxs[x][1]);
  return;
}

[CSP-S2019] 樹的重心

假如我們能動態 \(O(\log n)\) 維護樹的重心，我們就做出這個題了。

SATT 支持動態 \(O(\log n)\) 維護樹的重心，做到這需要 非局部搜索（Non-local Search）。

對於一種樹上的性質，如果一個點/一條邊在整棵樹中有這種性質，且在所有包含它的子樹中都包含此種性質，我們就稱這個性質是 局部的（Local），否則稱它是 非局部的（Non-local）。局部信息一般可以通過 pushup(x) 來維護

例如，權值最小值是局部的，因為一個點/一條邊如果在整棵樹中權值最小，那麼在所有包含它的子樹中它也是權值最小的，而權值第二小顯然就是非局部的。

我們上文維護的 \(diam\) 也是局部信息。

回到正題，重心顯然是一個非局部信息，無法通過簡單的 pushup(x) 來維護。我們考慮在 SATT 上搜索：

我們的搜索從 SATT 的根節點，即根簇開始。注意到重心有很好的性質：假如有一條邊的一側點的個數大於等於另一側點的個數，那麼邊的這一側一定至少有一個重心（重心可能有 2 個）。

記 \(sum\) 表示某一個簇的點個數，\(maxs\) 為一棵 Rake Tree 的所有 Rake Node 中兒子的 \(sum\) 最大值。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
void pushup(int x, int op) {
  if (op == 0) {
    /*是 compress node*/
    sum[x] = sum[ls(x)] + sum[rs(x)] + sum[ms(x)] + 1;
  } else {
    /*是 rake node*/
    maxs[x] = max(maxs[ls(x)], max(maxs[rs(x)], sum[ms(x)]));
    sum[x] = sum[ls(x)] + sum[rs(x)] + sum[ms(x)];
  }
  return;
}

現在我們在根簇

如圖，為在進行 Non-local Search 時的 SATT 和對應的 原樹 \(T\)。

我們做如下比較：

  1. 比較 簇 \(compress(Y)\) 的 \(sum\) 值與 簇 \(compress(Z)\)、簇 \(A\) 和點 \(X\) 的並（我們暫稱為簇 \(α\)）的 \(sum\) 值。若 \(compress(Y)\) 的 \(sum\) 值大於等於後者，説明至少有一個重心在 \(compress(Y)\) 的子樹中，我們遞歸到 \(compress(Y)\) 搜索。（如果此處取等，點 \(X\) 也是一個重心，需要記錄）

  2. 比較 簇 \(compress(Z)\) 的 \(sum\) 值與 簇 \(compress(Y)\)、簇 \(A\) 和點 \(X\) 的並（我們暫稱為簇 \(β\)）的 \(sum\) 值。若 \(compress(Z)\) 的 \(sum\) 值大於等於後者，説明至少有一個重心在 \(compress(Z)\) 的子樹中，我們遞歸到 \(compress(Z)\) 搜索。（如果此處取等，點 \(X\) 也是一個重心，需要記錄）

  3. 比較 點 \(x\) 中兒子 Rake tree 之中 \(sum\) 最大的更小簇（見 3-2）的 \(sum\) 值與 簇 \(compress(Y)\)、簇 \(A\)、點 \(X\) 及其它更小簇的並（我們暫稱為簇 \(Y\)）的 \(sum\) 值，若 那個更小簇 的 \(sum\) 值大於等於後者，説明至少有一個重心在 那個更小簇的 子樹中，我們遞歸到它搜索。（如果此處取等，點 \(X\) 也是一個重心，需要記錄）

  4. 若以上比較都不遞歸，則點 \(X\) 一定是一個重心，記錄並退出。

第一步的搜索顯然正確，之後應該怎麼搜呢？

假如我們遞歸到 \(Y\)，則現在 \(Y\) 儲存信息的並不完整，因為 \(compress(Y)\) 裏面只存儲了它自己這個簇的信息，而我們要求的是整棵樹的重心。解決方法是，將之前簇的信息記錄下來，在點 \(Y\) 上比較計算時將上一個簇的信息與 點 \(Y\) 自己的信息合併處理。具體實現如下：

 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
void non_local_search(int x, int lv, int rv, int op) {
  /*lv 和 rv 都是搜索的上一個簇的信息*/

  if (!x) return;
  psd(x, 0);
  if (op == 0) {
    if (maxs[ms(x)] >=
        sum[ms(x)] - maxs[ms(x)] + sum[rs(x)] + sum[ls(x)] + lv + 1 + rv) {
      if (maxs[ms(x)] ==
          sum[ms(x)] - maxs[ms(x)] + sum[rs(x)] + sum[ls(x)] + lv + 1 + rv) {
        if (ans1)
          ans2 = x;
        else
          ans1 = x;
      }
      non_local_search(
          ms(x),
          sum[ms(x)] - maxs[ms(x)] + sum[rs(x)] + sum[ls(x)] + 1 + lv + rv, 0,
          1);
      return;
    }
    if (ss[rs(x)] + rv >= ss[ms(x)] + ss[ls(x)] + lv + 1) {
      if (ss[rs(x)] + rv == ss[ms(x)] + ss[ls(x)] + lv + 1) {
        if (ans1)
          ans2 = x;
        else
          ans1 = x;
      }
      non_local_search(rs(x), sum[ms(x)] + 1 + sum[ls(x)] + lv, rv, 0);
      return;
    }
    if (sum[ls(x)] + lv >= sum[ms(x)] + sum[rs(x)] + 1 + rv) {
      if (sum[ls(x)] + lv == sum[ms(x)] + sum[rs(x)] + 1 + rv) {
        if (ans1)
          ans2 = x;
        else
          ans1 = x;
      }
      non_local_search(ls(x), lv, rv + sum[ms(x)] + 1 + sum[rs(x)], 0);
      return;
    }
  } else {
    if (maxs[ls(x)] == maxs[x]) {
      non_local_search(ls(x), lv, rv, 1);
      return;
    }
    if (maxs[rs(x)] == maxs[x]) {
      non_local_search(rs(x), lv, rv, 1);
      return;
    }
    non_local_search(ms(x), lv, rv, 0);
    return;
  }
  if (ans1)
    ans2 = x;
  else
    ans1 = x;
  return;
}

完整代碼如下：

示例代碼 
  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
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
#include <bits/stdc++.h>
#define ls(x) T[x][0]
#define rs(x) T[x][1]
#define ms(x) T[x][2]
#define maxn 1000005
using namespace std;

int read() {
  int s = 0;
  char a = getchar();
  while (!isdigit(a)) a = getchar();
  while (isdigit(a)) {
    s = (s << 1) + (s << 3);
    s += a ^ 48;
    a = getchar();
  }
  return s;
}

int T[maxn][3], tot, n, m, r[maxn], top, st[maxn], f[maxn], maxs[maxn],
    ss[maxn];

int nnd() {
  if (top) {
    top--;
    return st[top + 1];
  } else
    return ++tot;
}

bool isr(int x) { return rs(f[x]) != x && ls(f[x]) != x; }

bool dir(int x) { return rs(f[x]) == x; }

void psr(int x) {
  if (!x) return;
  r[x] ^= 1;
  swap(ls(x), rs(x));
}

void psd(int x, int ty) {
  if (ty) return;
  if (r[x]) {
    psr(ls(x));
    psr(rs(x));
    r[x] = 0;
    return;
  }
}

void psu(int x, int op) {
  psd(x, op); /*不知道哪沒 psd*/
  if (op == 0) {
    ss[x] = ss[ls(x)] + ss[rs(x)] + ss[ms(x)] + 1;
  } else {
    maxs[x] = max(maxs[ls(x)], max(maxs[rs(x)], ss[ms(x)]));
    ss[x] = ss[ls(x)] + ss[rs(x)] + ss[ms(x)];
  }
  return;
}

void upd(int x, int ty) {
  if (!isr(x)) upd(f[x], ty);
  psd(x, ty);
}

void stf(int x, int fa, int ty) {
  if (x) f[x] = fa;
  T[fa][ty] = x;
  return;
}

void rtt(int x, int ty) {
  int y = f[x], z = f[y], d = dir(x), w = T[x][d ^ 1];
  if (z) T[z][ms(z) == y ? 2 : dir(y)] = x;
  T[x][d ^ 1] = y;
  T[y][d] = w;
  if (w) f[w] = y;
  f[y] = x;
  f[x] = z;
  psu(y, ty);
  psu(x, ty);
}

void spy(int x, int ty, int gl = 0) {
  upd(x, ty);
  for (int y; y = f[x], (!isr(x)) && y != gl; rtt(x, ty)) {
    if (f[y] != gl && (!isr(y))) rtt(dir(x) ^ dir(y) ? x : y, ty);
  }
}

void cle(int x) {
  ls(x) = ms(x) = rs(x) = ss[x] = r[x] = maxs[x] = f[x] = 0;
  st[++top] = x;
}

void del(int x) {
  stf(ms(x), f[x], 1);
  if (ls(x)) {
    int p = ls(x);
    psd(p, 1);
    while (rs(p)) p = rs(p), psd(p, 1);
    spy(p, 1, x);
    stf(rs(x), p, 1);
    stf(p, f[x], 2);
    psu(p, 1);
    psu(f[x], 0);
  } else
    stf(rs(x), f[x], 2);
  cle(x);
}

void spl(int x) {
  spy(x, 1);
  int y = f[x];
  spy(y, 0);
  psd(x, 1);
  if (rs(y)) {
    swap(f[ms(x)], f[rs(y)]);
    swap(ms(x), rs(y));
  } else
    del(x);
  psu(x, 1);
  psu(y, 0);
  rtt(rs(y), 0);
}

void acs(int x) {
  spy(x, 0);
  if (rs(x)) {
    int y = nnd();
    stf(ms(x), y, 0);
    stf(rs(x), y, 2);
    rs(x) = 0;
    stf(y, x, 2);
    psu(y, 1);
    psu(x, 0);
  }
  while (f[x]) spl(f[x]);
}

void mkr(int x) {
  acs(x);
  psr(x);
}

void epo(int x, int y) {
  mkr(x);
  acs(y);
}

void lnk(int x, int y) {
  acs(x);
  mkr(y);
  stf(y, x, 1);
  psu(x, 0);
}

void cu(int x, int y) {
  epo(x, y);
  f[x] = ls(y) = 0;
  psu(y, 0);
}

int ans1, ans2;

void non_local_search(int x, int lv, int rv, int op) {
  if (!x) return;
  psd(x, 0);
  if (op == 0) {
    if (maxs[ms(x)] >=
        ss[ms(x)] - maxs[ms(x)] + ss[rs(x)] + ss[ls(x)] + lv + 1 + rv) {
      if (maxs[ms(x)] ==
          ss[ms(x)] - maxs[ms(x)] + ss[rs(x)] + ss[ls(x)] + lv + 1 + rv) {
        if (ans1)
          ans2 = x;
        else
          ans1 = x;
      }
      non_local_search(
          ms(x), ss[ms(x)] - maxs[ms(x)] + ss[rs(x)] + ss[ls(x)] + 1 + lv + rv,
          0, 1);
      return;
    }
    if (ss[rs(x)] + rv >= ss[ms(x)] + ss[ls(x)] + lv + 1) {
      if (ss[rs(x)] + rv == ss[ms(x)] + ss[ls(x)] + lv + 1) {
        if (ans1)
          ans2 = x;
        else
          ans1 = x;
      }
      non_local_search(rs(x), ss[ms(x)] + 1 + ss[ls(x)] + lv, rv, 0);
      return;
    }
    if (ss[ls(x)] + lv >= ss[ms(x)] + ss[rs(x)] + 1 + rv) {
      if (ss[ls(x)] + lv == ss[ms(x)] + ss[rs(x)] + 1 + rv) {
        if (ans1)
          ans2 = x;
        else
          ans1 = x;
      }
      non_local_search(ls(x), lv, rv + ss[ms(x)] + 1 + ss[rs(x)], 0);
      return;
    }
  } else {
    if (maxs[ls(x)] == maxs[x]) {
      non_local_search(ls(x), lv, rv, 1);
      return;
    }
    if (maxs[rs(x)] == maxs[x]) {
      non_local_search(rs(x), lv, rv, 1);
      return;
    }
    non_local_search(ms(x), lv, rv, 0);
    return;
  }
  if (ans1)
    ans2 = x;
  else
    ans1 = x;
  return;
}

int qu[maxn], qv[maxn];

int main() {
  int i, TT = read(), n, I, U, V, x;
  long long ANS;
  for (I = 1; I <= TT; I++) {
    n = read();
    tot = n;
    ANS = 0;
    for (i = 1; i <= n; i++) ss[i] = 1;
    for (i = 1; i <= n - 1; i++) {
      qu[i] = U = read();
      qv[i] = V = read();
      lnk(U, V);
    }
    for (i = 1; i <= n - 1; i++) {
      cu(qu[i], qv[i]);
      ans1 = 0;
      ans2 = 0;
      non_local_search(qu[i], 0, 0, 0);
      ANS += ans1 + ans2;
      if (ans1) acs(ans1);
      if (ans2) acs(ans2);
      ans1 = 0;
      ans2 = 0;
      non_local_search(qv[i], 0, 0, 0);
      ANS += ans1 + ans2;
      if (ans1) acs(ans1);
      if (ans2) acs(ans2);
      lnk(qu[i], qv[i]);
    }
    cout << ANS << '\n';
    for (i = 1; i <= tot; i++)
      T[i][0] = T[i][1] = T[i][2] = ss[i] = r[i] = maxs[i] = f[i] = 0;
    tot = top = 0;
  }
  return 0;
}

Referrence

1.《Self-Adjusting Top Trees Robert》E. Tarjan，Renato F. Werneck。

2.negiizhao 的博客

3.zhengrunzhe 的 sone1 題解

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