【APIO2018】铁人两项

题目描述

大意就是给定一张无向图，询问三元组\((s,c,f)\)中满足\(s\neq c\neq f\)且存在\((s\to c\to f)\)的简单路径（每个点最多经过一次）的数量。

\(1\leq n,\leq 10^5,1\leq m\leq 2*10^5\)

我们考虑枚举\(s,f\)然后计算中间\(c\)的数量。我们发现对于一张图上统计两点之间路径上的点数量很好做。于是我们考虑建圆方树。

我们将圆点的权值定为\(-1\)，将方点的权值定为与其直接相连的圆点的数量。\(u\)到\(v\)路径上可能经过的点的数量就是圆方树上\(u\to v\)路径上除了\(u,v\)的点权之和\(-2\)。

于是我们用树形\(\text{DP}\)，计算每个点对答案的贡献。

代码：

#include<bits/stdc++.h>

#define ll long long

#define N 200005

using namespace std;

inline int Get() {int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9') {if(ch=='-') f=-1;ch=getchar();}while('0'<=ch&&ch<='9') {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}return x*f;}

int n,m;

int tot;

struct graph {

	int to[N<<2],nxt[N<<2];

	int h[N],cnt;

	void add(int i,int j) {

		to[++cnt]=j;

		nxt[cnt]=h[i];

		h[i]=cnt;

	}

}s,g;

int dfn[N],low[N],id;

int st[N];

int val[N];

void work(int v,int to) {

	tot++;

	g.add(v,tot);

	val[tot]=1;

	while(1) {

		int j=st[st[0]--];

		val[tot]++;

		g.add(tot,j);

		if(j==to) return ;

	}

}

ll tot_size;

void tarjan(int v,int fr) {

	tot_size++;

	dfn[v]=low[v]=++id;

	st[++st[0]]=v;

	for(int i=s.h[v];i;i=s.nxt[i]) {

		int to=s.to[i];

		if(to==fr) continue ;

		if(!dfn[to]) {

			tarjan(to,v);

			low[v]=min(low[v],low[to]);

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

				work(v,to);

			}

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

	}

}

ll ans;

int size[N];

void dfs(int v) {

	int tim=0;

	for(int i=g.h[v];i;i=g.nxt[i]) {

		int to=g.to[i];

		dfs(to);

		ans+=1ll*val[v]*size[v]*size[to];

		tim+=size[v]*size[to];

		size[v]+=size[to];

	}

	if(v<=n) size[v]++;

	if(v<=n) {

		tim+=(size[v]-1)*(tot_size-size[v]);

		ans+=1ll*val[v]*(size[v]-1)*(tot_size-size[v]);

	} else {

		tim+=size[v]*(tot_size-size[v]);

		ans+=1ll*val[v]*size[v]*(tot_size-size[v]);

	}

}

int main() {

	n=Get(),m=Get();

	tot=n;

	int a,b;

	for(int i=1;i<=m;i++) {

		a=Get(),b=Get();

		s.add(a,b),s.add(b,a);

	}

	for(int i=1;i<=n;i++) val[i]=-1;

	for(int i=1;i<=n;i++) {

		if(dfn[i]) continue ;

		tot_size=0;

		tarjan(i,0);

		dfs(i);

		ans-=1ll*tot_size*(tot_size-1);

	}

	cout<<ans*2;

	return 0;

}