LCA 图论

点/边覆盖点/边独立集

我们常说的匹配就是边独立集。

在一般图上点覆盖 $\ge$ 边独立集，边覆盖 $\ge $ 点独立集，这是因为一个点/边不可能覆盖独立集里的多个边/点，二分图上二者可以取等。

注意边覆盖的定义需要图中无孤点，否则无法覆盖。

点独立集的补集总是点覆盖，反之亦然，边独立集的补集总是边覆盖，反之亦然，这是根据定义天然满足的。

如何证明二分图上最大匹配、最小点覆盖、最大独立集、最小边覆盖上的数量关系？我们需要一个更强的分析结构。

最大团

最大团总是补图的最大独立集，而二分图最大独立集是好做的，所以如果是两个团为基底的图，两个团中间连一些边，对这个图求最大团，可以转化为求补图（是一个二分图）的最大独立集。

P2423 [HEOI2012] 朋友圈

在很久很久以前，曾经有两个国家和睦相处，无忧无虑的生活着．

一年一度的评比大会开始了，作为和平的两国，一个朋友圈数量最多的永远都是最值得他人的尊敬，所以现在就是需要你求朋友圈的最大数目．两个国家看成是 AB 两国，现在是两个国家的描述：

A 国：每个人都有一个友善值，当两个 A 国人的友善值 $a,b$ ，如果 $(a\mathbin{\mathrm{xor}} b) \bmod 2=1$ ，那么这两个人都是朋友，否则不是；

B 国：每个人都有一个友善值，当两个 B 国人的友善值 $a,b$ ，如果 $(a\mathbin{\mathrm{xor}} b) \bmod 2=0$ 或者 $(a\mathbin{\mathrm{or}} b)$ 化成二进制有奇数个 $1$ ，那么两个人是朋友，否则不是朋友．

A、B 两国之间的人也有可能是朋友，数据中将会给出 A、B 之间「朋友」的情况．

对于朋友的定义，关系是是双向的．

在 AB 两国，朋友圈的定义：一个朋友圈集合 $S$ ，满足 $S \subset A \cup B$ ，对于所有的 $i,j \in S$ ， $i$ 和 $j$ 是朋友．

求最大朋友圈。

$T\le 6$ 。

第一类： $1 \le A \le 200, 1 \le B \le 200$ ．

第二类： $1 \le A \le 10, 1 \le B \le 3000$ ．

求的是这个图的最大团。

$A$ 图是个二分图，最大团最多是 $2$ ，所以这个东西是最后的细节工作，先不管。

$B$ 图是基于两个团的图加了一些边，根据上面的 trick，最大团等于补图最大独立集，转成二分图最大匹配。

对于 $A$ 图，我们枚举里面点的贡献， $0$ 不用管， $1$ 就枚举每个点，然后保留与这个点联通的 $B$ 图点跑最大团， $2$ 就是枚举一条边。

古老题的复杂度不是很对，不过时间戳优化的匈牙利不需要每次重新建图，跑的很快。

二分图匹配的匈牙利树结构

对于一个已经求完最大匹配的二分图，我们再次对其跑匈牙利算法，对每个非匹配点跑匈牙利算法，并使用 $\rm dfs$ 的剪枝，我们几乎会得到一棵 $\rm dfs$ 树。

点可以分为（匹配点，非匹配点）、（奇层点，偶层点）、（在其他非匹配点搜过，没搜过），边可以分为（匹配边，非匹配边）。

对其分析一下：

奇数层到偶数层是未匹配边，一个点可能有多个儿子，偶数层到奇数层是匹配边，一个点只有一个儿子。
奇数层连未搜过的匹配点：儿子。
奇数层连搜过的匹配点：返祖边/横叉边。
（不存在）奇数层连非匹配点：非匹配点也是另一棵树的根，这两棵树共用了这条到根的链，不可能发生因为此时存在一条 增广路。
偶数层匹配的另一端：儿子。
偶数层连向非匹配点：另一棵树的根，这两棵树共用了这个点的子树。
偶数层连（并非匹配的另一端）的匹配点：要么满足存在另一棵树横叉边到这颗树，要么是一个无法搜到的位置，若是后者，我们称其为 完美匹配结构，这个结构中每个点都是匹配点，很多题目中完美匹配的处理是平凡的，所以这个结构通常并不关心。

分析一下，我们至少可以把所有树根拎到上面，两棵树只会共用子树而不会共用链，所以我们。

其有如下性质：

