虚树
题单介绍
# 虚树
## 前置芝士
[虚树1](https://www.cnblogs.com/zzqsblog/p/5560645.html)
[虚树2](https://oi-wiki.org/graph/virtual-tree/)
所谓虚树吧，其实就是把一些有用的点给拿出来，然后通过最少的lca把这些节点给穿到一起，在新的树上做树形dp。
感觉这个专题的题目都挺好的，所以就基本上都写了篇题解。。
## 例题略解
### [P3233 [HNOI2014]世界树](https://www.luogu.com.cn/problem/P3233)
[**题解**](https://www.luogu.com.cn/blog/Varuxn/solution-p3233)
### [P2495 [SDOI2011]消耗战](https://www.luogu.com.cn/problem/P2495)
半个板子题，大致思路就是先构建虚树，然后在虚树上做树形dp。
先求出每个点到根节点路径上的最小值，然后在dfs时，区分有供给的岛和没有供给的岛，分不同情况转移就好了。
[$code$](https://www.luogu.com.cn/paste/0e27ynwq)
### [P3320 [SDOI2015]寻宝游戏](https://www.luogu.com.cn/problem/P3320)
有一点虚树的思想，但是实现上好像没有用到常规虚树的板子。
不难发现，最后的答案就是各个关键点之间的路径的权值乘2。
然后可以化成：
$$dis(s_n,s_1)+\sum\limits_{i=1}^{n-1}dis(s_i,s_{i+1})$$
然后不难发现插入点为x，并且他的dfs序两边是y和z的时候i，贡献就是$dis(x,y)+dis(x,z)-dis(y,z)$
然后用STL的set维护就好了（当然平衡树，树状数组等也可以）。
* 注意：set容器里元素不能`it+1`或者`it-1`，应该是`it++`或者`it--`这一类的。。。
[$code$](https://www.luogu.com.cn/paste/pw6xsvzl)
### [P4103 [HEOI2014]大工程](https://www.luogu.com.cn/problem/P4103)
[题解](https://www.cnblogs.com/Varuxn/p/14961038.html)
### [P5327 [ZJOI2019]语言](https://www.luogu.com.cn/problem/P5327)
[题解](https://www.cnblogs.com/Varuxn/p/14980663.html)