[Luogu4630][APIO2018]Duathlon 铁人两项

luogu

题目描述

比特镇的路网由 \(m\) 条双向道路连接的 \(n\) 个交叉路口组成。

最近，比特镇获得了一场铁人两项锦标赛的主办权。这场比赛共有两段赛程：选手先完成一段长跑赛程，然后骑自行车完成第二段赛程。

比赛的路线要按照如下方法规划：

在规划路径之前，镇长想请你帮忙计算，总共有多少种不同的选取 \(s,c\) 和 \(f\) 的方案，使得在第 \(2\) 步中至少能设计出一条满足要求的路径。

sol

像我这种连圆方树都不会的菜鸡就活该\(APIO\)被卡线qaq。

把圆方树建出来，在树中任意枚举两个圆点作为 \(s\) 和 \(f\) ，然后考虑 \(c\) 有多少种选法。

应该是这两个点路径上的每个点双中的点都可以选吧。

令每个圆点的权值为\(-1\)，每个方点的权值为点双大小，那么选法应该就是两点路径的权值和吧。

也就是说我们要求圆方树上\(n^2\)条圆点到圆点的路径的权值和。

很容易想到计算每个点被算了多少次。这样就可以在线性的时间内做完这题了。

code

#include<cstdio>

#include<algorithm>

#include<cstring>

using namespace std;

int gi(){

	int x=0,w=1;char ch=getchar();

	while ((ch<'0'||ch>'9')&&ch!='-') ch=getchar();

	if (ch=='-') w=0,ch=getchar();

	while (ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();

	return w?x:-x;

}

const int N = 4e5+5;

int n,tot,m,dfn[N],low[N],tim,S[N],val[N],sz[N],sum;

long long ans;

struct Graph{

	int to[N],nxt[N],head[N],cnt;

	void link(int u,int v){

		to[++cnt]=v;nxt[cnt]=head[u];head[u]=cnt;

	}

}G1,G2;

void Tarjan(int u){

	dfn[u]=low[u]=++tim;S[++S[0]]=u;

	sz[u]=1;val[u]=-1;

	for (int e=G1.head[u];e;e=G1.nxt[e]){

		int v=G1.to[e];

		if (!dfn[v]){

			Tarjan(v),low[u]=min(low[u],low[v]);

			if (low[v]>=dfn[u]){

				G2.link(u,++tot);val[tot]=1;int x=0;

				do{

					x=S[S[0]--];G2.link(tot,x);

					sz[tot]+=sz[x];++val[tot];

				}while (x!=v);

				sz[u]+=sz[tot];

			}

		}

		else low[u]=min(low[u],dfn[v]);

	}

}

void dfs(int u){

	if (u<=n) ans+=1ll*(sum-1)*val[u];

	ans+=1ll*(sum-sz[u])*sz[u]*val[u];

	for (int e=G2.head[u];e;e=G2.nxt[e]){

		int v=G2.to[e];

		ans+=1ll*(sum-sz[v])*sz[v]*val[u];

		dfs(v);

	}

}

int main(){

	tot=n=gi();m=gi();

	while (m--){

		int u=gi(),v=gi();

		G1.link(u,v);G1.link(v,u);

	}

	for (int i=1;i<=n;++i) if (!dfn[i]) Tarjan(i),sum=sz[i],dfs(i);

	printf("%lld\n",ans);return 0;

}