根是未匹配点，奇数层到偶数层是未匹配边，一个点可能有多个儿子，偶数层到奇数层是匹配边，一个点只有一个儿子（根的深度是 $1$ ）。
树上有返祖边、跨两棵树的横叉边和完美匹配结构三种特殊结构。
叶子一定是奇数层的匹配点，否则该图存在增广路。
由于是二分图不能有奇环，返祖边一定是奇数层连到偶数层，跨树的横叉边由于你都把根拎起来了，也一定是奇数层连到偶数层。
每个联通块的奇/偶层划分一定是原图的左/右（右/左）划分，构成二分图。

我们用这个东西来分析一下前文的问题，全都规约到匹配上：

如何证明二分图上最大匹配、最小点覆盖、最大独立集、最小边覆盖上的数量关系？

最小点覆盖：每条匹配边至少要选一个点，我们证明存在一种方案即可，对于树结构我们选所有偶数层的点（点数等于匹配边数），观察上面的所有边都是连接奇数层和偶数层的，对于完美匹配结构我们全选左部点/右部点即可。

最大独立集：虽然就是最小点覆盖取补集，但我们也可以用同样方式分析：每个匹配至多选一个点，我们尽量全选未匹配点，树结构只需选奇数层的点即可，每个匹配都选了一个点，每个未匹配点也都选了，性质中指出没有奇数层之间的边，完美匹配结构全选左部点即可。

最小边覆盖：考虑一条一条加入边覆盖的过程，覆盖的点数只会 $+1$ 和 $+2$ ，边数就是 $n-(+2)$ 的次数。

考虑 $+2$ 的边一定构成匹配，我们要最大化这个数量，那我们就取最大匹配中的边，每个未匹配点再配一个 $+1$ 即可。

P7816 「Stoi2029」以父之名

给定一个 $n$ 个点 $m$ 条边的无向图，边权均为 $1$ 或 $2$ 。保证每个点所相连的边权值之和均为奇数。你需要将这些边定向，使每个点的入边权值和与出边权值和之差的绝对值恰为 $1$ 。保证有解。输出任意一种方案。

第一行两个正整数： $n,m$ ，表示有 $n$ 个罪人和 $m$ 条罪的联系。

接下来 $m$ 行，第 $i+1$ 行为三个正整数： $u_i,v_i,w_i$ ，表示第 $i$ 条联系连接 $u_i$ 与 $v_i$ 且值为 $w_i$ 。

对于 $100\%$ 的数据， $1 \le u_i,v_i \le n \le 10^6$ ， $1 \le m \le 3 \times 10^6$ ， $w_i \in \{1,2\}$ 。

两种理解方式：

欧拉回路算法是可以进行配对的，你可以限定从谁入导向从谁出，所以对于有偶数个 $2$ 的人，你把 $2$ 两两配对， $1$ 两两配对，剩一个 $1$ 与虚边配对，对于有奇数个 $2$ 的人，我们直接两两配对，然后剩一个 $1$ 与 $2$ 配对，跑欧拉回路即可。
本题的关键并不是看到绝对值是 $1$ 马上每个点从虚点连一下，连了就爆了，此时一个初步的想法是先定 $2$ 再定 $1$ ，如果这个点有奇数个 $2$ 最后会剩下一个 $2$ ，那么我们要求它 $1$ 的配对中剩余点的方向和 $2$ 的方向相反，这个要求很强，两个图做不了。

只需建一个分层图，第一层是 $2$ 边第二层是 $1$ 边，如果 $2$ 边度数是偶数，就把第二层的点连向虚点，否则就连接两层的两个点（这样限制了两边的剩余方向不同），直接跑欧拉回路即可。

P9150 邮箱题

有一张 $n$ 个点和 $m$ 条边构成的有向图。每个点内都有一把另一个点的钥匙， $i$ 号点内有 $k_i$ 号点的钥匙。你能进入一个点当且仅当你有该点的钥匙。保证 $k_i$ 构成排列。

只要进入了一个点，就获得了这个点内有的钥匙。一旦获得钥匙就不会被消耗。

现在你拿到了 $i$ 号点的钥匙并到了 $i$ 号点。你需要对每个 $i$ 求出：

有多少点能被你到达。

有多少点能被你到达并返回起点 $i$ 。

请注意：给出的边均是有向边！

