圆方树学习笔记

oi wiki

模板

void tarjan(int u)
{
	dfn[u]=low[u]=++ct; st[++tp]=u; tot++;
	for(int v:g[u])
		if(!dfn[v])
		{
			tarjan(v); low[u]=min(low[v],low[u]);
			if(low[v]>=dfn[u]) // 注意这里是 dfn[u]
			{
				nyf++; int x;
				do
				{
					x=st[tp--]; yf[nyf].push_back(x),yf[x].push_back(nyf); 
				} while(x!=v); // 注意这里是 v
				yf[nyf].push_back(u),yf[u].push_back(nyf); // 注意这里要把 u 也扔进去
			}
		}
		else low[u]=min(low[u],dfn[v]);	// 注意这里是 dfn
}

例题

[APIO2018] 铁人两项

https://www.luogu.com.cn/problem/P4630

转化成求路径并的点数，转成圆方树，记圆点权值 -1 方点权值点双大小，就可以转化成所有简单路径路径权值和，考虑统计每个点的贡献即可

代码

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 1e5+5;
int n,m;
vector<int> g[N],yf[N<<1];
int nyf,dfn[N],low[N],st[N],tp,ct;
int w[N<<1],sz[N<<1],tot;
void tarjan(int u)
{
	dfn[u]=low[u]=++ct; st[++tp]=u; w[u]=-1; tot++;
	for(int v:g[u])
		if(!dfn[v])
		{
			tarjan(v); low[u]=min(low[v],low[u]);
			if(low[v]>=dfn[u])
			{
				nyf++; int x;
				do
				{
					x=st[tp--]; yf[nyf].push_back(x),yf[x].push_back(nyf); w[nyf]++;
				} while(x!=v);
				yf[nyf].push_back(u),yf[u].push_back(nyf); w[nyf]++;
			}
		}
		else low[u]=min(low[u],dfn[v]);	
}
ll ans=0;
void dfs(int u, int prv)
{
	sz[u]=(u<=n);
	for(int v:yf[u]) if(v!=prv) dfs(v,u),ans+=2ll*sz[u]*sz[v]*w[u],sz[u]+=sz[v];
	ans+=2ll*sz[u]*(tot-sz[u])*w[u];
}
int main()
{
	scanf("%d%d",&n,&m); nyf=n;
	for(int i=1,u,v; i<=m; i++) scanf("%d%d",&u,&v),g[u].push_back(v),g[v].push_back(u);
	for(int i=1; i<=n; i++) if(!dfn[i]) ct=0,tot=0,tarjan(i),tp--,dfs(i,i);
	printf("%lld\n",ans);
	return 0;
}

P4606 [SDOI2018]战略游戏

https://www.luogu.com.cn/problem/P4606

转成圆方树上路径并的点集大小\(-\left| S\right|\)

求点集大小：把点权扔到上面的边，转化成树上走一遍的边权和的一半，把点集按 dfn 排序，两两求距离即可，注意特判最上面的点

代码

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 1e5+5, M = 2e5+5;
int _,n,m,q;
vector<int> g[N],yf[M];
int dfn[N],low[N],st[N],tp,dfc,nyf;
void tarjan(int u)
{
	dfn[u]=low[u]=++dfc; st[++tp]=u;
	for(int v:g[u])
		if(!dfn[v])
		{
			tarjan(v); low[u]=min(low[u],low[v]);
			if(low[v]>=dfn[u])
			{
				nyf++; for(int x; x!=v; tp--) x=st[tp],yf[nyf].push_back(x),yf[x].push_back(nyf);
				yf[nyf].push_back(u),yf[u].push_back(nyf);
			}
		}
		else low[u]=min(low[u],dfn[v]);
}
int dfn2[M],top[M],sz[M],d[M],f[M],hson[M],dfi2[M],fa[M];
void slpf1(int u, int prv)
{
	fa[u]=prv; sz[u]=1;
	for(int v:yf[u]) if(v!=prv)
	{
		d[v]=d[u]+1; f[v]=f[u]+(v<=n); slpf1(v,u); sz[u]+=sz[v];
		if(sz[v]>sz[hson[u]]) hson[u]=v;
	}
}
void slpf2(int u)
{
	dfn2[u]=++dfc; dfi2[dfn2[u]]=u; if(hson[u]) top[hson[u]]=top[u],slpf2(hson[u]);
	for(int v:yf[u]) if(v!=fa[u] and v!=hson[u]) top[v]=v,slpf2(v);
}
int lca(int u, int v)
{
	while(top[u]!=top[v])
	{
		if(d[top[u]]<d[top[v]]) swap(u,v);
		u=fa[top[u]];
	}
	return d[u]<d[v]?u:v;
}
int dist(int u, int v) { return f[u]+f[v]-(f[lca(u,v)]<<1); }
int p[N];
int main()
{
	scanf("%d",&_);
	while(_--)
	{
		scanf("%d%d",&n,&m);
		for(int i=1; i<=n; i++) g[i].clear(); for(int i=1; i<=(n<<1); i++) yf[i].clear();
		for(int i=1,u,v; i<=m; i++) scanf("%d%d",&u,&v),g[u].push_back(v),g[v].push_back(u);
		for(int u=1; u<=n; u++) dfn[u]=low[u]=0; dfc=tp=0; nyf=n; tarjan(1);
		for(int u=1; u<=nyf; u++) dfn2[u]=top[u]=sz[u]=d[u]=f[u]=hson[u]=dfi2[u]=fa[u]=0;
		dfc=0; slpf1(1,0); top[1]=1; slpf2(1);
		scanf("%d",&q); int s;
		while(q--)
		{
			scanf("%d",&s); for(int i=1; i<=s; i++) scanf("%d",&p[i]);
			sort(p+1,p+s+1, [&] (const int &a, const int &b) { return dfn2[a]<dfn2[b]; });
			int t=p[s]; ll ans=dist(p[s],p[1]);
			for(int i=1; i<s; i++) ans+=dist(p[i],p[i+1]),t=lca(t,p[i]);
			printf("%lld\n",(ans>>1)+(t<=n)-s);
		}
	}
	return 0;
}