基环树学习笔记

基环树，又称环套树。顾名思义，就是有环的树，所以它是个图。

概念及定义

基环树，是一个有 $n$ 个节点和 $n$ 条边组成的无向连通图。由于比树多了条边，所以它会出现环。

很明显基环树只有一个环，因为如果有多个环的话，那么整张图不会联通。

而基环树森林则是由许多连通块构成的无向图，满足每个连通块都是基环树。

一般来讲，只要看到 $n$ 个点 $n$ 条边、每个点都有且仅有一个仇人/上级/xxx 这种条件，这个图就一定是基环树森林。

基环树的例子：

处理方法

常见的题型就是在基环树上 dp。

有两种方法，第一种是把环拎出来，对于环下面挂着的树进行 dp，然后信息合并到环上处理：

还有一种是断掉环的一条边，然后分类讨论进行 dp，最后合并答案。

比较常见的是第二种。

经典题目

CF711D Directed Roads

链接

由于有 $n$ 个点 $n$ 条边， $i$ 只会连向 $a_i$ ，所以是个基环树。

但是又没说联通，所以是基环树森林。

可以先找出所有的环，那么不被环包含的边可以随便定方向。

设当前找到的环的长度为 $len$ ，那么想要形成环只会有两种定方向的方式，所以不形成环的方案数是 $2^{len}-2$ 。

答案即为 $2^{n-\sum len}\sum 2^{len}-2$ 。

代码如下：

#include <iostream>
#include <cstdio>

using namespace std;

const long long S=500005,MS=200005,mod=1000000007;

int n;
int esum,to[S],nxt[S],h[MS];
int dep[MS],vis[MS];

inline void add(int x,int y)
{
	to[++esum]=y;
	nxt[esum]=h[x];
	h[x]=esum;
}

void dfs(int u,int fa,int &len)
{
	dep[u]=dep[fa]+1;
	vis[u]=1;
	for(int i=h[u],cnt=0;i;i=nxt[i])
	{
		int v=to[i];
		if(v==fa)
		{
			if(cnt==1)
			{
				len=2;
			}
			cnt++;
			continue;
		}
		if(vis[v]==1)
		{
			len=dep[u]-dep[v]+1;
			continue;
		}
		dfs(v,u,len);
	}
	vis[u]=2;
}

inline long long qpow(long long a,long long b)
{
	long long res=1,tmp=a;
	while(b>0)
	{
		if(b&1)
		{
			res=res*tmp%mod;
		}
		tmp=tmp*tmp%mod;
		b>>=1;
	}
	return res;
}

int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		int x;
		scanf("%d",&x);
		add(i,x);
		add(x,i);
	}
	long long ans=1,sum=n;
	for(int i=1;i<=n;i++)
	{
		if(vis[i]==0)
		{
			int len;
			dfs(i,0,len);
			sum-=len;
			ans=ans*(qpow(2,len)-2)%mod;
		}
	}
	printf("%lld\n",qpow(2,sum)*ans%mod);
	return 0;
}

P1453 城市环路

链接

很容易发现是个基环树，那么可以使用第二种方法，断掉一条边之后做没有上司的舞会。

但是有一些细节。首先断掉的边还是存在的，设这条边连接的两点为 $x,y$ ，那么最后要么 $x$ 不选 $y$ 选，要么都不选，要么 $x$ 选 $y$ 不选。前两种情况很好做，但是最后一种情况就有点难了。需要将 $y$ 的人流量设为 $-inf$ 再 dp。

最后需要注意一种很烦人的环：

这种情况下断掉 $u,v$ 之间的边后它们会不连通，所以断边后需要分别以 $u$ 和 $v$ 为根做 dp，然后计算贡献。

这题数据太水了所以上图的情况如果不特判也能过。

P2607 [ZJOI2008]骑士

链接

其实是城市环路的加强版，注意一下是个基环树森林即可。

P4381 [IOI2008] Island

链接

首先读题，可以发现这是个基环树森林。然后看一下坐船的条件：

你可以选择这种方法，仅当没有任何桥和以前使用过的渡船的组合可以由 S 走到 D (当检查是否可到达时，你应该考虑所有的路径，包括经过你曾游览过的那些岛)。

再结合一下样例解释，你就会惊喜的发现，坐船其实就是从基环树森林里的一棵基环树走到另一棵基环树上，然后一棵基环树走了之后就不能回来了。

所以问题转化为所有基环树的最长链之和。

