基环树笔记

update：“基本定义以及方法”这一节中出现的对基环树的特点描述中出现了较为严重的错误，对于一个 $N$ 点 $N$ 边的不连通图只有在保证每一个连通块点数等于边数的时候才是一个基环树森林。 对于博客的内容出现问题表示万分抱歉，笔者水平有限，如果还有相关问题请立即提出，谢谢各位/qq # 基环树 ~~啥啥啥鸡排？~~ 是无向树哇/youl 前置技能： 树的直径、最大独立集等有关树形DP的经典问题 $dfs$ 等基本图上算法 ## 基本定义以及方法 正如老婆饼没有老婆，基环树也不是树，他是个图 基环树，又称环套树，最显著的特点就是有 $N$ 个点 $N$ 条边，诶，比一棵树多一条边，这就导致这个图上出现了一个唯一的环，当然，这是保证这 $N$ 个点 $N$ 条边构成的是一个连通图的时候才是唯一环，如果图不连通但是每个连通块点数都等于边数的时候这个图就是一个基环树森林，可以有几个环  这就是标准的一个基环树，可见，由于多了一条红色的边，导致出现了一个环 如果图不连通那么就可能变成几个基环树构成的森林了 目前大概总结出两个方法 1. 把环抽出来，这样整个图就变成一个环上面挂了几个子树的样子了，然后对子树进行操作，将信息合并到环上的节点，最后就能把一个图上的问题降到环上处理 2. 先忽略掉导致整棵树出现环的一条边，然后对剩下的树进行操作 接下来具体题目具体分析了 ## 题目详解 ### CF711D #### 题意 有 $N$ 个点 $N$ 条无向边，现在想要给每一条边定一个方向，问使得定向后的图不出现环的方案数有多少种 $2\le N\le 2\times10^5$ 输入：$N+1$ 行，第一行一个整数表示 $N$，接下来 $N$ 行，每行一个数字 $a_i$ 表示第 $i$ 个节点与第 $a_i$ 个节点之间有一条边（$a_i\ne i$） #### 解法 首先我们知道，全部的方案数是 $2^N$ 种，接下来要从其中减去成环的方案数，这是 $N$ 点 $N$ 边的图，那么很容易会想到基环树，一个基环树中的环部分是唯一的  环外的边无论正向还是反向都无所谓，既不会影响已有的环，也不会增加环。 但是环内的任意一条边只要方向和其他的边不一样，就没救了。 所以我们发现在所有的方案中，只有环内边方向全部为正以及环内边方向全部为反两种情况是非法的，这时候非法方案数为 $2^{N-len}\times2$ ，其中 $len$ 为环上边的条数，合法方案数为 $(2^{len}-2)\times2^{N-len}$ ，那么我们这题就解决了¿ 并不是（ 因为题目并没有保证图是联通的，所以应该对于整个图找到所有的基环树的环，每一个基环树可以向上面描述的那样计算，答案为 $$\large2^{N-\sum len}\prod (2^{len}-2)$$ 每次输入一条边的时候就把边的端点用并查集合并到同一个联通块里，当发现一条边的端点已经在同一个联通块内的时候，这条边为一个环上的边，而对于一棵基环树，这样的边只会出现一次，因此可以存下来方便之后处理 ### P1453 城市环路 #### 题意 给出一个 $N$ 个点 $N$ 条边的连通图，每个点有点权，求出其最大独立集（不能选取相邻的节点情况下能选取点集的最大点权和） $1\le N\le10^5$ #### 解法  没错，就是方法2了 去掉多出来的一条边之后问题就变成了树的最大独立集问题，是个板子就不多赘述 问题是现在那条边还是连在图里的  假如我们已经把这条多余的边的两个端点找了出来，设为 $lt$ 和 $rt$ ，不难发现，对于最后的答案选取情况无非 $3$ 种，一是 $lt$ 选 $rt$ 不选，二是 $lt$ 不选 $rt$ 选，三是 $lt$、$rt$ 都不选 我们可以把这三种情况都计算出来，先强制不选取 $rt$，然后以 $lt$ 为根在忽略多出的一条边之后的树上跑最大独立集，可以得到当 $lt$ 选/不选并且 $rt$ 不选的时候得到的最大答案，然后强制不选取 $lt$ 允许选取 $rt$ 跑一次就能得到选取 $rt$ 并且不选取 $lt$ 的最大答案，三者求最大值即可。 现在是小细节部分 1. $lt$ 和 $rt$ 的选取我使用的是并查集，输入 $N$ 条边时，当加入的两条边的端点已经处于同一联通块之后就记录这两个端点（即为多余边的两个端点） 2. 强制选取的方法，我是暂时将节点的权值设为 $-\infty$ 来禁止选取该节点（要记得设为 $-\infty$ 后一定要换回来） 于是我们就解决了这题/cy ### P2607 骑士 #### 题意 有 $N$ 个骑士，每个骑士有且仅有一个厌恶的骑士（不会是他自己），每个骑士都有一个战斗力，现要求从中选取一些骑士，使得这 $N$ 个骑士之间相互不厌恶的同时，其战斗力之和最大，输出这个最大的战斗力之和 $1\le N\le10^6$ #### 解法 首先建模，相互厌恶的骑士之间连一条无向边，那么，答案就是最大独立集 熟悉的 $N$ 点 $N$ 边，那么就是一棵基环树 还是求最大独立集，似乎刚刚做的城市环路照搬即可？ 那当然不完全是（~~不然为啥这题是个紫题啊喂~~ 因为本题的图可以不连通，但是每个连通块点数仍然等于边数，所以图会变成基环树森林 这里插说一句，本人不是很喜欢用 $dfs$ 把环找出来（~~主要是因为太菜了不会/kk~~ 这里仍然使用并查集辅助找环 这时候你也许会表示疑惑：刚刚的图是联通的所以可以用并查集找到多余的那条边，要不是联通的，环不止一个，多余的边也不止一条怎么办？ 那就把所有的多余边的端点存下来/cy 然后对于每一个多余的边，它一定**对应且只能对应一棵**基环树，所以可以写函数直接计算单棵基环树的最大独立集，最后答案累加即可。 就将其当成若干个城市环路解决就行了。 ### P4381 [IOI2008]]Island #### 题意 这题考语文（（ 主要是对坐渡船的理解，这里坐渡船的条件是不能有桥直接连接坐船的起止点，也不能在一个地方反复坐船 对坐船次数实际上没有限制 每个点只能经过一次，要求最长的在桥上走的路程。（即求最长的一条路径） #### 解法 这就引入了一个很重要的问题——基环树的直径问题 基环树的直径是指基环树上任意两点间距离的最大值 本题求的是最长链，但是方法和直径差不多 （这道题目图不连通还是求最长链，因为坐船次数不受限，给出的如果是一个基环树森林我们就把每一棵基环树都求一个最长链，最后直接加和即可，因为我们可以走完一棵基环树的最长链再坐船去另外一棵基环树再走最长链） 所以接下来我们只关注一棵基环树的最长链 按照下图考虑，图抽象成一个环上面挂一堆子树  考虑这个最长链的起止点 最长链的起止点一定是没有叶结点的，否则继续向下走直径还能继续变长。 所以我们可以对于环上的每一个节点都预处理一下它下挂的子树的最最深深度和这个子树的直径（有可能一个子树的直径就能成为整棵基环树的最长链） 然后给环上的每个节点带上权，权值为该节点下挂子树的最深深度（没有子树权值就为0）  接下来就要选择一对点 $u,v$ 使得 $dis(u,v)+w[u]+w[v]$ 最大 现在的难点就在于 $dis(u,v)$ 的求法，由于这是个环， $dis(u,v)$ 有两种走法，似乎有些麻烦 对于环，我们有一个经典的方法叫**断环成链** 也就是将环倍长，  这样一条链上的选取方案就能包括原来环上的所有选取方案啦 加上链上的处理更简单，现在考虑 $dis(u,v)+w[u]+w[v]$ 这个式子的计算是不是好多了呢？ 我们从最左边的权值为 $5$ 的节点出发，设环长为 $len$ 作一个前缀和设为 $d[i]$ ，那么对于第 $i$ 个点，最长的可选链长即为 $$max(w[i]+d[i]-d[j]+w[j]),max(1,i-len)< j<i$$ 这是啥？ 滑动窗口嘛！ 我们用单队维护最大的 $w[j]-d[j]$ ，并且注意要把 “过期” 的 $j$ 及时弹出队列，就能解决这个问题了。 代码细节注意： 1. 过期的 $j$ 的范围要注意 2. 考虑一下自己的代码对像这样的二元环是否有抵抗力 3. 找环、处理环上/环外节点信息是否写对（特别是一个环的端点是不是处理到了） 另外提一句，这样的题目尽量不要为了只是少写一个函数去强行把功能集成到一个函数上，这样造出来的代码不会好看，笔者认为，不好看的代码它效果也一定不会好，该重构的时候就重构 推荐一个功能写一个函数，比如本题的 $dfs$ 总共有三种，一是找到环（并标记环），二是处理环上挂的子树，三是断环成链（当然并不一定都一定要用 $dfs$ 实现，自己觉得简单好写就行） 由于这题细节还比较多，以及实现时经常 “写丑”，[给一份代码](https://www.luogu.com.cn/paste/p7kixei6)，参考调试以及帮助不知道怎么实现好的同学。 （注释充足，代码....不敢评价成好看，但是绝对不丑QwQ） ~~我才不会告诉你这题代码写丑导致我114514了一下午~~ ### [NOI2013] 快餐店 #### 题意 给出一个 $N$ 点 $N$ 边的联通图，在图上找到一个位置使得该位置到所有点的距离中最大距离最短，输出这个最短的距离。 $1\le N\le10^5$ #### 解法 首先证明，答案即为基环树的直径的一半  假设中点落在橙色的节点上，红色的路径为直径，那么一定不存在节点到橙色节点距离比直径的两个蓝色端点更远。 否则，红色路径就不是直径了，这时候直径就变成了一半红色路径和那个离得更远的点组成的路径 至于为什么上面的图画的是个树不是基环树，基环树的直径一定是不会经过环上的所有边的  如图，最多经过 $len-1$ 条边， $len$ 为环的长度 所以把基环树环上的边可以断掉一条，这样他就是棵树了/cy 对于树我们是有比较好的解决方法的，直接求树的直径相信各位都会了，所以现在就有一个相当暴力的方法就是枚举环上的边依次断掉，然后对生成的树做一次DP求出直径，在所有直径中取一个最小值即可，时间复杂度是 $O(N^2)$ ，会爆炸 那么，既然图是一棵基环树，有什么更好的方法么？ 当然有 正如 $\mathsf{Island}$ 一题中我们采取的方法，先把环找出来，将环上的子树收缩到环上，断环成链 （搬图）    你会发现在断出来的链上的任意的连续 $len$ 个节点（在上图中 $len=4$ ）之间的边都恰好只有 $len-1$ 条，恰好符合我们暴力做法的构想。 那么能不能快速的统计这 $len$ 个节点相关的信息来得到这种情况下的直径呢？ 设数组 $w[\space]$ 为链上的点权，$sum[\space ]$ 为链上节点到链头的距离。 那么假设由点 $u,v$ 构成了某种情况的直径（假设点 $u$ 在链上后于点 $v$ 出现），那么直径长度即为 $sum[u]-sum[v]+w[u]+w[v]$，很显然，由于这是直径，所以这个长度在当前选取的 $len$ 个点中是最大的。 所以我们的目的就是在当前选取的 $len$ 个节点中选取最大的 $w[u]+sum[u]$ 和 $w[v]-sum[v]$ ，加在一起就是该种选取 $len$ 个节点的方案的直径了。 但是注意这里一定要满足 $u\ne v$ ，否则两个式子加在一起就变成了从一棵子树走下去再上来的路径，显然这不是直径。 因此，我们不能仅仅维护 $w[i]+sum[i]$ 的最大值和 $w[i]-sum[i]$ 的最大值，还要维护次大值。这样在出现 $u=v$ 的时候将次大值与最大值组合一下依然可以计算答案。 仍然可以使用单调队列，但是细节很多实现并不是很方便，可以考虑使用优先队列（堆），虽然这样会让时间复杂度带上一个 $log$，但是依然是一种不错的做法。无论是哪一种做法，时刻关注选出的 $w[i]-sum[i]$ （或者 $w[i]+sum[i]$）的 $i$ 的编号是否“过期”。 还要注意从基环树将子树收缩到环上的时候要计算子树内部的直径，这也是可能的答案。 ## 总结 好啦，题目也讲了不少了，现在你对基环树的理解应该不少啦，解题方法大多都跑不出开头提到的两种方法：忽略多出来的一条边 或者 抽出环上挂一堆子树然后把图降级到环最后降级到链。 ## 练习题 [CF835F](https://www.luogu.com.cn/problem/CF835F) [P2081](https://www.luogu.com.cn/problem/P2081)