题目大意

给一个有n个点，m条边的无向连通图，求所有点两两之间的最短路。$(2<=n<=10^5;n-1<=m<=n+42)$

solution

我们注意到$m-n+1$很小。先任意求一棵生成树，然后将剩余$m-n+1$条边涉及的点建一棵虚树。分类讨论如下情况即可：

（1）不属于虚树上任意一条边的点到所有点的贡献；单次操作$O(1)$（合并到虚树边上的点）

（2）一个点到同一条边内其它点的最短路和（非关键点）；单次操作$O(1)$

（3）一个在虚树上某条边的点（包括关键点）到其它边内非关键点的贡献。单次操作$O(m-n+1)$

（4）关键点到关键点的最短路和。$O((m-n+1)*$最短路复杂度$)$

用前缀和和后缀和优化即可，时间复杂度为$O(m(m-n+1))$。

#include
#include
#include
using namespace std;
#define ot original_tree
#define vt virtual_tree
typedef long long ll;
const int LEN=;
char str[];int pos=;
inline int rd(){
char c=str[pos++];int x=,flag=;
for(;c<''||c>'';c=str[pos++])if(c=='-')flag=-;
for(;c>=''&&c<='';c=str[pos++])x=x*+c-''; return x*flag; } const int N=,M=; int n,m;ll ans=; inline int min_(int x,int y){ return (x<=y)?x:y; } namespace original_tree{ struct tree{int dep,dfn,sz,fa[];}t[N]; struct edge{int to,nxt;}e[N<<]; int tim=,cur[N]={},head[N]={}; bool tag[N]={false}; void dfs(int u){ for(int i=;i<;i++) t[u].fa[i]=t[t[u].fa[i-]].fa[i-]; t[u].sz=;cur[t[u].dfn=++tim]=u; for(int i=head[u];i;i=e[i].nxt){ int v=e[i].to; if(t[v].sz) continue; tag[(i>m)?i-m:i]=true;
t[v].dep=t[u].dep+;
t[v].fa[]=u;dfs(v);
t[u].sz+=t[v].sz;
}
return;
}
void build(){
memset(t,,sizeof(t));
for(int i=;i<=m;i++){ int u=rd(),v=rd(); e[i]=(edge){v,head[u]};head[u]=i; e[m+i]=(edge){u,head[v]};head[v]=m+i; } dfs(); return; } inline int lca(int u,int v){ if(t[u].dep&&ot::t[st[top-]].dep>=ot::t[pre].dep;top--){
link(id[st[top]],id[st[top-]],ot::t[st[top]].dep-ot::t[st[top-]].dep);
fa[id[st[top]]]=id[st[top-]];
}
if(st[top]!=pre){
link(id[st[top]],id[pre]=++num,ot::t[st[top]].dep-ot::t[pre].dep);
fa[id[st[top]]]=id[pre];vid[num]=st[top]=pre;
}
vid[id[st[++top]=x]=++num]=x;
}
for(int i=top;i>;i--){
link(id[st[i]],id[st[i-]],ot::t[st[i]].dep-ot::t[st[i-]].dep);
fa[id[st[i]]]=id[st[i-]];
}
for(int i=;i<=m;i++) if(!ot::tag[i]) link(id[ot::e[i].to],id[ot::e[m+i].to],); return; } void spfa(){ memset(dis,0x3f,sizeof(dis)); for(int x=;x<=num;x++){ q[ql=qr=]=x;dis[x][x]=;inq[x]=true; while(ql<=qr){ int u=q[ql++];inq[u]=false; for(int i=head[u];i;i=e[i].nxt){ int v=e[i].to; if(dis[x][v]>dis[x][u]+e[i].dis){
dis[x][v]=dis[x][u]+e[i].dis;
if(!inq[v])
inq[q[++qr]=v]=true;
}
}
}
}
return;
}
void solve(){
for(int i=;i<=num;i++) for(int u=vid[i];u!=vid[fa[i]];u=ot::t[u].fa[]) inv[u]=true; inv[]=true; for(int u=;u<=n;u++){ if(!inv[u]) continue; sz[u]=; for(int i=ot::head[u];i;i=ot::e[i].nxt){ int v=ot::e[i].to,pos=ot::t[v].sz; if(inv[v]) continue; ans+=(ll)pos*(n-pos);sz[u]+=pos; ot::solve(v); } } for(int i=;i<=num;i++) len[i]=ot::t[vid[i]].dep-ot::t[vid[fa[i]]].dep-; for(int x=;x<=num;x++){ if(!len[x])continue; pre[len[x]+]=p[len[x]+]=suf[len[x]+]=s[len[x]+]=; for(int i=,u=ot::t[vid[x]].fa[];i<=len[x];i++,u=ot::t[u].fa[]) pre[i]=pre[i-]+(ll)i*sz[u],p[i]=p[i-]+sz[u]; for(int i=,u=ot::t[vid[x]].fa[];i<=len[x];i++,u=ot::t[u].fa[]) suf[i]=(ll)(len[x]-i+)*sz[u],s[i]=sz[u]; for(int i=len[x]-;i;i--) suf[i]+=suf[i+],s[i]+=s[i+]; int dist=dis[x][fa[x]],dep1=ot::t[vid[x]].dep;ll val=; for(int u=ot::t[vid[x]].fa[];u!=vid[fa[x]];u=ot::t[u].fa[]){ int now=dep1-ot::t[u].dep,d=min_(now,len[x]-now+);ll res=; res+=pre[now+d-]-pre[now-]-(p[now+d-]-p[now-])*now; res+=suf[now-d+]-suf[now+]-(s[now-d+]-s[now+])*(len[x]-now+); if(now==len[x]-now+){ val+=res*sz[u]; continue; } int l=now-d,r=now+d; if(r==len[x]+){ if(l<=dist+) res+=suf[]-suf[l+]-(s[]-s[l+])*(len[x]-now+); else{ int h=(l-dist-)>>,tg=(l-dist-)&;
res+=pre[h+tg]+p[h+tg]*(len[x]-now++dist);
res+=suf[l-dist-h]-suf[l+]-(s[l-dist-h]-s[l+])*(len[x]-now+);
}
}
else{
if(len[x]-r+<=dist+) res+=pre[len[x]]-pre[r-]-(p[len[x]]-p[r-])*now; else{ int h=(len[x]-r-dist)>>,tg=(len[x]-r-dist)&;
res+=pre[r+dist+h]-pre[r-]-(p[r+dist+h]-p[r-])*now;
res+=suf[len[x]-h-tg+]+s[len[x]-h-tg+]*(now+dist);
}
}
val+=res*sz[u];
}//point in the same edge
ans+=val>>;
for(int y=;y=len[x]){
if(dis1<=dis2) ans+=(pre[len[x]]+p[len[x]]*dis1)*sz[u]; else ans+=(suf[]+s[]*dis2)*sz[u]; continue; } int h=(len[x]-d)>>,tg=(len[x]-d)&;
if(dis1<=dis2){ val+=pre[d+h+tg]+p[d+h+tg]*dis1; val+=suf[len[x]-h+]-suf[len[x]+]+(s[len[x]-h+]-s[len[x]+])*dis2; } else{ val+=pre[h+tg]+p[h+tg]*dis1; val+=suf[len[x]-d-h+]+s[len[x]-d-h+]*dis2; } ans+=val*sz[u]; } }//edge to edge for(int i=;i<=num;i++){ int dis1=dis[x][i],dis2=dis[fa[x]][i]; int d=abs(dis1-dis2);ll val=; if(d>=len[x]){
if(dis1<=dis2) ans+=(pre[len[x]]+p[len[x]]*dis1)*sz[vid[i]]; else ans+=(suf[]+s[]*dis2)*sz[vid[i]]; continue; } int h=(len[x]-d)>>,tg=(len[x]-d)&;
if(dis1<=dis2){
val+=pre[d+h+tg]+p[d+h+tg]*dis1;
val+=suf[len[x]-h+]-suf[len[x]+]+(s[len[x]-h+]-s[len[x]+])*dis2;
}
else{
val+=pre[h+tg]+p[h+tg]*dis1;
val+=suf[len[x]-d-h+]+s[len[x]-d-h+]*dis2;
}
ans+=val*sz[vid[i]];
}//key point to edge
}
for(int i=;i<num;i++)
for(int j=i+;j<=num;j++)
ans+=(ll)sz[vid[i]]*sz[vid[j]]*dis[i][j];
return;
}
}
int main(){
fread(str,,LEN,stdin);
n=rd();m=rd();ot::build();
vt::build();vt::spfa();
vt::solve();
printf("%lld\n",ans);
return ;
}