首先考虑单棵基环树的最长链。把环拎出来后，最长链的组成方法有：

一棵吊着的树的直径
一棵吊着的树的高度+环上的一段边+另一棵不同的吊着的树的高度

所以我们可以使用第一种方法，计算出每棵吊着的树的直径和高度，然后考虑合并。

第一种直径的组成方式很明显可以处理，而第二种就有点麻烦了。我们记编号为 $i$ 的节点的子树的深度为 $w_i$ ，然后断环为链，很明显环变成了这样的东西：

然后做滑动的窗口即可。

代码如下：

#include <iostream>
#include <cstdio>
#include <vector> 

using namespace std;

const long long S=2000005,MS=1000005;

struct node
{
	int id;
	long long w,val;
}cir[MS];

int n;
int esum,to[S],nxt[S],h[MS];
long long c[S];
int vis[MS];
long long dp[MS][2],maxdep[MS],trd;
long long sum[MS],que[MS];
int tot;

inline void add(int x,int y,long long w)
{
	to[++esum]=y;
	c[esum]=w;
	nxt[esum]=h[x];
	h[x]=esum;
}

bool dfs(int u,int fa)
{
	bool res=false;
	vis[u]=1;
	for(int i=h[u],cnt=0;i;i=nxt[i])
	{
		int v=to[i];
		if(v==fa)
		{
			if(cnt==1)
			{
				cir[++tot]=(node){u,0,c[i]};
				vis[fa]=4;
				res=true;
			}
			cnt++;
			continue;
		}
		if(vis[v]==1)
		{
			cir[++tot]=(node){u,0,c[i]};
			vis[v]=4;
			res=true;
			continue;
		}
		if(vis[v]!=0)
		{
			continue;
		}
		if(dfs(v,u))
		{
			if(vis[u]!=2)
			{
				cir[++tot]=(node){u,0,c[i]};
				if(vis[u]==4)
				{
					vis[fa]=2;
				}
			}
			else
			{
				vis[fa]=2;
			}
			res=true;
		}
	}
	vis[u]=2;
	return res;
}

void dfs2(int u,int fa,int rt)
{
	dp[u][0]=dp[u][1]=0;
	maxdep[u]=0;
	for(int i=h[u];i;i=nxt[i])
	{
		int v=to[i];
		long long w=c[i];
		if(v==fa||v==rt)
		{
			continue;
		}
		dfs2(v,u,rt);
		maxdep[u]=max(maxdep[u],w+maxdep[v]);
		long long val=w+dp[v][0];
		if(val>=dp[u][0])
		{
			dp[u][1]=dp[u][0];
			dp[u][0]=val;
		}
		else if(val>=dp[u][1])
		{
			dp[u][1]=val;
		}
	}
	trd=max(trd,dp[u][1]+dp[u][0]);
}

int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		int x;
		long long L;
		scanf("%d%lld",&x,&L);
		add(i,x,L);
		add(x,i,L);
	}
	long long ans=0;
	for(int i=1;i<=n;i++)
	{
		if(vis[i]==0)
		{
			tot=0;
			dfs(i,0);
			long long curans=0;
			int m=tot;
			for(int j=1;j<=m/2;j++)
			{
				swap(cir[j],cir[m-j+1]);
			}
			for(int j=1;j<=m;j++)
			{
				int u=cir[j].id;
				trd=0;
				dfs2(u,cir[j==1?m:j-1].id,cir[j==m?1:j+1].id);
				curans=max(curans,trd);
				cir[j].w=maxdep[u];
			}
			for(int j=1;j<=m;j++)
			{
				cir[++tot]=cir[j];
			}
			int newsiz=m*2-1;
			for(int j=1;j<=newsiz;j++)
			{
				sum[j]=sum[j-1]+cir[j].val;
			}
			int hed=1,til=0;
			for(int j=1;j<=newsiz;j++)
			{
				while(hed<=til&&que[hed]<=j-m)
				{
					hed++;
				}
				if(hed<=til)
				{
					curans=max(curans,(cir[que[hed]].w+sum[j-1]-sum[que[hed]-1])+cir[j].w);
				}
				while(hed<=til&&(cir[que[til]].w+sum[j-1]-sum[que[til]-1])<=cir[j].w)
				{
					til--;
				}
				que[++til]=j;
			}
			ans+=curans;
		}
	}
	printf("%lld\n",ans);
	return 0;
}

细节

最重要的细节就是

这种环的处理和基环树森林的处理。