对于 $100\%$ 的数据，满足 $n \ge 3$ ， $m\ge 0$ ， $\sum n\le 1.5\times{10}^6$ ， $\sum m\le 3\times{10}^6$ ， $1 \le T\le 2\times{10}^4$ ， $1 \le x, y \le n$ ，保证图中不含重边或自环。

性质

首先可达关系是闭包，如果 $i\to j$ ，那么 $j$ 能到的 $i$ 一定能到，理由就是到达 $j$ 时钥匙只会更多。

返回关系也有很强的性质，如果 $i$ 能返回 $j$ ，那么 $(j,i)$ 的这些人可以 $i$ 先返回 $j$ 再从 $j$ 走到这些点。

其次我们每时每刻还没开启的持在手上的钥匙只有一把，所以我们实质上是在排列的环上跑。

暴力

我们已经有了一个高复杂度 $\text{poly}$ 做法，即每次判断能不能在环上多走一步时，都跑一遍连通性 $i$ 能不能通过 $[s,i]$ 的人到达 $nxt_i$ ，这是三方的。

接着思考，由于我们需要判断“ $i$ 能不能通过 $[s,i]$ 的人到达 $nxt_i$ ”，假设这个过程中跳到的（环意义下）最小的点是 $t$ ，这说明 $i\to t\to nxt_i$ ，而由于能扩展到 $i$ 必然有 $t\to i$ ，那么 $i,t$ 在同一个 SCC 中。

可以看出这个过程跟 SCC 有很大关系，我们有了一个新的暴力：不断加入新点的同时维护 SCC，形状呈一条 SCC 链，每次判断最后一个 SCC 能不能到新点，每次合并一个后缀的 SCC，这个算法单次 $\mathcal O(n\alpha)$ ，一共是平方的。

正解

考虑如何优化这个算法，由于可达关系是闭包，考虑断环为链后，从后往前加入每个点，计算答案，在统计到每个点靠前出现的位置时我们会统计到答案。

想象一下形态，你发现每个可达关系都是一条平铺在环上的链，每次我们加了一个新点和一些新边，要尝试合并前两条链。

考虑合并前两条链的条件：前一条链的最后一个 SCC 能到后一条链的第一个点（不是第一个 SCC，因为此时只能顺次扩展）。

由于是新边造成了合并，又是最后一个 SCC 造成了合并，所以如果需要合并那么第一条链只有一个 SCC。

综上，每条链只需记录最大的起点 $val_{c}$ ，使得该起点有一条跨 SCC 的返祖边（指向前面的边），顺便每个点维护最大的小于它的入点 $pre_x$ 。

每次我们先尝试合并第一条链的前两个 SCC，判断条件是第一条链的 $val$ 要大于该环的最后一个点，合并后记得清空第一条链的 $val$ 。

若第一条链只剩一个 SCC，那么我们尝试合并前两条链，判断条件是 $pre_{\text{the first one of the next chain}}$ 存在（只要存在就必定连到前面）。

建议参照第一篇题解的代码。

曾经的我以为这种题需要发明一个类 tarjan 算法来解决，但其实它的结构足以用 SCC 类似物描述，也就是说图论的连通性部分是有其分析算法的。

P6880 [JOI 2020 Final] オリンピックバス

给定有向图，你可以在出发前选择一条边翻转并把边权从 $w_i$ 改为 $r_i$ ，求所有情况下 $1$ 到 $n$ 最小代价。

$n\le 200,m\le 5\times 10^4$ 。

若你翻转的边在最短路树上，那么原先的最短路体系就不能用了，一共 $n$ 次，你需要重算最短路，使用平方 $\rm dijkstra$ 即可。

若不在最短路树上，由于你想利用这条边，用原图最短路拼一下即可。

P8456 「SWTR-8」地地铁铁

给定一张 $n$ 个点， $m$ 条边的无向连通图。每条边标有 D 或 d。

定义无序点对 $(x, y)$ 是「铁的」，当且仅当 $x \neq y$ 且 $x, y$ 之间存在同时出现 D 和 d 的简单路径。

小 A 深知自由组合定律 DdTt 的重要性，所以他让你对这样的点对计数。

注意：

简单路径定义为不经过重复节点的路径。

保证图无自环，可能有重边。

对于 $100\%$ 的数据：

$2\leq n \leq 4\times 10 ^ 5$ ， $n - 1\leq m\leq 10 ^ 6$ 。

$1\leq x, y\leq n$ 。

$c\in \{\texttt{D}, \texttt{d}\}$ 。

这题实质上给了你三个图，D 图 d 图还有放在一起的图，需要同时想想在不同的图上我们能做什么。

