Contest

A 消耗战（弱化版）

题意：只有一组询问的消耗战（B 题）。

这个题跟虚树没有半点关系。只是为 B 题做准备。

令 $f_u$ 为切断 $u$ 与其子树内所有关键点的最小代价（不需要考虑 $u$ 是关键点的情况）。答案为 $f_1$。

令 $mi_u$ 为 $1 \rightsquigarrow u$ 的最小边权（特别地，$mi_1 = \infty$）。一遍 DFS 预处理。

枚举 $u$ 的儿子 $v$：

• 若 $v$ 是关键点，则 $ans \gets ans + mi_v$。
• 若 $v$ 不是关键点，则 $ans \gets ans + f_v$。

还有一种可能：直接切 $mi_u$ 会更好。所以答案为 $\min(ans, mi_u)$。

时间复杂度 $\Theta(n)$。

B 消耗战

P2495 [SDOI2011] 消耗战

虚树是什么

给定树上的若干个关键点 $S$。往 $S$ 添加最少的点，使得 $S$ 对 LCA 运算封闭。

把新的点集叫做 $S’$。如果把 $S’$ 中的点按照原树的祖先后代关系连边，则可以形成一棵小树。这棵树被称为 $S$ 对应的虚树。

可以证明，$\lvert S \rvert \le \lvert S’ \rvert \le 2 \lvert S \rvert - 1$，即 $\lvert S’ \rvert = \Theta(\lvert S \rvert)$。

因此 $\sum \lvert S’ \rvert = \Theta(\sum \lvert S \rvert)$。在类似本题（限制关键点数目之和）的题目当中，保证了时间复杂度。

虚树的构造方法

虚树的构造方法有两种：单调栈和二次排序。其中单调栈用的似乎比较多。但是二次排序好写好背，所以下文介绍二次排序。

1. 预处理 $dfn$ 和 LCA。
2. 把 $S$ 按 $dfn$ 排序。
3. 枚举 $S$ 的每对相邻点对（$S_{i-1}$ 和 $S_i$），将 $\text{LCA}(S_{i-1}, S_i)$ 加入 $S’$。当然 $S$ 中的所有元素也要加入。
4. 把 $S’$ 按 $dfn$ 排序，并去重。此时 $S’$ 已经构造完毕。
5. 新建一个空图 $g$。枚举 $S’$ 的每对相邻点对（$S’{i-1}$ 和 $S’_i$），在 $g$ 上连边 $\text{LCA}(S’{i-1}, S’_i) \rightarrow S’_i$。虚树即为 $g$。

时间复杂度 $O(\lvert S \rvert \log \lvert S \rvert)$。

（备注：单调栈做法的好处在于，在点集已经排序的情况下，借助 $O(1)$ 查询的 LCA 可以做到 $\Theta(\lvert S \rvert)$ 构造虚树）

虚树的构造：正确性

Part 1：为什么这样构造的 $S’$ 对 LCA 封闭

• 引理 1 $\text{LCA}(S_{i-1}, S_{i+1}) \in {\text{LCA}(S_{i-1}, S_i), \text{LCA}(S_i, S_{i+1})}$。

证明：$\text{LCA}(S_{i-1}, S_i)$ 和 $\text{LCA}(S_i, S_{i+1})$ 是祖先后代关系，因为它们都是 $S_i$ 的祖先。那么他俩中 dep 小的那个就是 $\text{LCA}(S_{i-1}, S_{i+1})$。$\square$

• 引理 2 $\text{LCA}(S_i, S_j) \in {\text{LCA}(S_{k-1}, S_k) \mid i < k \le j}$。即 $\text{LCA}(S_i, S_j) \in S’$。

证明：用引理 1 数学归纳法即可。$\square$

• 引理 3 $\operatorname{LCA}\limits_{u \in T} u$ 为 $T$ 中 $dfn$ 最小和最大两个点的 LCA。

（这个好像是个常用结论，但是我不会）

证明：先证明这个点确实是所有点的 CA，然后证明它是 LCA。

设 $dfn$ 最小和最大的点为 $a,b$。

反证：设 $dfn_a < dfn_c < dfn_b$，且 $\text{LCA}(a,b)$ 不是 $c$ 的祖先。根据 $dfn$ 的性质，$c$ 不在 $\text{LCA}(a,b)$ 的子树内，因此 $dfn_c < dfn_a$ 或 $dfn_c > dfn_b$。矛盾。因此这个点确实是所有点的 CA。

如果这个点不是 LCA（即还有点比它更深），那么和它是 $\text{LCA}(a,b)$ 这一点矛盾。

$\square$

• 定理 $S’$ 对 $\text{LCA}$ 封闭。

证明：对于 $S’$ 中任意两个元素，他们的 LCA 必定是 $S$ 的一个子集的 LCA。通过引理 3 可以转化为 $S$ 的一个点对的 LCA，通过引理 2 可知必定在 $S’$ 中。$\square$

Part 2：为什么对 $S’$ 这样连边是正确的

根据 $S’$ 对 $\text{LCA}$ 的封闭性，$\text{LCA}(S’_{i-1}, S’_i)$ 是 $S’$ 中的元素，且确实是 $S_i’$ 的祖先。

因为 $S’{i-1}$ 与 $S’_i$ 按 $dfn$ 排序后是连续的，所以 $\text{LCA}(S’{i-1}, S’i) \rightsquigarrow S’_i$ 之间没别的 $S’$ 中的点了，确实就是 $\text{LCA}(S’{i-1}, S’_i)$ 应该连 $S’_i$。

虚树的构造：代码

T 即为上文的 $S’$。

vector<int> g[MAXN];
vector<int> build_virtual_tree(vector<int> S) {
    sort(S.begin(), S.end(), [&](int u, int v) {
        return dfn[u] < dfn[v];
    });
    vector<int> T;
    T.push_back(S[0]);
    for (int i = 1; i < S.size(); i++) {
        T.push_back(LCA(S[i-1], S[i]));
        T.push_back(S[i]);
    }
    sort(T.begin(), T.end(), [&](int u, int v) {
        return dfn[u] < dfn[v];
    });
    T.erase(unique(T.begin(), T.end()), T.end());
    for (int i = 1; i < T.size(); i++) {
        int u = LCA(T[i-1], T[i]), v = T[i];
        g[u].push_back(v);
    }
    return T;
}

虚树的小结论

$S = {S_0, S_1, \cdots, S_{m-1}}$（按 $dfn$ 排序）的虚树边权和为：

例题：P3320 [SDOI2015] 寻宝游戏 能看出 SDOI 挺喜欢虚树的

C 世界树

P3233 [HNOI2014] 世界树

TODO: Still Working on it!