记$d_{G}(x,y)$表示无向图$G$中从$x$到$y$的最短路，设给定的图为$G=(V,E)$，$T$为其生成树，$E_{T}$为$T$的边集
下面，考虑计算$f(x,y)$——
首先，对于一棵树$T$，$z$在$x$到$y$的路径上（包括$x$和$y$）当且仅当$d_{T}(x,z)+d_{T}(z,y)=d_{T}(x,y)$
同时，由于$T$的性质，上述这三项都与$d_{G}$中相同，即等价于$d_{G}(x,z)+d_{G}(z,y)=d_{G}(x,y)$
由于这与$T$无关，即可确定$T$中在$x$到$y$的路径上的点（满足上述条件的$z$）
进而，当点数不等于$d_{G}(x,y)+1$（也即有多条最短路）必然无解，否则显然最短路存在且唯一
反过来，也可以确定不在$x$到$y$路径上的点$z$，考虑在$T$中以$x$或$y$为根，$z$的父亲$fa$必然是同一个节点，且显然也满足以下性质——
$(z,fa)\in E_{T}$、$d_{T}(x,z)=d_{T}(x,fa)+1$且$d_{T}(y,z)=d_{T}(y,fa)+1$
类似的，第一个条件写作$(z,fa)\in E$，后两个条件也可以等价的写作$d_{G}$
此时，当确定每一个不在$x$到$y$路径上点的$fa$时，将所有的$(z,fa)$以及$x$到$y$的最短路上所有边构成$E_{T}$，由于最短路的性质，这必然合法
因此，最终答案即所有不在$x$到$y$路径上节点$fa$的个数乘积，预处理最短路后计算复杂度为$o(m)$
最短路使用bfs即$o(nm)$，总复杂度为$o(n^{2}m)$，可以通过
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define N 405 4 #define M 605 5 #define mod 998244353 6 struct Edge{ 7 int nex,to; 8 }edge[M<<1]; 9 queue<int>q; 10 int E,n,m,x,y,head[N],vis[N],d[N][N]; 11 void add(int x,int y){ 12 edge[E].nex=head[x]; 13 edge[E].to=y; 14 head[x]=E++; 15 } 16 void bfs(int st){ 17 memset(vis,0,sizeof(vis)); 18 q.push(st); 19 vis[st]=1; 20 while (!q.empty()){ 21 int k=q.front(); 22 q.pop(); 23 for(int i=head[k];i!=-1;i=edge[i].nex) 24 if (!vis[edge[i].to]){ 25 d[st][edge[i].to]=d[st][k]+1; 26 q.push(edge[i].to); 27 vis[edge[i].to]=1; 28 } 29 } 30 } 31 int main(){ 32 scanf("%d%d",&n,&m); 33 memset(head,-1,sizeof(head)); 34 for(int i=1;i<=m;i++){ 35 scanf("%d%d",&x,&y); 36 add(x,y); 37 add(y,x); 38 } 39 for(int i=1;i<=n;i++)bfs(i); 40 for(int i=1;i<=n;i++){ 41 for(int j=1;j<=n;j++){ 42 int tot=0,ans=1; 43 for(int k=1;k<=n;k++) 44 if (d[i][k]+d[k][j]==d[i][j])tot++; 45 else{ 46 int s=0; 47 for(int l=head[k];l!=-1;l=edge[l].nex) 48 if ((d[i][k]==d[i][edge[l].to]+1)&&(d[j][k]==d[j][edge[l].to]+1))s++; 49 ans=1LL*ans*s%mod; 50 } 51 if (tot!=d[i][j]+1)ans=0; 52 printf("%d ",ans); 53 } 54 printf("\n"); 55 } 56 }
原文：https://www.cnblogs.com/PYWBKTDA/p/14731845.html
