JustPureH₂O

二分图，又称二部图。顾名思义，在一个二分图中，所有的节点可以分成两部分（分别用黑白染色），并且满足相同颜色的点之间无边。如下图：

<ruby>双连通分量<rt>Double Connected Components</rt></ruby>，简称 \texttt{DCC}（电磁场）。是连通分量在无向图中的体现。分为点双连通分量 \texttt{v-DCC} 和边双连通分量 \texttt{e-DCC}。在一张连通无向图中，任意删去一条边，如果无论如何都不能使点 u,v 不连通，那么就称 u,v 边双连通；同样在一张连通无向图中，任意删去一个点（u,v 除外），如果无论如何都不能使 u,v 不连通，则称 u,v 点双连通。

在说 \texttt{SCC} 之前，先涉及最基本的概念：连通分量。如果一张有向图中，任意两个节点都能互相到达，则称它是一个连通分量，特殊地，一个点也算一个连通分量。<ruby>强连通分量<rt>Strongly Connected Component</rt></ruby>，简称 \texttt{SCC}（四川菜），是原图的极大连通分量。这里的“极大”是一个文艺复兴时期提出的概念——若一个事物，没有比它更大的事物存在，就称这个事物是极大的/最大的（例如：导数的极大值）。

实质是把节点每次向上暴力移动一步变成更加高明的按 {2^k} 步向上移动，借用的是每个数都可进行二进制分解的定理。期间维护一个父节点数组 fa，fa[i][k] 代表 i 向上移动 {2^k} 步的父节点。那我们该如何更新这个父节点呢？显然有 {2^k=2^{k-1}+2^{k-1}}，就是两次向上移动 {2^{k-1}} 步，因此可以用 fa[fa[i][k - 1]][k - 1] 来递归更新。

受限于在线编辑器的性能瓶颈（省流：写太多了会很卡），在此决定把另外的（不在算法提高课中）DP斜率优化题目单独拎出来写一篇做题笔记。旨在记录算式消元换元的原则与技巧、凸包维护的方法。题目大致由易到难。

前情提要：Day1 单调队列优化

有人私信我，说能不能不要在博客里写那么多“显然”。我的回答是：“好的，全部换成‘Apparently’”。我寻思我也没写那么多显然啊