题解 CF696B 【Puzzles】

ouuan

2018-12-11 13:24:57

Solution

用 $f[u]$ 表示访问节点 $u$ 的期望时间,$siz[u]$ 表示子树 $u$ 的大小。 令 $v$ 为 $u$ 的一个儿子,那么 $f[v]=f[u]+1+\frac{siz[u]-siz[v]-1}2$ 。 因为 $u$ 除了 $v$ 以外的其它儿子,每个儿子都有 $\frac 1 2$ 的概率在 $v$ 之前被访问、$\frac 1 2$ 的概率在 $v$ 之后被访问,一个儿子 $v'$ 对 $f[v]$ 的贡献就是 $\frac{siz[v']}2$ 。 参考代码: ```cpp #include <iostream> #include <cstdio> using namespace std; const int N=100010; void add(int u,int v); void dfs1(int u); void dfs2(int u); int head[N],nxt[N],to[N],cnt; int n,p[N],siz[N]; double f[N]; int main() { int i; scanf("%d",&n); for (i=2;i<=n;++i) { scanf("%d",p+i); add(p[i],i); } dfs1(1); f[1]=1; dfs2(1); for (i=1;i<=n;++i) { printf("%.6lf ",f[i]); } return 0; } void add(int u,int v) { nxt[++cnt]=head[u]; head[u]=cnt; to[cnt]=v; } void dfs1(int u) { int i,v; siz[u]=1; for (i=head[u];i;i=nxt[i]) { v=to[i]; dfs1(v); siz[u]+=siz[v]; } } void dfs2(int u) { int i,v; for (i=head[u];i;i=nxt[i]) { v=to[i]; f[v]=f[u]+1+(siz[u]-1-siz[v])/2.0; dfs2(v); } } ```