# 虛樹與樹鏈剖分
---
## 虛樹
----
例題：
https://www.luogu.com.cn/problem/P2495
https://atcoder.jp/contests/abc359/tasks/abc359_g
----
- 維護樹上性質時，如果會進行計算的點數不多（以下稱為關鍵點），可以幫那些點建一棵虛樹，把事情改成在虛樹上面做
- 虛樹的結構為包含所有關鍵點及關鍵點中任兩點的 $LCA$ 且滿足原樹祖孫關係的最小子樹
- 對於一棵大小為 $n$ 的樹，若其中含有 $k$ 個關鍵點，可以在 $\mathcal{O}(k \log n)$ 的時間內建好一顆 $\mathcal{O}(k)$ 大小的虛樹
----
建構方法如下：
```cpp
Graph constructVirtualTree(Graph &originalTree, vector<int> &keyPoints) {
// Sort the key points by DFS order
sort(keyPoints.begin(), keyPoints.end(), [&](int u, int v) {
return originalTree.dfsOrder(u) < originalTree.dfsOrder(v);
});
// Add the LCA of adjacent key points
int k = keyPoints.size();
keyPoints.reserve(2 * k - 1);
for (int i = 0; i < k - 1; i++)
keyPoints.push_back(originalTree.getLCA(keyPoints[i], keyPoints[i + 1]));
// Sort again and remove duplicates
sort(keyPoints.begin(), keyPoints.end(), [&](int u, int v) {
return originalTree.dfsOrder(u) < originalTree.dfsOrder(v);
});
k = unique(keyPoints.begin(), keyPoints.end()) - keyPoints.begin();
keyPoints.resize(k);
// Initialize the virtual tree
Graph virtualTree;
virtualTree.initializeSize(originalTree.size());
// Connect LCA(u, v) to v for each adjacent key points u and v
for (int i = 0; i < k - 1; i++)
virtualTree.addEdge(originalTree.getLCA(keyPoints[i], keyPoints[i + 1]), keyPoints[i + 1]);
return virtualTree;
}
```
----
證明如下：
- 分為「包含任兩點 $LCA$」「滿足祖孫關係」「為最小子樹」三個步驟
- 取 $DFS$ 序相鄰兩點的 $LCA$ 可以涵蓋任意兩點的 $LCA$，因為對於任兩個關鍵點，其 $LCA$ 至少有兩個以子節點為根的子樹包含關鍵點，取到橫跨這些子樹的相鄰關鍵點時就會算到這個 $LCA$
----
- 建邊時 $LCA(u, v)$ 一定在虛樹中（已加入所有點的 $LCA$）且在原樹中一定是 $v$ 的祖先，故滿足原樹中的祖孫關係
- $LCA(u, v)$ 至 $v$ 的鏈中必定沒有其他關鍵點，否則其與 $u$ 的 $DFS$ 序距離較 $v$ 小，與 $u, v$ 為相鄰兩點矛盾，而此方法建出 $k - 1$ 條邊，為最小子樹
---
## 樹鏈剖分
----
例題：
https://www.luogu.com.cn/problem/P3379
https://www.luogu.com.cn/problem/P3384
----
- 樹鏈剖分的思想是將樹劃分為一些鏈，然後以線性的資料結構維護樹上的性質
- 定義點的重子節點為子樹最大的子節點，連接重子節點的邊稱為重邊，其他均稱為輕邊
- 樹鏈剖分的結構是將所有連續的重邊當成鏈，稱為重鏈，重鏈間以輕邊相連（包含落單的節點）
----
這樣可以有一些好性質：（$n$ 為樹的大小）
- 樹上任意路徑最多包含 $\mathcal{O}(\log n)$ 條重鏈
- 同一條重鏈上的點 $DFS$ 序連續
----
建構方法如下：
```cpp
struct Decomposition {
vector<vector<int> > tree;
vector<int> depth, father, size, heavy, idx, top;
int cur;
Decomposition(const vector<vector<int> > &tree, int size, int root)
: tree(tree), depth(size, -1), father(size, -1), size(size, 1), heavy(size, -1), idx(size), top(size) {
depth[root] = cur = 0;
build(root);
decompose(root, root);
}
void build(int u) {
for (int v: tree[u])
if (depth[v] == -1) {
depth[v] = depth[u] + 1, father[v] = u;
size[u] += (build(v), size[v]);
if (heavy[u] == -1 || size[v] > size[heavy[u]])
heavy[u] = v;
}
}
void decompose(int u, int t) {
idx[u] = cur++, top[u] = t;
if (heavy[u] == -1) return;
decompose(heavy[u], t);
for (int v: tree[u])
if (v != father[u] && v != heavy[u])
decompose(v, v);
}
int lca(int u, int v) {
while (top[u] != top[v])
depth[top[u]] > depth[top[v]]
? u = father[top[u]]
: v = father[top[v]];
return depth[u] < depth[v] ? u : v;
}
};
```
----
證明如下：
- 由定義可知，每向下經過一條輕邊所在的子樹大小至少會除以二，把任意路徑根據最高點分為兩半，每半向下走最多經過 $\mathcal{O}(\log n)$ 條輕邊，即最多包含 $\mathcal{O}(\log n)$ 條重鏈
- 第二次 $DFS$ 的時候先走重邊可以保證重邊上下端的 $DFS$ 序差一，故重鏈上 $DFS$ 序連續
{"title":"虛樹與樹鏈剖分","description":"可愛的虛樹與樹鏈剖分:D","contributors":"[{\"id\":\"40538268-17e3-4dd2-91c0-0d5f3e29922e\",\"add\":30458,\"del\":24543}]"}