基环树

猿柒

6个月前更新

基环树，也是环套树，简单地讲就是树上在加一条边。它形如一个环，环上每个点都有一棵子树的形式。因此，对基环树的处理大部分就是对树处理和对环处理。显然，难度在于后者。

找环

这是几乎所有基环树处理的第一步。扣环的方法多种多样，各有千秋，反正都是O(n)的。这里贴一下本人扣环的代码。这个东西，稍微博采众长一下就好了。

有一个环，把这个环抽出来，这样整个图就变成了一个环上面有几个子树。然后对子树进行操作，将信息合并到环上的节点，最后就能把一个图上的问题降到环上处理。

忽略掉导致整棵树出现环的一条边，然后对剩下的树进行操作。

例题

P2607 [ZJOI2008] 骑士

因为一个骑士有且只有一个最讨厌的人
而且这个骑士不会讨厌自己
即该图中是没有自环的
然后从网上搜的很多题解都是用无向图存边
然后用一些高超的技巧(如位运算)判断卡掉无向二元环
事实证明存无向图是完全没有必要的
因为本身有向图就携带着指向上一个节点的信息
而且这个信息更利于维护我们删边之后的操作
这样不仅省去了判断的麻烦
还有利于维护信息
何乐而不为?
所以考虑这个有向图
我们把x所讨厌的人y设为x的父亲节点
这样考虑每一个人都有且只有一条出边
所以对一个”联通块”
只有根节点有机会形成环
即环一定包含根节点
为什么呢?
因为一个点的出度只能为1
考虑非根节点
它的出度一定是贡献给它的父亲的
而根节点它的出度只能贡献给它的后代
(这里的”根节点””叶子节点”都只是为了描述方便,并不严谨,也许可以理解为”删边以后的叶子和根”?)
所以我们又解决了一个问题:
每个联通块内有且只有一个简单环
这样我们考虑把每个联通块的环上删一条边
这样它必然构成树
然后要注意
删掉的边所连接的两点x,y
是不能同时选的
所以我们分别强制x,y其中一个点不选
对新树跑DP
显然相邻的点是不能选的
所以得到状态转移方程:
用f[i][0/1]表示以i为根节点的子树选i/不选i所能获得的最大价值
则 f[i][0]=sigema(max(f[son][0],f[son][1])); for each son of i
f[i][1]=sigema(f[son][0]); for each son of i
应该就很清楚了
再一个细节就是
答案会爆int

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e6+10;
int n;
int to[N*2],ne[N*2],h[N*2],cnt;
bool vis[N];
int l,r;
int f[N][3];
int w[N],ans;
void add(int x,int y){
	to[++cnt]=y;
	ne[cnt]=h[x];
	h[x]=cnt;
}
void find(int u,int root){
	vis[u]=true;
	for(int i=h[u];i;i=ne[i]){
		int v=to[i];
		if(v==root){
			l=u,r=v;
			return ;
		}
		if(vis[v])continue;
		find(v,root);
	}
}
int dfs(int u,int root){
	f[u][0]=0;
	f[u][1]=w[u];
	for(int i=h[u];i;i=ne[i]){
		int v=to[i];
		if(v==root)continue;
		dfs(v,root);
		f[u][0]+=max(f[v][1],f[v][0]);
		f[u][1]+=f[v][0];
	}
	return f[u][0];
}
signed main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		int v;
		cin>>w[i]>>v;
		add(v,i);
		
	}
	for(int i=1;i<=n;i++){
		if(!vis[i]){
			l=r=0;
			find(i,i);//断边
			if(l){
				int sum1=dfs(l,l);
				int sum2=dfs(r,r);
				ans+=max(sum1,sum2);
			}
		}
	}
	cout<<ans<<endl;
	return 0;
}

P1399 [NOI2013] 快餐店

