关于虚树
对于一些在树上进行某些询问的查询，且每个询问实际用到的点并不多的时候，可以考虑建虚树来查询。
虚树的建立复杂度是 \(O(m \log n)\) 的，\(m\) 是虚树节点数量，\(n\) 是原树节点数量。也有方法可以做到 \(O(m \log m)\)。
例题
题目链接。
分析
注意到范围：\(\sum k_i \le 5 \times 10^5\)，所以考虑虚树。
对于暴力做法，定义状态函数 \(f_i\) 表示使 \(i\) 不和其为根的子树中任意一个关键点联通的最小代价。不难有转移方程：
\[f_u = \left\{\begin{matrix} f_u + \min (f_v ,w_{u,v}) & [v~不是关键点]\\ f_u + f_v & [v~是关键点] \end{matrix}\right. \]可以发现，我们实际上有用的点只有所有的关键点，任意两个关键点的 \(\operatorname{LCA}\) 和节点 \(1\)。如果我们建立一棵只有这些点的树，那么上面的暴力就可以用复杂度为 \(O(m)\) 的暴力实现。由于 \(m \le 2 \times k\)，显然是可以过的。
建立虚树
这里介绍二次排序的做法。
先将所有的关键点按照 DFS 序排序。那么任意两个关键点的 \(\operatorname{LCA}\) 就相当于排序后相邻的两个关键点的 \(\operatorname{LCA}\)。
证明：
咕......
将得到的点再次排序去重后，就得到了虚树的所有节点。现在就只需要根据原树上节点祖孙关系给它们建边了。枚举相邻两个节点，然后将 \(a_i\) 成为 \(\operatorname{LCA}(a_{i-1},a_i)\) 在虚树上的儿子，虚树就建完了。
证明：
如果 \(x\) 是 \(y\) 的祖先，那么 \(x\) 直接到 \(y\) 连边。因为 dfn 序保证了 \(x\) 和 \(y\) 的 dfn 序是相邻的，所以 \(x\) 到 \(y\) 的路径上面没有关键点。
如果 \(x\) 不是 \(y\) 的祖先，那么就把 \(\operatorname{LCA}(x,y)\) 当作 \(y\) 的的祖先，根据上一种情况也可以证明 \(\operatorname{LCA}(x,y)\) 到 \(y\) 点的路径上不会有关键点。
所以连接 \(\operatorname{LCA}\) 和 \(y\)，不会遗漏，也不会重复。
复杂度 \(O(m \log n)\)，最后跑一遍暴力就行了。
练习题
CF613D
对于 DP，定义状态函数 \(f_i\) 表示使以 \(i\) 为根的子树中任意两个关键节点都不联通的最小代价，\(g_i\) 表示以 \(i\) 为根的子树中是否剩下 \(1\) 个与 \(i\) 联通的点关键点。则有转移方程：
\[f_u = \sum f_v + (\sum g_v)[u ~ 是关键点] + 1[u ~ 不是关键点 \land (\sum g_v)>1] \]\[g_u = \left\{\begin{matrix} 1 & [v~是关键点 \lor(v ~ 不是关键点 \land (\sum g_v) >1)]\\ \sum g_v & [v ~ 不是关键点 \land (\sum g_v) \le 1)] \end{matrix}\right. \]答案为 \(f_1\)。对于无解的情况，就是相邻两个节点都是关键点，这个在读入的时候判断即可。
世界树
咕......
大工程
问题 \(1\)
定义 \(cnt_i\) 表示 \(i\) 为根子树中关键点的数量（不包含 \(i\)），\(sum_i\) 表示 \(i\) 为根子树所有关键点到 \(i\) 的距离。
则从 \(i\) 的 \(x\) 子树中选一个关键点，从 \(i\) 的另一个子树中选一个关键点的路径长度和就是 \((cnt_i - (cnt_x+1) ) \times (w_{i,x} \times (cnt_j+1) +sum_j)\)。
从 \(i\) 的 \(x\) 子树中选一个关键点到 \(i\)（\(i\) 是关键点）的路径长度和为 \(sum_i\)。
\(sum_i =\sum sum_x +w_{i,x} \times (cnt_x+1)\)。
问题 \(2,3\)
存下 \(i\) 为根子树中关键点到 \(i\) 的最短和最长路。同问题 \(1\) 的 \(2\) 种情况分讨即可。