圆方树是什么
对于一个无向图的每一个点双连通分量，都新建一个点，让这个点给点双连通分量的每一个点都连一个边。不考虑原来的边的话，此时图变成了一棵……不一定是树的东西，。我们令原来的点为圆点，新增的点为方点。这就是一棵圆方树。
性质
由上，可以发现圆方树的性质有：
- 树上任意一个边的两个点都不是同一种点。
- 方点的数量 = 点双连通分量的数量
- 每一个方点的度数 = 点双连通分量的点数
实际应用
例题1 P4630 【APIO2018】 Duathlon 铁人两项
首先做一遍圆方树，我们发现对于每一个双连通分量而言，贡献的答案为siz-2（siz为连通块大小）（两个点有一个都在内部好考虑，对于两个点有一个外面的就发现外面汇入到这里面来的时候会重，要-2）。我们再给圆方树的方点/圆点分别赋予权值（这也是很多圆方树题的重点）。我们发现当我们令方点权值为他的度数，圆点权值为-1的时候，则答案为经过的点的权值。
朴素考虑两个点是(O(n^2))的，我们就对每个点考虑他对答案的贡献，然后就是套路dp，(O(n))，发现瓶颈在Tarjan上，是(O(n+m))的，反正能过。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <cmath>
namespace ztd{
using namespace std;
typedef long long ll;
const int mod = 998244353;
const int inf = 2147483647;
template<typename T> inline T read(T& t) {//fast read
t=0;short f=1;char ch=getchar();double d = 0.1;
while (ch<'0'||ch>'9') {if (ch=='-') f=-f;ch=getchar();}
while (ch>='0'&&ch<='9') t=t*10+ch-'0',ch=getchar();
if(ch=='.'){ch=getchar();while(ch<='9'&&ch>='0') t+=d*(ch^48),d*=0.1,ch=getchar();}
t*=f;
return t;
}
}
using namespace ztd;
const int maxn = 1e6+7, maxm = 4e6+7;
int n, m, s, l, a[maxn];
struct Graph{
int last[maxn], gg[maxm], y[maxm], ecnt;
inline void addedge(int x, int yy){
y[++ecnt] = yy, gg[ecnt] = last[x];
last[x] = ecnt;
}
inline void clear(){
memset(last,0,sizeof(last));
memset(y,0,sizeof(y));
memset(gg,0,sizeof(gg));
ecnt = 0;
}
}e, g;
int siz[maxn];
int totsiz, w[maxn];
//***Tarjan************************************************************
int dfx[maxn], low[maxn], dfxcnt, st[maxn], top, gtot;
void Tarjan(int x){
dfx[x] = low[x] = ++dfxcnt; st[top++] = x; ++totsiz;
for(int i = e.last[x], y = e.y[i]; i; i = e.gg[i], y = e.y[i]){
if(!dfx[y]){
Tarjan(y);
low[x] = min(low[x], low[y]);
if(low[y] >= dfx[x]){
w[++gtot] = 0;
++gtot;
do{
g.addedge(st[--top], gtot); g.addedge(gtot, st[top]);
++w[gtot];
}while(st[top] ^ y);
g.addedge(gtot, x); g.addedge(x, gtot); ++w[gtot];
}
}else low[x] = min(low[x], dfx[y]);
}
}
//*********************************************************************
ll ans;
void dfs(int x, int fa){
siz[x] = (x <= n);
for(int i = g.last[x]; i; i = g.gg[i]){
int y = g.y[i];
if(y == fa) continue;
dfs(y, x);
ans += 2ll * w[x] * siz[x] * siz[y];
siz[x] += siz[y];
}
ans += 2ll * w[x] * siz[x] * (totsiz-siz[x]);
}
signed main(){
gtot = read(n); read(m);
int xx, yy;
for(int i = 1; i <= n; ++i) w[i] = -1;
for(int i = 1; i <= m; ++i){
read(xx); read(yy);
e.addedge(xx,yy); e.addedge(yy,xx);
}
for(int i = 1; i <= n; ++i){
if(!dfx[i]){
totsiz = 0;
Tarjan(i); --top;
dfs(i,0);
}
}
cout << ans << '
';
return 0;
}