锐客网

  1. 首页 > it技术 > >

codeforces|codeforces E. Famil Door and Roads 期望

一棵树，n个节点，边长为1，有q个询问，每个询问给出u,v(u != v)，问在树上等概率加一条边，如果使得u，v在一个环内，则这种加边方式是合法的，此时的值为环的长度，所有合法的加边方式出现的概率相等，问值的期望。
2 <= n,m <= 10^5
对于u,v原来路径上的边一定在环内，贡献为1，新加的边也一定在环内，贡献为1，求其余的边的贡献就行了

分2种情况考虑：
1.lca(u,v) 不等于u 和 v
2.lca(u,v) 为u 或者 v

代码：

//File Name: cf629E.cpp //Created Time: 2017年01月05日 星期四 17时20分29秒#include #define LL long long using namespace std; const int MAXN = 100000 + 2; int siz[MAXN],dis[MAXN]; int pa[MAXN][20]; LL f[MAXN],g[MAXN]; vector G[MAXN]; void dfs0(int u,int p){ siz[u] = 1; dis[u] = dis[p] + 1; f[u] = 0; for(int i=0; i=0; --j){ if(dis[a] - (1<= dis[b]) a = pa[a][j]; } if(a == b) return a; for(int j=cnt; j>=0; --j){ if(pa[a][j] != -1 && pa[a][j] != pa[b][j]) a = pa[a][j],b = pa[b][j]; } return pa[a][0]; } int cal(int u,int v){ int cnt = 0; for(; (1<=0; --j){ if(dis[u] - (1< dis[v]) u = pa[u][j]; } return u; } void solve(int n,int m){ memset(pa,-1,sizeof(pa)); dfs0(1,0); //dis,siz,in,f,pa[i][0],dep g[1] = f[1]; dfs1(1,0,n); //g cal_pa(n); // pa int u,v,lca,w; while(m--){ scanf("%d %d",&u,&v); lca = cal_lca(u,v); if(lca != u && lca != v){ int tmp = dis[u] + dis[v] - 2 * dis[lca] + 1; double ans = tmp + (f[u] + 0.0) / siz[u] + (f[v] + 0.0) / siz[v]; printf("%.15f\n",ans); } else{ if(lca == u) swap(u,v); w = cal(u,v); if(pa[w][0] != v){ printf("-1"); return ; } int tmp = dis[u] - dis[v] + 1; double ans = tmp + (f[u] + 0.0) / siz[u] + (g[v] - f[w] - siz[w] + 0.0) / (n - siz[w]); printf("%.15f\n",ans); } } } int main(){ int n,m; scanf("%d %d",&n,&m); for(int i=1,u,v; i

【codeforces|codeforces E. Famil Door and Roads 期望】转载于:https://www.cnblogs.com/-maybe/p/6254154.html

    推荐阅读


    上一篇：Slim|Slim Span (最小生成树）

    下一篇：request/response解决中文乱码！！！