首先看到图没什么头绪，想想点双还是边双还是 dfs 树。

判断点双还是边双有一个好方法：点双实质上是对边的连通性进行分类，含有点不交字样，边双对点的连通性进行分类，含有边不交字样。

这题是点不交，且边有两类，那缩个点双先。

我们猜测若点双内同时有两种边，则点双内两两合法，但这显然是错的，易得反例是 $1\to 2\to 3$ 都是 D 边， $1\to 3$ 是 d 边。

上文是自己的思考，下面来说题解：

事实上，上文的思考已经相当接近正解。

考虑上文的反例出现的原因：点双内只有两个点有混色出边，这样在 check 这个点对的时候，如果你想要切换颜色就必须走到终点，那么你就寄了。

剩下的情况会不会出现反例呢，直观感受是没有的，感性理解是你可以走到新的切换颜色点去切换。

所以这种特殊点双贡献是 $\binom {siz}2-1$ ，剩的合法点双是 $\binom{siz}2$ 。

接下来考虑跨点双的点对，每个点双可以分为纯黑纯白和混色，直观感受是只要跨过的点双存在两种颜色就可以，这个也是好证的，纯黑纯白显然成立，混色至少可以选一种颜色。

那怎么统计这些点对呢，我们建出圆方树，可以考虑 dsu on tree。

但是那属于学魔怔了，每个点到当前子树的根只有纯黑、纯白、混色三种，信息量是 $\mathcal O(1)$ 的，所以写个类 $\rm dp$ 式合并信息就可以了。

实现上有一些边界细节，不妨统计总数减不合法点对数，这样我们只需统计每个纯黑连通块和纯白连通块的 $\binom{siz}{2}$ ，以及特殊点双的个数。

P10790 [NOI2024] 树形图

图上复杂路径

经典的题目是异或，这里讨论一些模意义下的性质。

经典性质：无向图上的所有环的线性组合就是 $\rm dfs$ 上所有返祖边的线性组合。

典题：欧拉子图

给定一个图，求欧拉子图数量。

欧拉子图是若干边不交的回路（圈）。

每个连通块分开考虑，非树边随便选，奇数次树边要选偶数次不选，也就是树边可以调整自适应。

所以就算 $2^{m-n-f}$ ， $f$ 是联通块数。

#508. 「LibreOJ NOI Round #1」失控的未来交通工具

一个带边权无向图，有两种操作：加边以及询问在 $x,x+b,...,x+(c-1)b$ 这些数中，有多少数存在一条从 $u$ 到 $v$ 的路径长度与之模 $m$ 同余（可以不是简单路径）。

$n,q\le 10^6$ 。

考虑有无反复走可以消掉的性质，显然走 $2m$ 次可以消掉，所以我们可以复合全图任意一个环。

注意到是无向图，所以每条边都是一个二元环，我们可以加上全图任意一条边的二倍。

所以 $m$ 是奇数已经解决了， $2$ 有逆，只需关心边无需关心环，直接维护联通块的 $\gcd$ 即可。

但 $m$ 是偶数就需要关心每个环，我们需要关心生成树上的到根的和，动态树？带权并查集！

求解答案只需跑 exgcd 实现等差数列求交即可。

注意带权并查集的权值，fa[y]=x,val[x]=vx+vy+w。

#E. 前行-这题因为断网我搬了整整四次（骂骂咧咧）& [AGC031F] Walk on Graph

有一张 $n$ 个点 $m$ 条边的无向连通图 $G$ ，每条边有长度 $L_i$ ，有一个人在上面游走。

有 $q$ 组询问，每组询问给出 $s_i,t_i,r_i$ ，询问是否存在一条从 $s_i$ 出发到 $t_i$ 结束且长度为 $r_i$ 的路径（不要求简单路径）。其中路径长度的定义为：假设走过了的边长度为 $L_1,L_2,\cdots, L_k$ ，则这条路径的长度为 $(\sum_{i=1}^kL_i\times 2^{i-1}) \bmod MOD$ 。

$1\leq n,m,q\leq 50000,MOD\leq 10^6$ 且 $MOD$ 为奇数。

对骆老师伟大题解的小小注脚：

时间维极其烦人，我们直接把路径倒过来，就变成每次 $x\gets 2x+w$ ，这样我们只关心当前权值。

奇数 $\bmod$ 保证了 $2$ 有逆元，所以我们暂且不用担心乘若干个 $2$ 会使可能的取值变少。

