虛樹

引入

「SDOI2011」消耗戰

題目描述

在一場戰爭中，戰場由 \(n\) 個島嶼和 \(n-1\) 個橋樑組成，保證每兩個島嶼間有且僅有一條路徑可達。現在，我軍已經偵查到敵軍的總部在編號為 \(1\) 的島嶼，而且他們已經沒有足夠多的能源維繫戰鬥，我軍勝利在望。已知在其他 \(k\) 個島嶼上有豐富能源，為了防止敵軍獲取能源，我軍的任務是炸燬一些橋樑，使得敵軍不能到達任何能源豐富的島嶼。由於不同橋樑的材質和結構不同，所以炸燬不同的橋樑有不同的代價，我軍希望在滿足目標的同時使得總代價最小。

偵查部門還發現，敵軍有一台神秘機器。即使我軍切斷所有能源之後，他們也可以用那台機器。機器產生的效果不僅僅會修復所有我軍炸燬的橋樑，而且會重新隨機資源分佈（但可以保證的是，資源不會分佈到 \(1\) 號島嶼上）。不過偵查部門還發現了這台機器只能夠使用 \(m\) 次，所以我們只需要把每次任務完成即可。

輸入格式

第一行一個整數 \(n\)，代表島嶼數量。

接下來 \(n-1\) 行，每行三個整數 \(u,v,w\)，代表 \(u\) 號島嶼和 \(v\) 號島嶼由一條代價為 \(w\) 的橋樑直接相連，保證 \(1\le u,v\le n\) 且 \(1\le w\le 10^5\)。

第 \(n+1\) 行，一個整數 \(m\)，代表敵方機器能使用的次數。

接下來 \(m\) 行，每行一個整數 \(k_i\)，代表第 \(i\) 次後，有 \(k_i\) 個島嶼資源豐富，接下來 \(k\) 個整數 \(h_1,h_2,\cdots ,h_k\)，表示資源豐富島嶼的編號。

輸出格式

輸出有 \(m\) 行，分別代表每次任務的最小代價。

數據範圍

對於 \(100\%\) 的數據，\(2\le n\le 2.5\times 10^5,1\le m\le 5\times 10^5,\sum k_i\le 5\times 10^5,1\le k_i\le n-1\)。

過程

對於上面那題，我們不難發現——如果樹的點數很少，那麼我們可以直接跑 DP。

首先我們稱某次詢問中被選中的點為——「關鍵點」。

設 \(Dp(i)\) 表示——使 \(i\) 不與其子樹中任意一個關鍵點連通的 最小代價。

設 \(w(a,b)\) 表示 \(a\) 與 \(b\) 之間的邊的權值。

則枚舉 \(i\) 的兒子 \(v\)：

若 \(v\) 不是關鍵點：\(Dp(i)=Dp(i) + \min \{Dp(v),w(i,v)\}\)；
若 \(v\) 是關鍵點：\(Dp(i)=Dp(i) + w(i,v)\)。

很好，這樣我們得到了一份 \(O(nq)\) 的代碼。

聽起來很有意思。

解釋

我們不難發現——其實很多點是沒有用的。以下圖為例：

vtree-1

如果我們選取的關鍵點是：

vtree-2

圖中只有兩個紅色的點是 關鍵點，而別的點全都是「非關鍵點」。

對於這題來説，我們只需要保證紅色的點無法到達 \(1\) 號節點就行了。

通過肉眼觀察可以得出結論——\(1\) 號節點的右子樹（雖然實際上可能有多個子樹，但這裏只有兩個子樹，所以暫時這麼稱呼了）一個紅色節點都沒有，所以沒必要去 DP 它。

觀察題目給出的條件，紅色點（關鍵點）的總數是與 \(n\) 同階的，也就是説實際上一次詢問中紅色的點對於整棵樹來説是很稀疏的，所以如果我們能讓複雜度由紅色點的總數來決定就好了。

