Sponsors

Codeforces Round #411 (Div. 2), problem: (F) Expected diameter of a tree Solution In C/C++

#include <set>
#include <vector>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N=200050;
vector<int>vec[N],dis[N],sum[N];
struct Node{int x,y;double ans;}JY;
bool operator<(Node a,Node b){if(a.x!=b.x)return a.x<b.x;return a.y<b.y;}
set<Node>s;set<Node>::iterator it;
int n,m,q,first[N],nxt[N],v[N],w[N],tot,root,xx,yy,vis[N];
int maxx[N][2],rec[N][2],f[N],Root[N],vv[N],fi,flag,size[N];
void add(int x,int y){w[tot]=1,v[tot]=y,nxt[tot]=first[x],first[x]=tot++;}
int find(int x){return x==f[x]?x:f[x]=find(f[x]);}
void get_dia(int x,int fa){
rec[x][0]=rec[x][1]=x;
for(int i=first[x];~i;i=nxt[i])if(v[i]!=fa){
get_dia(v[i],x);
if(maxx[v[i]][0]+w[i]>maxx[x][0])
maxx[x][1]=maxx[x][0],rec[x][1]=rec[x][0],
maxx[x][0]=maxx[v[i]][0]+w[i],rec[x][0]=rec[v[i]][0];
else if(maxx[v[i]][0]+w[i]>maxx[x][1])
maxx[x][1]=maxx[v[i]][0]+w[i],rec[x][1]=rec[v[i]][0];
}if(maxx[x][0]+maxx[x][1]>maxx[root][0]+maxx[root][1])root=x;
}
void DFS(int x,int fa,int deep){
vv[x]=max(vv[x],deep);
if(flag)vec[fi].push_back(vv[x]),size[fi]++;
for(int i=first[x];~i;i=nxt[i])if(v[i]!=fa){
DFS(v[i],x,deep+w[i]);
}
}
int main(){
memset(first,-1,sizeof(first));
scanf(“%d%d%d”,&n,&m,&q);
for(int i=1;i<=n;i++)f[i]=i;
for(int i=1;i<=m;i++)
scanf(“%d%d”,&xx,&yy),add(xx,yy),add(yy,xx),f[find(xx)]=find(yy);
for(int i=1;i<=n;i++){
fi=find(i);
if(!rec[fi][0]){
root=flag=0,get_dia(i,0),Root[fi]=root;
DFS(rec[root][0],0,0),flag=1,DFS(rec[root][1],0,0);
}
}
for(int i=1;i<=n;i++){
fi=find(i);
if(!vis[fi]){
vis[fi]=1;
dis[fi].resize(size[fi]+1),sum[fi].resize(size[fi]+1);
for(int j=0;j<vec[fi].size();j++)
dis[fi][vec[fi][j]]++,sum[fi][vec[fi][j]]+=vec[fi][j];
for(int j=size[fi]-1;j>=0;j–)
dis[fi][j]+=dis[fi][j+1],sum[fi][j]+=sum[fi][j+1];
}
}
while(q–){
scanf(“%d%d”,&xx,&yy);
int fx=find(xx),fy=find(yy);
if(fx==fy){puts(“-1”);continue;}
if(vec[fx].size()>vec[fy].size())swap(xx,yy),swap(fx,fy);
JY.x=fx,JY.y=fy;
if((it=s.find(JY))!=s.end()){printf(“%.10lf\n”,it->ans);continue;}
int dis1=maxx[Root[fx]][0]+maxx[Root[fx]][1];
int dis2=maxx[Root[fy]][0]+maxx[Root[fy]][1];
int Dis=max(dis1,dis2);
long long ans=0;
for(int i=0;i<vec[fx].size();i++){
ans+=sum[fy][Dis-vec[fx][i]]+1ll*dis[fy][Dis-vec[fx][i]]*(vec[fx][i]+1);
ans+=1ll*Dis*(size[fy]-dis[fy][Dis-vec[fx][i]]);
}
JY.ans=(double)ans/size[fx]/size[fy],s.insert(JY);
printf(“%.10lf\n”,(double)ans/size[fx]/size[fy]);
}
// for(int i=1;i<=n;i++)printf(“%d “,vv[i]);
}

AgelessRx 2026: Longevity Telehealth...

AgelessRx 2026: Revolutionizing Longevity and Anti-Aging Telehealth As we move...

Can you release pet...

Why Releasing Pet Fish Into the Wild Is an...

Law & Order: SVU...

The Evolution of Captain Curry in Law & Order:...

Did humans cause coral...

Did Humans Cause Coral Bleaching? Exploring the Scientific TruthCoral...

The true meaning of...

Decoding the Shift in Australian Media and Global Strategy Recent...

Beijing warns of more...

Beijing Warns of New Volatility in Global Semiconductor Markets The...

AgelessRx 2026: Longevity Telehealth Platform Overview — Treatments, Pricing, Compounded Medications, and What Prospective Patients Should Know

AgelessRx 2026: Revolutionizing Longevity and Anti-Aging Telehealth As we move into 2026, the quest for a longer, healthier life has transitioned from a niche pursuit...

Can you release pet fish into the wild?

Why Releasing Pet Fish Into the Wild Is an Environmental DisasterReleasing a pet fish into a local pond, lake, or river might seem like...

Law & Order: SVU Star Talks Learning From The ‘Best In The Business,’ But How Much Does Curry Have Benson’s Back?

The Evolution of Captain Curry in Law & Order: SVU"Law & Order: Special Victims Unit" has long been celebrated for its ability to balance...

Did humans cause coral bleaching?

Did Humans Cause Coral Bleaching? Exploring the Scientific TruthCoral reefs are often called the “rainforests of the sea,” providing essential habitats for roughly a...

The true meaning of AUKUS, the ABC’s new Q+A is a turn off, and news.com’s TikTok mystery

Decoding the Shift in Australian Media and Global Strategy Recent developments across the Australian media and political landscape have sparked significant debate, ranging from the...

Beijing warns of more chip supply worries after Nexperia China claims it was cut off from SAP

Beijing Warns of New Volatility in Global Semiconductor Markets The global semiconductor landscape is facing a fresh wave of uncertainty as China’s Ministry of Commerce...

Should I fear raccoons?

Understanding Raccoon Behavior: Safety and Awareness Raccoons are some of the most recognizable urban wildlife in North America. With their distinctive black masks and ringed...

Family, former presidents and a Hall of Famer give Rev. Jesse Jackson a final sendoff

Honoring a Legacy: Rev. Jesse Jackson’s Final Sendoff The world paused to honor a titan of the civil rights movement as family members, former presidents,...

Humpback whale recovery is changing who fathers the calves

The Shifting Dynamics of Humpback Whale Paternity The recovery of humpback whale populations across the globe is often cited as a triumph for environmental protection...