部分内容参照了OI-wiki
定义
对于这样的一个无向图，左侧的 \({1,2,3}\) 和右侧的 \({3,4,5}\) 分别构成一个点双联通分量。中间的 \(3\) 号节点就是一个割点。不难发现，点双与点双之间，通过割点连接。
把原图中的点双新建成一个节点，称之为方点；而原图中的割点以及剩下的孤点，称之为圆点。
不难发现，将圆点和方点建成一个新图后，新图中的边只会连接圆点和方点。那么新的图就显然是一棵树。对于上方给出的图，建出新图并适当扩展后，可以得到类似于下图的圆方树：
对于圆方树中的圆点，如果其为非叶子节点，那么就必然连接若干个方点，那么也就必然为割点；反之，若一个圆点为叶子节点，则其一定不为割点。
这一部分的代码实现：
inline void tarjan (int u)
{
low[u] = dfn[u] = ++dfs_tot; st[++tp] = u;
for (int v: e[u])
if (!dfn[v])
{
tarjan(v); low[u] = std::min(low[u], low[v]);
if (low[v] == dfn[u])
{
add(u, ++tot);
do add(st[tp], tot); while (st[tp--] != v);
}
}
else low[u] = std::min(low[u], dfn[v]);
}
对于一张无向图，从 \(A\) 点到 \(B\) 点的必经点，也就是圆方树上 \(A\) 点到 \(B\) 点路径上的割点。
应用
[SDOI2018]战略游戏
给出一个简单无向连通图。有 \(q\) 次询问：
每次给出一个点集 \(S（2 \le |S| \le n）\)，问有多少个点 \(u\) 满足 \(u \notin S\) 且删掉 \(u\) 之后 \(S\) 中的点不全在一个连通分量中。
思路
建出圆方树后，不难发现，可以枚举 \(S\) 中的每一对路径 \((u,v)\)，那么所求的点就是所有路径上的割点构成的集合的交集的大小。也就是包含 \(S\) 中所有点的最小联通块中的割点的数量 \(-|S|\) 。
于是可以考虑将圆方树中的圆点的点权设为 \(1\)，方点的点权设为 \(0\)。设 \(val[i]\) 表示 \(i\) 到根节点的点权和，设集合的大小为 \(k\)，再把集合中的点按照 \(dfs\) 序排列一遍，依次从 \(s[1]\) 往后走到 \(s[k]\)，最后再走回 \(s[1]\)。那么不难发现，除了 \(LCA(s[1],s[k])\)，其余的 \(LcA(s[i],s[i+1])\) 都会出现在其余的某一条路径上。换句话说，不为 \(LCA\) 的圆点，必然出现了两次。那么这一部分的答案就是：
\((\sum val[s[i]]+val[s[i+1]]-2*val[LCA(s[i],s[i+1]))/2\)。
而对于 \(LCA(s[1],s[k])\)，还需特判一下其是否为圆点。
code：
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=1e5+10,M=8e5+10;
int siz[N<<1],rh[N<<1],fa[N<<1][30],dep[N<<1],val[N<<1],dfn[N<<1],h[N],s[N],idx,n,m,bcc_cnt;
struct edge{int v,nex;}e[M];
void add(int h[],int u,int v){e[++idx]=edge{v,h[u]};h[u]=idx;}
int stk[N],top,Dfn[N],low[N],num;
void tarjan(int u)
{
Dfn[u]=low[u]=++num;stk[++top]=u;
for(int i=h[u];i;i=e[i].nex)
{
int v=e[i].v;
if(!Dfn[v])
{
tarjan(v);low[u]=min(low[u],low[v]);
if(low[v]==Dfn[u])
{
bcc_cnt++;add(rh,bcc_cnt,u);add(rh,u,bcc_cnt);
do{add(rh,bcc_cnt,stk[top]);add(rh,stk[top],bcc_cnt);
}while(stk[top--]!=v);
}
}
else low[u]=min(low[u],Dfn[v]);
}
}
void dfs(int u,int Fa)
{
fa[u][0]=Fa,dep[u]=dep[Fa]+1;val[u]=val[Fa]+(u<=n);dfn[u]=++num;siz[u]=1;
for(int i=1;i<=20;i++) fa[u][i]=fa[fa[u][i-1]][i-1];
for(int i=rh[u];i;i=e[i].nex)
{
int v=e[i].v;if(v==Fa) continue;
dfs(v,u);siz[u]+=siz[v];
}
}
int LCA(int x,int y)
{
if(dep[x]<dep[y]) swap(x,y);
for(int i=20;i>=0;i--) if(dep[fa[x][i]]>=dep[y]) x=fa[x][i];
if(x==y) return x;
for(int i=20;i>=0;i--)
if(fa[x][i]!=fa[y][i]) x=fa[x][i],y=fa[y][i];
return fa[x][0];
}
bool cmp(int x,int y){return dfn[x]<dfn[y];}
void solve()
{
scanf("%d%d",&n,&m);memset(h,0,sizeof(h));memset(rh,0,sizeof(rh));idx=num=top=0;bcc_cnt=n;
memset(Dfn,0,sizeof(Dfn));memset(low,0,sizeof(low));memset(siz,0,sizeof(siz));memset(fa,0,sizeof(fa));
for(int u,v,i=1;i<=m;i++) scanf("%d%d",&u,&v),add(h,u,v),add(h,v,u);
for(int i=1;i<=n;i++) if(!Dfn[i]) tarjan(i);num=0;dfs(1,0);int q,cnt;scanf("%d",&q);
while(q--)
{
scanf("%d",&cnt);int ans=0;
for(int i=1;i<=cnt;i++) scanf("%d",&s[i]);sort(s+1,s+cnt+1,cmp);s[cnt+1]=s[1];
for(int i=1;i<=cnt;i++) ans+=val[s[i]]+val[s[i+1]]-val[LCA(s[i],s[i+1])]*2;
ans>>=1;ans-=cnt;ans+=(LCA(s[1],s[cnt])<=n);
printf("%d\n",ans);
}
}
int main()
{
int T;scanf("%d",&T);while(T--) solve();
return 0;
}
CF487E Tourists
给定一张简单无向连通图，要求支持两种操作：
修改一个点的点权。
询问两点之间所有简单路径上点权的最小值。
思路
建立圆方树后，不难发现修改圆点的点权只需要树剖+线段树即可。主要问题出现在对于方点的修改。
可以用一个 multiset 维护一个方点的所有儿子节点的权值，删除时直接将对应的权值从集合中删除，若最小值发生变化，则更新方点的权值。而对于方点的父亲节点，则需要在询问时特判一下。
code：
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<set>
using namespace std;
const int N=1e5+10,M=6e5+10;
multiset<int>state[N];
int h[N],idx,n,m,q;
struct edge{int v,nex;}e[M];
void add(int h[],int u,int v){e[++idx]=edge{v,h[u]};h[u]=idx;}
int bcc_cnt,num,low[N],Dfn[N],stk[N],Top,id[N];
int dfn[N<<1],val[N<<1],rh[N<<1],siz[N<<1],son[N<<1],top[N<<1],fa[N<<1],dep[N<<1],pos[N<<1];
void chkmin(int &a,int b){if(b<a) a=b;}
void tarjan(int u)
{
Dfn[u]=low[u]=++num;stk[++Top]=u;
for(int i=h[u];i;i=e[i].nex)
{
int v=e[i].v;
if(!Dfn[v])
{
tarjan(v);low[u]=min(low[u],low[v]);
if(low[v]==Dfn[u])
{
bcc_cnt++,add(rh,u,bcc_cnt),add(rh,bcc_cnt,u);id[u]=bcc_cnt;int y;
do{y=stk[Top--];add(rh,bcc_cnt,y),add(rh,y,bcc_cnt);id[y]=bcc_cnt;
} while(y!=v);
}
}
else low[u]=min(low[u],Dfn[v]);
}
}
void dfs1(int u,int Fa)
{
// printf("NLC:%d %d\n",u,Fa);
siz[u]=1;dep[u]=dep[Fa]+1,fa[u]=Fa;
for(int i=rh[u];i;i=e[i].nex)
{
int v=e[i].v;if(v==Fa) continue;dfs1(v,u);
if(siz[v]>siz[son[u]]) son[u]=v;siz[u]+=siz[v];
}
}
void dfs2(int u,int t)
{
top[u]=t;dfn[u]=++num;pos[num]=u;if(son[u]) dfs2(son[u],t);
for(int i=rh[u];i;i=e[i].nex)
{
int v=e[i].v;if(v!=son[u]&&v!=fa[u]) dfs2(v,v);
}
}
int w[N<<3];
void push_up(int p){w[p]=min(w[p<<1],w[p<<1|1]);}
void build(int p,int l,int r)
{
if(l==r) return w[p]=val[pos[r]],void();int mid=l+r>>1;
build(p<<1,l,mid),build(p<<1|1,mid+1,r);push_up(p);
}
void update(int p,int l,int r,int x,int V)
{
if(l==r) return w[p]=V,void();int mid=l+r>>1;
if(x<=mid) update(p<<1,l,mid,x,V);else update(p<<1|1,mid+1,r,x,V);push_up(p);
}
int query(int p,int l,int r,int L,int R)
{
if(L<=l&&r<=R) return w[p];int mid=l+r>>1;
if(L>mid) return query(p<<1|1,mid+1,r,L,R);
if(R<=mid) return query(p<<1,l,mid,L,R);
return min(query(p<<1,l,mid,L,R),query(p<<1|1,mid+1,r,L,R));
}
int solve(int x,int y)
{
int ans=0x3f3f3f3f;
while(top[x]!=top[y])
{
if(dep[fa[top[x]]]<dep[fa[top[y]]]) swap(x,y);
chkmin(ans,query(1,1,num,dfn[top[x]],dfn[x]));x=fa[top[x]];
}
if(dfn[x]>dfn[y]) swap(x,y);if(x>n) chkmin(ans,val[fa[x]]);
// printf("%d %d %d\n",dfn[x],dfn[y],query(1,1,num,dfn[x],dfn[y]));
return min(ans,query(1,1,num,dfn[x],dfn[y]));
}
int main()
{
scanf("%d%d%d",&n,&m,&q);for(int i=1;i<=n;i++) scanf("%d",&val[i]);bcc_cnt=n;
for(int u,v,i=1;i<=m;i++) scanf("%d%d",&u,&v),add(h,u,v),add(h,v,u);
for(int i=1;i<=n;i++) if(!Dfn[i]) tarjan(i);num=0;dfs1(1,0),dfs2(1,1);
for(int i=2;i<=n;i++) state[id[i]-n].insert(val[i]);
for(int i=n+1;i<=num;i++) val[i]=state[i-n].empty()?0x3f3f3f3f:*state[i-n].begin();build(1,1,num);
// printf("NLC:%d %d\n",bcc_cnt,num);
// for(int i=1;i<=bcc_cnt;i++) printf("%d ",val[i]);puts("");
while(q--)
{
char op[2];int x,y;scanf("%s%d%d",op,&x,&y);
if(op[0]=='C')
{
update(1,1,num,dfn[x],y);
if(x==1){val[x]=y;continue;}
int z=id[x];
state[z-n].erase(state[z-n].find(val[x]));state[z-n].insert(y);
int minv=*state[z-n].begin();
if(minv==val[z]){val[x]=y;continue;}
update(1,1,num,dfn[z],minv);
val[z]=minv;val[x]=y;
}
else printf("%d\n",solve(x,y));
}
return 0;
}
[APIO2018] 铁人两项
给定一张简单无向图，问有多少对三元组 \(\langle s, c, f \rangle\)（\(s, c, f\) 互不相同）使得存在一条简单路径从 \(s\) 出发，经过 \(c\) 到达 \(f\)。
思路
建出圆方树后，对于一条树上的简单路径 \((s,f)\)，路径上的所有点可以成为 \(c\)。那么其实也就可以钦定当前的点为 \(c\)，经过它的路径数量也就是三元组的数量。
这里需要注意，因为一个圆点可以被统计在若干个方点当中，我们可以把圆点的权值设为 \(-1\)，方点的权值设为其代表的点双大小。这样就可以处理所有的情况。
code：
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define LL long long
const int N=1e5+10,M=8e5+10;
int h[N],idx,n,m;LL ans;
struct edge{int v,nex;}e[M];
void add(int h[],int u,int v){e[++idx]=edge{v,h[u]};h[u]=idx;}
int dfn[N],low[N],stk[N],top,num,bcc_cnt,tot;
int val[N<<1],rh[N<<1],siz[N<<1];
void tarjan(int u)
{
dfn[u]=low[u]=++num;tot++;stk[++top]=u;val[u]=-1;
for(int i=h[u];i;i=e[i].nex)
{
int v=e[i].v;
if(!dfn[v])
{
tarjan(v);low[u]=min(low[u],low[v]);
if(dfn[u]==low[v])
{
int y;bcc_cnt++;add(rh,u,bcc_cnt),add(rh,bcc_cnt,u);val[bcc_cnt]=1;
do{y=stk[top--];add(rh,y,bcc_cnt),add(rh,bcc_cnt,y);val[bcc_cnt]++;
} while(y!=v);
}
}
else low[u]=min(low[u],dfn[v]);
}
}
void dfs(int u,int fa)
{
siz[u]=(u<=n);
for(int i=rh[u];i;i=e[i].nex)
{
int v=e[i].v;if(v==fa) continue;dfs(v,u);
ans+=2ll*siz[u]*siz[v]*val[u];
siz[u]+=siz[v];
}
ans+=2ll*siz[u]*(tot-siz[u])*val[u];
}
int main()
{
scanf("%d%d",&n,&m);for(int u,v,i=1;i<=m;i++) scanf("%d%d",&u,&v),add(h,u,v),add(h,v,u);bcc_cnt=n;
for(int i=1;i<=n;i++)
if(!dfn[i])
{
tot=0;tarjan(i);dfs(i,0);
}
printf("%lld\n",ans);
return 0;
}