首页 > 代码库 > Codeforces 629 E. Famil Door and Roads
Codeforces 629 E. Famil Door and Roads
题目链接：http://codeforces.com/problemset/problem/629/E
询问这个简单环的期望。考虑将这个环拆成两部分。
令${deep[x]>=deep[y]}$，${size[x]}$表示以$x$为根的子树大小，${sdown[x]}$示以$x$为根的子树的所有节点到$x$的距离和，${sall[x]}$所有点到$x$的距离和。${ne}$表示从${y-->x}$路径上${y}$的儿子。
1.${dis(x,y)}$这是一个环肯定要经过的,算入答案。
2.分情况考虑:
若是${lca(x,y)!=y}$,会产生${\frac{sdown[x]}{size[x]}+\frac{sdown[y]}{size[y]}}$的贡献。
若是${lca(x,y)=y}$，会产生${\frac{sdown[x]}{size[x]}+\frac{sdall[y]-sdown[ne]-size[ne]}{n-size[ne]}}$的贡献。
1 #include<iostream> 2 #include<cstdio> 3 #include<algorithm> 4 #include<vector> 5 #include<cstdlib> 6 #include<cmath> 7 #include<cstring> 8 using namespace std; 9 #define maxn 200010 10 #define llg long long 11 #define yyj(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout); 12 llg n,m,T; 13 llg sall[maxn],sdown[maxn],deep[maxn],f[maxn][21],size[maxn]; 14 vector<llg>a[maxn]; 15 16 inline llg getint() 17 { 18 llg w=0,q=0; char c=getchar(); 19 while((c<‘0‘ || c>‘9‘) && c!=‘-‘) c=getchar(); if(c==‘-‘) q=1,c=getchar(); 20 while (c>=‘0‘ && c<=‘9‘) w=w*10+c-‘0‘, c=getchar(); return q ? -w : w; 21 } 22 23 void dfs1(llg x,llg fa) 24 { 25 llg w=a[x].size(),v; 26 deep[x]=deep[fa]+1; f[x][0]=fa; 27 size[x]=1; 28 for (llg i=0;i<w;i++) 29 { 30 v=a[x][i]; 31 if (v==fa) continue; 32 dfs1(v,x); 33 size[x]+=size[v]; 34 sdown[x]+=sdown[v]+size[v]; 35 } 36 } 37 38 void dfs2(llg x,llg fa) 39 { 40 llg w=a[x].size(),v; 41 for (llg i=0;i<w;i++) 42 { 43 v=a[x][i]; 44 if (v==fa) continue; 45 sall[v]=sall[x]+n-2*size[v]; 46 dfs2(v,x); 47 } 48 } 49 50 void init() 51 { 52 llg x,y; 53 cin>>n>>T; 54 for (llg i=1;i<n;i++) 55 { 56 x=getint(),y=getint(); 57 a[x].push_back(y),a[y].push_back(x); 58 } 59 deep[1]=1; 60 dfs1(1,0); 61 sall[1]=sdown[1]; 62 dfs2(1,0); 63 for (llg j=1;j<=20;j++) 64 for (llg i=1;i<=n;i++) 65 f[i][j]=f[f[i][j-1]][j-1]; 66 } 67 68 llg find(llg x,llg y) 69 { 70 for (llg i=20;i>=0;i--) 71 if (deep[f[x][i]]>=deep[y]) 72 x=f[x][i]; 73 if (x==y) return x; 74 for (llg i=20;i>=0;i--) 75 if (f[x][i]!=f[y][i]) 76 x=f[x][i],y=f[y][i]; 77 return f[x][0]; 78 } 79 80 llg dis(llg x,llg y) 81 { 82 return deep[x]+deep[y]-deep[find(x,y)]*2; 83 } 84 85 llg up(llg x,llg res) 86 { 87 for (llg i=20;i>=0;i--) 88 if (res>=(1<<i)) 89 { 90 x=f[x][i]; 91 res-=(1<<i); 92 } 93 return x; 94 } 95 96 int main() 97 { 98 yyj("tree"); 99 init();100 while (T--)101 {102 llg x,y;103 x=getint(),y=getint();104 if (deep[x]<deep[y]) swap(x,y);105 double ans=dis(x,y)+1;106 if (find(x,y)!=y)107 {108 ans+=(double)sdown[x]/(double)size[x]+(double)sdown[y]/(double)size[y];109 }110 else111 {112 llg ne=up(x,deep[x]-deep[y]-1);113 ans+=(double)sdown[x]/(double)size[x]+(double)(sall[y]-sdown[ne]-size[ne])/(double)(n-size[ne]);114 }115 printf("%.9lf\n",ans);116 }117 return 0;118 }
Codeforces 629 E. Famil Door and Roads
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。