虚树

在一些问题中，我们只关心关键点的信息，同时我们需要维护他们之间的树形结构，于是可以想到将它们和它们之间的 $\rm LCA$ 拉出来建一颗树，这棵树就被称作虚树。

有一个朴素的想法，就是对它们两两求 $\rm LCA$ ，并且对求出的 $\rm LCA$ 再求 $\rm LCA$ ，中途判重，最后按照祖先关系连边。

经过观察可以发现，我们只需要按照 $\rm dfs$ 虚从小到大的顺序枚举每个点，将相邻两点求 $\rm LCA$ 即可。具体来说，我们可以维护一个栈，这个栈中存的是当前点在虚树上的所有祖先。设当前栈顶为 $$v$$ ，对于新加入的结点 $$u$$ ，我们对它进行分类讨论：

若 $\rm LCA(u,v)=v$ ，那么直接将 $$u$$ 入栈。
若 $\rm LCA(u,v)$ 是栈中某个不为 $$v$$ 的点，则弹栈直到 $\rm LCA(u,v)$ ，每弹一个就向栈中比它深度多 $$1$$ 的结点连边，最后并把 $$u$$ 入栈。
若 $\rm LCA(u,v)$ 不在栈中，那么弹栈直到栈顶的 $\rm dfs$ 序小于 $\rm LCA(u,v)$ 的 $\rm dfs$ 序，每弹一个就向栈中比它深度多 $$1$$ 的结点连边，并把最后一个弹出的结点向 $\rm LCA(u,v)$ 连边，最后把 $\rm LCA(u,v)$ 和 $$u$$ 入栈。

不难发现这样一定是对的，并且设关键点数量为 $$k$$ ，则虚树内点数不超过 $$2k$$ 。

在一棵有 $$n$$ 个点的树上建立一颗有 $$k$$ 个点的虚树的时间复杂度为 $\Theta(k\log n)$ 。

经典例题

首先有一个暴力 $\rm DP$ ，设 $$dp_u$$ 表示将 $$u$$ 的子树内所有关键点与 $$u$$ 的联系断开所需要的最小代价。转移时枚举 $$u$$ 的所有子节点，分类讨论：

最终答案就是 $$dp_1$$ ，这个暴力的时间复杂度是 $\Theta(qn)$ 。

观察到 $\sum k\leqslant 5e5$ ，所以考虑对每次询问建虚树。

建虚树之前需要记 $$M_u$$ 表示从 $$1$$ 到 $$u$$ 的路径上最短的边权，因为只需要切掉最短的边权就可以让点 $$u$$ 与 $$1$$ 不连通，而切上面的边是更优的，所以可以用 $$M_u$$ 直接替换转移方程中的 $w_{u,v}$ 。

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

首先建虚树。

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

我们发现如果将虚树建出来，那么答案就是虚树上所有边权之和的两倍。

于是我们考虑动态维护虚树的边权之和。先把所有点的 $\rm dfs$ 序求出来，然后我们发现边权之和等于 $\rm dfs$ 序相邻两点的距离之和加上最左边和最右边两点的距离，于是我们可以使用 $\rm set$ 维护，树剖求 $\rm LCA$ 。

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