最近讲图论刚讲了个类似的，那我们肯定往上面想， $s\to t$ 的简单路径拼上点什么东西。

考虑一些节外生枝的东西能不能消掉，考虑反复走 $k$ 次： $2^kx+L\sum_{i=0}^{k-1} 2^i$ ，我们主要关心 $\sum 2^i$ 能不能凑出 $0$ ，等比数列求和化一下是 $2^k-1$ 状物，而 $2\perp \bmod$ ，那显然 $2^{\varphi(\text{mod})}-1\equiv0$ ，所以这里的结论也是一样的，我们仍然可以拼上全图中任意一个环，中间的多余路径可以通过反复走而消掉。

证明了这个性质后其实也证明了 每条路径都是可逆的，即如果我们考虑 $(i,j)$ 表示当前在 $i$ 权值是 $j$ 的状态，那么这其实是一个无向图。

在 $(i,j)$ 的意义下继续考虑连通性，你发现一条边的作用其实是做了一个置换（没有一对多或多对一），这个置换可以用简单的 $2x+w$ 来描述，置换的复合也可以只用 $kx+b$ 来描述。

我们可以对原图跑生成树，每个点的值都映射回 $1$ 号点，可以把状态精简为 $\text{mod}$ 个，假设映射到 $1$ 的函数是 $a_ux+b_u$ ，每条边 $(u,v,w)$ 的效果都是 $\forall x,a_ux+b_u\leftrightarrow a_v(2x+w)+b_v$ ，然后在这个图上跑并查集。

每次要在这个图上连 $x\to kx+b$ ， $k,b$ 都不是定值，完全无法战胜。

这个思路的问题是完全没有用到 $2$ 的性质，或者说仅仅利用了可逆性。

尝试考虑环但你发现一个环从哪里开始都不知道，并且你也不知道从哪里开始是否等价。

不妨先考虑二元环（一条边）的简单情况。

走回去再走回来的效果是 $x\to 4x+3w$ ，所以全图（上文已证，我们可以自由符合全图的每个环）如果有两条 $w_1,w_2$ 的边，那么 $4x+3w_1\leftrightarrow x\leftrightarrow 4x+3w_2$ ，由于 $4x$ 可逆，所以 $x+3w_1\leftrightarrow x+3w_2$ ，也就是说我们可以自由把数加上 $3(w_1-w_2)$ 。

根据裴蜀定理，我们可以自由加上 $3\gcd_{i=1}^n(w_i-w_1)$ ，以下简称为 $3g$ ，所有东西都可以 $\bmod \ 3g$ 。

由于 $g$ 是差的 $\gcd$ ，所以每个 $w$ 都可以变成 $z+kg(k\le2)$ ，其中 $z=w_1\bmod g$ 。

现在再看边的影响： $(u,x)\to (v,2x+z+kg)$ ，也就是 $(u,x-z)\to(v,2x-z+kg)$ ，我们把值域平移 $z$ ，即现在用 $(u,x)$ 表示以前的 $(u,x-z)$ （想起了刚上高一天天换元的文化课时光）。

那就是 $(u,x)\to (v,2x+kg)$ ，一样的套路，我们转回来： $(u,x)\to(u,2(2x+kg)+kg)=(u,4x)$ 。

$(u,x)$ 都与 $(u,4x)$ 联通了，这个性质太强了，发现 $(u,z)$ 能到的状态都是 $az+bg$ ， $a$ 是 $2$ 的幂， $b$ 是 $<3$ 的数。

由于 $x$ 与 $4x$ 联通，将 $az+bg$ 不断乘上 $4^{-1}$ ，于是我们也只需关心 $a\in[1,2]$ 的值了，共 $6n$ 个状态。

如果把 $2$ 变成 $p$ ，那么前文的另一个思路直接做复杂度是 $n+p^2$ 的，直接在图上跑是 $np$ 的。

一些细节：改完定义之后边的操作就是 $(u,x)\to (v,2x+kg)$ 了，也就是 $(u,x)\to (v,2x+w-z)$ ，询问的值要加上 $z$ 。

平面图

三角剖分图可以三染色判定。

#554. 「LibreOJ Round #8」MIN&MAX II

给定排列，每个点向左右第一个比它小/大的点连边， $q$ 次询问只保留一个区间的点和边，问染色数（至少需要几种颜色可以将点染色，每条边两边不一样）。

$n,q\le 3\times 10^5$ 。