作为一道NOI题，这道题是一道好(难)题，这道题给了一张N点N边的图，让你在图中找一点到图中最远点最近，输出这个距最远点最近的距离，首先问题降低，如果这是一棵树，求一点到最远点的最短距离，那其实就是树的直径的一半，但是这道题是一颗环套树，所以现在分两种情况
1 这个环套树的最长路径不经过环
这种情况是比较简单的，我们首先通过一些手段求出这个环，并记录环的信息，(方法：tarjan，dfs，并查集)；然后枚举每一个环上的点，对这些点下的子树求直径，取这些直径的最大值，记为ans1.
以上操作找环是O(n+m),对所有环上的点求子树是O(n)的，所以这一步总复杂度O(n+m);
时间复杂度的原因：每个点只便利了一次
2 这个环套树的最长路径经过环
这种情况是比较复杂的，O(n * n) 60分算法是枚举环上的断点，是无法AC的，因此需要优化。
规定环上每个点为1–> circle_cnt
A[i]表示(前缀链长度+当前换上节点子树最大深度)
B[i]表示(前缀中两个点子树的最大深度+两点之间的距离)
C[i]表示(后缀链长度+当前换上节点子树最大深度)
D[i]表示(后缀中两个点子树的最大深度+两点之间的距离) 因此当我们枚举到断裂环上i与i+1点之间的边时，
答案为max(max(B[i],D[i]),A[i]+C[i+1]+(1–>circle_cnt点的边权))；
这个式子的含义是取
max((前缀中的最大直径)，(后缀中的最大直径)，(前缀i与后缀i+1跨过1和circle_cnt点之间的边所组成的直径))
显然的我们要保留这里求出的最小值，因为这里求出的路径是所有路径都有可能，不一定是两点间的最短路，这里我就有疑问，但就像第一个样例，最长的路是3->1->4->2距离为5，事实上有3->1->2->4距离为4的路存在，这样无疑缩短了求的直径。
记这个最小值为ans2.这个步骤复杂度时O(circle_cnt)
最终输出max(ans1,ans2)/2;
How interesting it is!
以上就是主要思路，对于经过环上的路径也可以通过线段树来求，但是没有这种方法更优。

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int to[N*2],we[N*2],ne[N*2],h[N*2],idx;
int n;
int vis[N],f[N],w[N],inc[N],cv[N],cw[N],cn;
double d[N],A[N],B[N],C[N],D[N],ans1,ans2=1e18;
void add(int x,int y,int z){
	we[++idx]=z;
	to[idx]=y;
	ne[idx]=h[x];
	h[x]=idx;
}
int find(int u){
	vis[u]=1;
	for(int i=h[u];i;i=ne[i]){
		int v=to[i];
		if(v!=f[u]){
			f[v]=u;
			w[v]=we[i];
			if(!vis[v]){
				if(find(v))return 1;
			}
			else {
				int p=u;
				while(1){
					inc[p]=1;
					cv[++cn]=p;
					cw[cn]=w[p];
					p=f[p];
					if(p==u)break;
				}
				return 1;
			}
		}
	}
	return 0;
}
void dfs(int u,int fa){
	for(int i=h[u];i;i=ne[i]){
		int v=to[i],wei=we[i];
		if(!inc[v]&&v!=fa){
			dfs(v,u);
			ans1=max(ans1,d[u]+d[v]+wei);
			d[u]=max(d[u],d[v]+wei);
		}
	}
}
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		int x,y,z;
		cin>>x>>y>>z;
		add(x,y,z);
		add(y,x,z);
	}
	find(1);//寻找环
	for(int i=1;i<=cn;i++){
		dfs(cv[i],0);//求直径ans1 
	}
	double sum=0,maxn=0;
	//求前缀 
	for(int i=1;i<=cn;i++){
		sum+=cw[i-1];
		A[i]=max(A[i-1],sum+d[cv[i]]);
		B[i]=max(B[i-1],maxn+d[cv[i]]+sum);
		maxn=max(maxn,d[cv[i]]-sum); 
	}
	//求后缀
	sum=maxn=0;
	double cn_1=cw[cn];
	cw[cn]=0;
	for(int i=cn;i>=1;i--){
		sum+=cw[i];
		C[i]=max(C[i+1],sum+d[cv[i]]);
		D[i]=max(D[i+1],maxn+d[cv[i]]+sum);
		maxn=max(maxn,d[cv[i]]-sum);
	}
	double res;
	for(int i=1;i<cn;i++){
		res=max(max(B[i],D[i+1]),A[i]+C[i+1]+cn_1);
		ans2=min(ans2,res);
	}
	ans2=min(ans2,B[cn]);
	printf("%.1lf",max(ans1,ans2)/2);
	return 0;
}

P5022 [NOIP2018 提高组] 旅行

可以看到，对于一个环，假设有m条边，那么无论如何旅行，有且仅有m-1条边能被访问，也就是说，旅行的路径仍旧是一棵树。
也就是每次暴力的割断环上的每一条边，然后跑一遍，找一个字典序最小的就好了。
把所有的边存了一遍，然后两端点的点属于同一个点双的边就在环上了。

#include<bits/stdc++.h>
using namespace std;
const int N=5e4+10;
int cnt,poi,du,dv,vis[N];
vector<int>e[N];
pair<int,int>ed[N];
vector<int>path(N,N);
int n,m;
bool dfs(int u){
	if(!poi){
		if(u>path[cnt])return 1;
		if(u<path[cnt])poi=-1;
	}
	vis[u]=1;
	path[cnt++]=u;
	for(int i=0;i<e[u].size();i++){
		int v=e[u][i];
		if(vis[v])continue;
		if(v==du&&u==dv)continue;
		if(v==dv&&u==du)continue;
		if(dfs(v))return 1;
	}
	return 0;
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		int a,b;
		cin>>a>>b;
		e[a].push_back(b);
		e[b].push_back(a);
		ed[i]={a,b};
	}
	for(int i=1;i<=n;i++){
		sort(e[i].begin(),e[i].end());
	}
	if(n-1==m)dfs(1);
	else{
		for(int i=1;i<=m;i++){
			du=ed[i].first,dv=ed[i].second;
			memset(vis,0,sizeof vis);
			cnt=poi=0;
			dfs(1);
		}
	}
	for(int i=0;i<n;i++){
		cout<<path[i]<<" ";
	}
	return 0;
}

评分

欢迎为Ta评分