【题目链接】 http://codeforces.com/contest/804/problem/D
【题目大意】
给你一个森林，每次询问给出u,v，
从u所在连通块中随机选出一个点与v所在连通块中随机选出一个点相连，
问你此时相连出的树的直径期望是多少？（如果本身就在同一个连通块内，则输出-1）
【题解】
我们利用树形dp记录每个点属于的连通块，
以及每个点到不同分支最远点的距离，记为mxd[i]
一遍搜索计算出向下最远，再次搜索的时候得到向上最远即可。
得到各个分支的最远距离之后，我们将其进行排序，
通过最远和次远分支计算是否可能成为树的直径，更新所属树的直径的答案diam。
考虑连接u和v所属的树X和树Y，
如果连接是点x和点y，那么所做的期望贡献就是max(mxdx+mxdy+1,diamX,diamY),
考虑枚举每个mxdx和mxdy得到组合来计算期望复杂度过高，我们考虑优化，
我们发现当mxdx+mxdy<max(diamX,diamY)的时候，期望均为max(diamX,diamY)
那么对于mxdx，我们在mxdy的有序集合Disy中分治查找max(diamX,diamY)-mxdx的位置，
就得到对于mxdx来说贡献为max(diamX,diamY)的数量，大于部分则直接求和即可，
我们预处理每个有序集Dis的后缀和，以减少求和的复杂度。
计算出期望之后，考虑到可能有多组点计算的是同一对树，因此我们用map对答案进行记忆化。
【代码】
#include <cstdio>
#include <algorithm>
#include <utility>
#include <map>
#include <vector>
#include <cstring>
using namespace std;
const int N=100010;
typedef long long LL;
vector<int> v[N]; // 邻接表
vector<int> dis[N]; // 该点各个分支的最远距离
int cc[N],cn; // 从属的连通块编号
int mxd[N],diam[N]; // 到树的最远距离和树的直径
vector<int> Dis[N]; // 每个连通块中各点到树的最远距离集
vector<int> sum[N];
int dfs(int x,int fx){
cc[x]=cn;
int Dist=0;
for(int i=0;i<v[x].size();i++){
int y=v[x][i];
if(y==fx)continue;
dis[x][i]=dfs(y,x)+1;
Dist=max(Dist,dis[x][i]);
}return Dist;
}
void dfs2(int x,int fx,int Dis){
for(int i=0;i<v[x].size();i++){
int y=v[x][i];
if(y!=fx)continue;
dis[x][i]=Dis+1;
}if(dis[x].size()==0){mxd[x]=0;diam[cc[x]]=0;return;}
vector<pair<int,int> > Dists(dis[x].size());
for(int i=0;i<Dists.size();i++)Dists[i]=make_pair(dis[x][i],i);
sort(Dists.rbegin(),Dists.rend());
mxd[x]=Dists[0].first;
diam[cc[x]]=max(mxd[x],diam[cc[x]]);
if(Dists.size()>1)diam[cc[x]]=max(diam[cc[x]],Dists[0].first+Dists[1].first);
for(int i=0;i<v[x].size();i++){
int y=v[x][i];
if(y==fx)continue;
if(Dists[0].second!=i)dfs2(y,x,Dists[0].first);
else if(Dists.size()>1)dfs2(y,x,Dists[1].first);
else dfs2(y,x,0);
}
}
LL cal(int x,int y){
if(Dis[x].size()>Dis[y].size())swap(x,y);
LL ans=0;
int mxdiam=max(diam[x],diam[y]);
for(int i=0;i<Dis[x].size();i++){
LL len=lower_bound(Dis[y].begin(),Dis[y].end(),mxdiam-Dis[x][i])-Dis[y].begin();
ans+=len*mxdiam+(Dis[y].size()-len)*(Dis[x][i]+1)+sum[y][len];
}return ans;
}
void init(){
memset(cc,0,sizeof(cc));
memset(v,0,sizeof(v));
memset(dis,0,sizeof(dis));
memset(Dis,0,sizeof(Dis));
memset(sum,0,sizeof(sum));
}
int n,m,q;
int main(){
while(~scanf("%d%d%d",&n,&m,&q)){
init();
for(int i=0;i<m;i++){
int x,y;
scanf("%d%d",&x,&y);
v[x].push_back(y);
v[y].push_back(x);
dis[x].push_back(-1);
dis[y].push_back(-1);
}cn=0;
for(int i=1;i<=n;i++)if(!cc[i]){++cn;dfs(i,-1);dfs2(i,-1,0);}
for(int i=1;i<=n;i++)Dis[cc[i]].push_back(mxd[i]);
for(int i=1;i<=cn;i++){
sort(Dis[i].begin(),Dis[i].end());
sum[i].resize(Dis[i].size()+1);
sum[i][Dis[i].size()]=0;
for(int j=Dis[i].size()-1;j>=0;j--)sum[i][j]=sum[i][j+1]+Dis[i][j];
}
map<pair<int,int>,double> dp;
while(q--){
int x,y;
scanf("%d%d",&x,&y);
x=cc[x],y=cc[y];
if(x==y){puts("-1");continue;}
if(dp.count(make_pair(x,y))==1)printf("%0.9lf
",dp[make_pair(x,y)]);
else{
LL t=cal(x,y),u=(LL)Dis[x].size()*Dis[y].size();
double ans=(double)t/u;
printf("%0.9lf
",ans);
dp[make_pair(x,y)]=ans;
}
}
}return 0;
}