做点双连通的时候发现很多题目可以用圆方树写

特意去学了一下,入门很简单嘛,而且是个很神奇的东西!!

$前置知识:点双连通分量,没了$

圆方树

$大概就是把一般图变成树的结构,然后我们就可以在上面$乱搞了

$比如给定一张无向图,怎么把它转化为树?$

$大概做法是:求出所有点双连通分量,在每个点双连通中设置一个方点$

$把每个原图中的点看成一个圆点$

$然后每个点双连通分量中的点向新设的对应的方点连边$

$去掉原图中点双连通分量间的边$

看起来很不直观对吧…在这里盗用一张别人的图,很清楚

$如图所示,无向图经过设置方点和圆点构成了最右边的一棵树$

$但是这棵树有什么性质?看一道例题吧.......不难的(仅指这道例题emm)$

P4630 [APIO2018] Duathlon 铁人两项

题意:给出无向图,求(s,c,f)三元组的个数,代表从s出发经过c达到f(不能重复经过点)

$考虑建好的圆方树,怎么来写呢?$

$如果固定了s和f,能不能快速求出c呢?$

比如这张无向图

$我们构建的圆方树是这样的(每个点双都要新建一个方点!!)$

$现在如果s=4,f=5,c有几种可能?$

$不难发现,c可以取的值有2,3,1,6$

仔细观察会发现这些点都在s到f在圆方树上路径的方点周围

$这是很重要的性质$

$如果我们给方点赋一个权值为它代表的点双连通大小$

$所有圆点赋值为-1$

$那么s到f的权值和不就是c的取值可能吗?$

$你可能奇怪为什么圆点赋值-1$

$很简单呢,图中节点2被上下两个方点包含了(计算了2次权值)$

$如果给圆点2赋值-1就能很好解决这个问题$

$但是回到题目,没有给定s和t,枚举复杂度不得上天??$

转变思维,s和t任意,代表我们应该计算圆方树中任意2个圆点间的权值和

$等价于统计每个点被经过了x次,乘上权值就是这个点的贡献嘛!!$

$完成这个统计,就树型dp啊!!$

$至于怎么树型dp,代码很清楚,不再累赘了$

#include <bits/stdc++.h> using namespace std; #define int long long const int maxn=1e6+10; int n,m,ans; vector<int>vec[maxn]; struct edge{ int to,nxt; }d[maxn]; int head[maxn<<2],cnt=1; 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); } int low[maxn],dfn[maxn],stac[maxn],id,top; int square[maxn],nowsize,f,siz[maxn]; 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( 1 ) { 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] ); } } void dfs(int u,int fa) { siz[u] = ( u<=n ); 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]; } signed main() { cin >> n >> m; f=n;//方点编号从n+1起 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;//无序对,s和t可以交换 }