因此我們需要 濃縮信息，把一整顆大樹濃縮成一顆小樹。

虛樹 Virtual Tree

由此我們引出了 「虛樹」 這個概念。

我們先直觀地來看看虛樹的樣子。

下圖中，紅色結點是我們選擇的關鍵點。紅色和黑色結點都是虛樹中的點。黑色的邊是虛樹中的邊。

vtree-3

vtree-4

vtree-5

vtree-6

因為任意兩個關鍵點的 LCA 也是需要保存重要信息的，所以我們需要保存它們的 LCA，因此虛樹中不一定只有關鍵點。

不難發現虛樹中祖先後代的關係並不會改變。（就是不會出現原本 \(a\) 是 \(b\) 的祖先結果後面 \(a\) 變成 \(b\) 的後代了之類的鬼事）

但我們不可能 \(O(k^2)\) 暴力枚舉 LCA，所以我們不難想到——首先將關鍵點按 DFS 序排序，然後排完序以後相鄰的兩個關鍵點（相鄰指的是在排序後的序列中下標差值的絕對值等於 1）求一下 LCA，並把它加入虛樹。

我們的當務之急就是如何構造虛樹。

在提出方案之前，我們先確認一個事實——在虛樹裏，只要保證祖先後代的關係沒有改變，就可以隨意添加節點。

也就是，如果我們樂意，我們可以把原樹中所有的點都加入虛樹中，也不會導致 WA（雖然會導致 TLE）。

因此，我們為了方便，可以首先將 \(1\) 號節點加入虛樹中，並且並不會影響答案。

第一種構造過程：二次排序 + LCA 連邊

因為多個節點的 LCA 可能是同一個，所以我們不能多次將它加入虛樹。

非常直觀的一個方法是：

將關鍵點按 DFS 序排序；
遍歷一遍，任意兩個相鄰的關鍵點求一下 LCA，並且判重；
然後根據原樹中的祖先後代關係建樹。

具體實現上，在 關鍵點序列 上，枚舉 相鄰的兩個數，兩兩求得 \(lca\) 並且加入序列 \(A\) 中。

因為 DFS 序的性質，此時的序列 \(A\) 已經包含了 虛樹中的所有點，但是可能有重複。

所以我們把序列 \(A\) 按照 \(dfn\) 序 從小到大排序並去重。

最後，在序列 \(A\) 上，枚舉相鄰的兩個 點編號 \(x,y\)，求得它們的 \(lca\) 並且連接 \(lca,y\)，虛樹就構造完成了。

為什麼連接 \(lca\) 和 \(y\) 可以做到不重不漏呢？

證明

如果 \(x\) 是 \(y\) 的祖先，那麼 \(x\) 直接到 \(y\) 連邊。因為 dfn 序保證了 \(x\) 和 \(y\) 的 dfn 序是相鄰的，所以 \(x\) 到 \(y\) 的路徑上面沒有關鍵點。

如果 \(x\) 不是 \(y\) 的祖先，那麼就把 \(lca(x,y)\) 當作 \(y\) 的的祖先，根據上一種情況也可以證明 \(lca(x,y)\) 到 \(y\) 點的路徑上不會有關鍵點。

所以連接 \(lca\) 和 \(y\)，不會遺漏，也不會重複。

另外第一個點沒有被一個節點連接會不會有影響呢？因為第一個點一定是這棵樹的根，所以不會有影響，所以總邊數就是 \(m-1\) 條。

因為至少要兩個實點才能夠召喚出來一個虛點，再加上一個根節點，所以虛樹的點數就是實點數量的兩倍。

時間複雜度 \(O(m\log n)\)，其中 \(m\) 為關鍵點數，\(n\) 為總點數。

實現

int dfn[maxn];
bool valid[maxn];
int h[maxn], m, a[maxn], len;  // 存儲關鍵點

bool cmp(int x, int y) {
  return dfn[x] < dfn[y];  // 按照 dfn 序排序
}

