专栏文章

题解: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

感觉代码难度比较大吧。

题解

先判断无解条件,假如 u,vu,v 在一棵树内,显然怎么连答案都是 1-1
然后分类讨论新的直径是否经过 (u,v)(u,v) 这条边。
  • 经过。设 gxg_x 表示 xx 到连通块内最远点的距离,可以用两次 dfs 求出。那么新的直径就为 gu+gv+1g_u+g_v+1
  • 不经过。则为两棵树的直径取 max\max。设点 uu 所在的树的直径长度为 diudi_u
显然上述两种情况应该取 max\max
先不考虑多测,想想怎么做。设 d=max(diu,div)d = \max(di_u,di_v)
显然上述那个式子只和 gug_u 的值有关,故可以对每一棵树开一个桶来处理。
考虑枚举出一个 gug_u,那么如果 gvdgu1g_v \ge d-g_u-1,新的直径就为 gu+gv+1g_u+g_v+1,否则则是 dd。所以我们只要同时记录值和个数的后缀和就可以了。
这样做的复杂度是 O(maxgu)O(\max g_u),多测的话复杂度可能会退化到 O(qn)O(qn),无法接受。
发现 maxgun\max g_u \ge \sqrt{n} 的联通块个数 n\le \sqrt{n},故考虑根号分治,直接把 maxgun\max g_u \ge \sqrt{n} 的联通块拉出来,两两进行计算,那么复杂度就是 O(n)O(n) 的,直接使用 map 记录答案,询问的时候直接输出就可以了。
时间复杂度 O(n+qn)O(n + q\sqrt{n})
代码写的比较丑陋,凑合看吧 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 条评论,欢迎与作者交流。

正在加载评论...