快速题解to[APIO2018]Duathlon铁人两项 & 圆方树介绍

pengyule · 2022-01-09 21:58:38 · 题解

求不一定连通的简单无向图中，满足「存在一条路径 s\to f 经过 c 」的 \lang s,c,f\rang 的个数。\lang s,c,f\rang 和 \lang f,c,s\rang 算不同的元组。

点双的性质：对于一个点双连通分量中的两个点 u,v，从 u 到 v 的所有路径的并为点双连通分量的点集。证明略。

当我们建立圆方树之后，求固定的 s\to f 的 c 的个数等于与「从圆点 s 到圆点 f 上的所有方点」相连的圆点的个数 -2。-2 是因为 s,f 不算。

遇到用圆方树统计路径数的问题，重要做法是给每一个方点和圆点赋权值。

显然，每个方点应赋值为其所代表的点双节点数。所以圆点赋值 -1，以去重两个点双的公共部分。

这样，树上 s\to f 的点权值和就代表 c 的个数。注意，不需要再 -2，道理显然。

问题转化为：

求树上所有有序圆点点对间路径点权和之和。

这是一个简单的问题，只需要用“统计贡献”的角度计算即可。由于文字不方便描述，见下面代码：

void dfs(int x,int p){
    vis[x]=1; //vis[x]标记x到达，不重要
    ll sum=0; //sum统计有多少组点对。在这里先不考虑顺序，因为s!=f所以最后答案*2即可。
    //第12行及以前sum统计的都是x子树内的路径条数
    for(int i=0;i<T[x].size();i++){
        int y=T[x][i];
        if(y==p)continue;
        dfs(y,x);
        sum+=1ll*siz[y]*siz[x]; //这里的siz[x]还是已经遍历过的儿子节点的子树中圆点个数的总和
        siz[x]+=siz[y];
    }
    if(x<=n)sum+=siz[x],siz[x]++; //x<=n代表x是圆点，那么由x连向
    sum+=1ll*siz[x]*(tmp-siz[x]); //由x子树内的圆点连向x子树外的圆点必经过x；tmp是连通块内节点个数（因为图不连通）
    f[x]*=sum; //f[x]会事先存住x的点权
    ans+=f[x];
}

代码：

#include <bits/stdc++.h>
using namespace std;
const int N=1e5+5;
typedef long long ll;
int n,m,t,dfc,cnt,tmp,stk[N],dfn[N],low[N],siz[N*2],vis[N*2];
ll ans,f[N*2];
vector<int>G[N],T[N*2];
void Tarjan(int x){
    stk[++t]=x;
    dfn[x]=low[x]=++dfc;
    for(int i=0;i<G[x].size();i++){
        int y=G[x][i];
        if(!dfn[y]){
            Tarjan(y);
            low[x]=min(low[x],low[y]);
            if(low[y]==dfn[x]){
                cnt++;
                while(t){
                    T[cnt].push_back(stk[t]),T[stk[t]].push_back(cnt);
                    f[cnt]++;
                    if(stk[t--]==y)break;
                }
                T[cnt].push_back(x),T[x].push_back(cnt);
                f[cnt]++;
            }
        }
        else low[x]=min(low[x],dfn[y]);
    }
}
void dfs1(int x,int p){
    tmp+=x<=n;
    for(int i=0;i<T[x].size();i++){
        int y=T[x][i];
        if(y^p)dfs1(y,x);
    }
}
void dfs(int x,int p){
    vis[x]=1;
    ll sum=0;
    for(int i=0;i<T[x].size();i++){
        int y=T[x][i];
        if(y==p)continue;
        dfs(y,x);
        sum+=1ll*siz[y]*siz[x];
        siz[x]+=siz[y];
    }
    if(x<=n)sum+=siz[x],siz[x]++;
    sum+=1ll*siz[x]*(tmp-siz[x]);
    f[x]*=sum;
    ans+=f[x];
}
int main(){
    scanf("%d%d",&n,&m),cnt=n;
    for(int i=1,u,v;i<=m;i++)scanf("%d%d",&u,&v),G[u].push_back(v),G[v].push_back(u);
    for(int i=1;i<=n;i++)f[i]=-1;
    for(int i=1;i<=cnt;i++)if(!vis[i])Tarjan(i),tmp=0,dfs1(i,0),dfs(i,0);
    cout<<ans*2;
}

圆方树介绍

点双连通分量

我们都知道有向图的强连通分量叫 scc，无向图也有一种叫双连通分量的连通分量，分为点双(v-dcc)&边双(e-dcc)。

一个图为点双连通图等价于对于任意两个不同的点 u,v，存在两条（除端点外）不相交的从 u 到 v 的简单路径。特别地，仅存在两个点和一条连接它们的边的图也是点双连通图。
- 即不存在割点的无向连通图。
一个图为边双连通图等价于每条边都在某一个简单环中。
- 即不存在割边的无向连通图。
一个图的极大点双联通子图为它的一个点双连通分量。
一个图的极大边双联通子图为它的一个边双连通分量。
当一个图被划分为 v-dcc 和 e-dcc 时，相邻两个 e-dcc 之间没有公共点，分开它们的是割边；相邻两个 v-dcc 之间有一个公共点，该点为割点。换句话说，一个点可以存在于多个点双连通分量中。

圆方树

对于一个无向连通图，求出每一个 v-dcc 后，为每一个 v-dcc 建立一个新点，将 v-dcc 内的所有点与该新点相连。则该新点为方点，原图中的点为圆点，由新边构成的新图将成为一颗树状结构，发明它的陈俊琨叫它圆方树。非连通图将构成森林。圆方树可以将图转为树，从而实现树上操作。