「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)\)


代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#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;
}