void build_virtual_tree() {
  sort(h + 1, h + m + 1, cmp);  // 把關鍵點按照 dfn 序排序
  for (int i = 1; i < m; ++i) {
    a[++len] = h[i];
    a[++len] = lca(h[i], h[i + 1]);  // 插入 lca
  }
  a[++len] = h[m];
  sort(a + 1, a + len + 1, cmp);  // 把所有虛樹上的點按照 dfn 序排序
  len = unique(a + 1, a + len + 1) - a - 1;  // 去重
  for (int i = 1, lc; i < len; ++i) {
    lc = lca(a[i], a[i + 1]);
    conn(lc, a[i + 1]);  // 連邊，如有邊權 就是 distance(lc,a[i+1])
  }
}

其實這樣就足以構造一棵虛樹了。

第二種構造過程：使用單調棧

如何使用單調棧構造虛樹？

首先我們要明確一個目的——我們要用單調棧來維護一條虛樹上的鏈。

也就是一個棧裏相鄰的兩個節點在虛樹上也是相鄰的，而且棧是從底部到棧首單調遞增的（指的是棧中節點 DFS 序單調遞增），説白了就是某個節點的父親就是棧中它下面的那個節點。

首先我們在棧中添加節點 \(1\)。

然後接下來按照 DFS 序從小到大添加關鍵節點。

假如當前的節點與棧頂節點的 LCA 就是棧頂節點的話，則説明它們是在一條鏈上的。所以直接把當前節點入棧就行了。

vtree-7

假如當前節點與棧頂節點的 LCA 不是棧頂節點的話：

vtree-8

這時，當前單調棧維護的鏈是：

vtree-9

而我們需要把鏈變成：

vtree-10

那麼我們就把用虛線標出的結點彈棧即可，在彈棧前別忘了向它在虛樹中的父親連邊。

vtree-11

假如彈出以後發現棧首不是 LCA 的話要讓 LCA 入棧。

再把當前節點入棧就行了。

下面給出一個具體的例子。假設我們要對下面這棵樹的 4，6 和 7 號結點建立虛樹：

vtree-12

那麼步驟是這樣的：

將 3 個關鍵點 \(6,4,7\) 按照 DFS 序排序，得到序列 \([4,6,7]\)。
將 \(1\) 入棧。

vtree-13

我們用紅色的點代表在棧內的點，青色的點代表從棧中彈出的點。

取序列中第一個作為當前節點，也就是 \(4\)。再取棧頂元素，為 \(1\)。求 \(1\) 和 \(4\) 的 LCA：\(LCA(1,4)=1\)。
發現 \(LCA(1,4)=\) 棧頂元素，説明它們在虛樹的一條鏈上，所以直接把當前節點 \(4\) 入棧，當前棧為 \(4,1\)。

vtree-14

取序列第二個作為當前節點，為 \(6\)。再取棧頂元素，為 \(4\)。求 \(6\) 和 \(4\) 的 LCA：\(LCA(6,4)=1\)。
發現 \(LCA(6,4)\neq\) 棧頂元素，進入判斷階段。
判斷階段：發現棧頂節點 \(4\) 的 DFS 序是大於 \(LCA(6,4)\) 的，但是次大節點（棧頂節點下面的那個節點）\(1\) 的 DFS 序是等於 LCA 的（其實 DFS 序相等説明節點也相等），説明 LCA 已經入棧了，所以直接連接 \(1\to4\) 的邊，也就是 LCA 到棧頂元素的邊。並把 \(4\) 從棧中彈出。

vtree-15

結束了判斷階段，將 \(6\) 入棧，當前棧為 \(6,1\)。

vtree-16

