专栏文章
题解:CF804D Expected diameter of a tree
CF804D题解参与者 2已保存评论 1
文章操作
快速查看文章及其快照的属性,并进行相关操作。
- 当前评论
- 1 条
- 当前快照
- 1 份
- 快照标识符
- @mingm3gg
- 此快照首次捕获于
- 2025/12/02 02:05 3 个月前
- 此快照最后确认于
- 2025/12/02 02:05 3 个月前
CF804D Expected diameter of a tree
感觉代码难度比较大吧。
题解
先判断无解条件,假如 在一棵树内,显然怎么连答案都是 。
然后分类讨论新的直径是否经过 这条边。
- 经过。设 表示 到连通块内最远点的距离,可以用两次 dfs 求出。那么新的直径就为 。
- 不经过。则为两棵树的直径取 。设点 所在的树的直径长度为 。
显然上述两种情况应该取 。
先不考虑多测,想想怎么做。设 。
显然上述那个式子只和 的值有关,故可以对每一棵树开一个桶来处理。
考虑枚举出一个 ,那么如果 ,新的直径就为 ,否则则是 。所以我们只要同时记录值和个数的后缀和就可以了。
这样做的复杂度是 ,多测的话复杂度可能会退化到 ,无法接受。
发现 的联通块个数 ,故考虑根号分治,直接把 的联通块拉出来,两两进行计算,那么复杂度就是 的,直接使用
map 记录答案,询问的时候直接输出就可以了。时间复杂度 。
代码写的比较丑陋,凑合看吧 qwq
code:
CPP#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;
}
相关推荐
评论
共 1 条评论,欢迎与作者交流。
正在加载评论...