DAG 链剖分_随笔

DAG 链剖分

一句话，令 $f_x$ 是到达 $x$ 的路径数量，$g_x$ 是从 $x$ 出发的路径数量，则 $(u,v)$ 是重边当且仅当 $u$ 是 $v$ 中的 $\max f$，$v$ 是 $u$ 中的 $\max g$。

走一条轻边 $f,g$ 中至少有一个减半。

顺着拓扑序方向跳轻边，至多跳 $\log V$ 次，其中 $V$ 是该有向无环图的路径总数。

由于复杂度是 $\log V$，该结构天然适合在 $\rm SAM$ 这种路径条数有保证的图上行走。

后面忘了，这么毒瘤的东西知道是啥就行了，真去写对应的题还是太超前了。