基环树瞎吹

# 前言 写这篇文章的原因就是因为今年TG day2考了一道基环树的题，于是就写了这个东西。 -------- # 正题 -------- ## 一.概念 ----- ## 基环树 基环树就是有n个点n条边的图，由于比树只出现了一个环，那么就称之为基环树了。 基环树结构仍然很简单，但比树要恶心~~得多~~一些。 --- ## 特殊形态的基环树  无向树(N点N边无向图)  外向树(每个点只有一条入边)  内向树(每个点只有一条出边) 以上三种树有十分优秀的性质，就是可以直接将环作为根。就可以对每个环的子树进行单独处理，最后再处理环 ----- ## 二.get必备姿势!——找环 ----- ### 拓扑排序 处理无向图 可以找出环上的所有点。 code: ```cpp 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 处理有向图，码量小 ```cpp void check_c(int x) { v[x]=true; if(v[d[x]]) mark=x; else check_c(father[x]); return; } ``` mark就是环上的一个点 ---- ## 三.一般问题解决方法 ----- ### 断环法 每次断开环上的一条边跑一遍答案，然后取最大值。 适用于:数据较小，且环不会影响答案的题目 比如:[2018 TG day2 T1](https://www.luogu.org/problemnew/show/P5022) ------ #### 题目大意 一棵树(可能是基环树)，从1出发，每到达一个新的点就记录下编号。求一种走法使得记录下来的编号字典序最小。 --------- #### 解题思路 这道题有可能是个基环树 我们先不考虑基环树。我们可以发现每次走字典序小的点就好了。我们可以排序一下就可以做到这点。 之后我们考虑基环树，我们暴力删边将基环树变为一棵普通的树。然后计算答案。 时间复杂度:$O(n^2)$ 然后愉快的发现可以过 ----- #### $code$ ```cpp #include<cstdio> #include<queue> #include<cstring> #include<algorithm> #define N 5010 using namespace std; struct node{ int to,next; }a[2*N]; struct line{ int x,y; }l[2*N]; int tot,n,m,t,ls[N],in[N],state[N],w[N],ans[N],x,y,q[N]; bool k[N][N],v[N]; void addl(int x,int y)//加边 { a[++tot].to=y; a[tot].next=ls[x]; ls[x]=tot; in[y]++; } bool 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; } } } if(r==n) return true; return false; }//拓扑求环 bool cmp(line x,line y) {return x.y>y.y;} void dfs(int x)//走一遍 { state[++t]=x; v[x]=true; for(int i=ls[x];i;i=a[i].next) { int y=a[i].to; if(k[x][y]||v[y]) continue; dfs(y); } } void check()//判断是否为更小字典序 { int i; bool flag=false; for(i=1;i<=n;i++) if(state[i]<ans[i]) {flag=true;break;} else if(state[i]>ans[i]) return; if(!flag) return; for(;i<=n;i++) ans[i]=state[i]; } void get_ans(int xs)//暴力删边 { int x=xs,b=0,i,last=0; do { w[++b]=x; in[x]=1; for(i=ls[x];i;i=a[i].next) { int y=a[i].to; if(in[y]>1) {x=y;break;} } }while(i);//记录环的每个点 w[++b]=xs; for(int i=1;i<b;i++)//枚举删除的边 { k[w[i]][w[i+1]]=k[w[i+1]][w[i]]=true; memset(v,0,sizeof(v)); t=0; dfs(1); check(); k[w[i]][w[i+1]]=k[w[i+1]][w[i]]=false; } } int main() { memset(ans,127/3,sizeof(ans)); scanf("%d%d",&n,&m); for(int i=1;i<=m;i++) { scanf("%d%d",&x,&y); l[i]=(line){x,y}; l[i+m]=(line){y,x}; } sort(l+1,l+1+2*m,cmp);//排序 tot=1; for(int i=1;i<=2*m;i++)//加边 {addl(l[i].x,l[i].y);} if(m==n-1)//普通的树 { dfs(1); for(int i=1;i<=n;i++) printf("%d ",state[i]); return 0; } topsort(); for(int i=1;i<=n;i++) if(in[i]>1) { get_ans(i); break; } for(int i=1;i<=n;i++) printf("%d ",ans[i]); } ``` ----- ### 二次dp法 其实对于环，我们可以像环形dp一样将一条边强行断开处理一遍，然后强行连上再处理一遍 适用于:这样子跑满足正确性的 比如:[ZJOI2008骑士](https://www.luogu.org/problemnew/show/P2607) ------ #### 题目大意 每个骑士有一个不可以同时上场的骑士，和一个战斗力。求最大战斗力。 -------- #### 解题思路 类似没有上司的舞会 其实就是在基环树森林，我们可以利用二次树形dp的方法。 先找到环，然后强行将环断开进行一次dp，然后强行连上进行一次dp，两次答案求最大值。 ---------- #### code ```cpp #include<cstdio> #include<algorithm> #include<cstring> #define ll long long #define N 1000010 using namespace std; struct node{ ll to,next; }a[N]; ll w[N],n,x,ans,tot,fa[N],root,f[N],g[N],ls[N],d[N],mark; bool v[N]; void addl(ll x,ll y)//连边 { a[++tot].to=y; a[tot].next=ls[x]; ls[x]=tot; } void check_c(ll x)//找环 { v[x]=true; if(v[d[x]]) mark=x; else check_c(d[x]); return; } void dp(ll x)//树形dp { v[x]=true; f[x]=w[x];g[x]=0; for(ll i=ls[x];i;i=a[i].next) { ll y=a[i].to; if(y!=mark)//如果是断开就不选 { dp(y); g[x]+=max(f[y],g[y]); f[x]+=g[y]; } else f[y]=-2147483647/3; } return; } int main() { scanf("%lld",&n); for(ll i=1;i<=n;i++) scanf("%lld%lld",&w[i],&d[i]),addl(d[i],i); for(ll i=1;i<=n;i++) { if(v[i]) continue; check_c(i);dp(mark); ll maxs=max(f[mark],g[mark]); mark=d[mark]; root=0;dp(mark); ans+=max(maxs,max(f[mark],g[mark])); } printf("%lld",ans); } ``` ----- ### 断环复制法 其实对于环，我们依旧可以像环形dp一样断开环，然后再负制一遍放在后面 适用于:多个需要维护的 比如:[IOI2008 Island](https://www.luogu.org/problemnew/show/P4381) ------ #### 题目大意 有n个岛，n条无向边(保证每个岛都有边连到)。走过的路和岛不可以重走，可以坐船。 坐船要求之前没有任何使用过的船加上道路可以到达那个点才可以坐船。 求最长可以走多远。 ---------- #### 解题思路 首先这是一棵基环树森林，根据乘船的规定其实就是每棵基环树只可以走一次。这时候我们就可以发现答案就是每棵基环树的直径之和。然后我们考虑如何计算直径。 将环看作根。我们发现答案只有两种可能 1.经过根 2.不经过根 我们考虑不经过根的，计算出$f_x$($f_x$表示x子树中离x最远的点的距离)，然后用求树的直径的方法求出根以下每棵子树的直径并记录。然后我们计算经过根的。 假设环的节点为$s$集合，那么答案就是$max(f_{s_i}+f_{s_j}+dis_{i\sim j})$ dis表示环上i到j的最远距离。 我们可以通过单调队列dp计算出答案。 --------- #### code ```cpp #include<cstdio> #include<algorithm> #include<queue> #include<iostream> #define N 1000010 #define lls long long using namespace std; struct node{ int to,next,w; }a[2*N]; int n,x,y,tot,t; lls ls[N],in[N],cr[2*N],v[N],k[N],f[N],d[N],dis[2*N],ans,q[2*N]; void addl(int x,int y,int w)//加边 { a[++tot].to=y; a[tot].w=w; a[tot].next=ls[x]; ls[x]=tot; in[y]++; } void dfs(int now,int k){ v[now]=k; for (int i=ls[now];i;i=a[i].next){ int y=a[i].to; if(!v[y]) dfs(y,k); } }//标记联通块 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]--; d[v[now]]=max(d[v[now]],f[now]+f[y]+a[i].w); f[y]=max(f[y],f[now]+a[i].w); if(in[y]==1) q[++r]=y; } } } }//拓扑排序求环 void dp(int t,int x){ int m=0,y=x,i; do{ cr[++m]=f[y];in[y]=1; for(i=ls[y];i;i=a[i].next){ if(in[a[i].to]>1){ dis[m+1]=dis[m]+a[i].w; y=a[i].to; break; } } }while(i);//预处理环的数据 if(m==2){ int l=0; for (int i=ls[y];i;i=a[i].next) if(a[i].to==x) l=max(l,a[i].w); d[t]=max(d[t],f[x]+f[y]+l); return; }//特批 for(int i=ls[y];i;i=a[i].next){ if(a[i].to==x) { dis[m+1]=dis[m]+a[i].w; break; } }//连接首尾 for (int i=1;i<=m;i++){ cr[i+m]=cr[i]; dis[m+i]=dis[m+1]+dis[i]; }//复制一份放在后面 int l=1,r=0; q[++r]=1; for (int i=2;i<2*m;i++){ while(l<=r&&i-q[l]>=m) l++; d[t]=max(dis[i]-dis[q[l]]+cr[i]+cr[q[l]],d[t]); while(l<=r&&cr[q[r]]+dis[i]-dis[q[r]]<=cr[i]) r--; q[++r]=i; }//单调队列dp } int main(){ scanf("%d",&n); for (int i=1;i<=n;i++){ scanf("%d%d",&x,&y); addl(i,x,y); addl(x,i,y); } for (int i=1;i<=n;i++) if (!v[i]) dfs(i,++t); topsort(); for (int i=1;i<=n;i++){ if(in[i]>1&&!k[v[i]]) { k[v[i]]=1; dp(v[i],i); ans+=d[v[i]]; } } printf("%lld",ans); } ``` ------- ## 四.瞎吹总结 ----- 最后来梳理一下学了的内容 对于一个n点n边的图，图中只存在一个环。被称为基环树。 一般解决方法都是如果是树形dp。进对环部分进行环形dp的操作。不然可以考虑断环法。 对于每道题，要找到最好的解决方法