[APIO2018] Duathlon 铁人两项
圆方树+简单DP。
不会圆方树的话可以看看我的另一篇文章。
考虑暴力怎么写，枚举两个点，答案加上两个点之间的点的个数。
看到题面中的一句话：
考虑到安全因素，选择的路径经过同一个点至多一次。
换句话说就是简单路径，用（广义）圆方树的基本条件已经满足，可以把问题变到树上：令方点的权值为所在点双的大小，圆点会被算重所以点权为\(-1\)，统计任意两点间的点权和就好了。直接做是\(n ^ 2\)的，考虑枚举每一个点看会产生多少贡献，对答案的贡献就乘个点权。
注意图不一定联通。
#include <cstdio>
#include <cctype>
#include <vector>
#define R register
#define I inline
#define B 1000000
#define L long long
using namespace std;
const int N = 200003;
char buf[B], *p1, *p2;
I char gc() { return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, B, stdin), p1 == p2) ? EOF : *p1++; }
I int rd() {
R int f = 0;
R char c = gc();
while (c < 48 || c > 57)
c = gc();
while (c > 47 && c < 58)
f = f * 10 + (c ^ 48), c = gc();
return f;
}
L ans = 0;
int s[N], w[N], dfn[N], low[N], vis[N], sta[N], siz[N], n, tim, cnt, stp, tot;
vector <int> g[N], G[N];
I int min(int x, int y) { return x < y ? x : y; }
void dfs(int x) {
dfn[x] = low[x] = ++tim, sta[++stp] = x, w[x] = -1, ++tot;
for (R int i = 0, y, z; i < s[x]; ++i)
if (!dfn[y = g[x][i]]){
dfs(y), low[x] = min(low[x], low[y]);
if (low[y] >= dfn[x]) {
w[++cnt] = 1, G[x].push_back(cnt), G[cnt].push_back(x);
do {
z = sta[stp--], ++w[cnt], G[z].push_back(cnt), G[cnt].push_back(z);
} while (z ^ y);
}
}
else
low[x] = min(low[x], dfn[y]);
}
void calc(int x, int f) {
siz[x] = vis[x] = x <= n;
L tmp = 0;
for (R int i = 0, y, S = G[x].size(); i < S; ++i)
if ((y = G[x][i]) ^ f)
calc(y, x), tmp += 2ll * siz[y] * siz[x], siz[x] += siz[y];
tmp += 2ll * siz[x] * (tot - siz[x]), ans += tmp * w[x];
}
int main() {
freopen("a.in", "r", stdin);
R int m, i, x, y;
cnt = n = rd(), m = rd();
for (i = 1; i <= m; ++i)
x = rd(), y = rd(), g[x].push_back(y), g[y].push_back(x);
for (i = 1; i <= n; ++i)
s[i] = g[i].size();
for (i = 1; i <= n; ++i)
if (!vis[i])
stp = 0, tot = 0, dfs(i), calc(i, 0);
printf("%lld", ans);
return 0;
}