题解：CF804D Expected diameter of a tree

· · 题解

CF804D Expected diameter of a tree

感觉代码难度比较大吧。

题解

先判断无解条件，假如 u,v 在一棵树内，显然怎么连答案都是 -1。

然后分类讨论新的直径是否经过 (u,v) 这条边。

显然上述两种情况应该取 \max。

先不考虑多测，想想怎么做。设 d = \max(di_u,di_v)。

显然上述那个式子只和 g_u 的值有关，故可以对每一棵树开一个桶来处理。

考虑枚举出一个 g_u，那么如果 g_v \ge d-g_u-1，新的直径就为 g_u+g_v+1，否则则是 d。所以我们只要同时记录值和个数的后缀和就可以了。

这样做的复杂度是 O(\max g_u)，多测的话复杂度可能会退化到 O(qn)，无法接受。

发现 \max g_u \ge \sqrt{n} 的联通块个数 \le \sqrt{n}，故考虑根号分治，直接把 \max g_u \ge \sqrt{n} 的联通块拉出来，两两进行计算，那么复杂度就是 O(n) 的，直接使用 map 记录答案，询问的时候直接输出就可以了。

时间复杂度 O(n + q\sqrt{n})。

代码写的比较丑陋，凑合看吧 qwq

code:

#include<bits/stdc++.h>
using namespace std;
#define il inline
#define pii pair<int,ll>
#define fi first
#define se second
#define mkp make_pair
#define eb emplace_back
typedef long long ll;
const int N=1e5+5;
int n,m,q;
int bel[N],tmp[N],qwq[N];
int g[N];
int f[N][17],dep[N],des[N],sz[N];
bool vis[N];
vector<int> vec[N],euij;
vector<pii > tng[N];
map<pii,double> mp;
namespace Graph{
    int hd[N],cnt=0;
    struct edge{int to,nxt;}e[N<<1];
    il void adde(int from,int to){e[++cnt]={to,hd[from]};hd[from]=cnt;}
}using namespace Graph;
int rex;
void dfs0(int u,int fat,int tp){ 
    dep[u]=dep[fat]+1;
    f[u][0]=fat;
    bel[u]=tp;vec[tp].eb(u);//标记每一个点所在的树
    sz[tp]++;
    vis[u]=1;
    if(dep[u]>dep[rex]) rex=u;
    for(int i=1;i<=16;i++) f[u][i]=f[f[u][i-1]][i-1];//因为要算离得最远的点的距离，所以要倍增求lca 
    for(int i=hd[u],v;i;i=e[i].nxt) ((v=e[i].to)^fat)&&(dfs0(v,u,tp),831);
}
void dfs1(int u,int fat){
    des[u]=des[fat]+1;
    if(des[u]>des[rex]) rex=u;
    for(int i=hd[u],v;i;i=e[i].nxt) ((v=e[i].to)^fat)&&(dfs1(v,u),831);
}
il int lca(int x,int y){
    if(dep[x]<dep[y]) swap(x,y);
    for(int i=16;i>=0;i--) (dep[f[x][i]]>=dep[y])&&(x=f[x][i]);
    if(x==y) return x;
    for(int i=16;i>=0;i--) (f[x][i]^f[y][i])&&(x=f[x][i],y=f[y][i]);
    return f[x][0];
}
il int getd(int x,int y){return dep[x]+dep[y]-2ll*dep[lca(x,y)];}//两点距离 
il double sol(int o,int oo){//其中o是u所在的树，oo是v所在的树 
    int fo=tng[o].size(),foo=tng[oo].size();//两棵树的直径 
    int dd=max(fo,foo)-1;//文中的d 
    ll tot=0;//先求和 
    for(int i=0;i<fo;i++){//i -> g[x]
        int gac=tng[o][i].fi-(i!=fo-1?tng[o][i+1].fi:0);//g[x]的个数 
        if(!gac) continue;//如果根本没有g[x]是当前这个值 
        if(dd-i-1>=foo)  tot+=1ll*sz[oo]*gac*dd;//怎么连都不如d优 
        else if(dd-i-1<0) tot+=1ll*gac*(tng[oo][0].se+1ll*sz[oo]*(i+1));//怎么连都比d优 
        else tot+=1ll*gac*(tng[oo][dd-i-1].se+1ll*tng[oo][dd-i-1].fi*(i+1)+1ll*dd*(tng[oo][0].fi-tng[oo][dd-i-1].fi));//分类 
    }
    return 1.0*tot/sz[o]/sz[oo];//连法是 sz[o]*sz[oo] 种 
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>n>>m>>q;int B=sqrt(n);
    for(int i=1,u,v;i<=m;i++){
        cin>>u>>v;
        adde(u,v);adde(v,u);
    }
    for(int i=1;i<=n;i++) if(!vis[i]){
        rex=0;dfs0(i,0,i);
        int o1=rex,o2;
        rex=0;dfs1(o1,0);
        o2=rex;
        //求出直径两端点 
        int res=0;
        for(int x:vec[i]){
            g[x]=max(getd(x,o1),getd(x,o2));
            res=max(res,g[x]);//算出g[x] 
            qwq[g[x]]++;
        }
        if(res>=B) euij.eb(i);//把直径长度大于 sqrt(n) 的拎出来 
        for(int j=0;j<=res;j++) tng[i].eb(mkp(qwq[j],1ll*j*qwq[j]));
        for(int j=res-1;j>=0;j--)   tng[i][j]=mkp(tng[i][j+1].fi+tng[i][j].fi,tng[i][j+1].se+tng[i][j].se);//后缀和 
        for(int x:vec[i]) qwq[g[x]]=0;//清空 
    }

    for(int o:euij) for(int oo:euij) if(o^oo) mp[mkp(o,oo)]=sol(o,oo);
    for(int x,y;q;q--){
        cin>>x>>y;
        int o=bel[x],oo=bel[y];
        if(o==oo){cout<<-1<<'\n';continue;}//无解 
        int fo=tng[o].size(),foo=tng[oo].size();
        if(fo>B&&foo>B){cout<<fixed<<setprecision(7)<<mp[mkp(o,oo)]<<'\n';continue;}//已经预处理过了 
        if(fo>foo) swap(o,oo);//枚举小于 sqrt(n) 的那一部分 g[x] 
        cout<<fixed<<setprecision(7)<<sol(o,oo)<<'\n';
    } 
    return 0;
}