是不是$ vector$存图非常慢啊......
题意：求数对$(x,y,z)$的数量使得存在一条$x$到$z$的路径上经过$y$，要求$x,y,z$两两不同 LOJ #2587
$ Solution:$
首先考虑一棵树的情况怎么做
我们枚举每一个点计算贡献，贡献即为经过这个点的链的数量
只要求出这个点的所有子树大小就可以算出这个贡献
然后发现如果某条链经过某个点双联通分量
这个连通分量里的所有点都会被这条链的端点对计算贡献
我们直接构建圆方树，令方点的权值为这个点双连通分量的大小
由于每个圆点每次都会被多算一次贡献（被两个方点共用或者是端点），我们令圆点的点权为$ -1$
然后直接在树上做就好了
注意原图不一定连通
$ my \ code:$
#include<ctime>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>
#include<vector>
#define M 400010
#define rt register int
#define ll long long
using namespace std;
namespace fast_IO{
const int IN_LEN=,OUT_LEN=;
char ibuf[IN_LEN],obuf[OUT_LEN],*ih=ibuf+IN_LEN,*oh=obuf,*lastin=ibuf+IN_LEN,*lastout=obuf+OUT_LEN-;
inline char getchar_(){return (ih==lastin)&&(lastin=(ih=ibuf)+fread(ibuf,,IN_LEN,stdin),ih==lastin)?EOF:*ih++;}
inline void putchar_(const char x){if(oh==lastout)fwrite(obuf,,oh-obuf,stdout),oh=obuf;*oh++=x;}
inline void flush(){fwrite(obuf,,oh-obuf,stdout);}
}
using namespace fast_IO;
#define getchar() getchar_()
inline ll read(){
ll x = ; char zf = ; char ch = getchar();
while (ch != '-' && !isdigit(ch)) ch = getchar();
if (ch == '-') zf = -, ch = getchar();
while (isdigit(ch)) x = x * + ch - '', ch = getchar(); return x * zf;
}
void write(ll y){if(y<)putchar('-'),y=-y;if(y>)write(y/);putchar(y%+);}
void writeln(const ll y){write(y);putchar('\n');}
int i,j,k,m,n,x,y,z,cnt,size;
int F[M],L[M],N[M],a[M],val[M],dfn[M],low[M],sta[M],top;
void add(int x,int y){
a[++k]=y;
if(!F[x])F[x]=k;
else N[L[x]]=k;
L[x]=k;
}
vector<int>e[];
void Add(int x,int y){
e[x].push_back(y);
e[y].push_back(x);
}
void bemin(int &x,int y){
if(y<x)x=y;
}
int fa[],sz[],ds;
void tarjan(int x){
dfn[x]=low[x]=++cnt;sta[++top]=x;sz[x]=;
for(rt i=F[x];i;i=N[i]){
if(!dfn[a[i]]){
tarjan(a[i]),bemin(low[x],low[a[i]]);
if(low[a[i]]>=dfn[x]){
n++;
while(sta[top+]!=a[i])sz[n]+=sz[sta[top]],Add(sta[top],n),top--,val[n]++;
sz[x]+=sz[n];Add(x,n);val[n]++;
}
}
else bemin(low[x],dfn[a[i]]);
}
}
ll ret;
void calc(int x,int pre){
ll ans=;int allsz=;
for(auto i:e[x])if(i!=pre){
calc(i,x);
ans-=1ll*sz[i]*sz[i];
allsz+=sz[i];
}
ans+=2ll*(size-(x<=ds))*allsz-1ll*allsz*allsz;
ret+=ans/*val[x];
}
int main(){
n=ds=read();m=read();
for(rt i=;i<=m;i++){
x=read();y=read();
add(x,y);
add(y,x);
}
for(rt i=;i<=n;i++)val[i]=-;
for(rt i=;i<=ds;i++)if(!dfn[i])tarjan(i),size=sz[i],calc(i,i),ret-=1ll*size*(size-);
cout<<ret*;
return ;
}