P4630 [APIO2018] Duathlon 铁人两项
orz_z
·
·
题解
圆方树的定义
圆方树是用来解决仙人掌图的问题的，那什么是仙人掌图呢？
即不存在边同时属于多个环的无向连通图是一棵仙人掌。
点双连通分量的定义
要介绍圆方树，首先要介绍点双连通分量。
一个点双连通图的一个定义是：图中任意两不同点之间都有至少两条点不重复的路径。
一种简单的定义：不存在割点的图。
但这种定义对于两点一边的图时是没用的，它没有割点，但是并不能找到两条不相交的路径，因为只有一条路径。（也可以理解为那一条路径可以算两次，但的确没有相交，因为不经过其他点）。
在点双连通图内，一个点可能属于多个点双，但是一条边属于恰好一个点双。
更多关于有向图的强连通分量的知识，请看我的博客 \to 强连通分量
更多关于点双连通分量的知识，请看我的博客 \to 双连通分量
继续介绍圆方树
关于圆方树的建图，也比较简单，将一个点双连通分量内的所有边删去，再将一个点双连通分量中的每个点向一个新建的点连边，这个新建的点即是方点。
所以在圆方树中有 n+c 个点，其中 n 是原图点数，c 是原图点双连通分量的个数。
每个点双都可以形成一个菊花图，多个菊花图通过原图中的割点连接在一起（因为点双的分隔点是割点）。
显然，圆方树中每条边连接一个圆点和一个方点。
在下面这张图中，[1,2,3,4,5] 是圆点，[6,7] 是方点。
而如果圆方树连通，则有以下性质：
如果原图中某个连通分量只有一个点，则需要具体情况具体分析，我们在后续讨论中不考虑孤立点。
注意一条边连接两个点的在这里不算点双。
广义圆方树
普通圆方树只能解决仙人掌图上的问题，而广义圆方树则可以将所有无向图转化为圆方树处理。
广义圆方树性质：圆点方点相间，不存在两个‘’相同形状‘’的点相连。
与圆方树不同的是，广义圆方树需要把一条边连接两个点也看成一个点双，原本两个圆点有一条边相连，现在在中间插入一个方点间隔开就好了。
可以参照这张图
圆方树的应用
洛谷 P4630 [APIO2018] Duathlon 铁人两项
题目大意
给定一张简单无向图，问有多少对三元组 ⟨s,c,f⟩（s，c，f 互不相同）使得存在一条简单路径从 s 出发，经过 c 到达 t。
解题思路
考虑怎么计算这种三元组，可以枚举 s 和 f，然后计算从 s 到 f 的点不重复路径中可以经过的点的个数。
所以可以考虑缩点双之后建出圆方树，然后就只需要在树上求出每一对 $(u,v)$ 之间经过的点双点数大小。
但是直接将点双大小加起来的话两个点双的公共点会算重，于是将公共点的权值（圆点）设为 $-1$，方点的权值设为点双的大小。
原因是路径中除端点外每个圆点（即割点）都会被相邻的两点双算两遍，而两端点虽然只被算一遍但本身并不能被统计，故每个点都需要减一。
那么问题又进一步转化成了求树上所有路径的权值和，显然只要分别计算每个点的贡献即可，就是一个简单的 `DP`。
于是这题便转化成了求树上所有的圆点对之间的路径权值和。
直接做是 $n^2$，
可以换个角度考虑，改为统计每一个点对答案的贡献，即权值乘以经过它的路径条数，这可以通过简单的树形 DP 求出。
### AC CODE
```cpp
#include <bits/stdc++.h>
using namespace std;
const int _ = 100005;
int n, m, cnt;
vector<int> G[_], T[_ * 2];
long long Ans;
int dfn[_], low[_], cnt_node, num;
stack<int> s;
int wjy[_ * 2];
int vis[_ * 2], siz[_ * 2];
void Tarjan(int u)
{
low[u] = dfn[u] = ++cnt_node;
s.push(u);
++num;
for (auto v : G[u])
{
if (!dfn[v])
{
Tarjan(v);
low[u] = min(low[u], low[v]);
if (low[v] == dfn[u])
{
wjy[++cnt] = 0;
while (1)
{
int x = s.top();
s.pop();
T[cnt].push_back(x);
T[x].push_back(cnt);
++wjy[cnt];
if (x == v)
break;
}
T[cnt].push_back(u);
T[u].push_back(cnt);
++wjy[cnt];
}
}
else
low[u] = min(low[u], dfn[v]);
}
}
void dfs(int u, int fz)
{
vis[u] = 1;
siz[u] = (u <= n);
for (auto v : T[u])
if (v != fz)
{
dfs(v, u);
Ans += 2ll * wjy[u] * siz[u] * siz[v];
siz[u] += siz[v];
}
Ans += 2ll * wjy[u] * siz[u] * (num - siz[u]);
}
int main()
{
scanf("%d%d", &n, &m);
cnt = n;
for (int i = 1; i <= n; ++i)
wjy[i] = -1;
for (int i = 1; i <= m; ++i)
{
int u, v;
scanf("%d%d", &u, &v);
G[u].push_back(v);
G[v].push_back(u);
}
for (int i = 1; i <= n; ++i)
if (!dfn[i])
{
num = 0;
Tarjan(i);
dfs(i, 0);
}
printf("%lld\n", Ans);
return 0;
}
```