题目
给一片森林,\(q\) 个询问,每个询问两个点,
问将这两个点所在的集合连接起来组成的新集合,它的最远两点的距离的期望值是多少。
分析
首先将以每个点为根的最大深度求出来,然后对于两棵树,
只有超过两棵树直径的最大值才可能产生新的直径,
那么直接求 \(d[x]+d[y]\geq mx\) 的 \(d[x]+d[y]\),
用小的集合查询然后记忆化就可以做到 \(O(Q\sqrt{n}\log{n})\)
代码
#include <cstdio>
#include <cctype>
#include <map>
#include <algorithm>
#include <vector>
using namespace std;
const int N=100011; typedef long long lll;
map<pair<int,int>,lll>uk; vector<int>K[N];
struct node{int y,next;}e[N<<1]; vector<lll>F[N];
int col[N],f[N],g[N],dp[N],as[N],n,m,Q,et=1,upd,len[N];
int iut(){
int ans=0; char c=getchar();
while (!isdigit(c)) c=getchar();
while (isdigit(c)) ans=ans*10+c-48,c=getchar();
return ans;
}
int max(int a,int b){return a>b?a:b;}
void dfs1(int x,int fa){
col[x]=upd;
for (int i=as[x];i;i=e[i].next)
if (e[i].y!=fa){
dfs1(e[i].y,x),dp[upd]=max(dp[upd],f[x]+f[e[i].y]+1);
if (f[x]<f[e[i].y]+1) g[x]=f[x],f[x]=f[e[i].y]+1;
else if (g[x]<f[e[i].y]+1) g[x]=f[e[i].y]+1;
}
}
void dfs2(int x,int fa){
for (int i=as[x];i;i=e[i].next)
if (e[i].y!=fa){
if (f[x]==f[e[i].y]+1){
if (f[e[i].y]<g[x]+1) g[e[i].y]=f[e[i].y],f[e[i].y]=g[x]+1;
else if (g[e[i].y]<g[x]+1) g[e[i].y]=g[x]+1;
}else{
if (f[e[i].y]<f[x]+1) g[e[i].y]=f[e[i].y],f[e[i].y]=f[x]+1;
else if (g[e[i].y]<f[x]+1) g[e[i].y]=f[x]+1;
}
dfs2(e[i].y,x);
}
}
int main(){
n=iut(); m=iut(); Q=iut();
for (int i=1;i<=m;++i){
int x=iut(),y=iut();
e[++et]=(node){y,as[x]},as[x]=et;
e[++et]=(node){x,as[y]},as[y]=et;
}
for (int i=1;i<=n;++i)
if (!col[i]) ++upd,dfs1(i,0),dfs2(i,0);
for (int i=1;i<=n;++i) K[col[i]].push_back(f[i]);
for (int i=1;i<=upd;++i) sort(K[i].begin(),K[i].end());
for (int i=1;i<=upd;++i){
len[i]=K[i].size(),F[i].resize(len[i]+1);
for (int j=len[i];j;--j)
F[i][j-1]=F[i][j]+K[i][j-1];
}
for (int i=1;i<=Q;++i){
int x=col[iut()],y=col[iut()];
if (x==y) {printf("-1\n"); continue;}
if (len[x]>len[y]) swap(x,y);
if (uk.count(make_pair(x,y))) {printf("%.8lf\n",uk[make_pair(x,y)]/(1.0*len[x]*len[y])); continue;}
lll now=max(dp[x],dp[y]),ans=now*len[x]*len[y];
for (int j=0;j<len[x];++j){
int pos=lower_bound(K[y].begin(),K[y].end(),now-K[x][j])-K[y].begin();
ans+=F[y][pos]+(len[y]-pos)*(K[x][j]-now+1);
}
uk[make_pair(x,y)]=ans;
printf("%.8lf\n",ans/(1.0*len[x]*len[y]));
}
return 0;
}