我要看的是纳西达，搞一堆正太是什么意思！！！

定义

一棵只包含关键点和任意两个关键点的 $\text{lca}$ 的树。

构造过程

把关键点按照 dfn 序排序，把相邻的两个点的 lca 和关键点又丢到一个集合里，再按照 dfn 排序。

那么把相邻两个点的的 $\text{lca}$ 与后面的点连边，最后得到的就是虚树了。

SDOI2011 消耗战

建出虚树，令边权为原图上经过所有边的最小值。

设 $f_i$ 表示以 $i$ 为根的子树中所有的关键点都不与 $i$ 相连的最小花费。

那么显然有：

$f_i=\left\{\begin{matrix}\min(f_{son},Val(x\to i)) & op_x=0 \\ Val(x\to i) & \text{Otherwise.}\end{matrix}\right.$

CF613D Kingdom and its Cities

建出虚树，设 $f_i$ 表示以 $i$ 为根的子树不联通的最小代价，$ct_i$ 表示这时以 $i$ 为根剩余关键点的个数。

那么显然：

$f_i=\sum f_{son}+\left\{\begin{matrix}0 & (\sum ct_{son})\le 1\wedge op_x=0\\1 & (\sum ct_{son}) >1\wedge op_x=0\\ct_x & \text{Otherwise.}\end{matrix}\right.$

GZOI2017 共享单车

题目难度不够，题目乱描述来凑。

给定原点 $K$，建出最短路树，如果有多个最短路那么选择最后一个点的全驱最小的那一个。

对于操作 $0$，把输入的点全部颜色反转（初始时全部白色）。

对于操作 $1$，把 $K$ 和输入的点建出虚树，然后进行《消耗战》。