取序列第三個作為當前節點，為 \(7\)。再取棧頂元素，為 \(6\)。求 \(7\) 和 \(6\) 的 LCA：\(LCA(7,6)=3\)。
發現 \(LCA(7,6)\neq\) 棧頂元素，進入判斷階段。
判斷階段：發現棧頂節點 \(6\) 的 DFS 序是大於 \(LCA(7,6)\) 的，但是次大節點（棧頂節點下面的那個節點）\(1\) 的 DFS 序是小於 LCA 的，説明 LCA 還沒有入過棧，所以直接連接 \(3\to6\) 的邊，也就是 LCA 到棧頂元素的邊。把 \(6\) 從棧中彈出，並且把 \(LCA(6,7)\) 入棧。
結束了判斷階段，將 \(7\) 入棧，當前棧為 \(1,3,7\)。

vtree-17

發現序列裏的 3 個節點已經全部加入過棧了，退出循環。
此時棧中還有 3 個節點：\(1,3,7\)，很明顯它們是一條鏈上的，所以直接鏈接：\(1\to3\) 和 \(3\to7\) 的邊。
虛樹就建完啦！

vtree-18

我們接下來將那些沒入過棧的點（非青色的點）刪掉，對應的虛樹長這個樣子：

vtree-19

其中有很多細節，比如用鄰接表存圖的方式存虛樹的話，需要清空鄰接表。但是直接清空整個鄰接表是很慢的，所以我們在 有一個從未入棧的元素入棧的時候清空該元素對應的鄰接表 即可。

實現

建立虛樹的 C++ 代碼大概長這樣：

代碼實現

bool cmp(const int x, const int y) { return id[x] < id[y]; }

void build() {
  sort(h + 1, h + k + 1, cmp);
  sta[top = 1] = 1, g.sz = 0, g.head[1] = -1;
  // 1 號節點入棧，清空 1 號節點對應的鄰接表，設置鄰接表邊數為 1
  for (int i = 1, l; i <= k; ++i)
    if (h[i] != 1) {
      // 如果 1 號節點是關鍵節點就不要重複添加
      l = lca(h[i], sta[top]);
      // 計算當前節點與棧頂節點的 LCA
      if (l != sta[top]) {
        // 如果 LCA 和棧頂元素不同，則説明當前節點不再當前棧所存的鏈上
        while (id[l] < id[sta[top - 1]])
          // 當次大節點的 Dfs 序大於 LCA 的 Dfs 序
          g.push(sta[top - 1], sta[top]), top--;
        // 把與當前節點所在的鏈不重合的鏈連接掉並且彈出
        if (id[l] > id[sta[top - 1]])
          // 如果 LCA 不等於次大節點（這裏的大於其實和不等於沒有區別）
          g.head[l] = -1, g.push(l, sta[top]), sta[top] = l;
        // 説明 LCA 是第一次入棧，清空其鄰接表，連邊後彈出棧頂元素，並將 LCA
        // 入棧
        else
          g.push(l, sta[top--]);
        // 説明 LCA 就是次大節點，直接彈出棧頂元素
      }
      g.head[h[i]] = -1, sta[++top] = h[i];
      // 當前節點必然是第一次入棧，清空鄰接表併入棧
    }
  for (int i = 1; i < top; ++i)
    g.push(sta[i], sta[i + 1]);  // 剩餘的最後一條鏈連接一下
  return;
}

於是我們就學會了虛樹的建立了！

對於消耗戰這題，直接在虛樹上跑最開始講的那個 DP 就行了，我們等於利用了虛樹排除了那些沒用的非關鍵節點！仍然考慮 \(i\) 的所有兒子 \(v\)：

若 \(v\) 不是關鍵點：\(Dp(i)=Dp(i) + \min \{Dp(v),w(i,v)\}\)
若 \(v\) 是關鍵點：\(Dp(i)=Dp(i) + w(i,v)\)

於是這題很簡單就過了。

虛樹

引入

過程

解釋

虛樹 Virtual Tree

第一種構造過程：二次排序 + LCA 連邊

實現

第二種構造過程：使用單調棧

實現

推薦習題