图论专题-学习笔记：虚树
目录
- 1. 前言
- 2. 详解
- 2.1 虚树定义
- 2.2 虚树构造
- 2.3 例题
- 3. 总结
- 4. 参考资料
1. 前言
虚树，主要是用于一类树上问题，这类问题通常是需要取一些关键点，然后要在这些关键点和其 LCA 上做一些奇怪的玩意。
关键前置知识：LCA。
2. 详解
2.1 虚树定义
首先我们需要知道虚树是什么：
现在给出一棵 \(n\) 个点的树，从中选取出 \(k\) 个关键点，这些关键点以及其两两的 LCA 构成了对于这些关键点而言的虚树，特别注意如果取出来的树不连通的话我们还需要一个根节点来连通。
比如说对于下面这棵树：
如果取 \(7,8,10,11,14\) 这五个点作为关键点，那么对于这五个点的虚树是这样的：
其中加粗的节点表示我们需要的 LCA，剩下的就是 5 个关键点。
我们发现构建虚树之后，一些无用 / 干扰节点都被我们删去了，这样对开头所述的问题有不错的解决效果。
2.2 虚树构造
接下来详细讲一下虚树的构造。
一般的虚树构造是使用单调栈来构造的，也是相对比较大众的构造方法（包括日报），这里简要阐述一下：
- 首先将所有关键点按照 DFS 序升序排序，如果关键点中没有做 LCA 时指定的根节点我们需要人为加入这个点。
- 然后一个一个插入，采用一个对深度单调递增的单调栈维护，每次弹栈的时候将栈内第二个点与栈顶连边，然后弹出。
- 设当前插入节点为 \(x\)，栈顶节点为 \(y\)，其 LCA 为 \(z\)，那么当弹栈弹到深度小于 \(z\) 的时候就可以停止了。
- 这里需要注意，如果当前栈顶不是 \(z\) 的话我们需要将 \(z\) 丢进栈内，同时如果栈顶深度小于 \(z\) 我们也要从栈顶向 \(z\) 连边。
- 最后加入这个点即可。
- 上述所有关键点加入完毕之后，一起弹栈，重复执行 2 步骤。
上述方法更加具体的步骤与正确性证明见参考资料 - 1 中的日报。
这边我学的是另外一种更加简洁的方法：
- 首先将所有关键点按照 DFS 序升序排序，设该关键点序列为 \(\{a_n\}\)。
- 对于所有 \(i \in [2,n]\)，如果 \(a_i\) 和 \(a_{i-1}\) 的 LCA 不是他们中的任意一个，意味着这个点也是要加入序列里面的，丢到 \(\{a_n\}\) 的末尾，这样我们得到了一个新的序列 \(\{a_n\}\)。
- 对该序列去重之后重新按照 DFS 序升序排序。
- 最后对于所有 \(i \in [2,n]\)，\(a_i\) 的父亲就是 \(a_i\) 和 \(a_{i-1}\) 的 LCA，根节点就是 \(a_1\)。
这个方法看起来很简单但是很迷，我并没有找到证明过程，于是自己口胡了一个，有误请指出：
- 首先根据 2 操作，我们已经将所有虚树上有的节点丢到 \(\{a_n\}\) 里面了。
- 由 LCA 的性质，如果设 \(z\) 是 \(a_i,a_{i-1}\) 的 LCA，那么 \(dfn_z \leq \min \{dfn_{a_i},dfn_{a_{i-1}}\}\)，3 操作之后这个式子简化成了 \(dfn_z \leq dfn_{a_{i-1}} < dfn_{a_i}\)（后面这个小于号是因为我们去重了），且 \(z\) 是一定在 \(\{a_n\}\) 里面的。
- 于是我们就可以证明，对于任意 \(a_i \mid i \geq 2\)，其虚树上的父亲也在序列里面，且在 \(a_i\) 的前面而且一定不会与 \(a_i\) 相等。
现在分析两个方法的时间复杂度：
- 由于每个人的求 LCA 的方式并不一样，这里我采用的是 \(O(n \log n) - O(\log n)\) 的倍增求 LCA 的方法，下面的涉及到 LCA 的复杂度都以该复杂度为准。
- 注意我喜欢先带常数分析复杂度（虽然是错的），分析完之后再按照复杂度的定义去掉常数。
设 \(k\) 是关键点个数。
方法 1 的时间复杂度：
- 预处理 LCA 复杂度 \(O(n \log n)\)。
- 升序排序复杂度 \(O(k \log k)\)。
- 在插入一个点的时候求 LCA 复杂度 \(O(\log n)\)，单调栈复杂度会单独计算。
- 插入所有点求 LCA 复杂度是 \(O(k \log n)\)，单调栈复杂度单独是 \(O(2(k+p))\)（所有点进出栈各一次），其中 \(p\) 表示这些点的 LCA 的数量。为分析方便，取最坏情况（该情况取不到，但是可以拿来分析复杂度）\(p=k\)，则单调栈复杂度是 \(O(4k)\)。
- 因此该方法总复杂度是 \(O(n \log n + k (4 + \log k))\)，不记预处理复杂度情况下忽略常数后可化简为 \(O(k \log k)\)。
方法 2 的时间复杂度：
- 预处理 LCA 复杂度 \(O(n \log n)\)。
- 升序排序复杂度 \(O(k \log k)\)。
- 对于加入 LCA 的操作而言，这块的复杂度也是 \(O(k \log k)\)。
- 去重 + 重新排序复杂度是 \(O(2k \log (2k) + (k + p) \log (k + p))\)，\(p\) 跟方法一定义相同，最坏情况依然是 \(O(4k \log (2k))\)。
- 然后建树过程复杂度是 \(O(2k \log 2k)\)。
- 因此该方法总复杂度是 \(O(n \log n + k (\log k + 6 \log (2k))\)，不记预处理复杂度情况下忽略常数后可化简为 \(O(k \log k)\)。
发现两种方法的复杂度化简后是一样的，未化简前复杂度是方法 2 高一点，但是在 OI 中方法 2 比方法 1 写的更快，而且不会被卡（真的会有人卡你这玩意吗？），不容易写错（我是这么认为的），性价比较高。
需要注意的是，方法一建虚树的时候为了方便，通常会将 1 号点放入关键点序列中，但是方法二并不会，因此有些题采用方法 2 的时候需要特别注意根节点是否为 1。
2.3 例题
例题：CF613D Kingdom and its Cities
首先发现题目需要判无解情况，无解情况只可能是存在两个关键点之间有连边。
然后考虑有解情况，发现如果要断开两个关键点一定是 LCA 处最优，所以我们需要的点只有关键点和 LCA。
于是我们可以考虑先建虚树，然后这道题就变成了一道简单的树形 DP（或者不是）。
考虑对于所有的关键点，先将其 Size 设为 1，然后对一个点，这个点的贡献按 Size 分类：
- 如果 Size 为 0，考虑统计其直接儿子当中有几个点 Size 为 1（设为 \(x\)），如果 \(x=1\)，那么直接将这个点 Size 置为 1 即可，如果大于 1，那么就断掉这个点，贡献为 1。
- 如果 Size 为 1，考虑统计其直接儿子中有几个 Size 为 1，有几个答案就加几，因为我们随便断掉一个点即可。
这个地方存在直接儿子有 Size 为 1 是因为有些儿子的 Size 是其子树内传上来的，由于我们已经判了无解情况，所以这个做法是对的。
其实这道题去掉建虚树好像就没什么了（）
以后我代码还是不放 GitHub 上了，因为这玩意实在是太卡了，但是还是会同步更新的。
GitHub：CodeBase-of-Plozia
Code：
/*
========= Plozia =========
Author:Plozia
Problem:CF613D Kingdom and its Cities
Date:2021/11/29
========= Plozia =========
*/
#include
typedef long long LL;
const int MAXN = 1e5 + 5;
int n, q, sta[MAXN], Top, ask[MAXN << 1], fa[MAXN][21], dep[MAXN], Size[MAXN], dfn[MAXN], ans;
struct Graph
{
int cnt_Edge = 1, Head[MAXN];
struct node { int to, Next; } Edge[MAXN << 1];
void add_Edge(int x, int y) { ++cnt_Edge; Edge[cnt_Edge] = (node){y, Head[x]}; Head[x] = cnt_Edge; }
}og, ng;
int Read()
{
int sum = 0, fh = 1; char ch = getchar();
for (; ch < '0' || ch > '9'; ch = getchar()) fh -= (ch == '-') << 1;
for (; ch >= '0' && ch <= '9'; ch = getchar()) sum = sum * 10 + (ch ^ 48);
return sum * fh;
}
int Max(int fir, int sec) { return (fir > sec) ? fir : sec; }
int Min(int fir, int sec) { return (fir < sec) ? fir : sec; }
bool cmp(const int &fir, const int &sec) { return dfn[fir] < dfn[sec]; }
void dfs(int now, int father)
{
fa[now][0] = father; dep[now] = dep[father] + 1; ++dfn[0]; dfn[now] = dfn[0];
for (int i = og.Head[now]; i; i = og.Edge[i].Next)
{
int u = og.Edge[i].to;
if (u == father) continue ;
dfs(u, now);
}
}
void init()
{
for (int j = 1; j <= 20; ++j)
for (int i = 1; i <= n; ++i)
fa[i][j] = fa[fa[i][j - 1]][j - 1];
}
int LCA(int x, int y)
{
if (dep[x] < dep[y]) std::swap(x, y);
for (int i = 20; i >= 0; --i)
if (dep[fa[x][i]] >= dep[y]) x = fa[x][i];
if (x == y) return x;
for (int i = 20; i >= 0; --i)
if (fa[x][i] != fa[y][i]) x = fa[x][i], y = fa[y][i];
return fa[x][0];
}
void Calc(int now)
{
if (Size[now])
{
for (int i = ng.Head[now]; i; i = ng.Edge[i].Next)
{
int u = ng.Edge[i].to; Calc(u);
if (Size[u]) { Size[u] = 0; ++ans;}
}
}
else
{
int sum = 0;
for (int i = ng.Head[now]; i; i = ng.Edge[i].Next)
{
int u = ng.Edge[i].to; Calc(u);
if (Size[u]) ++sum; Size[u] = 0;
}
if (sum == 1) Size[now] = 1;
else if (sum > 1) ++ans;
}
ng.Head[now] = 0;
}
int main()
{
n = Read();
for (int i = 1; i < n; ++i)
{
int x = Read(), y = Read();
og.add_Edge(x, y); og.add_Edge(y, x);
}
dfs(1, 1); init(); q = Read();
for (int i = 1; i <= q; ++i)
{
int k = Read(); ans = 0;
for (int j = 1; j <= k; ++j) Size[ask[j] = Read()] = 1;
bool flag = 0;
for (int j = 1; j <= k; ++j)
if (ask[j] != 1 && Size[fa[ask[j]][0]]) flag = 1;
if (flag)
{
for (int j = 1; j <= k; ++j) Size[ask[j]] = 0;
puts("-1"); continue ;
}
//开始建虚树
std::sort(ask + 1, ask + k + 1, cmp); ask[0] = k;
for (int j = 2; j <= k; ++j)
{
int l = LCA(ask[j - 1], ask[j]);
if (l != ask[j - 1] && l != ask[j]) ask[++ask[0]] = l;
}
k = ask[0]; std::sort(ask + 1, ask + k + 1);
k = std::unique(ask + 1, ask + k + 1) - (ask + 1);
std::sort(ask + 1, ask + k + 1, cmp);
for (int j = 2; j <= k; ++j)
{
int l = LCA(ask[j - 1], ask[j]);
ng.add_Edge(l, ask[j]);
}
//建完了
Calc(ask[1]); ng.cnt_Edge = 1; printf("%d\n", ans);
for (int j = 1; j <= k; ++j) Size[ask[j]] = 0;
}
return 0;
}
3. 总结
虚树实际上就是将一棵树剔除不关键点的算法，本质上剥离出来后就是在一棵树上做一些算法。
其实我认为平常的树上问题就是一种所有点都是关键点的虚树吧。
4. 参考资料
- 【洛谷日报#185】浅谈虚树 - SSerxhs 的博客
- CF613D Kingdom and its Cities 洛谷全部题解