具体思路
题目问的是三元组 \((x,z,y)\) 使得 \(x\) 可以到达 \(z\)，且 \(z\) 可以到达 \(y\)，求三元组 \((x,z,y)\) 的数量。
我们转化一下问题，就是问 \(x,y\) 之间所有不重复路径的点的并集减 \(2\)。
显然，无向图中任意一个点都属于一个点双连通分量。
那么问题转化为 \(x,y\) 之间所有点双联通分量的并集减 \(2\)。
由于无向图中统计路径很难，而如果是树上问题，我们就可以树形 dp 了，于是考虑转化为树上问题。
那么需要建圆方树。
我们建好圆方树后，由于要求点双连通分量的并集，我们考虑给方点赋上点权，点权就是点双连通分量的大小。
但是这样会算重，因为一个割点可能并不只属于一个点双连通分量，因此我们需要给每个圆点在赋上 \(-1\) 的点权，就可以避免算重的问题了。
那么问题又转化为任意两个圆点之间的路径权值和。
直接计算的话时间复杂度为 \(O(n^2)\)，我们不满足于此，需要优化。
考虑计算每个点的贡献，显然就是这个点的权值乘上这个点被经过的次数。
考虑树形 dp。
我们令 \(x\) 为三元组的中间点，\(y\) 为三元组的终点，\(st\) 为三元组的起点。
我们强制让 \(y\) 在子树内，那么此时 \(st\) 可以在 \(y\) 前面的子树内，也可以是 \(x\) 上面其他子树内。
其实这里 \(st\) 可以在 \(y\) 后面的子树内，但是为了不算重，我们只计算前面的贡献，最后 \(\times 2\)即可。
-
若 \(st\) 在 \(y\) 前面的子树内，\(val=w_x \times siz_{前面子树} \times siz_y\)。
-
若 \(st\) 在 \(x\) 上面其他子树内， \(val=w_x \times (siz_{整颗子树} - siz_x)\)。
最后记得所有节点的贡献乘以二即可。
Code
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=1e5+5,M=2e5+5;
int n,m;
struct edge{
int x,y,pre;
}a[2*M];
int last[N],alen;
void ins(int x,int y){
a[++alen]=edge{x,y,last[x]};
last[x]=alen;
}
int dfn[N],low[N],id;
int top,sta[N];
int cnt,tot;LL w[2*N];
vector<int>G[2*N];
void tarjan(int x){
tot++;
dfn[x]=low[x]=++id;
sta[++top]=x;
w[x]=-1;
for(int k=last[x];k;k=a[k].pre){
int y=a[k].y;
if(!dfn[y]){
tarjan(y);
low[x]=min(low[x],low[y]);
if(dfn[x]<=low[y]){
cnt++;
int z;
do{
z=sta[top--];
G[cnt].push_back(z);
G[z].push_back(cnt);
w[cnt]++;
}while(z!=y);
G[cnt].push_back(x);
G[x].push_back(cnt);
w[cnt]++;
}
}
else low[x]=min(low[x],dfn[y]);
}
}
LL siz[2*N],ans=0;
void dfs(int x,int fa){
if(x<=n)siz[x]=1;
for(int y:G[x]){
if(y==fa)continue;
dfs(y,x);
ans=ans+2*siz[x]*siz[y]*w[x];
siz[x]=siz[x]+siz[y];
}
ans=ans+2*siz[x]*(tot-siz[x])*w[x];
}
int main(){
scanf("%d%d",&n,&m);
alen=1;memset(last,0,sizeof(last));
for(int i=1;i<=m;i++){
int x,y;scanf("%d%d",&x,&y);
ins(x,y),ins(y,x);
}
cnt=n;
for(int i=1;i<=n;i++){
if(!dfn[i]){
tot=0;
tarjan(i);
dfs(i,0);
}
}
printf("%lld",ans);
return 0;
}