Description

给出一张无向图，询问有多少个三元组\(<s,c,f>\)满足有一条简单路径从\(s\)出发，经过\(f\)，可以到达\(c\)

Solution

圆方树裸题。

两圆点在圆方树上的路径，与路径上经过的方点相邻的圆点的集合，就等于原图中两点简单路径上的点集。

建出原图的圆方树。圆点的点权为\(-1\)，方点的点权为双联通分量的大小，那么形如\(<x,y,f>\)的三元组数量应为\(x,y\)再圆方树上路径的点权和

我们转而考虑每个点的贡献，可以通过很简单的树形dp求得

Code 

//2019/3/8 15:44~16:51#include
    
     #define ll long long#define max(a,b) ((a)>(b)?(a):(b))#define min(a,b) ((a)<(b)?(a):(b))inline int read(){    int x=0,f=1;char ch=getchar();    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}    while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}    return x*f;}const int MN=1e5+5,ME=4e5+5;struct edge{int to,nex;}e[ME],E[ME];int en,hr[MN],En,Hr[MN<<1];inline void ins(int f,int t,int &end,int *h,edge *Ed){    Ed[++end]=(edge){t,h[f]};h[f]=end;    Ed[++end]=(edge){f,h[t]};h[t]=end;}int N,M,dfn[MN],low[MN],st[MN],tp,dind,siz[MN<<1],val[MN<<1],num;void tarjan(int x){    dfn[x]=low[x]=++dind;st[tp++]=x;register int i;    for(i=hr[x];i;i=e[i].nex)    {        if(!dfn[e[i].to])        {            tarjan(e[i].to);low[x]=min(low[x],low[e[i].to]);            if(low[e[i].to]==dfn[x])                for(val[++num]=1,Hr[num]=0,ins(num,x,En,Hr,E);st[tp]!=e[i].to;--tp)val[num]++,ins(num,st[tp-1],En,Hr,E);        }        else low[x]=min(low[x],dfn[e[i].to]);    }}ll ans;inline void dfs(int x,int f=0){    register int i;siz[x]=x<=N;    for(i=Hr[x];i;i=E[i].nex)if(E[i].to^f)    {        dfs(E[i].to,x);ans+=2ll*siz[x]*siz[E[i].to]*(ll)val[x];        siz[x]+=siz[E[i].to];    }    ans+=2ll*siz[x]*(dind-siz[x])*(ll)val[x];}int main(){    num=N=read(),M=read();    register int i;    while(M--) i=read(),ins(i,read(),en,hr,e);    for(i=1;i<=N;++i)val[i]=-1;    for(i=1;i<=N;++i)if(!dfn[i])    {num=N,dind=En=tp=0,tarjan(i),dfs(i);}    return 0*printf("%lld\n",ans);}
    

---

Blog来自PaperCloud，未经允许，请勿转载，TKS！