圆方树

前置知识

圆方树

用于维护仙人掌或无向图的重构图。其实本质上就是缩了点，但又没完全缩点的点双连通分量。

直接告诉你构建方法，先求出点双连通分量，然后为每个点双连通分量创造一个方点，而原图上的点为圆点。我们在新图上把一个连通分量内的所有点与对应方点连接，得到一棵树（或者不连通图得到森林），这个就是圆方树。

圆方树的构建:

void dfs1(int u,int f){
	dfn[u]=low[u]=++idx;
	sta[++top]=u;
	if(u==f and G1.head[u]==-1){
		++Ctot;--top;
		G2.join(Ctot,u);
		G2.join(u,Ctot);
	}
	for(int i=G1.head[u];~i;i=G1.nxt[i]){
		int v=G1.to[i].v;
		if(!dfn[v]){
			dfs1(v,u);
			low[u]=std::min(low[u],low[v]);
			if(low[u]>=dfn[u]){
				++Ctot;
				while(1){
					G2.join(sta[top],Ctot);
					G2.join(Ctot,sta[top]);
					if(sta[top]==v){
						--top;
						break;
					}
					--top;
				}
				G2.join(u,Ctot);
				G2.join(Ctot,u);
			}
		}else if(v!=f){
			low[u]=std::min(low[u],dfn[v]);
		}
	}
}

构建还是简单的吧，我认为圆方树难的地方在于如何利用这么一幅图去求解答案。

例题分析

铁人二项

题目大意：对于一张图，\(n\) 个点 \(m\) 条边，无重边无自环，问有多少个三元组 \(\)，满足存在一天简单路径从 \(a\) 出发再到达 \(b\) 再到达 \(c\) 。

首先建立圆方树，然后我们会发现一个结论。对于一个点双连通分量，其中任意三点都满足题目描述的三元组。

证明一下：考虑点双连通分量的定义，每个点之间存在两条及以上无交的简单路径互达。那么如果我们从 \(a\) 走到 \(b\) ,一定存在一条路径不经过刚才走过的点到达 \(c\)，结论成立。

因此，我们对于题目中的一组三元组，可以转换成圆方树上的两个圆点之间的路径，中介点可以是两个圆点路径之上的每一个方点下的每一个圆点或者路径上的圆点。

那么我们换一下思路，计算对于每个点被多少个路径经过即可。然后对于方点，其贡献是这个点双的大小与覆盖其的路径数的乘积，而对于圆点，其贡献为覆盖其的路径数乘 \(-1\) ，这是因为它被在与其相连的两个方点计算两次，所以在此减去一份。

代码如下：

#include
#define ll long long
#define db double
#define filein(a) freopen(#a".in","r",stdin)
#define fileot(a) freopen(#a".out","w",stdout)
#define sky fflush(stdout);
#define Better_IO 1
namespace IO{
	inline bool blank(const char &c){
		return c==' ' or c=='\n' or c=='\t' or c=='\r' or c==EOF;
	}
	#if Better_IO==true
		char buf[(1<<20)+3],*p1(buf),*p2(buf);
		char buf2[(1<<20)+3],*p3(buf2);
		const int lim=1<<20;
		inline char gc(){
			if(p1==p2) p2=(p1=buf)+fread(buf,1,lim,stdin);
			return p1==p2?EOF:*p1++;
		}
		#define pc putchar
	#else
		#define gc getchar
		#define pc putchar
	#endif
	inline void gs(char *s){
		char ch=gc();
		while(blank(ch) ) {ch=gc();}
		while(!blank(ch) ) {*s++=ch;ch=gc();}
		*s=0;
	}
	inline void gs(std::string &s){
		char ch=gc();s+='#';
		while(blank(ch) ) {ch=gc();}
		while(!blank(ch) ) {s+=ch;ch=gc();}
	}
	inline void ps(char *s){
		while(*s!=0) pc(*s++);
	}
	inline void ps(const std::string &s){
		for(auto it:s) 
			if(it!='#') pc(it);
	}
	template
	inline void read(T &s){
		s=0;char ch=gc();bool f=0;
		while(ch<'0'||'9'
	inline void read(T &s,A &...a){
		read(s);read(a...);
	}
};
using IO::read;
using IO::gs;
using IO::ps;
const int N=1e5+3;
const int M=2e5+3;
int n,m,Q;
struct EdgeList1{
	std::vectorhead,nxt;
	struct edge{
		int u,v;
	};
	std::vectorto;
	inline void join(int u,int v){
		nxt.push_back(head[u]);
		head[u]=to.size();
		to.push_back({u,v});
	}
}G1,G2;
int low[N],dfn[N],idx;
int sta[N],top;
int Ctot,sum;
int val[N<<1];
void dfs1(int u,int f){
	dfn[u]=low[u]=++idx;
	sta[++top]=u;
	++sum;
	if(u==f and G1.head[u]==-1){
		++Ctot;
		G2.join(Ctot,u);
		G2.join(u,Ctot);
	}
	for(int i=G1.head[u];~i;i=G1.nxt[i]){
		int v=G1.to[i].v;
		if(!dfn[v]){
			dfs1(v,u);
			low[u]=std::min(low[u],low[v]);
			if(low[v]>=dfn[u]){
				++Ctot;
				val[Ctot]=0;
				while(1){
					G2.join(sta[top],Ctot);
					G2.join(Ctot,sta[top]);
					++val[Ctot];
					if(sta[top]==v){
						--top;
						break;
					}
					--top;
				}
				G2.join(u,Ctot);
				G2.join(Ctot,u);
				++val[Ctot];
			}
		}else if(v!=f){
			low[u]=std::min(low[u],dfn[v]);
		}
	}
}
ll ans=0;
int sz[N<<1];
void dfs2(int u,int f){
	sz[u]=(u<=n);
	for(int i=G2.head[u];~i;i=G2.nxt[i]){
		int v=G2.to[i].v;
		if(v==f) continue;
		dfs2(v,u);
		ans+=2ll*val[u]*sz[u]*sz[v];
		sz[u]+=sz[v];
	}
	ans+=2ll*val[u]*sz[u]*(sum-sz[u]);
}
int main(){
	filein(a);fileot(a);
	read(n,m);
	G1.head.resize(n+3,-1);
	G2.head.resize(2*n+3,-1);
	for(int i=1;i<=n;++i){
		val[i]=-1;
	}
	for(int i=1;i<=m;++i){
		int u,v; read(u,v);
		G1.join(u,v); G1.join(v,u);
	}
	Ctot=n;
	for(int i=1;i<=n;++i){
		if(!dfn[i]){
			top=0; sum=0;
			dfs1(i,i);
			dfs2(i,i);
		}
	}
	printf("%lld\n",ans);
	return 0;
}