题解 CF629E 【Famil Door and Roads】

# 题目分析 我们首先以1为根。 对于给定的 $a,b$，若 $lca_{a,b}$ 不是 $a,b$，则只有在分别连接 $a,b$ 的子树内的点时（分别记为 $x,y$），$a,b$ 才可能在一个环内，此时环的长度就是 $1+dis_{a,b}+dis_{a,x}+dis_{b,y}$，所以我们只需求出$dis_{a,x},dis_{b,y}$ 的期望长度即可，这只需求出 $a$ 子树内所有点到 $a$ 的距离和，再除以 $size_a$ 即可，对 $b$ 同理，这个直接DP即可求出。 若 $lca_{a,b}$ 是 $a,b$ 中的一个（这里假设等于 $a$），则我们需要求出 $a$ 的儿子中在 $(a,b)$ 这条链上的儿子，即 $b$ 的$dep_b-dep_a-1$ 级祖先(记为 $son$)。然后可以发现只有在连接 $b$ 的子树内的点（记为 $x$）和除去 $son$ 的子树外的所有点(记为 $y$)时，$a,b$ 才可能在一个环内，此时环的长度就是 $1+dis_{a,b}+dis_{a,x}+dis_{b,y}$，所以我们只需求出$dis_{a,x},dis_{b,y}$ 的期望长度即可，$dis_{b,y}$ 的期望的计算方法同上，$dis_{a,x}$ 的期望需要我们求出所有点到 $a$ 的长度和，再减去 $son$ 的贡献，再除以 $n-size_{son}$，这个需要换根DP。 我使用了倍增来在线求LCA和K级祖先，复杂度 $O(NlogN)$，但其实可以用离线求LCA和K级祖先来做到 $O(N)$ ``` cpp #include <bits/stdc++.h> using namespace std; template <class T> inline void read(T &x) { x= 0; char c= getchar(); while(!isdigit(c)) c= getchar(); while(isdigit(c)) x= x * 10 + (c & 15), c= getchar(); } #define N 100001 int n, m, head[N], cnt, dep[N], fa[N][17], sz[N]; long long a1[N], a2[N];//a1x表示x子树内节点到x的距离和,a2x表示x除去x子树外的所有点到x的距离和 struct Edge { int a, b; } e[N << 1]; inline void add(int a, int b) { e[++cnt].a= head[a], e[cnt].b= b, head[a]= cnt; } inline void dfs1(int x, int y)//第一遍dfs求出a1数组 { fa[x][0]= y, sz[x]= 1; for(int i= 1; i < 17; i++) fa[x][i]= fa[fa[x][i - 1]][i - 1]; for(int i= head[x]; i; i= e[i].a) { if(e[i].b == y) continue; dep[e[i].b]= dep[x] + 1, dfs1(e[i].b, x); sz[x]+= sz[e[i].b]; a1[x]+= a1[e[i].b] + sz[e[i].b];//从儿子转移 } } inline void dfs2(int x, int y)//第二遍dfs求出a2数组 { for(int i= head[x]; i; i= e[i].a) { if(e[i].b == y) continue; a2[e[i].b]= a2[x] + n - sz[x] + 1 + a1[x] - a1[e[i].b] - sz[e[i].b] + sz[x] - sz[e[i].b] - 1;//计算祖先的贡献和父亲的其他儿子的贡献 dfs2(e[i].b, x); } } inline int lca(int x, int y)//倍增求LCA { int k= dep[y] - dep[x]; for(int i= 0, j= 1; i < 17; i++, j<<= 1) if(k & j) y= fa[y][i]; if(x == y) return x; for(int i= 16; i >= 0; i--) if(fa[x][i] != fa[y][i]) x= fa[x][i], y= fa[y][i]; return fa[x][0]; } inline int ancestor(int x, int k)//倍增求K级祖先 { for(int i= 0, j= 1; i < 17; i++, j<<= 1) if(k & j) x= fa[x][i]; return x; } signed main() { read(n), read(m); for(int i= 1, x, y; i < n; i++) read(x), read(y), add(x, y), add(y, x); dfs1(1, 0), dfs2(1, 0); for(int i= 1, x, y; i <= m; i++) { read(x), read(y); if(dep[x] > dep[y]) swap(x, y); int l= lca(x, y); if(x == l)//x是两个点的LCA，即上文的第二种情况 { int a= ancestor(y, dep[y] - dep[x] - 1); double ans= 1 + 1.0 * (a2[x] + a1[x] - a1[a] - sz[a]) / (n - sz[a]) + 1.0 * a1[y] / sz[y] + dep[y] - dep[x]; printf("%0.10lf\n", ans); } else//上文的第一种情况 { double ans= 1 + 1.0 * a1[x] / sz[x] + 1.0 * a1[y] / sz[y] + dep[x] + dep[y] - (dep[l] << 1); printf("%0.10lf\n", ans); } } return 0; } ```