不经过重点，考虑点双
点双，考虑圆方树
两个点s,t，中间路径上，所有点双里的点都可以经过，特别地，s,t作为割点的时候，不能往后走，也就是不能经过身后的方点
也就是，(s,t)经过树上路径上的所有圆点和方点
把方点权值设为点双大小-2，圆点权值设为1，（s,t）路径上的权值就是c的选择方案数（不算s,t自己权值）
问题转化为：求树上任意点对的距离和，(x,y),(y,x)算两次
在转化为考虑每个点的贡献，树形DP即可
注意：
1.可能不连通
2.sz统计的是圆点的个数
3.最后乘2
#include#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=0;bool fl=false; while(!isdigit(ch=getchar()))(ch=='-')&&(fl=true); for(x=numb;isdigit(ch=getchar());x=x*10+numb); (fl==true)&&(x=-x);}namespace Miracle{const int N=200000+5;const int M=200000+5;int n,m;struct node{ int nxt,to;}e[2*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=0;int vis[N];int val[N];int typ[N];vector mem[N];int num;int sta[N],top;void tarjan(int x){ typ[x]=1; val[x]=1; 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[2*N];int totsz=0;void fin(int x,int fa){ vis[x]=1; 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]=1; 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=1;i<=m;++i){ rd(x);rd(y); add(x,y);add(y,x); } for(reg i=1;i<=n;++i){ if(!dfn[i]) tarjan(i); } int tot=n; memset(hd,0,sizeof hd); cnt=0; //cout<<" num "< <