codeforces E. Famil Door and Roads 期望

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 <bits/stdc++.h>
#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<int> G[MAXN];
void dfs0(int u,int p){siz[u] = 1;dis[u] = dis[p] + 1;f[u] = 0;for(int i=0;i<G[u].size();++i){int v = G[u][i];if(v == p) continue;pa[v][0] = u;dfs0(v,u);siz[u] += siz[v];f[u] += f[v] + siz[v];}
}
void dfs1(int u,int p,int n){for(int i=0;i<G[u].size();++i){int v = G[u][i];if(v == p) continue;g[v] = n + g[u] - 2 * siz[v];dfs1(v,u,n);}
}
void cal_pa(int n){for(int j=1;(1<<j)<=n;++j){for(int i=1;i<=n;++i){if(pa[i][j-1] != -1)pa[i][j] = pa[pa[i][j-1]][j-1];}}
}
int cal_lca(int a,int b){if(dis[a] < dis[b]) swap(a,b);int cnt = 0;for(;(1<<cnt)<=dis[a];++cnt);--cnt;for(int j=cnt;j>=0;--j){if(dis[a] - (1<<j) >= 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<<cnt)<=dis[u];++cnt);--cnt;for(int j=cnt;j>=0;--j){if(dis[u] - (1<<j) > 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],depg[1] = f[1];dfs1(1,0,n);     //gcal_pa(n); // paint 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("%.15fn",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("%.15fn",ans);}}
}
int main(){int n,m;scanf("%d %d",&n,&m);for(int i=1,u,v;i<n;++i){scanf("%d %d",&u,&v);G[u].push_back(v);G[v].push_back(u);}solve(n,m);return 0;
}

转载于:.html