【算法笔记】基环树

整理的算法模板合集： ACM模板

---

目录

基环树找环的两种方式拓扑排序dfs 例题：P4381 [IOI2008]Island

基环树

基环树（基于环的树 ），也是环套树，是一种有 $n$ 个点 $n$ 条边的图，简单地讲就是树上在加一条边。它形如一个环，环上每个点都有一棵子树的形式。

基环内向树：每个点出度为1（因此每个环上点的子树，儿子指向父亲）

基环外向树：每个点入度为1（因此每个环上点的子树，父亲指向儿子）

基环树的关键就是找到环，可以先把环当作这个无根树的 “根” ，也就是把环当成一个点（先不管它），这样一颗基环树就变成了一个普通的树，然后我们先按照解决普通树的方法对“根”的所有子树依次处理求解答案，最后在单独对环上所有的点进行操作求解最终答案即可。

找环的两种方式

拓扑排序

处理无向图

可以找出环上的所有点。

void topsort(){ int l=0,r=0; for (int i=1;i<=n;i++) if(in[i]==1) q[++r]=i; while(l<r) { int now=q[++l]; for (int i=ls[now];i;i=a[i].next){ int y=a[i].to; if(in[y]>1){ in[y]--; if(in[y]==1) q[++r]=y; } } } }

之后入度 $>=2$ 的点就是环上的点

dfs

处理有向图，码量小

