20250821 圆方树总结

引子

前置芝士：树、点双、呃，还有建图。

圆方树

A1:圆方树是什么？
Q1:把一张图转换成一棵树，这棵树就叫圆方树，也叫虚树。

A2:我们为什么要把一张图转换成一棵树？
Q2:因为树对于一般图来说有许多友好的性质。

A3:圆方树为什么叫圆方树？
Q3:因为圆方树是由一堆圆点和方点组成的树，所以叫圆方树。

A4:圆方树能干什么？
Q4:把图上的问题转化成树上问题，可以使问题更加简洁明了。

A5:圆方树具体怎么实
Q5:哦，我们先来看个样例吧！

例子

这是原图，首先声明一下，原图内的所有原点都为圆点。第一步，我们要找到所有的点双，这张图总共有5个点双；第二步，在每个点双里面设立一个方点，注意，这是虚构的点，然后，在新图里面将这个方点与这个点双里面的所有点连接起来，这样圆方树就建好了！

这就是圆方树，建树本身不难，会求点双就能用把圆方树建出来，难点在于如何恰当的赋权值使得在圆方树上能求解原问题。

例题，铁人两项

题面:上洛谷自己搜

算了，压缩一下题面：给定一张无向图，问有多少互不相同三元组<a, b, c>
使得存在一条从a到b经过c的简单路径。

在同一个点双中任意选取两点，它们之间的所有简单路径的并集恰好构成该点双。具体来说，两点间简单路径经过的顶点集合等于路径上各点双的并集。

将这一性质转化到圆方树上，可以表述为：两个圆点之间的路径覆盖的顶点集合包括路径上的所有圆点，以及这些圆点相邻的方点所对应的圆点。由于c不能等于a或b，最终答案就是这个集合的大小减去2。

具体统计方法如下：假设u到v的路径为u→s₁→c₁→s₂→v。路径上的点权之和为valu + vals₁ + valc₁ + vals₂ + valv。为了准确计算方点相邻圆点的数量，我们可以将方点的权值设为其相邻圆点的数量。但为了避免圆点被多个相邻方点重复计算，需要将圆点的权值设为-1。这样处理能有效解决两方点夹一圆点时的重复计数问题，同时首尾两点的贡献无需计入。

最终，圆方树上任意两圆点间的路径距离即为它们对答案的贡献值。问题因此转化为计算树上所有圆点对之间路径权值之和。通过树形DP统计每个顶点在路径中出现的次数与其权值的乘积，即可求得最终答案。

struct edge{//直接提交有惊喜哦int to,nxt;
}d[maxn];
vector<int> vec[maxn];
long long head[maxn*2],square[maxn],stac[maxn],low[maxn],dfn[maxn],siz[maxn],n,m,ans,cnt=1,id,top,nowsize,f;
void add(int u,int v){d[++cnt]=(edge){v,head[u]},head[u]=cnt;
}
void ins(int u,int v){vec[u].push_back(v);
}
void dfs(int u,int fa){siz[u]=u<=n?1:0;for(int i=0;i<vec[u].size();i++){int v=vec[u][i];if(v==fa)continue;dfs(v,u);ans+=siz[v]*siz[u]*square[u];siz[u]+=siz[v];}ans+=siz[u]*(nowsize-siz[u])*square[u];
}
void tarjan(int u){low[u]=dfn[u]=++id;stac[++top]=u;nowsize++;for(int i=head[u];i;i=d[i].nxt){int v=d[i].to;if(!dfn[v]){tarjan(v);low[u]=min(low[u],low[v]);if(low[v]>=dfn[u]){square[++f]=0;while(true){ins(f,stac[top]);ins(stac[top],f);square[f]++;if(stac[top--]==v)break;}ins(f,u);ins(u,f);square[f]++;}}else{low[u]=min(low[u],dfn[v]);}}
}
int main(){cin>>n>>m;f=n;for(int i=1;i<=n;i++){square[i]=-1;}for(int i=1;i<=m;i++){int l,r;cin>>l>>r;add(l,r);add(r,l);}for(int i=1;i<=n;i++){if(dfn[i])continue;nowsize=0;tarjan(i);top--;dfs(i,0);}cout<<ans*2;
}