「LOJ 2587」「APIO2018」铁人两项

LOJ #2587

题意

你有一张 \(n\) 个点 \(m\) 条边的无向图，你需要选择三个互不相同的点 \(s,c,f\)

询问有多少种选择的方案使得存在至少一条从 \(s\) 出发经过 \(c\) 到达 \(f\) 的简单路径（不经过重复点）

\(n\le 10^5,m\le 2*10^5\)

---

做法

建圆方树，对每个点双建一个方点

把两个相邻的点也看做一个点双，这会使得圆方树上圆点和方点都是交替出现的

考虑怎么统计答案

枚举起点和终点 \(s,f\) ，并随便找出一条 \(s\to f\) 的路径，可行的中间点 \(c\) 的集合就是路径经过的所有点双包含的点

那么在圆方树上这两个点的路径包含的所有方点都会有一个 点双大小 \(-1\) 的贡献

给每个方点赋一个上述的权值，圆点权值为 \(0\)

一对起点和终点的贡献就是 带点权的路径长度 \(-1\)

在每个方点上计算对答案的贡献，最后减掉选两个点的方案数就是答案了

复杂度 \(\mathcal O(n+m)\)

---

代码

#include<cstdio>
#include<algorithm>
#include<ctype.h>
#include<string.h>
#include<math.h>
#include<vector>

using namespace std;
#define ll long long

inline char read() {
	static const int IN_LEN = 1000000;
	static char buf[IN_LEN], *s, *t;
	return (s==t?t=(s=buf)+fread(buf,1,IN_LEN,stdin),(s==t?-1:*s++):*s++);
}
template<class T>
inline void read(T &x) {
	static bool iosig;
	static char c;
	for (iosig=false, c=read(); !isdigit(c); c=read()) {
		if (c == '-') iosig=true;
		if (c == -1) return;
	}
	for (x=0; isdigit(c); c=read()) x=((x+(x<<2))<<1)+(c^'0');
	if (iosig) x=-x;
}

const int N = 100005;
ll ans;
int num=1, n, m, cnt, top, p, tot, h[N], dfn[N], low[N], stk[N], g[N<<1], siz[N<<1], e[N<<2], pre[N<<2];
vector<int> f[N<<1];
inline void add(int x, int y){ e[++num]=y, pre[num]=h[x], h[x]=num;}
void tarjan(int u, int fa=0){
	++tot;
	dfn[u]=low[u]=++cnt;
	stk[++top]=u;
	int son=0;
	for(int i=h[u]; i; i=pre[i]) if(i!=fa){
		if(!dfn[e[i]]){
			tarjan(e[i], i^1), low[u]=min(low[u], low[e[i]]);
			++son;
			if(low[e[i]]>=dfn[u]){
				++p;
				f[u].push_back(p);
				do f[p].push_back(stk[top]), ++g[p]; while(stk[top--]!=e[i]);
			}
		}
		else low[u]=min(low[u], dfn[e[i]]);
	}
}
void dfs(int u){
	siz[u]=(u<=n);
	for(int i:f[u]) dfs(i), ans+=(ll)g[u]*siz[i]*(tot-siz[i]), siz[u]+=siz[i];
	ans+=(ll)g[u]*siz[u]*(tot-siz[u]);
}
int main() {
	read(n), read(m), p=n;
	for(int i=1; i<=m; ++i){
		static int x, y;
		read(x), read(y), add(x, y), add(y, x);
	}
	for(int i=1; i<=n; ++i) if(!dfn[i]) tot=0, tarjan(i), dfs(i), ans-=(ll)tot*(tot-1);
	return printf("%lld", ans), 0;
}