图论好题
[P5304] 旅行者
集合最短路+二进制拆分
集合最短路
求一个集合S中的点，到任意一个集合T中点的最短路
建立超级源点连S、超级汇点连T即可
二进制拆分
两遍dijkstra染色
[P3953] 逛公园
搜索
考虑搜索出全部合法路径
易想到记录\(rdis[i]\)为\(i->n\)的最短路来剪枝
跑反图可得\(rdis[i]\)（记住这个\(rdis[i]\)，后面要用）
动态规划
观察到k很小，先考虑分层图
发现路径数总是往不低于自己层数的层转移
即为DAG，考虑DP （下面用分层图理解更直观）
设状态\(f[i][j]\)为第\(i\)个节点，和\(j\)的路径数最短路长相差
转移方程：\(f[v][now]+=f[x][j]\)
其中\(now\)为转移至v点后与最短路长相差的长度，易知\(now=rdis[v]+e[i].dis-rdis[x]+j\)
如果\(u->v\)在最短路上，DP方程在本层转移，因此需要注意节点枚举顺序
易知先处理dis值小的可以转移完全（在最短路形成的DAG上跑拓扑应该也行）
拓扑排序
考虑0边这个条件，会使得我们的DP发生一些变化
当有
\(1->2\ \ \ w=1\)
\(1->3\ \ \ w=1\)
\(3->2\ \ \ w=0\)
时
会有\(1->3->2\)这条路径，但如果只按dis值排序，可能会先转移节点2，使得该路径丢失
所以我们要在dis值排序的基础上，对等dis点做些处理
因为0边有向，且0边不能成环（会有无限条路径），则0边构成的图为DAG，具有可排序性
做出0边相连的点的拓扑序，按拓扑序处理等dis点，DP可以转移完全
拓扑排序即可
细节处理
1、并不是所有0环都会使路径数无限，前提是能走到0环上，所以只需处理合法点（\(dis[i]+rdis[i]<=dis[n]+k\)）
2、注意数组边界（层数超过k就不要转移了，不然会越界访问，不是WA就是RE）
P7518 [省选联考 2021 A/B 卷] 宝石
倍增+离线
关键在于想到链上倍增（别整天惦记着你那树剖+线段树，这里的贡献显然不可任意合并，只能接头尾）
链上：对于\(i\)点，\(nxt[i][j]\)处理出跳到\(p\)数组中下\(2^j\)个数的位置，倍增跳到终点即可（st[]找该点开始第一个起点）
树上：分成\(s \to lca\)和\(lca \to t\)两段，前一段如上，后一段不好处理，观察到\(lca \to t\)中编号较小的终点更容易与前段衔接，考虑二分答案，做反跳数组\(rnxt[]\)即可
注意桶\(bac[]\)在此的妙用：由于dfs栈中始终为连续的\(1 \to i\)的路径，可用于记录最后出现的\(p[i]\)的位置，这在预处理和二分找反跳起点是很有用