不经过重点，考虑点双
点双，考虑圆方树
两个点s,t，中间路径上，所有点双里的点都可以经过，特别地，s,t作为割点的时候，不能往后走，也就是不能经过身后的方点
也就是，(s,t)经过树上路径上的所有圆点和方点
把方点权值设为点双大小-2，圆点权值设为1，（s,t）路径上的权值就是c的选择方案数（不算s,t自己权值）
问题转化为：求树上任意点对的距离和，(x,y),(y,x)算两次
在转化为考虑每个点的贡献，树形DP即可
注意：
1.可能不连通
2.sz统计的是圆点的个数
3.最后乘2
#include<bits/stdc++.h>
#define reg register int
#define il inline
#define numb (ch^'0')
using namespace std;
typedef long long ll;
il void rd(int &x){
char ch;x=;bool fl=false;
while(!isdigit(ch=getchar()))(ch=='-')&&(fl=true);
for(x=numb;isdigit(ch=getchar());x=x*+numb);
(fl==true)&&(x=-x);
}
namespace Miracle{
const int N=+;
const int M=+;
int n,m;
struct node{
int nxt,to;
}e[*M];
int hd[N],cnt;
void add(int x,int y){
e[++cnt].nxt=hd[x];
e[cnt].to=y;
hd[x]=cnt;
}
int dfn[N],df;
int low[N];
ll ans=;
int vis[N];
int val[N];
int typ[N];
vector<int>mem[N];
int num;
int sta[N],top;
void tarjan(int x){
typ[x]=;
val[x]=;
low[x]=dfn[x]=++df;
sta[++top]=x;
for(reg i=hd[x];i;i=e[i].nxt){
int y=e[i].to;
if(!dfn[y]){
tarjan(y);
low[x]=min(low[x],low[y]);
if(low[y]>=dfn[x]){
++num;
int z;
do{
z=sta[top];
mem[num].push_back(z);
--top;
}while(z!=y);
mem[num].push_back(x);
}
}else low[x]=min(low[x],dfn[y]);
}
}
int sz[*N];
int totsz=;
void fin(int x,int fa){
vis[x]=;
totsz+=typ[x];
for(reg i=hd[x];i;i=e[i].nxt){
int y=e[i].to;
if(y==fa) continue;
fin(y,x);
}
}
void dfs(int x,int fa){
vis[x]=;
sz[x]=typ[x];
for(reg i=hd[x];i;i=e[i].nxt){
int y=e[i].to;
if(y==fa) continue;
dfs(y,x);
sz[x]+=sz[y];
}
ll tmp=totsz-sz[x];
for(reg i=hd[x];i;i=e[i].nxt){
int y=e[i].to;;
if(y==fa) continue;
ans=ans+tmp*sz[y]*val[x];
tmp+=sz[y];
}
}
int main(){
rd(n);rd(m);
int x,y;
for(reg i=;i<=m;++i){
rd(x);rd(y);
add(x,y);add(y,x);
}
for(reg i=;i<=n;++i){
if(!dfn[i]) tarjan(i);
}
int tot=n;
memset(hd,,sizeof hd);
cnt=;
//cout<<" num "<<num<<endl;
for(reg i=;i<=num;++i){
++tot;
typ[tot]=;
val[tot]=mem[i].size()-;
//cout<<" tot "<<tot<<endl;
for(reg j=;j<(int)mem[i].size();++j){
//cout<<" mem "<<mem[i][j]<<endl;
add(tot,mem[i][j]);
add(mem[i][j],tot);
}
}
for(reg i=;i<=tot;++i){
if(!vis[i]){
totsz=;
fin(i,);
dfs(i,);
}
}
printf("%lld",ans*);
return ;
} }
signed main(){
Miracle::main();
return ;
} /*
Author: *Miracle*
Date: 2019/2/15 9:04:01
*/