摘要：各种图论相关的内容。

线段树优化建边

除了板子似乎没有其它什么题了，其实更多的是一种思想。板子题link，线段树优化建图是拆边的一种方法，当一个点需要向一个区间内所有节点连边时，我们需要做的就是先把这些节点按照建线段树的方式来分组，然后对于一个区间找到对应的 $\log n$ 级别的组对应的节点，向这些节点连边即可。细节有一些，比如要建两棵线段树，分别对应区间连入和区间连出；对应的叶子节点要建双向边等。

最小斯坦纳树&最小树形图

首先是最小树形图，意思是有一张带权有向图，钦定一个点，希望保留一些边使得这个点可以到达所有点，最小化边权和。思路上就是说贪心地选择每个点权最小的入边并加入集合中，这样形成的图兴许是最优的（和某B开头的最小生成树算法异曲同工）。但是有可能会出现环，此时就需要缩点，然后一直做下去即可。就这么个思想，还没看到哪道题里有应用，就先放到这里吧，板子有些细节但还是比较好背的。拓展：若没有钦定根，建立虚拟点并向每个点连极大边即可。

然后是最小斯坦因树。给定一张图，有很少的特殊点，希望保留尽量少的边使得这些点联通。板子的链接。由于特殊点数量很少，考虑状压，用 $f_{x,s}$ 代表 $x$ 为根的子树包含集合 $s$ 中的边的最小代价。有两种转移，一种是 $f_{x,s}=\min(f_{x,t}+f_{x,s-t})$，另一种是考虑当前状态从另一个点那里转移过来，即 $f_{x,s}=f_{y,s}+\text{dis}(x,y)$，这一部分用 SPFA 来跑就可以了。复杂度是 $O(n3^k)$，毕竟有个枚举子集在那里。

板子题还有 游览计划，需要稍微改变一下方程（因为代价变成了点权而非边权），所以会变成 $f_{x,s}=\min(f_{x,t}+f_{x,s-t})-a_x$，边权要变成目标点的点权。输出方案其实还好，记录一下每个点从哪里转移过来的即可。