本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-02-15 11:04:08

P2149 [SDOI2009] Elaxia的路线

4遍dij （一个点一遍）

x1存在dis[1]里 ，x2存在dis[2]里，y1存在dis[3]里,$y2\to dis[4]$

易证公共路径为一条链

如果$dis_{1,x}+dis_{3,y}+w==dis_{1,y}$ 则$x\to y$在 x1到y1的最短路上

同理，可以得到$x\to y$在 x2到y2的最短路上，$y\to x$在 x2到y2的最短路上的情况

这样就得到了一个DAG

同向逆向分开跑最长链，取max

[GXOI/GZOI2019] 旅行者

按二进制位分组，第 $i$ 位为1一组，0一组，对于每一组建超级源点

有向图，两遍

P2371 [国家集训队] 墨墨的等式

同于最短路，$n$ 元跳楼机

P3403 跳楼机

Legacy

线段树优化建图

P4001 [ICPC-Beijing 2006] 狼抓兔子

最短路/网络流（最小割）

P3398 仓鼠找 sugar

找LCA

看二者的LCA是否在对方的路径上

P4281 [AHOI2008] 紧急集合 / 聚会

两两求lca找出深度最大的点，集合点在那里

然后再求路径长度

加强

$m$ 次询问，每次 $k$ 个点

$1\le m,n\le5\times10^5,1\le \sum k \le2\times 10^6$

如果两两分组走，发现其中每条边恰好走两遍

答案即为 $sun/2$

[BJWC2010] 严格次小生成树

不断用非树边替换树边

Indecisive Taxi Fee