void check_c(int x) { v[x]=true; if(v[d[x]]) mark=x;//环上的一点 else check_c(father[x]); return; }

我们稍加修改就可以保存所有的环上的节点了。

inline bool dfs(int x, int in_edge) { if(v[x] == 1){//再次访问说明到了环的链接点，标记它是环(v[x] = 2) v[x] = 2, loop[++ cnt] = x, v2[x] = 1; return true; } v[x] = 1; for(int i = head[x]; ~i; i = nex[i]){ int y = ver[i]; //如果当前边不是上一条边(没有往回走)并且当前节点在环上 if(i != ((in_edge) ^ 1) && dfs(y, i)){//每次存一个点，靠继续dfs遍历整个环 if(v[x] != 2)//当前节点不是衔接点,把环里的点存起来 loop[++ cnt] = x, v2[x] = 1, s[cnt] = s[cnt - 1] + edge[i]; else {//环的链接点 s[st - 1] = s[st] - edge[i];//又转回来（破环成链） return false; } return true; } } return false; }

例题：P4381 [IOI2008]Island

由于这个公园有n座岛屿和n座桥，就相当于一个由N个节点和N条边构成的无向图。显然，这样的一个无向图就是一个基环树森林。（题目中的渡船是没有用的干扰项，因为渡船使用的条件是两点之间没有路，但是所有的点之间都有一条无向边…）

我们要求的最长的路径实际上就是基环树森林的直径。我们考虑先找到环，然后把环当作当前这颗基环树的“根节点”，我们发现直径有两种情况：

在“根节点”的某一棵子树中经过“根节点”，在“根节点”的某两棵子树中

情况一我们直接以环的每一个点为根找它的子树的直径，这里我们直接用树形dp即可，如果用dfs会爆栈。最后取最大值。

情况二我们需要找到环上的两个节点$i,j$，使得$d_i+d_j+dis{t}_{i,j}$最大，其中$dis{t}_{i,j}$表示节点$i,j$在环上的距离。如果一个个枚举的话，显然时间复杂度太大，不可行。这里可以断开环将断开后的链复制到两倍的长度，用单调队列进行优化. 因为需要O(1)得到换上任意两点之间的距离，所以我们可以直接维护一个距离的前缀和s数组。 我们要找的是最大的$d_i+d_j+dis{t}_{i,j}$，其中$dis{t}_{i,j}$即为$s_i-s_j(j<i)$。整理后即为：$d_i+s_i+d_j-s_j$。 其中单调队列中

对于每个节点$i$，显然如果一个节点$j(j<i)$满足$d_j-s_j\le d_i-s_i$，那么根据最优性， $j$ 是一定不会被选作最终决策的，因此可以将其从答案队列中删除。

所以本题就是基环树：dfs找环+树形DP求树的直径+破环成链+单调队列优化

typedef long long ll; const int N = 2000007, M = 5000007, INF = 0x3f3f3f3f; int n, m; int head[N], ver[M], nex[M], edge[M], tot; int loop[N], cnt; int v[N];//表示dfs时走过这个点 int v2[N];//表示这个点所在的基环树已经被走过了，在dfs里标记环中的点，在dp中标记非环点 ll ans, ans1, ans2, ans3, res, st; ll dist[N], dp[N]; ll s[N];//前缀和，方便计算两点距离 //ans存储当前子树的直径，ans2存储第一种情况的答案 void add(int x, int y, int z) { ver[tot] = y; nex[tot] = head[x]; edge[tot] = z; head[x] = tot ++ ; } //dfs找环 inline bool dfs(int x, int in_edge) { if(v[x] == 1){//再次访问说明到了环的链接点，标记它是环(v[x] = 2) v[x] = 2, loop[++ cnt] = x, v2[x] = 1; return true; } v[x] = 1; for(int i = head[x]; ~i; i = nex[i]){ int y = ver[i]; //如果当前边不是上一条边(没有往回走)并且当前节点在环上 if(i != ((in_edge) ^ 1) && dfs(y, i)){//每次存一个点，靠继续dfs遍历整个环 if(v[x] != 2)//当前节点不是衔接点,把环里的点存起来 loop[++ cnt] = x, v2[x] = 1, s[cnt] = s[cnt - 1] + edge[i]; else {//环的链接点 s[st - 1] = s[st] - edge[i];//又转回来（破环成链） return false; } return true; } } return false; } inline void tree_dp(int x){//树形DP处理第一种情况——不经过环的树的直径 v2[x] = 1;//标记整棵基环树的非环部分 for(int i = head[x]; ~i; i = nex[i]){ int y = ver[i]; if(v2[y])continue; tree_dp(y); ans = max(ans, dist[x] + dist[y] + edge[i]); dist[x] = max(dist[x], dist[y] + edge[i]); } } //对于这一颗基环树来说 inline ll brt(int root){ //这里的cnt是一只累加的，表示的是整个基环树森林的所有环的边数 //所以我们每次从上一颗基环树的编号+1开始一颗新的基环树 st = cnt + 1, ans2 = 0, ans3 = 0; dfs(root, 0); //dfs找到环以后，从st开始走，跑当前基环树的所有的环 for(int i = st; i <= cnt; ++ i){ ans = 0; tree_dp(loop[i]); ans2 = max(ans2, ans);//找出第一种情况的最大答案 //我们破环成链，2*n的链表示整个环，初始化dp数组 dp[i + cnt - st + 1] = dp[i] = dist[loop[i]]; s[i + cnt - st + 1] = s[i + cnt - st] + (s[i] - s[i - 1]); //s[i] - s[i - 1]表示的是i和i-1两点之间的距离 == edge[i]; //因为cnt没有重置，一直用的一个数，所以 //环上的节点个数为 cnt - st + 1 } deque<int>q; for(int i = st; i <= 2 * cnt - st + 1; ++ i){//对复制后的链进行遍历 while(q.size() && q.front() <= i - cnt + st - 1) q.pop_front();//排除超出范围的决策(越界的pop) if(q.size()) ans3 = max(ans3, dp[i] + dp[q.front()] + s[i] - s[q.front()]); while(q.size() && dp[q.back()] - s[q.back()] <= dp[i] - s[i]) q.pop_back(); //排除过时的决策(单调队列维护单增，要是还没有新来的强，那就永远追不上了，就pop吧) q.push_back(i);//将当前决策插入队列 }//处理第二种情况 return max(ans2, ans3);//取两种情况的最大值 } int main() { memset(head, -1, sizeof head); scanf("%d", &n); for(int i = 1; i <= n; ++ i){ int y, z; scanf("%d%d", &y, &z); add(i, y, z); add(y, i, z); } res = 0; for(int i = 1; i <= n; ++ i){ //求整个基环树森林的直径，一次dfs不一定能遍历所有的树，因为不一定都相连 if(!v2[i])//如果没走过就走 res += brt(i);//加上这颗树的直径 } printf("%lld\n", res); return 0; }

推荐博客，对基环树的三种情况的讲解非常详细：

https://www.luogu.com.cn/blog/user52918/qian-tan-ji-huan-shu

一些例题：

https://www.cnblogs.com/mangoyang/p/9314823.html