先预处理出每棵树的直径 d 和从每个点开始的最长路v。这样的话对于一个询问可以枚举在两棵树中选择的点，对答案的贡献是 max(d1,d2,vx+vy+1) 对。每棵树的 v 排序，在一棵树上枚举点，另一棵树上二分，可以做到O(nlogn)。 然后这个题就做完了，复杂度是 (nn√logn) 。 单次询问的复杂度可以看成是 O(min(sizeu,sizev)log(max(sizeu,sizev))) 。这样最坏情况出现在每一块大小都相等的时候，总的复杂度是 O(min(n,(nT)2)TlogT) ，其中 T 为每一块的大小。当T=n√时复杂度最大，为 O(qn√logn) 。
#include<cstdio> #include<vector> #include<map> #include<algorithm> using namespace std; const int maxn=200010; int down[maxn],from[maxn],down2[maxn],up[maxn],bel[maxn],dia[maxn],size[maxn],n,m,q,tot; double s[maxn]; vector<int> a[maxn],to[maxn]; vector<double> sum[maxn]; map<pair<int,int>,double> ans; void dfs1(int u,int f) { bel[u]=tot; size[tot]++; for (vector<int>::iterator it=to[u].begin();it!=to[u].end();++it) if ((*it)!=f) { dfs1(*it,u); if (down[*it]+1>=down[u]) { down2[u]=down[u]; down[u]=down[*it]+1; from[u]=*it; } else down2[u]=max(down2[u],down[*it]+1); } } void dfs2(int u,int f) { int x; if (f!=-1) { up[u]=up[f]+1; if (from[f]!=u) up[u]=max(up[u],down[f]+1); else up[u]=max(up[u],down2[f]+1); } x=max(up[u],down[u]); dia[tot]=max(x,dia[tot]); a[tot].push_back(x); for (vector<int>::iterator it=to[u].begin();it!=to[u].end();++it) if ((*it)!=f) dfs2(*it,u); } int main() { //freopen("in.txt","r",stdin); int u,v,x; double res,d,now; pair<int,int> pr; vector<int>::iterator i2; scanf("%d%d%d",&n,&m,&q); for (int i=1;i<=m;i++) { scanf("%d%d",&u,&v); to[u].push_back(v); to[v].push_back(u); } for (int i=1;i<=n;i++) if (!bel[i]) { tot++; dfs1(i,-1); dfs2(i,-1); sort(a[tot].begin(),a[tot].end()); sum[tot].push_back(now=0); for (vector<int>::iterator it=a[tot].begin();it!=a[tot].end();++it) sum[tot].push_back(now+=(*it)); s[tot]=now; } while (q--) { scanf("%d%d",&u,&v); u=bel[u]; v=bel[v]; if (u==v) { printf("-1\n"); continue; } if (size[u]>size[v]||(size[u]==size[v]&&u>v)) swap(u,v); pr=make_pair(u,v); if (ans.count(pr)) { printf("%.10f\n",ans[pr]); continue; } res=0; d=max(dia[u],dia[v]); for (vector<int>::iterator it=a[u].begin();it!=a[u].end();++it) { x=upper_bound(a[v].begin(),a[v].end(),d-(*it)-1)-a[v].begin(); res+=d*x+((*it)+1.0)*(size[v]-x)+s[v]-sum[v][x]; } res/=(double)size[u]*size[v]; printf("%.10f\n",ans[pr]=res); } }